hanoi(非递归).cpp

汉诺塔问题的非递归解决

#include<iostream.h>
#define MAX 100
struct Node{
	int n,tag;
	char x,y,z;
};

void Hanoi(int n,char x,char y,char z)
{
	Node stack[MAX];
	stack[0].n=n;
	stack[0].x=x;
	stack[0].y=y;
	stack[0].z=z;
	stack[0].tag=1;
	int j=0;
	do{
		if(stack[j].tag==1)
		{
			for(int i=stack[j].n-1;i>=1;i--)
			{
				stack[j+1].n=(stack[j].n)-1;
				stack[j+1].x=stack[j].x;
				stack[j+1].y=stack[j].z;
				stack[j+1].z=stack[j].y;
				stack[j+1].tag=1;
				j++;
			}
			cout<<stack[j].x<<" -> "<<stack[j].z<<endl;
			j--;
		}
		else{
			while(stack[j-1].tag==2)
			{
				j--;
				if(j==0) return;
			}
			j--;
			
		}
		cout<<stack[j].x<<" -> "<<stack[j].z<<endl;
		stack[j].tag=2;
		if(j>=0)
		{
			j++;
			stack[j].x=stack[j-1].y;
			stack[j].y=stack[j-1].x;
			stack[j].z=stack[j-1].z;
			stack[j].n=stack[j-1].n-1;
			stack[j].tag=1;
			if(stack[j].n==1)
			{
				cout<<stack[j].x<<" -> "<<stack[j].z<<endl;
				j--;
				continue;
			}
			
		}
		
	}while(1);

}

void main()
{
	int n;
	char A='A',B='B',C='C';
	cout<<"请输入n"<<endl;
	cin>>n;
	Hanoi(n,A,B,C);

}