hanoi.cpp

该程序用非递归的方法实现了汉诺塔问题的求解。当源盘的数目较少时该算法的执行速度比递归算法快

/**********************************************************************
该程序的基本思想为:假设柱A为源柱，柱B为中间柱，柱C为目的柱。A,B,C按顺时针围成一圈。
当输入的源盘的块数为奇数时:
第一步为:将A柱的顶块移向C柱。
第二步为:将A柱的顶块移向B柱。
其后的任意一步的算法为:当A,B,C三个柱子上面都有源盘时,首先找到A,B,C柱子顶部的第二大的圆盘。
当将第二大的圆盘移向最大的圆盘上面时若移上去后各个柱子的圆盘分布情况和上一步不同则这一步可进行，
否则 则找到A,B,C柱子顶部的最小的圆盘。按照逆时针方向将最小的圆盘移向他的下一个柱子上。

当A,B,C三个柱子上面有一个柱子上面没有源盘时,首先找到A,B,C柱子顶部的最大的圆盘。
当将最大的圆盘移向没有圆盘的柱子上时若移上去后各个柱子的圆盘分布情况和上一步不同则这一步可进行，
否则 则找到有圆盘的柱子顶部的最小的圆盘。按照逆时针方向将最小的圆盘移向他的下一个柱子上。
不存在A,B,C三个柱子有两个柱子没有圆盘的情况。

当输入的源盘的块数为偶数时(将A看成C，C看成A):
第一步为:将A柱的顶块移向B柱。
第二步为:将A柱的顶块移向C柱。
其后的任意一步的算法为:当A,B,C三个柱子上面都有源盘时,首先找到A,B,C柱子顶部的第二大的圆盘。
当将第二大的圆盘移向最大的圆盘上面时若移上去后各个柱子的圆盘分布情况和上一步不同则这一步可进行，
否则 则找到A,B,C柱子顶部的最小的圆盘。按照顺时针方向将最小的圆盘移向他的下一个柱子上。

当A,B,C三个柱子上面有一个柱子上面没有源盘时,首先找到A,B,C柱子顶部的最大的圆盘。
当将最大的圆盘移向没有圆盘的柱子上时若移上去后各个柱子的圆盘分布情况和上一步不同则这一步可进行，
否则 则找到有圆盘的柱子顶部的最小的圆盘。按照顺时针方向将最小的圆盘移向他的下一个柱子上。
不存在A,B,C三个柱子有两个柱子没有圆盘的情况。
************************************************************************/

#include<iostream>
#include<list>
#include<algorithm>
#include<ctime>

#define DISKNO 19

using namespace std;

//初始化源柱。
void initSourceList(list<int>& sourceList)
{
	for(int i=1;i<=DISKNO;i++)
		sourceList.push_back(i);
}

//Initialization the first and the second steps.
void initFirSecStep(list<int>& sourceList,list<int>& transferList,list<int>& aimList)
{
	unsigned int a,b;
	if(DISKNO==1){
		cout<<"只有一个盘子故直接将盘子从源柱搬到目的柱!!"<<endl;
		exit(1);
	}
	else{
		cout<<"1: A-->C"<<endl;
		a=sourceList.front();
		sourceList.pop_front();
		aimList.push_front(a);

		cout<<"2: A-->B"<<endl;
		b=sourceList.front();
		sourceList.pop_front();
		transferList.push_front(b);
	}
}

//Find the Max number.
char max(const unsigned int x,const unsigned int y,const unsigned int z)
{
	if(x>=y&&x>=z)return 'A';
	if(y>=x&&y>=z)return 'B';
	if(z>=x&&z>=y)return 'C';
	else return 'E';
}

//find the Middle number.
char mid(const unsigned int x,const unsigned int y,const unsigned int z)
{
	if((x>=y&&x<=z)||(x>=z&&x<=y))return 'A';
	if((y>=x&&y<=z)||(y>=z&&y<=x))return 'B';
	if((z>=x&&z<=y)||(z>=y&&z<=x))return 'C';
	else return 'E';
}

//Find the Min number.
char min(const unsigned int x,const unsigned int y,const unsigned int z)
{
	if(x<=y&&x<=z)return 'A';
	if(y<=x&&y<=z)return 'B';
	if(z<=x&&z<=y)return 'C';
	else return 'E';
}

//得到max,mid,min所在柱子的标志.
void getFlag(char& chmin,char& chmid,char& chmax,const int x,const int y,const int z)
{
	chmid=mid(x,y,z);
	chmax=max(x,y,z);
	chmin=min(x,y,z);
}

//保留这一次动作前的各个柱子的状态。
void numberExchange(unsigned int& x,unsigned int& y,unsigned int& z,
					unsigned int& x1,unsigned int& y1,unsigned int& z1)
{
	unsigned int temp;

	temp=x;
	x=x1;
	x1=temp;

	temp=y;
	y=y1;
	y1=temp;

	temp=z;
	z=z1;
	z1=temp;
}

