学步园

问题描述：与梵塔问题相同，设ABC是3个塔座，初始时塔座A上有四个圆盘，各圆盘从小到大编号为：1、2、3、4，奇数号圆盘为红色，偶数号圆盘为蓝色。现要求将塔座A上的圆盘移到塔座C上，除满足梵塔问题的移动规则外，还必须满足：任何时刻不允许将同色圆盘叠在一起。试设计一个算法，以最少次数完成上述移动，并输出每次移动的圆盘编号、起始塔座、目的塔座。并对自己的程序进行复杂性分析。

#include<iostream>
#include <stack>
#include<cstdio>
using namespace std;

int count=0;

void move(stack<char> &a,stack<char> &c)
{
	char flag1=a.top(); a.pop();
	char flag2=c.top();c.pop();
	
	if(!c.empty()&&(c.top()+a.top())%2==0)    //奇数加奇数为偶数，奇数加偶数为奇数
	{
		cout<<"移动过程中出现错误"<<endl<<endl;
	}

	cout<<"第"<<++count<<"次移动的圆盘编号为 "<<a.top()<<endl;
	cout<<"移动方向为："<<flag1<<" -> "<<flag2<<endl<<endl;
	c.push(a.top());
	a.pop();
	c.push(flag2); a.push(flag1);
}

void haino(int n,stack<char> &c,stack<char> &a,stack<char> &b)    //借助于b，把a上的元素移动到c上
{
	if(n==1)
		move(a,c);
	else
	{
		haino(n-1,b,a,c);
		move(a,c);
		haino(n-1,c,b,a);
	}
}

int main()
{
	int i;
	int n;
	while(cin>>n)
	{
		stack<char> sa;
		stack<char> sb;
		stack<char> sc;
		for(i=n;i>0;i--)
		{
			sa.push(i+'0');
		}
		sa.push('A');
		sb.push('B');
		sc.push('C');
		haino(n,sc,sa,sb);
		cout<<"C 中的元素："<<endl;
		while(!sc.empty())
		{
			cout<<sc.top()<<endl;
			sc.pop();
		}
	}
	
	system("pause");
	return 0;
}