問題
有 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。