【C++】河內塔問題(Tower of Hanoi)

問題

有 3 根柱子 A、B、C。
A 柱上有 n 個盤子，盤的尺寸由上到下依次變大。
要按照以下規則將所有盤子移到 C 柱上：
(1.)每次只能移動一個盤子。
(2.)大盤不能疊在小盤上面。
請問最少須搬動幾次？

解法

先把 A 頂部的 n-1 個盤子移到 B，
再把 A 剩下最大的盤子移到 C，
最後再把 B 的 n-1 個盤子移到 C。

程式碼

#include <iostream>
using namespace std;
int step=0;
//(n, from, mid, to)
void hanoi(int n, char A, char B, char C){
    if(n == 1){
        cout << A << " to " << C << '\n';
        step++;
    }
    else{
        hanoi(n-1, A, C, B);
        hanoi(1, A, B, C);
        hanoi(n-1, B, A, C);
    }
}
int main(){
    int n;
    cin >> n;
    hanoi(n, 'A', 'B', 'C');
    cout << step << '\n';
}

執行結果

3
A to C
A to B
C to B
A to C
B to A
B to C
A to C
7

數學解

最少步驟數 = 2^n-1。