Tower of Hanoi（汉诺塔）

汉诺塔游戏：A,B,C三根柱子，A柱子上有由上至下依由小至大排列的n张碟子，现在要将这n张碟子移动到C柱子上，移动过程中必须保持由上至下依由小至大排列顺序。
n张碟子，需要移动步数step=2^n-1

• c语言算法

[root@VM_0_3_centos ~]# cat alg01.c
#include <stdio.h>
int     step;

void hanoi_move(int n,char origin,char auxiliary,char destination){
        if(n==1){
                printf("Step %d:",step++);
                printf("Move sheet%d from %c to %c\n",n,origin,destination);
        }
        else{
                hanoi_move(n-1,origin,destination,auxiliary);
                printf("Step %d:",step++);
                printf("Move sheet%d from %c to %c\n",n,origin,destination);
                hanoi_move(n-1,auxiliary,origin,destination);
        }
}
int main(){
        int n;
        step=1;
        printf("input sheets number:");
        scanf("%d",&n);
        hanoi_move(n,'A','B','C');
        return 0;
}

[root@VM_0_3_centos ~]# gcc -o alg01 alg01.c
[root@VM_0_3_centos ~]# ./alg01
input sheets number:4
Step 1:Move sheet1 from A to B
Step 2:Move sheet2 from A to C
Step 3:Move sheet1 from B to C
Step 4:Move sheet3 from A to B
Step 5:Move sheet1 from C to A
Step 6:Move sheet2 from C to B
Step 7:Move sheet1 from A to B
Step 8:Move sheet4 from A to C
Step 9:Move sheet1 from B to C
Step 10:Move sheet2 from B to A
Step 11:Move sheet1 from C to A
Step 12:Move sheet3 from B to C
Step 13:Move sheet1 from A to B
Step 14:Move sheet2 from A to C
Step 15:Move sheet1 from B to C
[root@VM_0_3_centos ~]#

• Python语言

[root@VM_0_3_centos ~]# cat alg01.py
#!/usr/bin/python
def hanoi_move(number,origin,auxiliary,destination):
        if number==1:
                print "Move sheet%d from %s to %s" %(number,origin,destination);
        else:
                hanoi_move(number-1,origin,destination,auxiliary);
                print "Move sheet%d from %s to %s" %(number,origin,destination);
                hanoi_move(number-1,auxiliary,origin,destination);

        return;


print "input the sheets number:"
number=input()
hanoi_move(number,"A","B","C");
[root@VM_0_3_centos ~]# python ./alg01.py
input the sheets number:
3
Move sheet1 from A to C
Move sheet2 from A to B
Move sheet1 from C to B
Move sheet3 from A to C
Move sheet1 from B to A
Move sheet2 from B to C
Move sheet1 from A to C
[root@VM_0_3_centos ~]#