关于Hanoi塔的问题
手动可以推出来怎么样移动,但就是不会写,书上也给出用递归的答案,但想不明白啊,是不是俺真的很笨啊...
高手们帮帮忙,谢谢~!
[解决办法]
你可能钻牛尖了，hanoi的递归最好理解了，解决hanoi问题就是三步：
（1）借助于第三个盘子，把上面的N - 1个移到第二个上去；
（2）把最后一个盘子从第一个拿到第三个上去；
（3）借助第一个盘子把最后二个盘子上的拿到第三个上去。
由于第一步和第三步的N - 1个盘子的移动也是一模一样的hanoi问题（只是个数不一样），所以直接递归就可以解决它。
然后就是递归要有结整条件，即：当N等于1时，挪一下即可。
至于递归调用是怎么起作用的，那是编译器设计者的器。那些做编译器的人都能实现让一个函数调用别的函数，那么调用它自已就更能实现。
当然如果你感兴趣，看看编译方面的书应该能获得一些理解。但那跟hanoi问题真的没多少直接关系，完全是两个层次上的事，是你想多了。
[解决办法]
建议楼主在网上搜索一下Hanoi塔的程序,要有显示的那种,我以前找到一个可以设置每个移动步骤的时间,这样就可以慢慢看是怎么移动的了
[解决办法]
那个应该是数据结构的一个教程程序...可以看到每步的运行步骤
[解决办法]
HANOI塔问题的动画演示
对源程序的一点说明：
在屏幕作图之前, 必须根据显示器适配器种类将显示器设置成为某种图形模
式, 在未设置图形模式之前, 微机系统默认屏幕为文本模式(80列, 25行字符模
式), 此时所有图形函数均不能工作。设置屏幕为图形模式, 可用下列图形初始
化函数:
void far initgraph(int far *gdriver, int far *gmode, char *path);
其中gdriver和gmode分别表示图形驱动器和模式, path是指图形驱动程序所
在的目录路径（即EGAVGA.BGI所在的目录路径）。
本程序中的initgraph函数调用形式为
initgraph(&gdriver,&gmode, "c:\\tc20\\bgi ")，其中 "c:\\tc20\\bgi "是
我电脑上的图形驱动程序EGAVGA.BGI所在的目录路径。
要使程序在别的电脑上运行，必须改成所在电脑上的图形驱动程序
EGAVGA.BGI所在的目录路径。
/*
Name: hanoime.c
Author: zhuqing
Description: HANOI塔问题的递归解的动画演示
Date: 06-08-03 11:44
Copyright:
*/
#include <stdlib.h>
#include <graphics.h>
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#define N 5
#define COLOREXP (i+1)%15
/* 原柱，中间柱，目标柱初值数组 */
char a[]={ '1 ', '2 ', '3 ', '4 ', '5 ', '6 ', '7 ', '8 ', '9 '};
char b[]={ '0 ', '0 ', '0 ', '0 ', '0 ', '0 ', '0 ', '0 ', '0 '};
char c[]={ '0 ', '0 ', '0 ', '0 ', '0 ', '0 ', '0 ', '0 ', '0 '};
int step=0;
int m;
int gdriver,gmode;
int stick1x,stick2x,stick3x;
int base,top,stkwid;
int thick,width;
int startx,starty,endx,endy;
int *pic,size,i;
int dif;
int delaytime;
void disp(int);
void drawplate(int startx,int starty,int endx,int endy,int color){
int i;
setcolor(color);
for(i=startx;i <=endx;i++)
line(i,starty,i,endy);
}
main()
{
thick=10;
width=100;
stkwid=10;
top=120;
stick1x=120;
stick2x=320;
stick3x=520;
dif=16;
delaytime=800000;
printf( "\n Please choice disp mode: 1 automatic 2 step by step\n ");
scanf( "%3d ",&m);
gdriver=DETECT;
/* registerbgidriver(EGAVGA_driver); */
initgraph(&gdriver,&gmode, "c:\\tc20\\bgi ");
setcolor(BLUE);
setbkcolor(LIGHTCYAN);
base=getmaxy()-60;
line(60,base+1,580,base+1);
setwritemode(XOR_PUT);
setlinestyle(0, 0, 1); /*设置1点宽实线*/
disp(N);
getch();
disp(N);
move(N,a,b,c);
getch();
closegraph();
}
/* 递归函数 */
move(int n,char a1[],char b1[],char c1[])
{
int i=0;
if(n> 0){
move(n-1,a1,c1,b1);
c1[n-1]=a1[n-1];
a1[n-1]= '0 '
disp(N);
while(i <N&&c[i]!= '0 ')i++;
if(i <N){
if(m==1)
delay(delaytime);
else
getch();
disp(N);
move(n-1,b1,a1,c1);
}
}
}
/* 打印输出结果到屏幕的函数 */
void disp(int n)
{
int i;
int count;
int startx,starty,endx,endy;
int color;
stick1x=120;
stick2x=320;
stick3x=520;
/* 画A柱的盘子*/
count=0;
starty=base;
for(i=0;i <N;i++){
if(a[N-1-i]!= '0 '){
color=COLOREXP;
setcolor(color);
startx=stick1x-(width-dif*i-stkwid)/2;
starty=base-thick*(count+1)-count;
endx=startx+(width-dif*i);
endy=base-thick*count-count;
/* rectangle(startx,starty,endx,endy); */
drawplate(startx,starty,endx,endy,color);
count++;
}
}
/* 画A柱*/
setcolor(BLUE);
rectangle(stick1x,top,stick1x+stkwid,starty);
/* 画B柱的盘子*/
count=0;
starty=base;
for(i=0;i <N;i++){
if(b[N-1-i]!= '0 '){
color=COLOREXP;
setcolor(color);
startx=stick2x-(width-dif*i-stkwid)/2;
starty=base-thick*(count+1)-count;
endx=startx+(width-dif*i);
endy=base-thick*count-count;
/* rectangle(startx,starty,endx,endy); */
drawplate(startx,starty,endx,endy,color);
count++
}
}
/* 画B柱*/
setcolor(BLUE);
rectangle(stick2x,top,stick2x+stkwid,starty);
/* 画C柱的盘子*/
count=0;
starty=base;
for(i=0;i <N;i++){
if(c[N-1-i]!= '0 '){
color=COLOREXP;
setcolor(color);
startx=stick3x-(width-dif*i-stkwid)/2;
starty=base-thick*(count+1)-count;
endx=startx+(width-dif*i);
endy=base-thick*count-count;
/* rectangle(startx,starty,endx,endy); */
drawplate(startx,starty,endx,endy,color);
count++;
}
}
/* 画C柱*/
setcolor(BLUE);
rectangle(stick3x,top,stick3x+stkwid,starty);
}
[解决办法]
另外一个可以参考的：
计算机解决64层的汉诺塔，首先考虑a杆下面的盘子而非杆上最上面的盘子，于是任务变成了：
*将上面的63个盘子移到b杆上；
*将a杆上剩下的盘子移到c杆上；
*将b杆上的全部盘子移到c杆上。
将这个过程继续下去，就是要先完成移动63个盘子、62个盘子、61个盘子....的工作。
为了更清楚地描述算法，可以定义一个函数movedisc(n,a,b,c)。该函数的功能是：将N个盘子从A杆上借助C杆移动到B杆上。这样移动N个盘子的工作就可以按照以下过程进行：
1) movedisc(n-1,a,c,b);
2) 将一个盘子从a移动到b上；
3) movedisc(n-1,c,b,a)；
重复以上过程，直到将全部的盘子移动到位时为止。
*程序与程序注释
#include <stdio.h>
void movedisc(unsigned n,char fromneedle,char toneedle,char usingneedle);
int i=0;
void main()
{
unsigned n;
printf( "please enter the number of disc: ");
scanf( "%d ",&n); /*输入N值*/
printf( "\tneedle:\ta\t b\t c\n ");
movedisc(n, 'a ', 'c ', 'b '); /*从A上借助B将N个盘子移动到C上*/
printf( "\t Total: %d\n ",i);
}
void movedisc(unsigned n,char fromneedle,char toneedle,char usingneedle)
{
if(n> 0)
{
movedisc(n-1,fromneedle,usingneedle,toneedle);
/*从fromneedle上借助toneedle将N-1个盘子移动到usingneedle上*/
++i;
switch(fromneedle) /*将fromneedle 上的一个盘子移到toneedle上*/
{
case 'a ': switch(toneedle)
{
case 'b ': printf( "\t[%d]:\t%2d.........> %2d\n ",i,n,n);
break;
case 'c ': printf( "\t[%d]:\t%2d...............> %2d\n ",i,n,n);
break;
}
break;
case 'b ': switch(toneedle)
{
case 'a ': printf( "\t[%d]:\t%2d <...............> %2d\n ",i,n,n);
break;
case 'c ': printf( "\t[%d]:\t %2d........> %2d\n ",i,n,n);
break;
}
break;
case 'c ': switch(toneedle)
{
case 'a ': printf( "\t[%d]:\t%2d <............%2d\n ",i,n,n);
break;
case 'b ': printf( "\t[%d]:\t%2d <........%2d\n ",i,n,n);
break;
}
break;
}
movedisc(n-1,usingneedle,toneedle,fromneedle);
/*从usingneedle上借助fromneedle将N-1个盘子移动到toneedle上*/
}
}