c/c++语言开发共享C语言超详细讲解递归算法汉诺塔

题目描述

汉诺塔问题起源于一个传说

汉诺塔又被称为河内塔，传说，在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。

印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。 不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。 僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

我们现在要研究的就是在不同情况下盘子的移动顺序和移动的次数。

画图分析

由简到繁，我们先从最简单的情况来分析：

~~只有一个盘子的时候：

只有一个盘子我们直接把它从a柱移到c柱就行，此时移动次数是1，移动顺序是 a->c

~~有两个盘子的时候：

有两个盘子的时候我们需要先将较小的盘子移动到b柱，然后将较大的盘子移动c柱，再将b柱上的盘子移动到c柱；此时移动次数是3，移动顺序是 a->b a->c b->c

~~有三个盘子的时候：

有三个盘子的时侯，我们把最小的盘子命名为1，中间的为2，最大的为3，那么移动顺序应该是：1号移到到c柱，2号移动到b柱，1号移动到b柱，3号移动到c柱，1号移动到a柱，2号移动到c柱，1号移动到c柱；一共移动7次，移动顺序是a->c a->b c->b a->c b->a b->c a->c

a->c a->b c->b

a->c b->a

b->c a->c

思路总结

在上面的移动过程中，b柱始终起着中转的作用，我们我们可以理解为：

• a柱：起始柱
• b柱：中转柱
• c柱：目标柱

同时，我们发现一个盘子时需要移动一次，两个盘子时需要移动3次，3个盘子时需要移动7次，所以总结规律：n个盘子需要移动的次数是 2n-1 次。

其次，我们可以把上面的移动过程简化为三个步骤：

• 把n-1个盘子通过c柱移到b柱上。
• 把a柱上的最后一个盘子移动到c柱上。
• 把n-1个盘子通过a柱移动到c柱上。  

比如，上面盘子个数为三的时候，我们可以分解为：第一步：1号移到到c柱，2号移动到b柱，1号移动到b柱；第二步：3号移动到c柱；第三步：1号移动到a柱，2号移动到c柱，1号移动到c柱。

所以，n个盘子的移动顺序为：

1、把n-1个盘子通过c柱移到b柱上。

2. 把a柱上的最后一个盘子移动到c柱上。

3. 把n-1个盘子通过a柱移动到c柱上。

代码实现

#include<stdio.h>    //move函数，用来移动盘子，pos1表示起始柱，pos2表示目标柱  void move(char pos1, char pos2)  {  	printf("%c->%c ", pos1, pos2);  //把pos1的盘子移动到pos2  }    //hanoi函数，用来实现汉诺塔，其中n表示盘子的个数，pos1表示起始柱，pos2表示中转柱，pos3表示目标柱  void hanoi(int n, char pos1, char pos2, char pos3)  {  	if (1 == n)  //当n==1时，直接把盘子从a柱移动到c柱  	{  		move(pos1, pos3);    	}  	else   //当n不等于1时，分三步走  	{  		//第一步：将n-1个盘子通过c柱移动到b柱,此时c柱时中转柱，b柱是目标柱  		hanoi(n - 1, pos1, pos3, pos2);  		//第二步：把a柱最后一个盘子直接移动到c柱  		move(pos1, pos3);  		//第三步：将n-1个盘子通过a柱移动到c柱，此时b柱是起始柱，a柱是中转柱，c柱是目标柱  		hanoi(n - 1, pos2, pos1, pos3);  	}  }  int main()  {  	//定义一个变量来表示盘子的个数  	int n = 0;     	//定义三个字符变量来表示三根柱子  	char pos1 = 'a';  	char pos2 = 'b';  	char pos3 = 'c';  	//调用hanoi函数  	hanoi(1, pos1, pos2, pos3);  //n为1  	printf("n");  	hanoi(2, pos1, pos2, pos3);  //n为2  	printf("n");  	hanoi(3, pos1, pos2, pos3);  //n为3  	printf("n");  	hanoi(4, pos1, pos2, pos3);  //n为4  	printf("n");  	return 0;  }

总结

知道了汉诺塔的逻辑后，我们重新回到这个问题，我们发现，要把64片金片全部挪完需要挪动 264-1 次，假设这个僧侣一秒钟移动一次，那么一共要挪 (264-1) / 3600 / 24 / 365 = 584,942,417,355(年)，那时候地球已经毁灭也不是没有可能，哈哈。

到此这篇关于c语言超详细讲解递归算法汉诺塔的文章就介绍到这了,更多相关c语言汉诺塔内容请搜索<计算机技术网>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<计算机技术网>！

需要了解更多c/c++开发分享C语言超详细讲解递归算法汉诺塔，都可以关注C/C++技术分享栏目—计算机技术网（www.ctvol.com）