汉诺塔递归问题的理解

sunman2006

最近学到递归，汉诺塔的递归，看了好久，但是总感觉有层纸没有捅破，虽然程序写出来了，但是是照着课本写出来的，要是自己想，不看答案的话，完全写不出来。那位大神有理解汉诺塔递归的通俗易懂的解释，代码也放上来，给更不明白的，有个视觉的理解。

#include <stdlib.h>
#include <stdio.h>
#include <windows.h>

int plate[100][3]={{0},{0,0,0},{0,0,0}};
int a=0,b=1,c=2,position[100]={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][a]=j+1;
                position[j+1]=j;

        }





        printf("您输入的汉诺塔如下：\n");
        for(j=0;j<numbers;j++)
        {

                for(i=0;i<=2;i++)printf("%10d",plate[j][i]);
                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[m];
        for(j=numbers-1;j>=0;j--)
        {
                if(plate[j][y]==0)
                {

                        plate[j][y]=plate[p][x];
            position[m]=j;
                        plate[p][x]=0;
                       

                        break;
                }
                else continue;

        }



        system("cls");
        printf("\n");
        for(j=0;j<numbers;j++)
        {
        for(i=0;i<=2;i++)printf("%10d",plate[j][i]);
        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[n-1][x]);
                //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[n-1][x]);
                //printf("%c-->%c\n",x+65,z+65);
                move(n,x,z);
               

                hanoi(n-1,y,x,z);

        }





}

sunman2006

没有人？

Mountain_gs

#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;
}

这是我之前写的一个，你看看

sunman2006

Mountain_gs 发表于 2018-11-9 17:19
这是我之前写的一个，你看看

这个是c++吧？

Mountain_gs

嗯,没学过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)。
一般来说，正向推导可以写成循环，逆向推导可以写成递归。所以很多情况下，同一个问题有循环和递归两种解法，这两种解法也可以互相转化。
比如求裴波那契数列，比如遍历二叉树。
但是某些问题情况复杂，选用其中的一种解法会比另一种好，思路清晰、简洁明了。

sunman2006

Mountain_gs 发表于 2018-11-13 13:39
嗯,没学过c,不过应该影响不大。主要的思想就是注释那一块

对，就是思想不太理解，我是从思想到算法的转换理解不了

sunman2006

啊涂涂 发表于 2018-11-13 16:38
你可以看下小甲鱼讲的递归那一课，挺简单的我感觉，程序功能也简单，主要是算法思想的实现

是的，我就是看的那一讲，不过看的不太明白

sunman2006

砚堂_ 发表于 2018-11-13 20:39
递归的思想比较简单吧。
已知两个条件：1，f(n)和f(n-1)的递推式；2，某个具体的f(x)的值，通常x=0或1。显 ...

你说的这个真的挺厉害，我觉得好像说到点子上了，不过从思想到算法的转换，真的很难想通，思想不太理解，算法也不太明白，两个加起来，脑子糊了

啊涂涂

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上

两个条件备齐，可以了。