汉诺塔新问题
那位大哥可以帮我写个双列汉诺塔的程序?用C/C++都可以.
问题描述:
双列汉诺塔就是比一般传统的汉诺塔多出一组盘.汉诺塔的是3针汉诺塔.也就是说第一针和最后一针各有1组盘子,盘子数目在3-7之间.不同的盘子之间可以随便叠加,但是同种盘子之间只能小的压大的.另外还要求打印出移动步骤.
谢谢了.最好还能给出算法和设计思路.
[解决办法]
#include <stdio.h>
//递归汉诺塔程序
//参数定义：n为移动的盘子数，from指开始所在盘，tmp为中间盘，to为目标盘
void haoii(int n,int from,int tmp,int to)
{
if (n==0) return;
//将n-1个盘子以目标盘为中介，从开始盘递到中间盘
haoii(n-1,from,to,tmp);
将最后一个盘子移到目标盘
printf( "Move %d from %d to %d\n ",n,from,to);
//将中间盘上的n-1个盘子移到目标盘
haoii(n-1,tmp,from,to);
}
main()
{
haoii(32,1,2,3);
getchar();
return 0;
}
[解决办法]
程序没有
思路倒有一个
针 X,Y,Z
原来的汉诺塔程序是
借助Z把上面n-1个盘从X转移到Y
然后把X最后一块转移到Z
最后借助X把n-1个盘从Y转移到Z
而现在X,Z上都有一组盘子,个数分别设为m和n,你只要按下面的步骤
1.先把X的m个盘子转移到Y,方法如下
借助Y把上面的m-1从X转移到Z
然后把X最后一块转移到Y
最后借助X把m-1个盘从Z转移到Y
2.然后把Z的n个盘子转移到X,方法如下
借助X把上面的n-1从Z转移到Y
然后把Z最后一块转移到X
最后借助Z把n-1个盘从Y转移到X
3.最后把Y上(第一步从X转移过来的)m个盘子转移到Z
借助Z把上面的m-1从Y转移到X
然后把Y最后一块转移到Z
最后借助Y把m-1个盘从X转移到Z
这样就完成了整个过程
[解决办法]
键盘控制移动过程，这样一来还有算法可言吗？
============================================
我猜lz的意思
键盘 控制显示 移动过程
[解决办法]
相当于交差欠套一个汉诺塔问题 ～
[解决办法]
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);
}
[解决办法]
#include "stdio.h "
#include "graphics.h "
#include "conio.h "
#define M 3
#define N 5
void xyzprn();
int hanoi(int n, char from, char tmp, char to);
int totalNum=0;
int X[M+N]={5,3,1};
int Y[M+N]={0};
int Z[M+N]={10,8,6,4,2};
int CurX=M;
int CurY=0;
int CurZ=N;
int main()
{
int driver,mode;
driver=DETECT;
mode=0;
initgraph(&driver,&mode, "c:\\TC2\\BGI ");
gotoxy(1,25);
printf( "press any key to continue... ");
hanoi(M, 'X ', 'Z ', 'Y ');
hanoi(N, 'Z ', 'Y ', 'X ');
hanoi(M, 'Y ', 'X ', 'Z ');
getch();
closegraph();
return 0;
}
int hanoi(int n, char from, char tmp, char to)
{
if (n==0) return;
hanoi(n-1,from,to,tmp);
if(getch())
{
if(from== 'Z ' && to == 'X ')
{
CurX++;
X[CurX-1]=Z[CurZ-1];
Z[CurZ-1]=0;
CurZ--;
}
if(from== 'Z ' && to == 'Y ')
{
CurY++;
Y[CurY-1]=Z[CurZ-1];
Z[CurZ-1]=0;
CurZ--;
}
if(from== 'Y ' && to == 'X ')
{
CurX++;
X[CurX-1]=Y[CurY-1];
Y[CurY-1]=0;
CurY--;
}
if(from== 'Y ' && to == 'Z ')
{
CurZ++;
Z[CurZ-1]=Y[CurY-1];
Y[CurY-1]=0;
CurY--;
}
if(from== 'X ' && to == 'Z ')
{
CurZ++;
Z[CurZ-1]=X[CurX-1];
X[CurX-1]=0;
CurX--;
}
if(from== 'X ' && to == 'Y ')
{
CurY++;
Y[CurY-1]=X[CurX-1];
X[CurX-1]=0;
CurX--;
}
xyzprn();
totalNum++;
gotoxy(1,25);
printf( "step %2d : Move top disk from %c to %c\n ",totalNum,from,to);
}
hanoi(n-1,tmp,from,to);
}
void xyzprn()
{
int i,j,k;
cleardevice();
setcolor(WHITE);
line(100,20,100,350);
line(300,20,300,350);
line(500,20,500,350);
for(i=0; i <M+N; i++)
{
if(X[i]!=0)
{
if(X[i] % 2 ==0)
setcolor(WHITE);
else
setcolor(YELLOW);
line(100-X[i]*8,350-i*4,100+X[i]*8,350-i*4);
}
}
for(j=0; j <M+N; j++)
{
if(Y[j]!=0)
{
if(Y[j] % 2 ==0)
setcolor(WHITE);
else
setcolor(YELLOW);
line(300-Y[j]*8,350-j*4,300+Y[j]*8,350-j*4);
}
}
for(k=0; k <M+N; k++)
{
if(Z[k]!=0)
{
if(Z[k] % 2 ==0)
setcolor(WHITE);
else
setcolor(YELLOW);
line(500-Z[k]*8,350-k*4,500+Z[k]*8,350-k*4);
}
}
}
----------------------
在TC2.0下调试通过
缺点:画面有点因清屏重绘产生的闪烁
注意:
initgraph(&driver,&mode, "c:\\TC2\\BGI ");
c:\\TC2\\BGI
要根据你的TC安装目录进行修改.
[解决办法]
顺便把三列的也给做了
#include "stdio.h "
#include "graphics.h "
#include "conio.h "
#define NDELAY 1
#define M 3
#define N 4
#define P 4
int flag=0;
void xyzprn();
int hanoi(int n, char from, char tmp, char to);
int totalNum=0;
int X[M+N+P]={7,4,1};
int Y[M+N+P]={12,9,6,3};
int Z[M+N+P]={11,8,5,2};
int CurX=M;
int CurY=P;
int CurZ=N;
int main()
{
int driver,mode;
driver=DETECT;
mode=0;
initgraph(&driver,&mode, "c:\\TC2\\BGI ");
gotoxy(1,25);
printf( "press a auto-display,press s step-display. ");
hanoi(P, 'Y ', 'X ', 'Z ');
hanoi(M, 'X ', 'Z ', 'Y ');
hanoi(P, 'Z ', 'X ', 'Y ');
hanoi(N, 'Z ', 'Y ', 'X ');
hanoi(P, 'Y ', 'X ', 'Z ');
getch();
closegraph();
return 0;
}
int hanoi(int n, char from, char tmp, char to)
{
if (n==0) return;
hanoi(n-1,from,to,tmp);
if(1)
{
if(flag==0 && (getch()== 'a '))
flag=1;
if(flag==1)
{
sleep(NDELAY);
while(kbhit())
{
if(getch()== 's ')
flag=0;
}
}
if(from== 'Z ' && to == 'X ')
{
CurX++;
X[CurX-1]=Z[CurZ-1];
Z[CurZ-1]=0;
CurZ--;
}
if(from== 'Z ' && to == 'Y ')
{
CurY++;
Y[CurY-1]=Z[CurZ-1];
Z[CurZ-1]=0;
CurZ--;
}
if(from== 'Y ' && to == 'X ')
{
CurX++;
X[CurX-1]=Y[CurY-1];
Y[CurY-1]=0;
CurY--;
}
if(from== 'Y ' && to == 'Z ')
{
CurZ++;
Z[CurZ-1]=Y[CurY-1];
Y[CurY-1]=0;
CurY--;
}
if(from== 'X ' && to == 'Z ')
{
CurZ++;
Z[CurZ-1]=X[CurX-1];
X[CurX-1]=0;
CurX--;
}
if(from== 'X ' && to == 'Y ')
{
CurY++;
Y[CurY-1]=X[CurX-1];
X[CurX-1]=0;
CurX--;
}
xyzprn();
totalNum++;
gotoxy(1,24);
printf( "press a auto-display,press s step-display. ");
gotoxy(1,25);
printf( "step %3d : Move top disk from %c to %c\n ",totalNum,from,to);
}
hanoi(n-1,tmp,from,to);
}
void xyzprn()
{
int i,j,k;
cleardevice();
setcolor(LIGHTGRAY);
line(100,20,100,350);
line(300,20,300,350);
line(500,20,500,350);
for(i=0; i <M+N+P; i++)
{
if(X[i]!=0)
{
if(X[i] % 3 ==0)
setcolor(WHITE);
else if(X[i] % 3 ==1)
setcolor(YELLOW);
else
setcolor(LIGHTBLUE);
line(100-X[i]*8,350-i*4,100+X[i]*8,350-i*4);
}
}
for(j=0; j <M+N+P; j++)
{
if(Y[j]!=0)
{
if(Y[j] % 3 ==0)
setcolor(WHITE);
else if(Y[j] % 3 ==1)
setcolor(YELLOW);
else
setcolor(LIGHTBLUE);
line(300-Y[j]*8,350-j*4,300+Y[j]*8,350-j*4);
}
}
for(k=0; k <M+N+P; k++)
{
if(Z[k]!=0)
{
if(Z[k] % 3 ==0)
setcolor(WHITE);
else if(Z[k] % 3 ==1)
setcolor(YELLOW);
else
setcolor(LIGHTBLUE);
line(500-Z[k]*8,350-k*4,500+Z[k]*8,350-k*4);
}
}
}
