package j1.lesson09;
import java.io.*;
/**
* 課題0904 - 解答例.
* @author s.arakawa
* @version $Id: Hanoi_java.rps,v 1.1 2006/03/06 12:56:15 java2005 Exp $
*/
public class Hanoi {
/**
* コンソールから1以上の整数を入力させ、
* 入力された値だけ円盤を持つ「ハノイの塔」の問題を解く流れを表示するプログラム。
* 「ハノイの塔」というのは、次のような問題である。
* <p>
* 3つの柱がある。そのうちの1つの柱に穴のあいた円盤を何枚か通して積み重ねてある。
* それらの円盤は下のものほど大きく、上のものほど小さい。
* そのすべての円盤を以下の規則に従って動かし、指定した柱に円盤を全て移動させる。
* </p>
* <ol>
* <li>円盤は、一度に一つだけ移動させることができる</li>
* <li>円盤は、それより小さな円盤の上に積むことはできない</li>
* </ol>
* @param args 無視される
* @throws IOException 入力時に例外が発生した場合
*/
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
System.out.print("円盤の数を入力：");
int disks = Integer.parseInt(reader.readLine());
if (disks < 1) {
System.out.println("1以上の整数を入力してください");
}
else {
hanoi(disks);
}
}
/**
* 引数に指定された値を円盤の数として、その円盤の数を持つハノイの塔を解き
* 手順を以下のように表示する。
* <pre> 円盤の番号: 移動元の塔の番号 -> 移動先の塔の番号 </pre>
* ただし、円盤の番号は一番小さい円盤を 1 とし、小さい順に 1, 2, 3,.. と割り振られる。
* また、塔の番号は次のように割り振られる。
* <ol>
* <li> 最初に円盤が置いてある場所 </li>
* <li> 円盤を移動させる際に経由させる場所 </li>
* <li> 円盤を移動させる先 </li>
* </ol>
* <code>n</code> が0以下の場合は考慮しない。
* @param n 円盤の数
*/
public static void hanoi(int n) {
// n 個のハノイの塔を表示する
// ただし、それぞれの塔に番号をつける
// start: 最初に円盤が置いてある塔 = 1
// temp: 円盤を移動させる際に経由させる塔 = 2
// target: 円盤を移動させる先の塔 = 3
hanoiView(n, 1, 2, 3);
}
/**
* <b>このメソッドは課題の仕様に含まれていない</b>。
* 引数で指定した塔の番号 <code>start</code> から <code>target</code> へ <code>n</code> 個の円盤を
* 移動する手順を表示する。
* <code>temp</code> は円盤を移動させる際に経由させる塔の番号を表す。
* @param n 移動させる円盤の個数
* @param start 移動元の塔の番号
* @param temp 移動させる際に経由させる塔の番号
* @param target 移動先の塔の番号
*/
public static void hanoiView(int n, int start, int temp, int target) {
// まず、ハノイの塔を解くに当たり、作業を3つに分ける
// 1. start から temp へ n - 1 個の円盤を移す
// 2. start には一番大きな円盤が残るので、それを target へ移す
// 3. temp から target へ n - 1 個の円盤を移す
//
// このように考えると、1, 3 はn-1個の円盤を移すハノイの塔であると
// 考えることができ、2 は単純に円盤を一つ移すだけの作業になる。
// ただし、円盤 0 個のハノイの塔 ということは、何もしないということである
if (n == 0) {
return;
}
// start 上にある n - 1 個の円盤を temp へ移す
// つまり、
// start から temp へ、 target を経由して
// n - 1 個の円盤を持つハノイの塔を実行する
// よって、以下のように塔の番号を入れ替えて実行する
// start -> start
// temp -> target
// target -> temp
hanoiView(n - 1, start, target, temp);
// 上記の作業が終わると、各塔にある円盤の数は以下のようになる
// start = 1 個
// temp = N - 1 個
// target = 0 個
// start に残っている円盤は最も大きな円盤であるので、
// target に移動する
// 実際に円盤を移す作業なので、これを表示する
System.out.println(n + ": " + start + " -> " + target);
// temp 上にある n - 1 個の円盤を target へ移す
// つまり、
// temp から target へ、 start を経由して
// n - 1 個の円盤を持つハノイの塔を実行する
// よって、以下のように塔の番号を入れ替えて実行する
// start -> temp
// temp -> start
// target -> target
hanoiView(n - 1, temp, start, target);
}
}
|