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

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

文章图片

文章图片

我们以三片开始讨论。而讨论题目开始先明白，这个柱子的位置并不影响移动，只是特定的柱子才是关键。
我们来看看如果只有一个金片，要移动多少次。

文章图片

很明显，只要一次就够了。
再来看看两片金片。

文章图片

文章图片

由于要全移动到C柱

1：
a:A->B
2:
b:A->C
3;
a:B->C

三步就可以全移动过去。
或者想要移动b片要先移动a片，将空C柱留给b片，去考虑a片的移动。
再来看看三片的移动

文章图片

再来根据上面的思路，要想移动c片，得先移动a和b两片，把C柱留给c片。
要先满足这个条件

文章图片

且大不能在小上面。要先移成这个样子。

文章图片

且，要满足这个样子得，先这样。

文章图片

总结一下
第一步

文章图片

第二步

文章图片

第三步

文章图片

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

文章图片

成了这个样子。再来看看，我文章开头说的，柱子的位置不是关键，位置是可以改变，只是要移动到特定的柱子。现在这样，像不像，我们先前去移动两个金片的步骤？

文章图片

看清楚，这个样子，就是移动两个金片的步骤。再按上面的方法步骤，就行了。
我们来计算一下这写步骤
第一部分：
移动两个金片到B柱。
第二部分：
移动C片到C柱
第三部分：
在移动两个金片到C柱。
总结一下
就是移两个金片的步骤，移两次，再移一次最下面的金片。总共2*3+1==7次。
再来看看四个金片的步骤。
要想移动这四个金片，必需要将这最下面的金片移动

文章图片

这样来看，分两部分。
一：
移动d片到C柱
二：
移动a.b.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语言递归算法的资料请关注脚本之家其它相关文章！