汉诺塔递归问题的理解
最近学到递归，汉诺塔的递归，看了好久，但是总感觉有层纸没有捅破，虽然程序写出来了，但是是照着课本写出来的，要是自己想，不看答案的话，完全写不出来。那位大神有理解汉诺塔递归的通俗易懂的解释，代码也放上来，给更不明白的，有个视觉的理解。#include <stdlib.h>
#include <stdio.h>
#include <windows.h>
int plate={{0},{0,0,0},{0,0,0}};
int a=0,b=1,c=2,position={0};
int numbers,count=0,time=10;
void main()
{
int move(int,int,int);
int hanoi(int,int,int,int);
int i,j;
printf("请输入汉诺塔的层数：");
scanf("%d",&numbers);
printf("\n请输入下一步的间隔时间(毫秒)：");
scanf("%d",&time);
printf("\n");
for(j=0;j<numbers;j++)
{
plate=j+1;
position=j;
}
printf("您输入的汉诺塔如下：\n");
for(j=0;j<numbers;j++)
{
for(i=0;i<=2;i++)printf("%10d",plate);
printf("\n");
}
printf("按回车键继续\n");
getchar();
getchar();
hanoi(numbers,a,b,c);
printf("演示完成回车键退出\n");
getchar();
getchar();
}
int move(int m,int x,int y)
{
int i=0,j=0,p=0;
p=position;
for(j=numbers-1;j>=0;j--)
{
if(plate==0)
{
plate=plate;
position=j;
plate=0;
break;
}
else continue;
}
system("cls");
printf("\n");
for(j=0;j<numbers;j++)
{
for(i=0;i<=2;i++)printf("%10d",plate);
printf("\n");
}
Sleep(time);
}
int hanoi(int n,int x,int y,int z)
{
int move(int m,int x,int y);
if (n==1)
{
count++;
//printf("第%d个,%c%c%c,%d次",n,x+65,y+65,z+65,count);
//printf("plate[%d][%d]%d,",n-1,x,plate);
//printf("%c-->%c\n",x+65,z+65);
move(n,x,z);
}
else
{
hanoi(n-1,x,z,y);
count++;
//printf("第%d个,%c%c%c,%d次",n,x+65,y+65,z+65,count);
//printf("plate[%d][%d]%d,",n-1,x,plate);
//printf("%c-->%c\n",x+65,z+65);
move(n,x,z);
hanoi(n-1,y,x,z);
}
}
没有人？ #include<iostream>
using namespace std;
int num;
void Move(int n, char x, char y, char z)//将n个铁块从经由y从x移动到z上
{
if (1 == n) //只移动一块
{
num++;
cout << x<<"-->"<<z <<" ";
cout << num << endl;
}
else
{
Move(n - 1, x, z, y); //将n-1个铁块从经由y从x移动到y上
Move(1, x, y, z); //将最后一块从x移动到z上
Move(n - 1, y, x, z); //将n-1个铁块从经由x从y移动到z上
}
}
int main()
{
int n;
cout << "请输入要移动的层数：" << endl;
cin >> n;
Move(n, 'X', 'Y', 'Z');
system("pause");
return 1;
}
这是我之前写的一个，你看看 Mountain_gs 发表于 2018-11-9 17:19
这是我之前写的一个，你看看
这个是c++吧？ 嗯,没学过c,不过应该影响不大。主要的思想就是注释那一块 你可以看下小甲鱼讲的递归那一课，挺简单的我感觉，程序功能也简单，主要是算法思想的实现 递归的思想比较简单吧。
已知两个条件：1，f(n)和f(n-1)的递推式；2，某个具体的f(x)的值，通常x=0或1。显然，有了这两个条件，我们是可以求出一切f(n)的。
满足这两个条件的问题，一般有两种解决的思路：
1，正向推导，从f(1)推f(2),f(3),...f(n)
2，逆向推导，f(n)和f(n-1)相关，f(n-1)和f(n-2)相关，所以可以推导出f(n)和f(n-2)的关系，持续下去，可以推出f(n)和f(1)的关系，由此计算出f(n)。
一般来说，正向推导可以写成循环，逆向推导可以写成递归。所以很多情况下，同一个问题有循环和递归两种解法，这两种解法也可以互相转化。
比如求裴波那契数列，比如遍历二叉树。
但是某些问题情况复杂，选用其中的一种解法会比另一种好，思路清晰、简洁明了。
Mountain_gs 发表于 2018-11-13 13:39
嗯,没学过c,不过应该影响不大。主要的思想就是注释那一块
对，就是思想不太理解，我是从思想到算法的转换理解不了{:10_266:} 啊涂涂 发表于 2018-11-13 16:38
你可以看下小甲鱼讲的递归那一课，挺简单的我感觉，程序功能也简单，主要是算法思想的实现
是的，我就是看的那一讲，不过看的不太明白{:10_277:} 砚堂_ 发表于 2018-11-13 20:39
递归的思想比较简单吧。
已知两个条件：1，f(n)和f(n-1)的递推式；2，某个具体的f(x)的值，通常x=0或1。显 ...
你说的这个真的挺厉害，我觉得好像说到点子上了，不过从思想到算法的转换，真的很难想通，思想不太理解，算法也不太明白，两个加起来，脑子糊了{:10_285:}{:10_250:} sunman2006 发表于 2018-11-14 11:02
你说的这个真的挺厉害，我觉得好像说到点子上了，不过从思想到算法的转换，真的很难想通，思想不太理解， ...
主要是他的程序传参一定要弄清楚，x y z 的位置不变，只是传参，他下面变成了 x z y 的意思就是把 z 上面的值传到 y 上面来，把 y 的值传到 z 里面去，传了之后的顺序还是 x y z，就比如说是 x y z 分别等于 x=1 y=3 z=5，然后变成 x z y，也就是传参，就变成了 x = 1 y = 5 z = 3.一定要注意好，x y z 的顺序是始终不变的 sunman2006 发表于 2018-11-14 11:02
你说的这个真的挺厉害，我觉得好像说到点子上了，不过从思想到算法的转换，真的很难想通，思想不太理解， ...
嗯，你是想不明白这个程序的运行过程吗？
这个是没有必要弄清楚的。
一般我们理解一个递归程序，看它正不正确，就是看它的两个条件是不是完善。
只要它两个条件是完善的，就可以放心地认为它是对的。至于整个递归过程，只有初学递归的时候为了理解它的思想，才会手工推演。而且也是推演简单的递归问题，不会弄这么复杂的。你初学递归，可以试试把曾经用循环写过的程序都改成递归，看能不能帮助理解。比如n个数求和，字符串的反转，等等。
像阶乘问题，f(n)=n*f(n-1),f(0)=1;写成程序就是 int f(n){ return n>0?n*f(n-1):1;}
像斐波那契数列问题，f(n)=f(n-1)+f(n-2),f(0)=f(1)=1; 写成程序是 int f(n){ return n>1?f(n-1)+f(n-2):1;)
像这个汉诺塔问题，所求的f(n,x,y,z)是：
Move(int n, char x, char y, char z) //将n个铁块从经由y从x移动到z上
初值f(1,x,y,z)是：
if (1 == n) //只移动一块
{
num++;
cout << x<<"-->"<<z <<" ";
cout << num << endl;
}
从f(n,x,y,z) 到 f(n-1,x,y,z)的递推关系是：
Move(n - 1, x, z, y); //将n-1个铁块从经由y从x移动到y上
Move(1, x, y, z); //将最后一块从x移动到z上
Move(n - 1, y, x, z); //将n-1个铁块从经由x从y移动到z上
两个条件备齐，可以了。
页:
[1]