11729-ハノイタワー移動順

質問する

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

入力

第1行は、第1の棒に積まれた円板の個数N(1≦N≦20)を与える.

しゅつりょく

1行目に移動した回数出力K.
2行目から実行プロセスの出力を開始します.2行目から、2つの整数A BをK行に分けて出力します.これは、A番タワーの一番上の円板をB番タワーの一番上に移動することを意味します.

Solution

Java

import java.util.Scanner;

public class Main {
    public static StringBuilder sb = new StringBuilder();
    public static void Hanoi(int N, int start, int mid, int target) {
        if (N == 1) {
            sb.append(start + " " + target + "\n");
            return;
        }
        Hanoi(N-1, start,target,mid);
        sb.append(start + " " + target + "\n");
        Hanoi(N-1,mid,start,target);
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        sb.append((int) (Math.pow(2, N) - 1)).append('\n');
        Hanoi(N, 1, 2, 3);
        System.out.println(sb);
    }
}

再帰の代表的な問題であるハノイタワー問題.
最下原版以外のn-1原版を再帰的に移動する.