解いてみた。「Aランク：ハノイの塔」

問題

「Aランク：ハノイの塔」

コード

Javaで解いてみました。

import java.util.*;

public class Main {
    
    private static ArrayList<Stack<Integer>> alst;
    private static int nT;
    
    public static void main(String[] args) {
   
        Scanner sc = new Scanner(System.in);
        int nN = sc.nextInt();
        nT = sc.nextInt();
    
        // 初期設定
        alst = new ArrayList<Stack<Integer>>();
        for (int i = 0; i < 3; i++) {
            alst.add(new Stack<Integer>());
        }
        
        for (int i = nN; i > 0; i--) {
            alst.get(0).push(i);
        }

        // 移動開始
        move(0, 2, nN);

        // 結果出力
        printStack();
    }
    
    private static void printStack() {
        for (int i = 0; i < 3; i++) {
            if (alst.get(i).empty()) {
                System.out.println("-");
            } else {
                Iterator<Integer> it = alst.get(i).iterator();
                boolean bFirst = true;
                while (it.hasNext()) {
                    if (!bFirst) {
                        System.out.print(" ");
                    } else {
                        bFirst = false;
                    }
                    System.out.print(it.next());
                }
                System.out.println("");
            }
        }
    }
    
    private static void move(int a, int b, int n) {
        if (n <= 0) { return; }

        int c = findSpace(a, b);
        
        // a -> c に 盤1 〜 N-1 を移動
        move(a, c, n-1);

        if (nT <= 0) {  // 残り回数チェック
            return;
        }
        
        // a -> b に 盤N を移動 
        int tmp = alst.get(a).pop();
        alst.get(b).push(tmp);
        --nT;   // 回数を -1 する

        // c -> b に 盤1 〜 N-1 を移動        
        move(c, b, n-1);
    }
    
    // a,bと異なる3本目の塔cを返す。
    private static int findSpace(int a, int b) {
        if (a > b) {
            int tmp = a; 
            a = b;
            b = tmp;
        }
        
        if (b == 1) { return 2; }
        if (a == 1) { return 0; }
        return 1;
    }
    
}

解説

標準入力からの数値の読み取り

Scanner インスタンスを作り、nextInt()メソッドで数値を取得しています。

解き方

1 〜 N の円盤が積まれている柱を a、移動先を b、残りの柱を c とすると、

1. 1 〜 N-1 の円盤の山を a から c に移動する
2. N番目の円盤を a から b に移動する
3. 1 〜 N-1 の円盤の山を c から b に移動する

これらの処理を、N-1, N-2, ..., 1 について行えば良いことがわかります。これを再帰関数を用いて実現しています。

メソッドの説明

printStack()

3本の柱にある円盤のそれぞれの状態を表示します。

• 柱（Stack）が空の場合は、"-"を表示しています
• それ以外の場合は、Stackの中身を順に表示しています。なお、余計な空白を表示させないために。bFirstフラグを設定しています

move()

再帰処理で円盤の移動を行います。n=0の時、再帰処理を終了しています。

findSpace()

3本の柱のうち2本を指定すると、残りの1本の番号（0 〜 2）を返します。