汉诺塔.cpp

来自「共有10个文件代码」· C++ 代码 · 共 76 行

#include<iostream.h>
#define MaxLen 50
void hanoi1(int n,char a,char b,char c)
{
	if(n==1)
		cout<<"\t将第"<<n<<"个盘子从"<<a<<"移动到"<<c<<endl;
	else
	{
		hanoi1(n-1,a,c,b);
		cout<<"\t将第"<<n<<"个盘子从"<<a<<"移动到"<<c<<endl;
		hanoi1(n-1,b,a,c);
	}
}
void hanoi2(int n,char a,char b,char c)
{
	struct stack
	{
		int no,ns;
		char x,y,z;
	}st[MaxLen];
	int top=1,n1,a1,b1,c1;
	st[top].no=1;
    st[top].ns=n;
	st[top].x=a;
	st[top].y=b;
	st[top].z=c;
	while(top>0)
	{
		if(st[top].no==1)
		{
			n1=st[top].ns;
			a1=st[top].x;
			b1=st[top].y;
			c1=st[top].z;
			top--;
			top++;
			st[top].no=1;
			st[top].ns=n1-1;
			st[top].x=b1;
			st[top].y=a1;
			st[top].z=c1;
			top++;
			st[top].no=0;
			st[top].ns=n1;
			st[top].x=a1;
			st[top].y=c1;
			top++;
			st[top].no=1;
			st[top].ns=n1-1;
			st[top].x=a1;
			st[top].y=c1;
			st[top].z=b1;
		}
		while(top>0 &&(st[top].no==0||st[top].ns==1))
		{
			if(top>0 && st[top].no==0)
			{
				cout<<"\t将第"<<st[top].ns<<"个盘子从"<<st[top].x<<"移动到"<<st[top].y<<endl;
				top--;
			}
			if(top>0 && st[top].ns==1)
			{
				cout<<"\t将第"<<st[top].ns<<"个盘子从"<<st[top].x<<"移动到"<<st[top].z<<endl;
				top--;
			}
		}
	}
}
void main()
{
	int n=5;
	cout<<"hanoi(5)递归求解结果:"<<endl;
	hanoi1(n,'X','Y','Z');
	cout<<"hanoi(5)非递归求解结果:"<<endl;
	hanoi2(n,'X','Y','Z');
}