発展課題 (r1:ベーシック)

注意点

このページは復習 (1)の発展課題を掲載しています。発展課題については「復習回の課題について」をよく読んでから取り掛かってください。

作業について

今回の課題は以下のパッケージに作成してください。

パッケージの名前
j1.review01

作成するクラスの名前は問題ごとに指示があります。下記を参照してください

課題の提出方法については下記を参照してください。

また、別のコンピューター上に移動する際には、下記を参考にプログラムを持ち帰ってください。

問題

1. ハノイの塔の手順を表示するプログラム

作成するクラスの名前
Hanoi

「ハノイの塔」という問題があります。これは3本の塔のうちひとつに数枚の円盤がおいてあって、これを別の塔に全て移動するというゲームです。

図: ハノイの塔

ただし、円盤を移動する場合にはいくつか規則があります。

  • 重なって隣り合う円盤は、必ず下のほう上のものよりが大きくなければならない
  • 円盤は1枚ずつしか移動できない

上記のルールを守りながら、1番目の塔から3番目の塔に円盤を移動する手順を表示するプログラムを作成してください。ただし、円盤の枚数は入力ダイアログで入力できるものとします。

package j1.review01;

import javax.swing.JOptionPane;

public class Hanoi {

    public static void main(String[] args) {
        new Hanoi().start();
    }

    void start() {
        String input = JOptionPane.showInputDialog("円盤の枚数は？");
        int disks = Integer.parseInt(input);
        if (disks >= 1) {
            moveTower(1, 3, disks);
        }
        JOptionPane.showMessageDialog(null, input);
    }

    void moveTower(int from, int to, int disks) {


    }

    void moveDisk(int from, int to) {
        JOptionPane.showMessageDialog(null,
            from + "番目から" + to + "番目に1枚移動");
    }
}

例として、入力ダイアログに1を入力した場合は次のように表示します。

  • 1番目から3番目に1枚移動

入力ダイアログに2を入力した場合は次のように表示します。

  • 1番目から2番目に1枚移動
  • 1番目から3番目に1枚移動
  • 2番目から3番目に1枚移動

入力ダイアログに3を入力した場合は次のように表示します。

  • 1番目から3番目に1枚移動
  • 1番目から2番目に1枚移動
  • 3番目から2番目に1枚移動
  • 1番目から3番目に1枚移動
  • 2番目から1番目に1枚移動
  • 2番目から3番目に1枚移動
  • 1番目から3番目に1枚移動

すでに書いてあるmoveTowerメソッドは、(from)番目から(to)番目に、(disks)枚の円盤を移動する手順をまとめるものです。このメソッドの中身を書いてください。

ヒント

1番目から3番目にN枚の円盤を移動する手順は、次のように書けます。

  • 1番目から2番目にN-1枚の円盤を移動する
  • 1番目から3番目に1枚の円盤を移動する
  • 2番目から3番目にN-1枚の円盤を移動する

絵を描いてみるのがいいと思います。

ヒント

A番目からB番目に0枚の円盤を移動する手順は、「何もしない」ということになります。

ヒント

ハノイの塔では3本の塔を使い、この問題では1番目、2番目、3番目と呼んでいます。これらは合計すると常に 1 + 2 + 3 = 6 となります。A番目とB番目がわかっているとき、残りの1本はどのように計算できるでしょうか？