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柱。
成了这个样子。再来看看，我文章开头说的，柱子的位置不是关键，位置是可以改变，只是要移动到特定的柱子。现在这样，像不像，我们先前去移动两个金片的步骤？
看清楚，这个样子，就是移动两个金片的步骤。再按上面的方法步骤，就行了。
我们来计算一下这写步骤
第一部分：
移动两个金片到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 <stdio.h>
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 <stdio.h>
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语言递归算法的资料请关注软件开发网其它相关文章！
