ハノイの塔むずかしい

問題

3本の柱 A, B, C があり、柱 A に N 枚の円盤が小さい順（上が小さい）に積まれています。これをすべて柱 C へ移してください。ルールは次の2つです。

1回に動かせるのは一番上の1枚だけ
小さい円盤の上に、大きい円盤を置いてはいけない

最小手数で移すときの手順を、1手ずつ X->Y の形（例 A->C）で1行ずつ出力してください（全部で 2^N − 1 行）。

入出力例

入力	出力
`1`	`A->C`
`2`	`A->B A->C B->C`

💡 ヒント（クリックで必要な知識が開きます）

再帰（関数が自分自身を呼ぶ）で解くのが定番です。「N枚を A から C へ」は次の3ステップに分解できます：
1. 上の N-1 枚を A から B へ移す
2. 一番下の1枚を A から C へ動かす（A->C を出力）
3. N-1 枚を B から C へ移す

これを関数にします（from＝今ある柱、to＝行き先、via＝経由。%c で1文字を出力）：

void hanoi(int n, char from, char to, char via) {
    if (n == 1) { printf("%c->%c\n", from, to); return; }
    hanoi(n - 1, from, via, to);
    printf("%c->%c\n", from, to);
    hanoi(n - 1, via, to, from);
}

main から hanoi(n, 'A', 'C', 'B'); と呼び出します。

コーディング

※ コンパイル・実行はブラウザ内の簡易C言語/C++エンジン（JSCPP）で動いています。学習用のため、本物のコンパイラ（Visual Studio など）と一部の挙動・エラー表示が異なる場合があります。