汉诺塔

来源

汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。解答结果恰如上题，面对庞大的数字(移动圆片的次数)18446744073709551615，看来，众僧们耗尽毕生精力也不可能完成金片的移动。
后来，这个传说就演变为汉诺塔游戏:

  1. 有三根杆子A,B,C。A杆上有若干碟子
  2. 每次移动一块碟子,小的只能叠在大的上面
  3. 把所有碟子从A杆全部移到C杆上

动态演示：

经过研究不难发现：

假设有n块木块，记移动的次数为f(n) ，则f(n)=2f(n-1) +1；具体可见代码

基于c语言代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//   汉诺塔问题   
#include <stdio.h>
#include <stdlib.h>
/*
算法思想：递归
1.将物块分为两份，第一份为n-1块，第二份为第n块。先将n-1块木块移到从A经过C移到B
（注：当n>2时，n-1木块需要从c到b）
2.将第n块木块移到c.
3.将n-1块木块从b经a移到c.
*/
void hanoi(int n,char a,char b,char c);
int main(){
    int n;
    scanf("%d",&n);
    // n记为总的木块数
    hanoi(n,'A','B','C');
    system("pause");
    return 0;
}
void hanoi(int n,char a,char b,char c){
    if (n>0){
        hanoi (n-1,a,c,b);
        printf ("moving from %c from %c\n",a,c);
        hanoi (n-1,b,a,c);
    }
}