【递归】Hanoi 塔问题

港控/mmm° 2022-10-20 01:17 167阅读 0赞

> Hanoi 塔问题起源于印度神话：传说在世界中心贝拿勒斯的神庙里，一个黄铜板上插着3根金刚石柱子。  
> 印度教的主神梵天在创造世界的时候，在其中一根柱子上从下到上穿好了由大到小的64个黄金圆盘，这就是所谓的 Hanoi 塔。  
> 不论白天和黑夜，总有一个僧侣在按照下面的法则移动这些圆盘：一次只移动一个圆盘，不管在哪根柱子上，小圆盘必须在大圆盘的上面。  
> 僧侣们预言：当所有的圆盘从梵天穿好的那根柱子上移动到另一根柱子上时，世界将在一声霹雳中消失，而Hanoi 塔，宇宙和众生也都将同归于尽。  
> ![汉诺塔][20210712153322355.png]

--------------------

## 【Analysis】 ##

设A柱子上有n个圆盘（n>=1）,则解题思路如下。

1.  如果只有1个圆盘，则不需要利用c柱，直接将圆盘从柱子A移动到柱子B.
2.  如果有2个圆盘。  
    第一步：将柱子A上的一个圆盘移到柱子C；  
    第二步：将柱子A上的一个圆盘移到柱子B；  
    第三步：将柱子C上的一个圆盘移到柱子B。
3.  如果有3个圆盘，那么根据2个圆盘的结论，可以借助柱子B将柱子A的两个圆盘移动到柱子C；将最大的一个圆盘从柱子A移动到柱子B；然后再借助柱子A，将柱子C上的两个圆盘移动到柱子B。
4.  如果有4个圆盘，那么首先借助柱子B，将柱子A上的3个圆盘移动到移动到柱子C；将最大的一个圆盘从柱子A移动到柱子B；借助柱子A，将柱子C上的63个圆盘移动到柱子B。

--------------------

![思路图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70]  
从上面的分析中可以看出，当n>=2时，移动的过程可分解为3个步骤。  
（1）把n-1 个圆盘从柱子A借助柱子B移到柱子C。  
（2）把剩下的最大的一个圆盘从柱子A移动到柱子B。  
（3）把n-1个圆盘从柱子C借助柱子A移到柱子B，完成全部圆盘的移动。

## 【Solution】 ##

#include <stdio.h>
    void move(char a,char b);
    void hanoi(int n,char a,char c,char b);
    int main(int argc, char *argv[])
    { 
    	int m;
    	printf("Input the number of diskes: \n");
    	scanf("%d",&m);
    	printf("The step of moving %3d diskes.\n",m);
    	hanoi(m,'A','C','B'); 
    	return 0;
    }
    /* 定义 move 函数，将一个圆盘从柱子a移到柱子b */ 
    void move(char a,char b){ 
        printf("%c --> %c\n",a,b);		
    }
    /* 定义 hanoi 函数，将n个圆盘从柱子a借助柱子c，移到柱子b */ 
    void hanoi(int n,char a,char c,char b){ 
    	if(n==1)
    	   move(a,b);
    	   else{ 
       		hanoi(n-1,a,b,c);  //递归调用函数 hanoi
    		move(a,b);         
    		hanoi(n-1,c,a,b);  //递归调用函数 hanoi 
       	      } 
    }

## 【Note】 ##

*  本程序中 move 函数只是打印出移动圆盘的方案，并未真正移动圆盘。
 *  现在我们考虑一下把64个圆盘由一根柱子移动到另一根柱子上，并且始终保持上小下大的顺序，需要移动多少次？
 *  设有n个圆盘，移动次数为 f(n),显然：f(1)=1,f(2)=3,f(3)=7,f(k+1)=2\*f(k)+1.不难证明 f(n)=2^n-1。
 *  则当n=64时，f(64)=2^64-1=18446744073709551615。
 *  假如僧侣们每秒钟移动一次圆盘，夜以继日废寝忘食地找这样干下去，需要多少年呢？
 *  一年按365天计算，则18446744073709551615/（60*60*24\*365），大约需要5849亿年，而地球存在至今不过45亿年，据说太阳系的预期寿命也就是数百亿年，真的过了5849亿年，不说太阳系和银河系，地球上的一切生命，连同Hanoi 塔，宇宙等，可能早已经灰飞烟灭了。

[20210712153322355.png]: /images/20221004/a50e650c6adf4b50b8f1562f83ea4073.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzU0MDUzOTkw_size_16_color_FFFFFF_t_70]: /images/20221004/90e2a78dc15e4baa86e4e45be03564a7.png