하노이의 탑(Tower of Hanoi)은 퍼즐의 일종이다. 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다.
게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다.
- 한 번에 하나의 원판만 옮길 수 있다.
- 큰 원판이 작은 원판 위에 있어서는 안 된다.
기둥이 A, B, C 있고 A 기둥에 원판이 n개 쌓여있을 때,
A -> (C를 거쳐) B로 옮기는 경우의 수 : an-1
A -> C로 옮기는 경우의 수 : 1
B -> (A를 거쳐) C로 옮기는 경우의 수 : an-1
따라서,
an = an-1 + 1 + an-1
양변에 1을 더하면,
(an + 1) = 2(an-1 + 1)
이것은 첫째항이 an + 1 이고, 공비가 2인 등비수열이다.
기본 등비수열 점화식이 (an + p) = (a1 + p) * kn-1 이므로
an = 2 * kn-1 - 1
a0 = 1 이므로,
a0 = 2 * k-1 - 1 = 1
k-1 = 1
따라서,
k = 1
최종적으로,
an = 2n-1 - 1
static String[] top = new String[]{"SIZE-1", "SIZE-2", "SIZE-3"};
static Stack<String> A = new Stack<>();
static Stack<String> B = new Stack<>();
static Stack<String> C = new Stack<>();
static int moveCount = 0;
public static void main (String[] args) {
A.push(top[2]);
A.push(top[1]);
A.push(top[0]);
hanoi(A.size(), "A", "B", "C");
System.out.println(moveCount + " moves.");
}
public static void hanoi (int topNo, String from, String via, String to) {
if (topNo == 1) {
move(from, topNo, to);
return;
}
// A -> C -> B
hanoi(topNo - 1, from, to, via);
// A -> C
move(from, topNo, to);
// B -> A -> C
hanoi(topNo - 1, via, from, to);
}
public static void move (String from, int topNo, String to) {
Stack<String> fromStack = getStack(from);
Stack<String> toStack = getStack(to);
toStack.push(fromStack.pop());
System.out.printf("%s--(%s)-->%s\n", from, top[topNo - 1], to);
System.out.println("A Stack" + A);
System.out.println("B Stack" + B);
System.out.println("C Stack" + C);
System.out.println("--------------");
moveCount += 1;
}
public static Stack<String> getStack(String stackName) {
if ("A".equals(stackName)) {
return A;
} else if ("B".equals(stackName)) {
return B;
} else {
return C;
}
}
static int count = 0;
public static void main(String[] args) {
Stick A = new Stick("A");
Stick B = new Stick("B");
Stick C = new Stick("C");
A.disks.push(Disk.DISK_C);
A.disks.push(Disk.DISK_B);
A.disks.push(Disk.DISK_A);
hanoi(A.disks.size(), A, B, C, () -> {
System.out.println("Stick A:" + A.disks);
System.out.println("Stick B:" + B.disks);
System.out.println("Stick C:" + C.disks);
});
System.out.println(count + " moves.");
}
public static void hanoi(int diskNo, Stick from, Stick via, Stick to, Runnable showStatus) {
if (diskNo == 1) {
Stick.move(from, to);
showStatus.run();
count += 1;
return;
}
// A -> C -> B
hanoi(diskNo - 1, from, to, via, showStatus);
// A -> C
Stick.move(from, to);
showStatus.run();
count += 1;
// B -> A -> C
hanoi(diskNo - 1, via, from, to, showStatus);
}
public enum Disk {
DISK_A, DISK_B, DISK_C;
}
public static class Stick {
final String name;
Stack<Disk> disks = new Stack<>();
public Stick(String name) {
this.name = name;
}
static void move(Stick from, Stick to) {
Disk disk = from.disks.pop();
to.disks.push(disk);
System.out.printf("%s--(%s)-->%s\n", from.name, disk, to.name);
}
@Override
public String toString() {
return "Stick[" + name + "]" + disks;
}
}
A--(SIZE-1)-->C
A Stack[SIZE-3, SIZE-2]
B Stack[]
C Stack[SIZE-1]
--------------
A--(SIZE-2)-->B
A Stack[SIZE-3]
B Stack[SIZE-2]
C Stack[SIZE-1]
--------------
C--(SIZE-1)-->B
A Stack[SIZE-3]
B Stack[SIZE-2, SIZE-1]
C Stack[]
--------------
A--(SIZE-3)-->C
A Stack[]
B Stack[SIZE-2, SIZE-1]
C Stack[SIZE-3]
--------------
B--(SIZE-1)-->A
A Stack[SIZE-1]
B Stack[SIZE-2]
C Stack[SIZE-3]
--------------
B--(SIZE-2)-->C
A Stack[SIZE-1]
B Stack[]
C Stack[SIZE-3, SIZE-2]
--------------
A--(SIZE-1)-->C
A Stack[]
B Stack[]
C Stack[SIZE-3, SIZE-2, SIZE-1]
--------------
7 moves.