The Tower of Hanoi
In the Tower of Hanoi puzzle:
- There are three stacks (towers), numbered 0, 1, 2.
- There are N disks numbered 0, ..., N-1.
=> 0 is the smallest. - Initially, the disks are placed in tower 0, in the order largest to smallest.
=> Smallest on top. - Goal: to move the disks to tower 1 using only legal moves.
- What's a legal move?
- You can move only a disk at the top of a tower.
- You can move only one disk at a time.
- You cannot place a disk on top of a smaller one.
- There are three key steps in the recursion:
- Step 1: move disks 0, ..., N-2 from tower 0 to tower 2
=> Sub problem of smaller size. - Step 2: move disk N-1 from tower 0 to tower 1.
- Step 3: move disks 0, ..., N-2 from tower 2 to tower 1.
=> Sub problem of smaller size.
- Step 1: move disks 0, ..., N-2 from tower 0 to tower 2
- In pseudocode (without base case):
Algorithm towerOfHanoi (n, i, j) Input: Disks numbered 0, ..., n are to be moved from tower i to tower j 1. // ... base case ... // First find the third tower, other than i and j: 2. k = otherTower (i, j) // Step 1: move disks 0,..,n-1 from i to k 3. towerOfHanoi (n-1, i, k) // Step 2: move disk# n from i to j 4. move (n, i, j) // Step 3: move disks 0,...,n-1 from k to j 5. towerOfHanoi (n-1, k, j)
- The base case: move a single disk
Here's the program: (source file)
public class TowerOfHanoi { public static void main(String[] argv) { // A 3-disk puzzle: System.out.println("3-Disk solution: "); solveHanoi(2, 0, 1); // A 4-disk puzzle: System.out.println("4-Disk solution: "); solveHanoi(3, 0, 1); } static void solveHanoi(int n, int i, int j) { // Bottom-out. if (n == 0) { // The smallest disk. move(0, i, j); return; } int k = other(i, j); solveHanoi(n - 1, i, k); // Step 1. move(n, i, j); // Step 2. solveHanoi(n - 1, k, j); // Step 3. } static void move(int n, int i, int j) { // For now, we'll merely print out the move. System.out.println("=> Move disk# " + n + " from tower " + i + " to tower " + j); } static int other(int i, int j) { // return 3-i-j; // this is simpler. // Given two towers, return the third. if ((i == 0) && (j == 1)) { return 2; } else if ((i == 1) && (j == 0)) { return 2; } else if ((i == 1) && (j == 2)) { return 0; } else if ((i == 2) && (j == 1)) { return 0; } else if ((i == 0) && (j == 2)) { return 1; } else if ((i == 2) && (j == 0)) { return 1; } // We shouldn't reach here. return -1; } }
Note:
- The above program merely prints out the moves needed
=> We don't actually maintain the state of each tower.
Next, suppose we want to maintain the state of each tower:
- The ideal data structure is a stack.
- We'll use one stack for each tower.
Here's the program: (source file)
import java.util.*; public class TowerOfHanoi2 { // towers[0], towers[1] and towers[2] are the three stacks. static Stack<Integer>[] towers; public static void main(String[] argv) { // A 3-disk puzzle: System.out.println("3-Disk solution: "); solveHanoi(2, 0, 1); // A 4-disk puzzle: System.out.println("4-Disk solution: "); solveHanoi(3, 0, 1); } static void solveHanoi(int n, int i, int j) { // Create the three stacks. towers = new Stack[3]; for (int k = 0; k < 3; k++) { towers[k] = new Stack<Integer>(); } // Put disks 0,...,n on stack 0. for (int k = n; k >= 0; k--) { towers[0].add(k); } // Print the initial stack. printTowers(); // Now solve recursively. Note: this is the method below. solveHanoiRecursive(n, i, j); } static void solveHanoiRecursive(int n, int i, int j) { // Bottom-out. if (n == 0) { move(0, i, j); return; } int k = other(i, j); solveHanoiRecursive(n - 1, i, k); // Step 1. move(n, i, j); // Step 2. solveHanoiRecursive(n - 1, k, j); // Step 3. } static void move(int n, int i, int j) { // Pull out the top disk on stack i. int topVal = towers[i].pop(); // Put it on stack j. towers[j].push(topVal); // Print status. System.out.println("Towers after moving " + n + " from tower " + i + " to tower " + j); printTowers(); } static int other(int i, int j) { return 3-i-j; } static void printTowers() { for (int i = 0; i < towers.length; i++) { System.out.print("Tower " + i + ": "); if (!towers[i].isEmpty()) { for (Integer I : towers[i]) { System.out.print(" " + I); } } System.out.println(); } } }
From: http://www.seas.gwu.edu/~drum/cs1112/lectures/module9/module9.html
相关推荐
This is the GUI version of Hanoi problem, it is really cool
TowerofHanoi.java
Tower of Hanoi implementation using Microsoft C#
TowerOfHanoi
matlab开发-TowersofHanoi。一个Matlab图形用户界面为河内流行的双塔益智游戏提供手动或自动解决方案。
Hanoi小游戏,从实际操作中掌握递归规律
VC++汉诺塔算法的实现,动态移动图形。
1.1 河内塔 The Tower Of Hanoi 1.2 平面上的直线 Lines In The Plane 1.3 约瑟夫问题 The Josephus Problem 2 和式 Sums 2.1 记号 Notation 2.2 和式和递归式 Sums And Recurrences 2.3 和式的处理 Manipulation ...
汉诺塔游戏源码。也是网上高人奉献的。不敢独享。感谢大家
JavaScript
汉诺塔 可以实现汉诺塔的解决 步骤的计算
汉诺塔代码A*算法,根据人工智能提供的算法思路,编写的程序
河内塔 著名的河内塔的 Java 程序。
hanoi tower,hanoi kuleleri
自编程序,matlab实现汉诺塔步骤,demo程序为5层,参数可修改
汉诺塔游戏,VS2019MFC平台开发,此为发行版内含exe文件和源码。可鼠标拖动盘子(不会出现盘子移动轨迹),画面清晰流畅;可连续演示和单步演示(上一步、下一步),可暂停;可记录游戏用时和步数,并排序展示。...
该项目收集了许多编程语言中的经典“河内塔”问题,包括鲜为人知和/或深奥的语言。
Towers of Hanoi Hanoi 用pb编程 可播放声音、单步执行
河内塔这个应用程序是著名的河内塔游戏的简单版本。 该应用程序是使用 jquery/javascript 实现的。入门苹果系统 open ...免责声明此应用程序旨在作为技术演示。 如果您有任何问题或疑虑,请随时通过与我联系。
河内游戏塔Java 客观的: 该游戏的目标是将所有N个磁盘从极点A移到极点C,并且需要2 ^ n-1次移动。 您不能将较大的磁盘移动到较小的磁盘上。 观看演示: