[求助] "汉诺塔问题“求解 - 编程论坛

#2

nuciewth2007-10-22 10:27

A B C
要把N个盘子借助B从A放到C,且保证同样的顺序
分三步走:
1.将A上面N-1个盘子借助C放到B上
2.然后再把A上的最后一个盘子放到C上.
3.最后借助C把B上的N-1个盘子放到A上

现在要解决的是把A上的N-1个盘子借助B放到C上
这个过程和上面的是一样的,只是规模N变小的.
递归过程就出来

#3

jxnuwy042007-10-22 12:23

这个应该是个动态规划的思想吧？

#4

卧龙孔明2007-10-22 12:25

基础递推:

f(n)=f(n-1)*2+1

f(1)=1

#5

六道2007-10-22 15:29

#include <stdio.h>
void move(char x,char y)
{
printf("%c-->%c\n",x,y);
}
void hanoi(int n,char one,char two,char three)
{
if(n==1) move(one,three);
else
{
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
}
}

main()
{
int m;
printf("input the unmber of diskes:");
scanf("%d",&m);
printf("the step to moving %3d diskes:\n",m);
hanoi(m,'A','B','C');
}

#6

eagleboycn2007-10-22 17:18

以下是引用六道在2007-10-22 15:29:07的发言：

#include <stdio.h>
void move(char x,char y)
{
printf("%c-->%c\n",x,y);
}
void hanoi(int n,char one,char two,char three)
{
if(n==1) move(one,three);
else
{
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
}
}

main()
{
int m;
printf("input the unmber of diskes:");
scanf("%d",&m);
printf("the step to moving %3d diskes:\n",m);
hanoi(m,'A','B','C');
}

Thank you so much!

#7

eagleboycn2007-10-22 17:24

以下是引用六道在2007-10-22 15:29:07的发言：
if(n==1) move(one,three);
else
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);

谢谢！
现在我明白这个递归序列了

#8

六道2007-10-22 17:29

共同学习,没时间改成C++的,就发了个C的~

#9

eagleboycn2007-10-22 17:33

我把它改成C++的了：
#include <iostream>
using namespace std;
void move(char x,char y)
{
cout<<x<<"-->"<<y<<endl;
}
void hanoi(int n,char one,char two,char three)
{
if(n==1) move(one,three);
else
{
hanoi(n-1,one,three,two);
move(one,three);
hanoi(n-1,two,one,three);
}
}

int main()
{
int N;
cout<<"input the unmber of diskes:"<<endl;
cin>>N;
cout<<"the step to moving "<<N<<" diskes:"<<endl;
hanoi(N,'A','B','C');
return 0;
}

#10

eagleboycn2007-10-22 17:37

当时看书上的碟子数量N是64，认为很复杂，头都大了
看来，结果是结果
我要了解的只是推理过程，递归序列
当时虽然看了书上的递归介绍，但是不理解
现在终于明白了

#11

aipb20072007-10-22 19:14

N=64用递归是不可能计算出来的

#12

eagleboycn2007-10-23 07:31

以下是引用aipb2007在2007-10-22 19:14:26的发言：
N=64用递归是不可能计算出来的

何解？
为什么？
能说明原因吗？
谢谢了

#13

aipb20072007-10-23 10:34

你算算 2^64-1

就算有无限大的内存使用，时间也不够啊！

#14

eagleboycn2007-10-23 16:41

以下是引用aipb2007在2007-10-23 10:34:07的发言：
你算算 2^64-1

就算有无限大的内存使用，时间也不够啊！

也就是说理论上有结果
但是结果会接近无限长？
我用64运行过，等了1分多钟，看还在算，就没等了

#15

xiaodong58002010-03-06 20:37

#include<stdio.h>
void main()
{
int m;
void mana(int n,char one,char two,char three);
scanf("%d",&m);
mana(m,'A','B','C');
}
void mana(int n,char one,char two,char three)
{
void move(int no,char x,char y);
if(n==1)
move(n,one,three);
else
{
mana(n-1,one,three,two);
move(n,one,three);
mana(n-1,two,one,three);
}
void move(int no,char x,char y)
{
printf("Move disk %d from %c to %c",no,x,y);
printf("\n");
}
}
情不自禁自己也写了一个，不过和大家的差不多