cpp1.cpp

递归方法的汉诺塔问题

#include<iostream>
#include<string>
using namespace std;
#include <stdlib.h>
#define MAX 10000
/////////////////////////////////////////////////////////////////////////////////////
//  两个类: Tower类（栈）Hanoi类（包含三个Tower类对象组成）                        //
//  程序中大部份功能函数封装在这两个类中 包括：递归算法Hanoi::Move()               //
//  图形显示Hanoi::Outlin() 移动演示Hanoi::MoveShow() 等                           //
//  塔的盘子是字符串由（'=',' '）组成 方法 Tower::disc();                          //
/////////////////////////////////////////////////////////////////////////////////////                             

/////塔////类////开////始////
struct Stack//链栈
{
	string data;//存放盘子
	Stack *next;
};
class Tower
{
    int floor;//塔的层数
    int broad;//塔的底座宽度
public:
	Stack *top;  //栈顶指针（游戏模式需要访问）
    int Top;//记录当前层数
    Tower(int store)//构造函数
    {
        floor=store;
        if(floor<6)broad=4+2*floor;//塔的层数与塔的底座宽度的关系
		else broad=2+2*floor;
		Top=0;
		string bro;
        for(int i=0;i<broad/2;i++)
        {
            bro=bro+"[]";//底座 【】【】【】【】【】【】
        }
		Stack *temp=new Stack;
		temp->data=bro;
		temp->next=top;
		top=temp;
    }
	string OutFloor(int i) //显示第temp层的数据
	{
		Stack *toptemp=top;
		for(int j=0;j<Top-i;j++)
		{
			toptemp=toptemp->next;
		}
		return toptemp->data;
	}
    void push(string disc)//放入盘子
    {
		Stack *temp=new Stack; 
		temp->data=disc;
		temp->next=top;
		top=temp;
		Top++;
    }
    string pop()//取出盘子
    {
        Stack *temp;
		string x;
        if(top==NULL) return NULL;
		else
		{
			x=top->data;
			temp=top;
			top=top->next;
			free(temp);
			Top--;
            return x;
		}
    }
    string disc(int space)//盘子(由'='和' '组成)
    {
        string dis;
        for(int i=0;i<space;i++)          //
        {                                 //   ________     ________      ________
            dis=dis+' ';                  //  |  ====  |   |  ====  |    |  ====  |   
        }                                 //  | ====== |   | ====== |    | ====== |  
        for(int j=space;i<broad-space;i++)//  |========|   |========|    |========|  
        {                                 //
            dis=dis+'=';                  //
        }                                 //
        for(int k=broad-space;k<broad;k++)//
        {                                 //
            dis=dis+' ';                  //
        }
        return dis;                         
    }
};
/////塔////类////结////束////

//////汉////诺/////塔////类////开////始////
class Hanoi //汉诺塔类 三个塔组成
{

    int Store;//汉诺塔的层数
	int broad;//塔的底座宽度
    Tower *A;//
	Tower *B;// 定义三座塔 指针方便释放内存
	Tower *C;//

	///汉///诺////塔////的///递///归///算///法///开///始///

	int step;//移动步数
	int STEP[MAX];//存放移动步骤
    void move(int A,int C)              
	{
		step++;
	    STEP[step]=A*10+C;//规定：12 A->B,13 A->C; 21 B->A,23 B->C; 31 C->A,32 C->B
	}
    void Move(int n,int A,int B,int C) //递归 （这里的A，B，C是相对的，不等同外面定义的A塔，B塔，C塔）
	{
		if(n==1)//递归的终止条件
		{
			move(A,C);//将A塔上的最后一个盘子盘子直接移动到C塔
		}
	    else
		{
			Move(n-1,A,C,B);//将A塔上的n-1个盘子通过C塔移动到B塔
		    move(A,C);      //将A塔上的最后一个盘子盘子直接移动到C塔
	        Move(n-1,B,A,C);//将B塔上的n-1个盘子通过A塔移动到C塔
		}
	}

