/********hanoi.c*********/
#include <graphics.h>
struct H
{
int data[15]/*存放每个盘的代号*/
int top/*每个塔的具体高度*/
}num[3]/*三个塔*/
void move(char x,char y,struct H num[3])/*移动的具体过程*/
void hanoi(char x,char y,char z,int n,struct H num[3])/*递归*/
void Init(void)/*初始化*/
void Close(void)/*图形关闭*/
int computer=1/*自动控制与手动控制的标志*/
int speed=0/*全局变量speed主要是演示过程的速度*/
void main(void)
{
Init()/*初始状态*/
Close()/*图形关闭*/
exit(0)
}
void Init(void)/*初始化*/
{
int gd=DETECT,gm
int i,n,color
clrscr()
printf("please input n(n<=10): ")/*输入要演示的盘子数*/
scanf("%d",&n)
printf("Please input 1 or 2:\n1.computer 2.people\n")
scanf("%d",&i)
if(i==2)/*选择手动控制标志为0*/
computer=0
if(n<1||n>10)
n=10/*越界的话n当10处理*/
if(computer)/*如果是自动控制的话输入速度*/
{
printf("please input speed: ")/*输入速度*/
scanf("%d",&speed)
}
initgraph(&gd,&gm,"c:\\tc")
cleardevice()
for(i=0i<3i++)
num[i].top=-1/*三个地方的高度开始都为-1*/
for(i=0i<ni++)/*画一开始的塔座A上的盘子*/
{
num[0].top++/*栈的高度加1*/
num[0].data[num[0].top]=i/*最大的盘子代号为0，依次为1，2，…n-1*/
color=num[0].data[num[0].top]+1/*盘子的颜色代码为栈顶盘子代号加1*/
setfillstyle(SOLID_FILL,color)
bar(100-(33-3*num[0].data[num[0].top]),400-20*i-8,100+
(33-3*num[0].data[num[0].top]),400-20*i+8)/*画矩形*/
}
setcolor(YELLOW)
outtextxy(180,450,"any key to continue")
settextstyle(0,0,2)
outtextxy(90,420,"A")/*塔座标志*/
outtextxy(240,420,"B")
outtextxy(390,420,"C")
getch()/*接收字符后就执行递归操作*/
hanoi('a','b','c',n,num)
}
void move(char x,char y,struct H num[3])/*移动的具体过程*/
{
int i
char num1[3],num2[3]
sprintf(num1,"%c",x-32)/*将小写变成大写，并转换成字符串输出*/
sprintf(num2,"%c",y-32)
setfillstyle(SOLID_FILL,BLACK)/*把原来的地方移去涂黑*/
bar(0,0,640,60)
setcolor(RED)
outtextxy(150,30,num1)/*输出移动过程*/
outtextxy(200,30,"--->")
outtextxy(310,30,num2)
settextstyle(0,0,2)
setfillstyle(SOLID_FILL,BLACK)/*把原来的地方移去涂黑*/
bar(100+150*(x-97)-(33-3*num[x-97].data[num[x-97].top]),
400-20*num[x-97].top-8,100+150*(x-97)+(33-3*
num[x-97].data[num[x-97].top]),400-20*num[x-97].top+8)
num[y-97].top++/*入栈，目标点的top加1*/
num[y-97].data[num[y-97].top]=num[x-97].data[num[x-97].top]/*在目标点盘子的代号与源点盘子的代号相同*/
num[x-97].top--/*出栈，原来地方的top减1*/
setfillstyle(SOLID_FILL,num[y-97].data[num[y-97].top]+1)/*盘子颜色代码是栈顶盘子代号加1*/
bar(100+150*(y-97)-(33-3*num[y-97].data[num[y-97].top]),
400-20*num[y-97].top-8,100+150*(y-97)+
(33-3*num[y-97].data[num[y-97].top]),400-20*num[y-97].top+8)
if(computer)/*自动控制就用delay*/
delay(speed)/*延时函数*/
else
getch()/*手动控制的话就自己按键盘来控制*/
}
void hanoi(char one,char two,char three,int n,struct H num[3])/*递归n为盘子数，num为堆栈*/
{
if(n==1)
move(one,three,num)/*如果盘子为1，将这个盘子从塔座A移动到塔座C*/
else
{
hanoi(one,three,two,n-1,num)/*将塔座A的前n-1个盘子移到塔座B*/
move(one,three,num)/*将塔座A的第n个盘子移到塔座C*/
hanoi(two,one,three,n-1,num)/*将塔座B的n-1个盘子移到塔座C*/
}
}
void Close(void)/*图形关闭*/
{
getch()
closegraph()
}
这不在这儿吗,不长眼还发彪啊?●汉诺塔算法的非递归实现C++源代码
#include iostream
using namespace std
圆盘的个数最多为64
const int MAX = 64
用来表示每根柱子的信息
struct st{
int s[MAX]柱子上的圆盘存储情况
int top栈顶，用来最上面的圆盘
char name柱子的名字，可以是A，B，C中的一个
int Top()取栈顶元素
{
return s[top]
}
int Pop()出栈
{
return s[top–]
}
void Push(int x)入栈
{
s[++top] = x
}
}
long Pow(int x, int y)计算x^y
void Creat(st ta[], int n)给结构数组设置初值
void Hannuota(st ta[], long max)移动汉诺塔的主要函数
int main(void)
{
int n
cin n输入圆盘的个数
st ta[3]三根柱子的信息用结构数组存储
Creat(ta, n)给结构数组设置初值
long max = Pow(2, n) - 1动的次数应等于2^n - 1
Hannuota(ta, max)移动汉诺塔的主要函数
system(“pause”)
return 0
}
void Creat(st ta[], int n)
{
ta[0].name = ‘A’
ta[0].top = n-1
把所有的圆盘按从大到小的顺序放在柱子A上
for (int i=0ini++)
ta[0].s[i] = n - i
柱子B，C上开始没有没有圆盘
ta[1].top = ta[2].top = 0
for (int i=0ini++)
ta[1].s[i] = ta[2].s[i] = 0
若n为偶数，按顺时针方向依次摆放 A B C
if (n%2 == 0)
{
ta[1].name = ‘B’
ta[2].name = ‘C’
}
else 若n为奇数，按顺时针方向依次摆放 A C B
{
ta[1].name = ‘C’
ta[2].name = ‘B’
}
}
long Pow(int x, int y)
{
long sum = 1
for (int i=0iyi++)
sum = x
return sum
}
void Hannuota(st ta[], long max)
{
int k = 0累计移动的次数
int i = 0
int ch
while (k max)
{
按顺时针方向把圆盘1从现在的柱子移动到下一根柱子
ch = ta[i%3].Pop()
ta[(i+1)%3].Push(ch)
cout ++k “ “
“Move disk “ ch ” from “ ta[i%3].name
” to “ ta[(i+1)%3].name endl
i++
把另外两根柱子上可以移动的圆盘移动到新的柱子上
if (k max)
{
把非空柱子上的圆盘移动到空柱子上，当两根柱子都为空时，移动较小的圆盘
if (ta[(i+1)%3].Top() == 0
ta[(i-1)%3].Top() 0 &&
ta[(i+1)%3].Top() ta[(i-1)%3].Top())
{
ch = ta[(i-1)%3].Pop()
ta[(i+1)%3].Push(ch)
cout ++k “ “ “Move disk “
ch ” from “ ta[(i-1)%3].name
” to “ ta[(i+1)%3].name endl
}
else
{
ch = ta[(i+1)%3].Pop()
ta[(i-1)%3].Push(ch)
cout ++k “ “ “Move disk “
ch ” from “ ta[(i+1)%3].name
” to “ ta[(i-1)%3].name endl
}
}
}
}
理解计算机的递归过程，和以前数学中的递推证明非常接近。数学的递推证明的思想是，假定n-1的时候是正确的，证明n也是正确就可以了。
递归过程的思想是，如果已经有了解决<n的方法（汉诺塔中，移动n-1个盘子），怎么来处理当前n的问题（如果n-1个盘子已经移好了，那只要把最后一个盘子移过去就可以）。
当然，还要处理一下递归的结束条件（当n=1的时候），否则递归就不会结束了。
利用递归解决汉诺塔，其最巧妙之处在于实参和形参的不断变幻。就是形参x, y ,z所对应的实参，在递归过程中是不断改变的。
注意：形参
move(int n,int x,int y,int z)// 函数的目的是把x柱的n个盘子，借助y柱，移到z柱
而在递归时，柱子改变了，例如
move(n-1,x,z,y) // 这是把x柱的n-1个盘子，借组z柱，移到y柱
在进入递归时，盘子数量减少了，实际的柱子也改变了。
