Question

汉塔的递归算法~ 让我玩 多少个我都能玩出来。但是程序看不懂。

对于递归我的理解就是当时的解决依赖于上一层的解决。无限反向递归下去。就解决问题了。但是这该死的程序俺还是看的不太明白。

Answer 1

我是这样理解的A----起点 B----中间点 C-----终点
1个的时候，直接1放到C即可（1-C）
2个的时候，最小的一个（我们叫1吧）放到B,最下面一个（2）放到-C,然后B上面的1放到C(1-B,2-C,1-C)
3个的时候,先完成2个时候的A-B,，在完成第3个的A-C,再完成B上面2个的B-C即可，对吧？
4个的时候,先完成3个时候的A-B,，在完成第4个的A-C,再完成B上面3个的B-C即可
(4个的时候，需要完成的3个A-B,是把B当终点，C当中间点)
。
N个的时候：1、先完成N-1个时候的A-B,
2、在完成第N个的A-C,
3、完成B上面N-1个的B-C即可，

所以我们的递归函数就是这样：
# include<stdio.h>
void main()
{
void hanoi(int n,char one,char two,char three); /*对hanoi函数的声明*/
int m;
printf(“input the number of disker:”);
scanf(“%d”,&m);
printf(“The step to moveing %d diskes:\n”,m);
hanoi(m,’A’,’B’,’C’);
}
void hanoi(int n,char one,char two,char three) /*定义hanoi函数*/
/*将n个盘从one座借助two座，移到three座*/
{
void move(char x,char y); /*对move函数的声明*/

if(n= =1)
move(one,three); //如果只有一个盘子，只需要将第一个搬到第三个柱子上就完成任务了
else//如果还有n(n != 1)，只需要三步就可以完成
{
hanoi(n-1,one,three,two); //步骤1：把上面的n-1个通过第三个柱子搬到第二个柱子上去
move(one,three); // 步骤2： 把最下面的那个大盘子N移动到第三个柱子上去
hanoi(n-1,two,one,three);//步骤3： 把第二个柱子上面的n-1个盘子通过第一个移动到第三个柱子上去
}
}
void move(char x,char y) /*定义move函数*/
{
printf(“%c――>%c\n”,x,y);; //move就不用多说了，cong柱子x到 y
}

Answer 2

递归算法的本质是把原问题分解成两个或两个以上的子问题，子问题要么能直接求解，要么规模比原问题要小，且解法与要问题相同。比如：N!=N*(N-1)!-----是把原问题N！分解成两个子问题：×和（N-1）！

Answer 3

对于f(n)从a移到c，以b做辅助。就是先将上面的n-1移到b上，将n移到c上，
Hannoi（n-1，a，c，b）//n-1 从a到b，c是辅助。
Move（n，a，c）//n从a到c
这里b现在是n-1的问题了，要将n-1 从b移到c，以a为辅助，
Hannoi（n-1，b，a，c） //中间是辅助的
而边界条件是n=1时可以直接移动。
#include <stdio.h>

void Move(int n,char a,char b)
{
printf("move %d from %c to %c.\n",n,a,b);
}

void Hannoi(int n,char a,char b,char c)
{
if (n == 1)
Move(1,a,c);
else
{
Hannoi(n-1,a,c,b);
Move(n,a,c);
Hannoi(n-1,b,a,c);
}
}

int main()
{
int n;
scanf("%d",&n);

Hannoi(n,'a','b','c');
return 0;
}

Answer 4

好歹把程序发上来呀 说明哪里不懂 才好给你解释