こんにちは。「Javaを復習する初心者」です。
前回Queueインターフェースの実装クラスとしてLinkedListクラスを使用しました。今回はDequeインターフェースの実装クラスとしてLinkedListクラスを使おうと考え、ハノイの塔のプログラムを書いてみました。
ハノイの塔とは
ハノイの塔というパズルがあります。棒が3本あり、数枚の円盤が1本の棒に通されています。これを目的の棒に積みなおしましょうという問題です。円盤には大小があり、小さい円盤の上に大きな円盤を置くことはできないルールです。細かいところはネットを見ると参考になる資料がたくさん出てきますので、ここでは省略します。
ハノイの塔をプログラミングで解くことができるようです。参考にしたサイトは以下のサイトです。
http://www.atmarkit.co.jp/ait/articles/0810/01/news135_3.html
JavaScriptで書かれていたので、Javaにしてみました。towerというオブジェクトはprototypeを使っているため、
Java側ではクラスを定義して、メソッドを定義しています。this.[プロパティ]となっている個所もクラスを定義し、フィールドを定義しました。変数processListというはJavaScriptの配列です。これはLinkedListを使いました。使い方を見るとスタックとして使っている様子なので、このクラスを選択しました。displayTower()メソッドはHTMLの要素に描画をしている様子だったため、このメソッドはJava側には移しませんでした。
Javaで実装
今回はDequeインターフェースの実装クラスとしてLinkedListクラスを使っています。pop()メソッドとpush(E e)メソッドを使い、スタックから取り出し、スタックへ積むということをやってます。
以下はソースと実行結果です。
ソース
package practice;
import java.util.Deque;
import java.util.LinkedList;
public class Hello20160820 {
private static final int TOWER_ID_FROM = 0;
private static final int TOWER_ID_SPARE = 1;
private static final int TOWER_ID_TO = 2;
Deque<Process> processList = new LinkedList<>();
int index = 0;
int disks = 2;
Tower[] towers = {
new Tower(TOWER_ID_FROM),
new Tower(TOWER_ID_SPARE),
new Tower(TOWER_ID_TO)
};
public static void main(String[] args) {
new Hello20160820().start();
}
public void start() {
// 円盤の動かし方
hanoi(TOWER_ID_FROM, TOWER_ID_TO, TOWER_ID_SPARE, disks);
// 出力
for (Process p : processList) {
System.out.println(p);
}
System.out.println();
// ディスクの初期位置
for (int i = 0; i < disks; i++) {
towers[TOWER_ID_FROM].set(disks - i);
}
for (Tower t: towers) {
System.out.println(t);
}
while (towers[TOWER_ID_TO].step.size() != disks) {
move();
System.out.println("--------------");
for (Tower t: towers) {
System.out.println(t);
}
}
}
public void hanoi(int from, int to, int spare, int numberOfDisk) {
if (numberOfDisk > 1) {
hanoi(from, spare, to, numberOfDisk - 1);
processList.add(new Process(from, to));
hanoi(spare, to, from, numberOfDisk - 1);
} else {
processList.add(new Process(from, to));
}
}
public void move() {
if (processList.size() == 0) {
return;
}
Process p = processList.pop();
towers[p.moveFrom].move(towers[p.moveTo]);
}
}
class Process {
int moveFrom;
int moveTo;
@Override
public String toString() {
return "Process [moveFrom=" + moveFrom + ", moveTo=" + moveTo + "]";
}
public Process(int moveFrom, int moveTo) {
this.moveFrom = moveFrom;
this.moveTo = moveTo;
}
}
class Tower {
int id;
Deque<Integer> step;
public Tower(int id) {
this.id = id;
this.step = new LinkedList<>();
}
@Override
public String toString() {
return "id: " + id + step.toString();
}
public void set(int disk) {
this.step.push(disk);
}
public int get() {
if (this.step.size() > 0) {
return this.step.pop();
}
return 0;
}
public void move(Tower toTower) {
toTower.set(this.get());
}
}結果
Process [moveFrom=0, moveTo=1]
Process [moveFrom=0, moveTo=2]
Process [moveFrom=1, moveTo=2]
id: 0[1, 2]
id: 1[]
id: 2[]
--------------
id: 0[2]
id: 1[1]
id: 2[]
--------------
id: 0[]
id: 1[1]
id: 2[2]
--------------
id: 0[]
id: 1[]
id: 2[1, 2]hanoi()メソッドで円盤の動かし方がProcessクラスとして生成され、リストに格納されます。最初の出力がリストの内容を表しています。Process [moveFrom=0, moveTo=1]はid0番の棒からid1番の棒へ円盤を移動させることを表します。
実際に円盤を動かしているメソッドがmove()です。id: 0[1, 2]はidが0番の棒に上から1番, 2番の円盤が積まれていることを表しています。最後の出力でid: 2[1, 2]になって完了です。
円盤が3つのときは以下になります。
円盤3つの場合の結果
Process [moveFrom=0, moveTo=2]
Process [moveFrom=0, moveTo=1]
Process [moveFrom=2, moveTo=1]
Process [moveFrom=0, moveTo=2]
Process [moveFrom=1, moveTo=0]
Process [moveFrom=1, moveTo=2]
Process [moveFrom=0, moveTo=2]
id: 0[1, 2, 3]
id: 1[]
id: 2[]
--------------
id: 0[2, 3]
id: 1[]
id: 2[1]
--------------
id: 0[3]
id: 1[2]
id: 2[1]
--------------
id: 0[3]
id: 1[1, 2]
id: 2[]
--------------
id: 0[]
id: 1[1, 2]
id: 2[3]
--------------
id: 0[1]
id: 1[2]
id: 2[3]
--------------
id: 0[1]
id: 1[]
id: 2[2, 3]
--------------
id: 0[]
id: 1[]
id: 2[1, 2, 3]hanoi()メソッドの再起呼び出しが上手く機能しているがわかります。