河內塔

河內塔： (n ,A,B,C) = (n-1,A,C,B)  +  n:A→C  +  (n-1,B,A,C)

可參考：http://www.mathland.idv.tw/game/hanoi/hanoi.htm

(說明一)

要將n個環由A塔搬至C塔，B塔可以暫放，需 2ⁿ-1步，假設n=4需15步

● 第1~7步：將(123)由A搬至B  (說明二再拆解)

● 第8步：將(4)由A搬至C

● 第9~15步：將(123)由B搬至C  (這裏有9~15步當練習吧)

(說明二)

以上第1~7步：將(123)由A搬至B，C當暫放區，即n=3分成三部份

● 第1~3步：將(12)由A搬至C   (說明三再拆解)

● 第4步：將(3)由A搬至B

● 第5~7步：將(12)由C搬至B   (說明四再拆解)

(說明三)

以上第1~3步：將(12)由A搬至C，B當暫放區，即n=2分成三部份

● 第1步：將(1)由A搬至B 

● 第2步：將(2)由A搬至C

● 第3步：將(1)由B搬至C

(說明四)

以上第5~7步：將(12)由C搬至B，A當暫放區，即n=2分成三部份

● 第5步：將(1)由C搬至A 

● 第6步：將(2)由C搬至B

● 第7步：將(1)由A搬至B

以C++解出

4 1:1A->B 2:2A->C 3:1B->C 4:3A->B 5:1C->A 6:2C->B 7:1A->B 8:4A->C 9:1B->C 10:2B->A 11:1C->A 12:3B->C 13:1A->B 14:2A->C 15:1B->C

程式碼如下

#include <iostream>

using namespace std;

int stp=0; //總步數

void hanoi(int n, char A, char B, char C)

{

        if(n==1) cout <<++stp<<":"<<n<<A<<"->"<<C<<endl;

        else

        {

                hanoi(n-1,A,C,B);

                cout <<++stp<<":"<<n<<A<<"->"<<C<<endl;

                hanoi(n-1,B,A,C);

        }

    return;

}

int main( void )

{

        int n;

        cin >> n;

        hanoi(n, 'A' , 'B', 'C');

}