题目描述
汉诺塔问题起源于一个传说
汉诺塔又被称为河内塔,传说,在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。
印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的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语言汉诺塔内容请搜索<计算机技术网(www.ctvol.com)!!>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<计算机技术网(www.ctvol.com)!!>!
需要了解更多c/c++开发分享C语言超详细讲解递归算法汉诺塔,都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/1248216.html