C语言编程递归算法实现汉诺塔

汉诺塔 法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片:一次只移动一片,不管在哪根针上,小片必须在大片上面。僧侣们预言,当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,而梵塔、庙宇和众生也都将同归于尽。
这个传说挺有意思的,这个传说是说有64片金片。但我们要讨论是只有3片或4片金片。看看网图吧。
C语言编程递归算法实现汉诺塔
文章图片

C语言编程递归算法实现汉诺塔
文章图片

我们以三片开始讨论。而讨论题目开始先明白,这个柱子的位置并不影响移动,只是特定的柱子才是关键。
我们来看看如果只有一个金片,要移动多少次。
C语言编程递归算法实现汉诺塔
文章图片

很明显,只要一次就够了。
再来看看两片金片。
C语言编程递归算法实现汉诺塔
文章图片

C语言编程递归算法实现汉诺塔
文章图片

由于要全移动到C柱

1:
a:A->B
2:
b:A->C
3;
a:B->C
三步就可以全移动过去。
或者想要移动b片要先移动a片,将空C柱留给b片,去考虑a片的移动。
再来看看三片的移动
C语言编程递归算法实现汉诺塔
文章图片

再来根据上面的思路,要想移动c片,得先移动a和b两片,把C柱留给c片。
要先满足这个条件
C语言编程递归算法实现汉诺塔
文章图片

且大不能在小上面。要先移成这个样子。
C语言编程递归算法实现汉诺塔
文章图片

且,要满足这个样子得,先这样。
C语言编程递归算法实现汉诺塔
文章图片

总结一下
第一步
C语言编程递归算法实现汉诺塔
文章图片

第二步
C语言编程递归算法实现汉诺塔
文章图片

第三步
C语言编程递归算法实现汉诺塔
文章图片

这么看下来,跟先前我们探讨只移两片,就没什么区别了。
再将c片移动到C柱。
【C语言编程递归算法实现汉诺塔】C语言编程递归算法实现汉诺塔
文章图片

成了这个样子。再来看看,我文章开头说的,柱子的位置不是关键,位置是可以改变,只是要移动到特定的柱子。现在这样,像不像,我们先前去移动两个金片的步骤?
C语言编程递归算法实现汉诺塔
文章图片

看清楚,这个样子,就是移动两个金片的步骤。再按上面的方法步骤,就行了。
我们来计算一下这写步骤
第一部分:
移动两个金片到B柱。
第二部分:
移动C片到C柱
第三部分:
在移动两个金片到C柱。
总结一下
就是移两个金片的步骤,移两次,再移一次最下面的金片。总共2*3+1==7次。
再来看看四个金片的步骤。
要想移动这四个金片,必需要将这最下面的金片移动
C语言编程递归算法实现汉诺塔
文章图片

这样来看,分两部分。
一:
移动d片到C柱
二:
移动a.b.c这仨个金片到C柱。
与上面移三片类比,、
第 一目的
C语言编程递归算法实现汉诺塔
文章图片

第 二目的
C语言编程递归算法实现汉诺塔
文章图片

第三目的
C语言编程递归算法实现汉诺塔
文章图片

可以分三部完成。可见三片移法要移两次。
就是2*7+1==15次。
依此类推 当移动N片金片时,要先考虑,
一–>移动这N-1片金片。
二–>再移第N片,
三–>再移动那N-1片到目的地。
可以分这三步。
柱子的位置对移动并没有上面影响。
看代码,这是计算次数的代码。
#include int hanoi(int n){ if (n >= 2)return 2 * hanoi(n - 1) + 1; return 1; }int main(void){ printf("Problem of Hanoi\n"); printf("please input the number for problem:>\n"); int n; scanf("%d", &n); printf("%d",hanoi(n)); return 0; }

这是编译步骤的代码
#include void move(char start,char end,int n){ static int count = 0; count++; printf("NO.%d step,the %d moves from %c to %c\n", count, n, start, end); }void hanoi(int n,char pose1,char pose2,char pose3){ if (n == 1)move(pose1, pose3, 1); //一个是特例,不存在中间位置 else {hanoi(n - 1, pose1, pose3, pose2); //对应第一次移动N-1个金片move(pose1, pose3, n); //对应移动第N个金片hanoi(n - 1, pose2, pose1, pose3); //最后一次移动N-1个金片 }}int main(void){ char pose1 = 'A'; //起始位置 char pose2 = 'B'; //中间位置 char pose3 = 'C'; //结束位置 int n; scanf("%d", &n); hanoi(n, pose1, pose2, pose3); return 0; }

使用递归时,要将其理解成一个功能模块,而不是一步一步去分析。使用它的功能,同时确定终止条件并接近这个条件。
运用递归写函数,可以”轻松“计算。
只为加深自己理解,含有学生气,勿笑。
如有问题,烦请指点一二。
以上就是C语言编程递归算法实现汉诺塔的详细内容,更多关于C语言递归算法的资料请关注脚本之家其它相关文章!

    推荐阅读