白準ハノイタワー移動順[java]

8768 ワード
コーディングテスト練習 テキストリンク
質問元:https://www.acmicpc.net/problem/11729

問題の説明


3本の棒があり、1本目の棒にはn個の半径の異なる円板が積み上げられている.各円板は半径の大きい順に積み上げられている.現在、修道僧たちは以下の規則に従って、最初の棒から3番目の棒に移動します.
一度に1枚の原版を別の塔に移すしかない.
積み上げられたフィルムはいつも上のほうが下のより小さい.
プログラムを作成し、この操作を実行するために必要な移動順序を出力します.ただし、移動回数を最小限に抑える必要があります.
下図は5枚のバックグラウンドの例です.

入力
第1行は、第1の棒に積まれた円板の個数N(1≦N≦20)を与える.
しゅつりょく
1行目に移動した回数出力K.
2行目から実行プロセスの出力を開始します.2行目から、2つの整数A BをK行に分けて出力します.これは、A番タワーの一番上の円板をB番タワーの一番上に移動することを意味します.
入力例
3
サンプル出力
7
1 3
1 2
3 2
1 3
2 1
2 3
1 3

問題を解く

import java.io.*;

class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int total = Integer.parseInt(br.readLine());
        System.out.println((int) Math.pow(2, total) - 1);
        StringBuilder sb = new StringBuilder();
        hanoi(total, 1, 2, 3, sb);
        System.out.println(sb);

        br.close();
    }

    public static void hanoi(int N, int start, int mid, int to, StringBuilder sb) {

        //System.out.println("thread loc:" + start + " " + mid + " " + to);
        if (N == 1) {
            sb.append(start + " " + to).append("\n");
            return;
        }
        
        hanoi(N - 1, start, to, mid, sb);
        
        sb.append(start + " " + to).append("\n");
        
        hanoi(N - 1, mid, start, to, sb);
    }
}
問題自体は理解できず、次の2つのソースを参考に理解と解答を行いました.
参考資料
https://ko.wikipedia.org/wiki/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98_%ED%83%91
https://st-lab.tistory.com/96
伯俊-平均値を超えたはず(4344)
intellij idea登録機