	///汉///诺////塔////的///递///归///算///法///结///束///

public:
    Hanoi(int store)//构造函数
    {
        Store=store;
		if(Store<6)broad=4+2*Store;//塔的层数与塔的底座宽度的关系
		else broad=2+2*Store;
        A=new Tower(store);
		for(int i=1;i<=Store;i++)
		{
			A->push(A->disc(i));
		}
        B=new Tower(store);
        C=new Tower(store);
		step=0;
		Move(Store,1,2,3);
    }
	void OutStep()//输出步骤
	{
		int StepTemp;
		cout<<"\n\t移动方法："<<endl;
		for(StepTemp=1;StepTemp<=step;StepTemp++)
		{
			cout<<"\n\t"<<"第"<<StepTemp<<"步："<<STEP[StepTemp]/10<<"-->"<<STEP[StepTemp]%10<<"\t";
		}
	}
	void Outlin()//绘图显示当前状态
	{
		  int i=Store;         //层数(依层画)
		  string space;
		  for(int j=0;j<broad;j++)              //
		  {                                     //     ====                   ====       !!异常调试!!
			  space=space+" ";                  //    ======        ======        ====== 
		  }                                     //   [][][][]      [][][][]      [][][][]
		  cout<<"\n\n"<<endl;                   //
		  while(i>=0)                 
		  {                           
			 cout<<"\t";                                 //         
			 if(A->Top>=i)cout<<A->OutFloor(i);          //                        
			 else cout<<space;                           //     ====          ====          ====     i=4
			 cout<<"\t";                                 //    ======        ======        ======    i=3
		     if(B->Top>=i)cout<<B->OutFloor(i);          //   ========      ========      ========   i=2
			 else cout<<space;                           //  ==========    ==========    ==========  i=1
			 cout<<"\t";                                 // [][][][][][]  [][][][][][]  [][][][][][] i=0   
			 if(C->Top>=i)cout<<C->OutFloor(i);          //
			 else cout<<space;                           //
			 cout<<"\n";                                 //
			 i--;
		  }
	}
	void MoveShow() //演示
	{
	    int Step=1;
		string ans;
	    Outlin();
	    do
		{
			cout<<"\n\t第"<<Step<<"步："<<STEP[Step]/10<<"-->"<<STEP[Step]%10<<endl;
		    switch(STEP[Step])
			{
			case 12:
				B->push(A->pop());//将A 塔上的盘子移动到B盘上 以下同理
				break;
            case 13:
				C->push(A->pop());
	           	break;
            case 21:
				A->push(B->pop());
	           	break;
            case 23:
				C->push(B->pop());
		        break;
            case 31:
				A->push(C->pop());
		        break;
	        case 32:
				B->push(C->pop());
			}
		    Outlin();
		    if(Step<step)system("pause");
		    Step++;
		}while(Step<=step);
		cout<<"\n  演示完毕！(输入任意字符退出)\n\n";
		cin>>ans;
	}
	void GameMove()//游戏模式
	{
		int from,go;
		Outlin();
		do
		{
			cout<<"\n\t请输入移动哪个塔（1，2，3）：";
			cin>>from;
			while(from>3||from<1)
			{
				cout<<"-_-!";
				cin>>from;
			}
			cout<<"\n\t请输入移到哪个塔（1，2，3）：";
			cin>>go;
			while(go>3||go<1||go==from)
			{
				cout<<"-_-!";
				cin>>go;
			}
			int temp=from*10+go;
		    switch(temp)
			{
			case 12:
				if(A->top->data<B->top->data)B->push(A->pop());//将A 塔上的盘子移动到B盘上 以下同理
				else cout<<"ERROR!";
				break;
            case 13:
				if(A->top->data<C->top->data)C->push(A->pop());
				else cout<<"ERROR!";
	           	break;
            case 21:
				if(B->top->data<A->top->data)A->push(B->pop());
				else cout<<"ERROR!";
	           	break;
            case 23:
				if(B->top->data<C->top->data)C->push(B->pop());
				else cout<<"ERROR!";
		        break;
            case 31:
				if(C->top->data<A->top->data)A->push(C->pop());
				else cout<<"ERROR!";
		        break;
	        case 32:
				if(C->top->data<B->top->data)B->push(C->pop());
				else cout<<"ERROR!";
			}
		    Outlin();
		}while(C->Top!=Store);
		cout<<"你太强了！！\n"<<endl;
		system("pause");
	}
};
//////汉////诺/////塔////类////结////束////

////////////MAIN/////函数//////开始//////////////
void Arithmetic();//算法思想

Hanoi *hanoi;//定义汉诺威对象

