郝斌数据结构5递归之汉诺塔

Dear 丶 2022-03-02 14:28 264阅读 0赞

1 汉诺塔  
汉诺塔问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。  
可以从百度上搜汉诺塔的小游戏玩一下，就明白了！  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70]  
或许下面的解释会好理解一些:  
现在要求庙里的老和尚把这64个盘子全部移动到第三个柱子上。移动的时候始终只能小盘子压着大盘子，一次移动一个。  
001、此时老和尚（后面我们叫他第1个和尚）觉得很难，所以他想：要是有一个人能把前63个盘子先移动到第二个柱子上，我再把最后一个盘子直接移动到第三个柱子，再让那个人把刚才的前63个盘子从第二个柱子上移动到第三个柱子上，我的任务就完成了，简单。所以他找了第2个和尚，命令：  
① 你把前63个盘子移动到第二柱子上  
② 等我自己把第64个盘子移到第三个柱子上后  
③ 你把前63个盘子移动到第三柱子上

002、第2个和尚接了任务，也觉得很难，所以他也和第1个和尚一样想：要是有一个人能把前62个盘子先移动到第三个柱子上，我再把最后一个盘子直接移动到第二个柱子，再让那个人把刚才的前62个盘子从第三个柱子上移动到第二个柱子上，我的任务就完成了，简单。所以他也找了第3个和尚，命令：  
① 你把前62个盘子移动到第三柱子上  
② 等我自己把第63个盘子移到第二个柱子上后  
③ 你把前62个盘子移动到第二柱子上

003、第3个和尚接了任务，又把移动前61个盘子的任务依葫芦画瓢的交给了第4个和尚，递推下去，直到把任务交给了第64个和尚为止。（估计第64个和尚很郁闷，没机会也命令下别人，因为到他这里盘子只有一个了）。

004、到此任务下交完成，到各司其职完成的时候了。完成后开始回推了：  
第64个和尚移动第1个盘子，把它移开，然后第63个和尚移动他给自己分配的第2个盘子。第64个和尚再把第1个盘子移动到第2个盘子上。到这里第64个和尚的任务完成，第63个和尚完成了第62个和尚交给他的任务的第一步。  
从上面可以看出，只有第64个和尚的任务完成了，第63个和尚的任务才能完成，只有第2到第64个和尚的任务完成后，第1个和尚的任务才能完成。这是一个典型的递归问题。

现在我们以有3个盘子来分析：

第1个和尚命令：  
㈠ 第2个和尚你先把第一柱子前2个盘子移动到第二柱子。（借助第三个柱子）。  
㈡第1个和尚我自己把第一柱子最后的盘子移动到第三柱子。  
㈢第2个和尚你把前2个盘子从第二柱子移动到第三柱子。

很显然，第㈡步很容易实现 (∩\_∩)  
其中第㈠步。第2个和尚他有2个盘子，他就命令：  
① 第3个和尚你把第一柱子第1个盘子移动到第三柱子。（借助第二柱子）  
② 第2个和尚我自己把第一柱子第2个盘子移动到第二柱子上。  
③ 第3个和尚你把第1个盘子从第三柱子移动到第二柱子。  
同样，第②步很容易实现，但第3个和尚他只需要移动1个盘子，所以他也不用下派任务了。  
（注意: 这就是停止递归的条件，也叫边界值）

第㈢步可以分解为，第2个和尚还是有2个盘子，命令：  
①第3个和尚你把第二柱子上的第1个盘子移动到第一柱子。  
② 第2个和尚我把第2个盘子从第二柱子移动到第三柱子。  
③第3个和尚你把第一柱子上的盘子移动到第三柱子。

分析组合起来就是：1→3 1→2 3→2 1→3 2→1 2→3 1→3共需要7步，也就是一共3个盘子需要7步。（百度搜汉诺塔小游戏玩一遍就会了(∩\_∩)）

如果是4个盘子，则第1个和尚的命令中第1步和第3步各有3个盘子，所以各需要7步，共14步，再加上第1个和尚的1步，所以4个盘子总共需要移动7+1+7=15步，同样，5个盘子需要15+1+15=31步，6个盘子需要31+1+31=63步……由此可以知道，移动n个盘子需要  
(2的n次方减1)

从上面分析可知把n个盘子从一柱移到三柱的伪算法：  
（1）把一柱上（n-1）个盘子借助三柱移到二柱。  
（2）把一柱上第n个盘子移到三柱。  
（3）把二柱上（n-1）个盘子借助一柱移到三柱。

汉诺塔程序:

#include <stdio.h>
    #include <stdlib.h>
    
    void hannuota(int n,int a,int b,int c)
    { 
    	/* 如果是一个盘子 直接将一柱子上的盘子从一移到三 否则 先将一柱子上的n-1个盘子借助三移到二 直接将一柱子上的盘子从一移到三 最后将二柱子上的n-1个盘子借助一移到三 */
    	if(1 == n)
    	{ 
    		printf("将编号为%d的盘子直接从%d柱子移动到%d柱子\n",n,a,c);
    	}
    
    	else
    	{ 
    		hannuota(n-1,a,c,b);
    		printf("将编号为%d的盘子直接从%d柱子移动到%d柱子\n",n,a,c);
    		hannuota(n-1,b,a,c);
    	}
    }
    
    int main(void)
    { 
    	int a = 1;
    	int b = 2;
    	int c = 3;
    	int n;
    
    	printf("请输入盘子的个数:");
    	scanf("%d",&n);
    
    	hannuota(n,a,b,c);
    	
    	system("pause");
    	return 0;	
    }

经过汉诺塔小游戏的验证，程序是正确的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdnb25nXzE5OTE_size_16_color_FFFFFF_t_70]: /images/20220302/ff8dcc9de98240f7945953d6523e8c7e.png