Question

汉诺塔问题看不懂，有人能帮一下我吗？看不懂那个过程，或者告诉我怎么去想这个问题。

这个题目的核心是递归吧，所以希望听完你的讲解后，我能了解到一点。

Answer 1

想要把方块从A柱子移到C柱子，需要B柱子作为媒介，比如说，一个方块可以直接放到C上，但是两个方块就不行了，要先把小的那块放在B柱子上，然后将第二块方块从A柱子移到C柱子上，再将第一块方块移到C柱子上，从2块方块开始，以后有n块方块，就必须要将n-1块方块放在B柱子上，第n块方块移到C上，再将n-1块方块移到C上。而对于n-1块方块，又有n-2块方块需要移到A或者C上，这样第n-1块方块才能移到B上。核心公式就是f(n)=2^n-1次
码字不易，不知帮到您了没有

追问

公式我也知道，但是我想知道书上那代码的过程。。是怎么体现递归的。
重点在递归不是这些公式啦。抱歉啦。

追答

是具体的过程还是结果代码？我附上结果代码，你看一下吧。

#include
#include
#include
using namespace std;
int ans=1;
void fun(int num)
{
if(num==0)
return;
ans*=2;
fun(num-1);
}

int main()
{
int n;
cin>>n;
fun(n);
cout<<ans-1<<endl;
system("pause");
return 0;
}
从第n个柱子到第n-1个柱子，所需要的移动数要*2，当我们不需要移动时，返回即可，比如说，当我们移动一个柱子，那就是2-1次，当我们要移动2个柱子时，就是2*2-1次

如果说是递归的话，是在已知规律的条件下对于问题的一种推导，我们知道汉诺塔问题的公式是f(n)=2^n-1，那么我们定义了ans，每次询问这个问题前面问题的结果是什么，最后*2就可以了，边界是num=0，这个边界我也是现推的，不同的代码有不同的边界条件，我发现输入1的时候输出0，所以把边界改成了num=0，这样当你询问f(1)的时候，它就会查询f(0)，发现到边界，返回。ans*2=2，2-1=1

再提一下，递归使用的是一种名字叫做"栈"的东西，系统中的栈基本在10万左右，超出了系统的栈就会栈溢出，许多时候我们都是自己定义栈的。关于栈的知识你要上网自学，我这就不讲模拟栈的代码了

Answer 2

#include <stdio.h>

#include <iostream>

using namespace std;

//入参int n:代表第n个盘子

int move(int n,char a, char b)
{
printf("==>==>: 把第 %d 个盘子 从 %c座 搬到 %c座\n\n",n,a,b);
return 0;
}

//入参int n：代表 共剩余n个盘子
int hanoi(int n,char a,char b,char c)
{
cout<<"******************int hanoi(int n,char a,char b,char c) begin!!!"<<endl;
if (n == 1)
{
cout<<"剩余盘子数 n="<<n<<"，盘子在"<<a<<"座上，可以直接搬到"<<c<<"座"<<endl;
}
else
{
cout<<"剩余盘子数 n="<<n<<"，盘子在"<<a<<"座上，需借助"<<b<<"座，搬到"<<c<<"座"<<endl;
}
if( n==1 )
{
cout<<endl<<"11111=>: ";
move (1,a,c);
}
else
{
hanoi(n-1,a,c,b);//根据上面解说知道：移动n个盘子需要（2的n次方）-1步，这里需要移动n-1个盘子需要（2的n次方）-2步，也就是说这里的第一轮递归 要进行 n-1 层递归循环，才会结束调用，完成 将 n-1 个盘子从a座上借助c座，最终放到了b座上，
move(n,a,c);//完成 将 最后一个盘子即第 n 个盘子从a座上放到了c座上，至此完成第一轮的调用，其结果是将最后一个盘子完成了任务，其余的盘子都还在b座上放着呢，下面一步是对剩余的n-1个盘子进行新一轮的递归调用
hanoi(n-1,b,a,c);//开启新一轮的递归调用
};
if (n == 1)
{
cout<<"对应-----------剩余盘子数 n="<<n<<"，盘子在"<<a<<"座上，可以直接搬到"<<c<<"座"<<endl;
}
else
{
cout<<"对应-----------剩余盘子数 n="<<n<<"，盘子在"<<a<<"座上，需借助"<<b<<"座，搬到"<<c<<"座"<<endl;
}
cout<<"int hanoi(int n,char a,char b,char c) end end end end end end @@@!!!@@@"<<endl<<endl;
return 0;
}
int main()
{
freopen("hanoi.in","r",stdin);
freopen("hanoiOutPut.txt","w",stdout);
int num;
scanf("%d",&num);
cout<<"开始"<<endl<<endl;
hanoi(num,'A','B','C');
cout<<endl<<endl<<"结束"<<endl<<endl;
return 0;
}

