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];   //用來存貯當(dāng)前的盤的位置。hold[0]為第一個盤所在的柱號
    char Place[]  = {'A', 'C', 'B'};
    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; //1+2+3等于6，所以6減去其它兩個，剩下那個就是要移去的柱子
            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;
}

 

/*問題描述：有三個柱子A, B, C. A柱子上疊放有n個盤子，每個盤子都比它下面的盤子要小一點，可以從上

到下用1, 2, ..., n編號。要求借助柱子C，把柱子A上的所有的盤子移動到柱子B上。移動條件為：1、一

次只能移一個盤子；2、移動過程中大盤子不能放在小盤子上，只能小盤子放在大盤子上。

算法要點有二：
1、確定哪一個盤子要移動。有n個盤子的Hanoi塔需要移動2^n -1次，設(shè)m為n位的二進(jìn)制數(shù)，則m的取值范

圍為0～2^n -1。讓m每次遞增1，可以發(fā)現(xiàn)，m中最低一位的剛剛由0變?yōu)?的位置的位置編號，和即將要移

動的盤子編號有確定關(guān)系。

2、這個盤子往哪個柱子上移。
a.第一次需要移動1號盤，n為奇數(shù)時，1號盤首先移動到柱子B，為偶數(shù)時首先移動到柱子C。
b.接下來如果移動的盤子不是1號盤。你有兩個柱子可以選擇。先找到1號盤所在的柱子，因為移動的盤子

不能疊放到1號盤上，所以該盤可以移動的位置就是沒有1號盤的那個柱子。
c.如果移動的盤子是1號盤。也有兩個柱子可以選擇。找到1號盤原先是從哪個柱子上移來的，因為移動的

順序（順時針或逆時針）一旦確定，就不會更改，所以排除from的那個柱子后，移動方向也就唯一了。*/