//action.
void singularDiskes(list<int>& sourceList,list<int>& transferList,list<int>& aimList)
{
	unsigned int x=0,y=0,z=0;
	unsigned int x1=1,y1=0,z1=0;
	unsigned int i=3;
	char chmin,chmid,chmax;
	bool flag=false;

	/*if(sourceList.empty())x=0;
	else x1=sourceList.front();

	if(transferList.empty())y=0;
	else y1=transferList.front();

	if(aimList.empty())z=0;
	else z1=aimList.front();*/

//第一步动作后各柱的柱顶状态。
	x1=2;
	y1=0;
	z1=1;

	while(!flag){
		if(sourceList.empty())x=0;
		else x=sourceList.front();
	
		if(transferList.empty())y=0;
		else y=transferList.front();

		if(aimList.empty())z=0;
		else z=aimList.front();

		getFlag(chmin,chmid,chmax,x,y,z);
	//cout<<chmin<<'\t'<<chmid<<'\t'<<chmax<<'\t'<<endl;

		if(!sourceList.empty()&&!transferList.empty()&&!aimList.empty()){
			if(chmid=='A'){
				if(chmax=='B'&&x!=y1){
					cout<<i<<": A-->B"<<endl;
					transferList.push_front(x);
					sourceList.pop_front();
				}
				else if(chmax=='C'&&x!=z1){
					cout<<i<<": A-->C"<<endl;
					aimList.push_front(x);
					sourceList.pop_front();
				}
				else{
					if(chmin=='B'){
						cout<<i<<": B-->A"<<endl;
						sourceList.push_front(y);
						transferList.pop_front();
					}
					if(chmin=='C'){
						cout<<i<<": C-->B"<<endl;
						transferList.push_front(z);
						aimList.pop_front();
					}
				}
			}

			if(chmid=='B'){
				if(chmax=='A'&&y!=x1){
					cout<<i<<": B-->A"<<endl;
					sourceList.push_front(y);
					transferList.pop_front();
				}
				else if(chmax=='C'&&y!=z1){
					cout<<i<<": B-->C"<<endl;
					aimList.push_front(y);
					transferList.pop_front();
				}
				else{
					if(chmin=='A'){
						cout<<i<<": A-->C"<<endl;
						aimList.push_front(x);
						sourceList.pop_front();
					}
					if(chmin=='C'){
						cout<<i<<": C-->B"<<endl;
						transferList.push_front(z);
						aimList.pop_front();
					}
				}
			}

			if(chmid=='C'){
				if(chmax=='A'&&z!=x1){
					cout<<i<<": C-->A"<<endl;
					sourceList.push_front(z);
					aimList.pop_front();
				}
				else if(chmax=='B'&&z!=y1){
					cout<<i<<": C-->B"<<endl;
					transferList.push_front(z);
					aimList.pop_front();
				}
				else{
					if(chmin=='A'){
						cout<<i<<": A-->C"<<endl;
						aimList.push_front(x);
						sourceList.pop_front();
					}
					if(chmin=='B'){
						cout<<i<<": B-->A"<<endl;
						sourceList.push_front(y);
						transferList.pop_front();
					}
				}
			}
		}
		
		//if(sourceList.empty()||transferList.empty()||aimList.empty()){
		else{
			if(chmax=='A'){
				if(chmin=='B'&&x!=y1){
					cout<<i<<": A-->B"<<endl;
					transferList.push_front(x);
					sourceList.pop_front();
				}
				else if(chmin=='C'&&x!=z1){
					cout<<i<<": A-->C"<<endl;
					aimList.push_front(x);
					sourceList.pop_front();
				}
				else{
					if(chmid=='B'){
						cout<<i<<": B-->A"<<endl;
						sourceList.push_front(y);
						transferList.pop_front();
					}
					if(chmid=='C'){
						cout<<i<<": C-->B"<<endl;
						transferList.push_front(z);
						aimList.pop_front();
					}
				}
			}

			if(chmax=='B'){
				if(chmin=='A'&&y!=x1){
					cout<<i<<": B-->A"<<endl;
					sourceList.push_front(y);
					transferList.pop_front();
				}
				else if(chmin=='C'&&y!=z1){
					cout<<i<<": B-->C"<<endl;
					aimList.push_front(y);
					transferList.pop_front();
				}
				else{
					if(chmid=='A'){
						cout<<i<<": A-->C"<<endl;
						aimList.push_front(x);
						sourceList.pop_front();
					}
					if(chmid=='C'){
						cout<<i<<":C-->B"<<endl;
						transferList.push_front(z);
						aimList.pop_front();
					}
				}
			}

			if(chmax=='C'){
				if(chmin=='A'&&z!=x1){
					cout<<i<<": C-->A"<<endl;
					sourceList.push_front(z);
					aimList.pop_front();
				}
				else if(chmin=='B'&&z!=y1){
					cout<<i<<": C-->B"<<endl;
					transferList.push_front(z);
					aimList.pop_front();
				}
				else{
					if(chmid=='A'){
						cout<<i<<": A-->C"<<endl;
						aimList.push_front(x);
						sourceList.pop_front();
					}
					if(chmid=='B'){
						cout<<i<<": B-->A"<<endl;
						sourceList.push_front(y);
						transferList.pop_front();
					}
				}
			}
		}
		numberExchange(x,y,z,x1,y1,z1);
        if(sourceList.empty()&&transferList.empty())flag=true;
		else flag=false;
		i++;
    }
}

void main()
{
	time_t current_time;    
	time_t start_time;
	time(&start_time);

	list<int> sourceList;
	list<int> transferList;
	list<int> aimList;

	initSourceList(sourceList);
	initFirSecStep(sourceList,transferList,aimList);
	singularDiskes(sourceList,transferList,aimList);

	time(&current_time);
	cout<<"\n该程序的执行时间为: "<<current_time-start_time<<" 秒."<<endl;
}