hannuota.cpp

汉诺塔的非递归实现

//韩诺塔问题的递归实现
/*#include <iostream.h>
#include <fstream.h>
//using namespace std;//why????
ofstream fout("out.txt");
int count = 0;

void move(int n,char x,char y)
{
	fout<<"移动第"<<n<<"个盘子从"<<x<<"到"<<y<<endl;
}

void hannoi(int n,char a,char b,char c)
{   count++;
	if(n==1)    move(n,a,c);
	else {
		hannoi(n-1,a,c,b);
		move(n,a,c);
		hannoi(n-1,b,a,c);
	}	
}

int main()
{
	int n;

	cout<<"输入n的值："<<endl;
	cin>>n;

	fout<<"以下是"<<n<<"韩诺塔的解法："<<endl;	
   	hannoi(n,'a','b','c');
	fout<<"总的移动次数是：    "<<count;
	fout.close();
	cout<<count;
    
	cout<<"输出完毕！"<<endl;

	return 0;
}*/


//*********************************************************************************************
//*********************************************************************************************

//韩诺塔问题的非递归实现
#include <iostream.h>
#include "hannuota.h"

void Creat(st ta[],int n);
int Pow(int m,int n);
void Hannuota(st ta[],int 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, n);//移动汉诺塔的主要函数 

//    system("pause");
      return 0;
} 

void Creat(st ta[],int n)
{
	ta[0].name='A';
	if(n%2==0)
	{
		ta[1].name='B';
		ta[2].name='C';
	}
	else
	{	
		ta[1].name='C';
		ta[2].name='B';
	}

	ta[0].top=n-1;
	ta[1].top=0;
	ta[2].top=0;
	for(int i=0;i<n;i++){

		ta[0].s[i]=n-i;
		ta[1].s[i]=ta[2].s[i]=0;
	}
}

/*int Pow(int m,int n)
{   
	int sum=1;

	for(int i=1;i<=n;i++)

		sum*=2;

	return sum;

}*/

void Hannuota(st ta[],int n)
{
	int k=0,i=0,ch;

	while(n%2==0 && ta[2].top!=n-1 || n%2!=0 && ta[1].top!=n-1)
	{
		ch=ta[i%3].Pop();
		ta[i%3].Push(ch);
		cout << ++k << ": " <<
         "Move disk " << ch << " from " << ta[i%3].name <<
         " to " << ta[(i+1)%3].name << endl;
		i++;
		//把另外两根柱子上可以移动的圆盘移动到新的柱子上
		if(n%2==0 && ta[2].top!=n-1 || n%2!=0 && ta[1].top!=n-1)
		{
			//将非空柱子上的盘子移动的空的柱子上
			//如果两个盘子都非空就将盘子多的柱子上的盘子移动到盘子少的柱子上
			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;
			}

		}
	}
	//输出最后一次的移动
	ch=ta[i%3].Pop();
	ta[i%3].Push(ch);
	cout << ++k << ": " <<
    "Move disk " << ch << " from " << ta[i%3].name <<
    " to " << ta[(i+1)%3].name << endl;
}