/*开始

******************int hanoi(int n,char a,char b,char c) begin!!!

剩余盘子数 n=3，盘子在A座上，需借助B座，搬到C座

******************int hanoi(int n,char a,char b,char c) begin!!!

剩余盘子数 n=2，盘子在A座上，需借助C座，搬到B座

******************int hanoi(int n,char a,char b,char c) begin!!!

剩余盘子数 n=1，盘子在A座上，可以直接搬到C座

11111=>: ==>==>: 把第 1 个盘子 从 A座 搬到 C座

对应-----------剩余盘子数 n=1，盘子在A座上，可以直接搬到C座

int hanoi(int n,char a,char b,char c) end end end end end end @@@!!!@@@

==>==>: 把第 2 个盘子 从 A座 搬到 B座

******************int hanoi(int n,char a,char b,char c) begin!!!

剩余盘子数 n=1，盘子在C座上，可以直接搬到B座

11111=>: ==>==>: 把第 1 个盘子 从 C座 搬到 B座

对应-----------剩余盘子数 n=1，盘子在C座上，可以直接搬到B座

int hanoi(int n,char a,char b,char c) end end end end end end @@@!!!@@@

对应-----------剩余盘子数 n=2，盘子在A座上，需借助C座，搬到B座

int hanoi(int n,char a,char b,char c) end end end end end end @@@!!!@@@

==>==>: 把第 3 个盘子 从 A座 搬到 C座

******************int hanoi(int n,char a,char b,char c) begin!!!

剩余盘子数 n=2，盘子在B座上，需借助A座，搬到C座

******************int hanoi(int n,char a,char b,char c) begin!!!

剩余盘子数 n=1，盘子在B座上，可以直接搬到A座

11111=>: ==>==>: 把第 1 个盘子 从 B座 搬到 A座

对应-----------剩余盘子数 n=1，盘子在B座上，可以直接搬到A座

int hanoi(int n,char a,char b,char c) end end end end end end @@@!!!@@@

==>==>: 把第 2 个盘子 从 B座 搬到 C座

******************int hanoi(int n,char a,char b,char c) begin!!!

剩余盘子数 n=1，盘子在A座上，可以直接搬到C座

11111=>: ==>==>: 把第 1 个盘子 从 A座 搬到 C座

对应-----------剩余盘子数 n=1，盘子在A座上，可以直接搬到C座

int hanoi(int n,char a,char b,char c) end end end end end end @@@!!!@@@

对应-----------剩余盘子数 n=2，盘子在B座上，需借助A座，搬到C座

int hanoi(int n,char a,char b,char c) end end end end end end @@@!!!@@@

对应-----------剩余盘子数 n=3，盘子在A座上，需借助B座，搬到C座

int hanoi(int n,char a,char b,char c) end end end end end end @@@!!!@@@

结束*/

追问

你这样的话和我看教材一样..没多少帮助。那你可以告诉我递归是怎么一回事吗？

Answer 3

我在校那时也不明白,后来想,等以后用到的时候在学吧.
后来工作之后发现,我竟然从没用过递归.
有的时候是运行环境不支持,单片机类的跑起来容易爆栈,或者编译器直接就报错.
更多的时候是在搞软件工程,算法反而用的不多.
如何调用库,或者自己写一个库,快速完成需求.
如何写一个良好的界面.
如何写出层次清晰,功能完善的代码.
如何写出后期维护起来更容易的代码.
以上这些事情反而成为了我工作中的主要内容.

我并没有答题,关于递归我也自认肯定没有其它几位答主答的更好.
我只是在讲,题主如果现在不理解,也不必强求.编程还有很多更好玩的东西.

追问

那样太迟了...我现在想看看能不能从别人的理解中知道点什么。

Answer 4

假如有A,B,C三根杆，一开始全部圈在A杆，目的用汉诺塔规则借助C杆将所有圈从A转移到C。
一个圈（1）：1（A->B）1次
两个圈（1、2）：1（A->C）（1次），2（A->B），1（A->C），共3次
三个圈（1、2、3）：1、2（A->C）(3次)，3（A->B）,1、2（A->C）（3次），共7次
..................
以此类推，假设n代表圈圈个数，z为总次数，则有：
z(n)=z(n-1)+1+z(n-1)=2*z(n-1)+1
z(3)=z(2)+1+z(2)=2*3+1=7
递归：z(3)=2*z(2)+1=2*(2*z(1)+1)+1=7

追问

次数的话是2^n-1吧？？而且- -！我没讲明来意。。。

Answer 5

赵薇演过一个电影叫《天地英雄》，我是看了那部电影，然后明白了递归的含义。