void main()
{
    int cord1,cord2;
    do
    {
        system("cls");
        cout<<"\n\n\n\t\t\t 汉诺塔问题的动态演示   \n";
		cout<<"\t\t\t -------------------   李兆龙 钱伟 90622S\n";
        cout<<"\n\t\t\t    1.建立汉诺塔\n";
        cout<<"\n\t\t\t    2.算法思想\n";
        cout<<"\n\t\t\t    3.结束程序\n";
		cout<<"\t\t\t -------------------   \n";
        cout<<"\t\t\t 请输入你的选择 (1,2,3)：";
        cin>>cord1;
		while(cord1>3||cord1<1)
		{
			cout<<"-_-!";
			cin>>cord1;
		}
        switch(cord1)
        {
        case 1:
			int ans;
			cout<<"\n\t\t\t    请输入层数(1-10)：";
			cin>>ans;
			if(ans<1) ans=1;
			if(ans>10) ans=10;
			hanoi=new Hanoi(ans);//实例,动态分配内存
			hanoi->Outlin();
			cout<<"\n"<<endl;
			system("pause");
        ////////////子/////菜/////单/////开/////始/////////
            do
            {
                system("cls");
                cout<<"\n\n\n\t\t\t      汉诺塔   \n";
                cout<<"\n\t\t\t    1.开始演示\n";
                cout<<"\n\t\t\t    2.输出步骤\n";
				cout<<"\n\t\t\t    3.游戏模式\n";
                cout<<"\n\t\t\t    4.返回主菜单\n";
                cout<<"\n\t\t\t    5.终止程序\n";
                cout<<"\t\t\t -------------------\n";
                cout<<"\t\t\t 请输入你的选择 (1,2,3,4,5)：";
                cin>>cord2;
				while(cord2>5||cord2<1)
				{
					cout<<"-_-!";
			        cin>>cord2;
				}
                switch(cord2)
                {
                case 1://演示模式
					system("cls");
					hanoi->MoveShow();
					delete hanoi;//释放内存
					hanoi=new Hanoi(ans);//实例,动态分配内存
                    break;
                case 2://输出步骤
					system("cls");
					hanoi->OutStep();
					cout<<"\n"<<endl;
					system("pause");
                    break;
				case 3://游戏模式
					system("cls");
					hanoi->GameMove();
					delete hanoi;//释放内存
					hanoi=new Hanoi(ans);//实例,动态分配内存
                    break;
                case 4://返回主菜单
                    break;
                case 5://退出
                    exit(0);
                }
            }while(cord2<=5&&cord2!=4);
			delete hanoi;//释放内存
			break;//  丢掉它switch继续直至break （@_@!）
        //////////////子/////菜/////单/////结/////束//////////
        case 2:
			system("cls");
			Arithmetic();
            break;
        case 3:
            exit(0);
        }    
    }while(cord1<=3);

    return;
}
////////////MAIN/////函数//////结束//////////////

void Arithmetic()//算法
{
	string ans;
	cout<<"\n\n";
	cout<<"  把N层塔看做两部份：N-1,1(如图所示)          ====     |   |  "<<endl;
	cout<<"                                             ======    n-1 n  "<<endl;
	cout<<"                                            ========   |   |  "<<endl;
	cout<<"                                           ==========      |  "<<endl;
	cout<<"                                                               "<<endl<<endl;
	cout<<"   1.把N-1部份移到B塔： "<<endl;
	cout<<"         A              B            C       "<<endl;
	cout<<"                      ====                   "<<endl;
	cout<<"                     ======                  "<<endl;
	cout<<"     ==========     ========                 "<<endl;
	cout<<"    [][][][][][]  [][][][][][]  [][][][][][] "<<endl<<endl<<endl;


	cout<<"   2.把最后一部份移到C塔： "<<endl;
	cout<<"          A             B             C      "<<endl;
	cout<<"                      ====                   "<<endl;
	cout<<"                     ======                  "<<endl;
	cout<<"                    ========     ========== "<<endl;
	cout<<"    [][][][][][]  [][][][][][]  [][][][][][] "<<endl<<endl;


	cout<<"   3.把N-1部份移到C塔： "<<endl;
	cout<<"         A              B             C      "<<endl;
	cout<<"                                    ====     "<<endl;
	cout<<"                                   ======    "<<endl;
	cout<<"                                  ========   "<<endl;
	cout<<"                                 ==========  "<<endl;
	cout<<"    [][][][][][]  [][][][][][]  [][][][][][] "<<endl<<endl;

	cout<<"  4.下面要做的就是通过1，2，3步结合递归思想，再分解N-1部分，直至N=1最简情况"<<endl<<endl;
	cout<<"   补充：汉诺塔的实质是栈都具有先进后出的性质！！"<<endl<<endl;
	cout<<"输入任意字符退出";
	cin>>ans;
}