/*
問題描述：有三個柱子A, B, C. A柱子上疊放有n個盤子，每個盤子都比它下面的盤子要小一點，
可以從上到下用1, 2, ..., n編號。要求借助柱子B，把柱子A上的所有的盤子移動到柱子C上。
移動條件為：1、一次只能移一個盤子；
2、移動過程中大盤子不能放在小盤子上，只能小盤子放在大盤子上。
*/
/*
遞歸的算法相信大多數人都知道，非遞歸算法也有出現過。
如：摘自http://www.programfan.com/club/old_showbbs.asp?id=96548
作者：qq590240
#include <iostream>
#include <stdlib.h>
#ifdef _WIN32
using namespace std;
#endif
static void hanoi(int height)
{
??? int fromPole, toPole, Disk;
??? int *BitStr = new int[height],
??????? *Hold?? = new int[height];
??? char Place[]? = {'A', 'B', 'C'};
??? int i, j, temp;
??? for (i=0; i < height; i++)
??? {
??????? BitStr[i] = 0;
??????? Hold[i] = 1;
??? }
??? temp = 3 - (height % 2);
??? int TotalMoves = (1 << height) - 1;
??? for (i=1; i <= TotalMoves; i++)
??? {
??????? for (j=0 ; BitStr[j] != 0; j++)
??????? {
??????????? BitStr[j] = 0;
??????? }
??????? BitStr[j] = 1;
??????? Disk = j+1;
??????? if (Disk == 1)
??????? {
??????????? fromPole = Hold[0];
??????????? toPole = 6 - fromPole - temp;
??????????? temp = fromPole;
??????? }
??????? else
??????? {
??????????? fromPole = Hold[Disk-1];
??????????? toPole = 6 - Hold[0] - Hold[Disk-1];
??????? }
??????? cout << "Move disk " << Disk << " from " << Place[fromPole-1]
???????????? << " to " << Place[toPole-1] << endl;
??????? Hold[Disk-1] = toPole;
??? }
}
?
int main(int argc, char *argv[])
{
??? cout << "Towers of Hanoi: " << endl
???????? << "moving a tower of n disks from pole A to pole B by using pole C" << endl;
??? cout << "Input the height of the original tower: ";
??? int height;
??? cin >> height;
??? hanoi(height);
??? system("PAUSE");
??? return EXIT_SUCCESS;
}
?////////////////////////////////////////////////////////////
?我在這里根據《數學營養菜》（談祥柏 著）提供的一種方法，編了一個程序來實現。
*/
/*
算法介紹：
首先容易證明，當盤子的個數為n時，移動的次數應等于2^n - 1。
一位美國學者發現一種出人意料的方法，只要輪流進行兩步操作就可以了。
首先把三根柱子按順序排成品字型，把所有的圓盤按從大到小的順序放在柱子A上。
根據圓盤的數量確定柱子的排放順序：若n為偶數，按順時針方向依次擺放 A B C；
若n為奇數，按順時針方向依次擺放 A C B。
（1）按順時針方向把圓盤1從現在的柱子移動到下一根柱子，即當n為偶數時，若圓盤1在柱子A，則把它移動到B；
若圓盤1在柱子B，則把它移動到C；若圓盤1在柱子C，則把它移動到A。
（2）接著，把另外兩根柱子上可以移動的圓盤移動到新的柱子上。
即把非空柱子上的圓盤移動到空柱子上，當兩根柱子都非空時，移動較小的圓盤
這一步沒有明確規定移動哪個圓盤，你可能以為會有多種可能性，其實不然，可實施的行動是唯一的。
（3）反復進行（1）（2）操作，最后就能按規定完成漢諾塔的移動。
*/
#include <iostream>
using namespace std;
const int MAX = 64; //圓盤的個數最多為64
struct st{? //用來表示每根柱子的信息
????? int s[MAX]; //柱子上的圓盤存儲情況
????? int top; //棧頂，用來最上面的圓盤
????? char name; //柱子的名字，可以是A，B，C中的一個
?????
????? int Top()//取棧頂元素
????? {
??????????? return s[top];
????? }
????? int Pop()//出棧
????? {
??????????? return s[top--];
????? }
????? void Push(int x)//入棧
????? {
??????????? s[++top] = x;
????? }
} ;
long Pow(int x, int y); //計算x^y
void Creat(st ta[], int n); //給結構數組設置初值
void Hannuota(st ta[], long 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, max);//移動漢諾塔的主要函數
????? system("pause");
????? return 0;
}
void Creat(st ta[], int n)
{
????? ta[0].name = 'A';
????? ta[0].top = n-1;
????? for (int i=0; i<n; i++) //把所有的圓盤按從大到小的順序放在柱子A上
??????????? ta[0].s[i] = n - i;
???????????
????? ta[1].top = ta[2].top = 0;//柱子B，C上開始沒有沒有圓盤
????? for (int i=0; i<n; i++)
??????????? ta[1].s[i] = ta[2].s[i] = 0;
???????????
????? if (n%2 == 0) //若n為偶數，按順時針方向依次擺放 A B C
????? {
??????????? ta[1].name = 'B';
??????????? ta[2].name = 'C';
????? }
????? else? //若n為奇數，按順時針方向依次擺放 A C B
????? {
??????????? ta[1].name = 'C';
??????????? ta[2].name = 'B';
????? }
}
long Pow(int x, int y)
{
????? long sum = 1;
????? for (int i=0; i<y; i++)
??????????? sum *= x;
????? return sum;
}
void Hannuota(st ta[], long max)
{
????? int k = 0; //累計移動的次數
????? int i = 0;
????? int ch;
????? while (k < max)
????? {
??????????? //按順時針方向把圓盤1從現在的柱子移動到下一根柱子
??????????? ch = ta[i%3].Pop();
??????????? ta[(i+1)%3].Push(ch);
??????????? cout << ++k << ": " << "Move disk " << ch << " from " << ta[i%3].name << " to " << ta[(i+1)%3].name << endl;
??????????? i++;
??????????? //把另外兩根柱子上可以移動的圓盤移動到新的柱子上
??????????? if (k < max)
??????????? {???? //把非空柱子上的圓盤移動到空柱子上，當兩根柱子都為空時，移動較小的圓盤
????????????????? 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;
????????????????? }
??????????? }
????? }
}
?