原文:
In the classic problem of the Towers of Hanoi, you have 3 rods and N disks of different sizes which can slide onto any tower. The puzzle starts with disks sorted in ascending order of size from top to bottom (e.g., each disk sits on top of an even larger one).
You have the following constraints:
- Only one disk can be moved at a time.
- A disk is slid off the top of one rod onto the next rod.
- A disk can only be placed on top of a larger disk.
Write a program to move the disks from the first rod to the last using Stacks
译文:
编程解决汉诺塔问题,使用数据结构栈
经典递归题,非递归解法参考:
http://blog.csdn.net/shaohui/article/details/660018
http://hawstein.com/posts/3.4.html
下面只列举递归解法:
package Stack_Queue;
import java.util.Stack;
public class S3_4 {
static class Tower {
private Stack<Integer> disks;
private int index;
public Tower(int i) {
disks = new Stack<Integer>();
index = i;
}
public int index() {
return index;
}
// 添加一个disk到当前栈
public void add(int disk) {
// 不能把一个大的盘放在一个小的盘上面
if(!disks.isEmpty() && disks.peek() <= disk) {
System.out.println("Error placing disk " + disk);
} else {
disks.push(disk);
}
}
// 把当前栈顶元素移到Tower t的栈顶
public void moveTopTo(Tower t) {
int top = disks.pop();
t.add(top);
}
public void print() {
System.out.println("Contents of Tower " + index() + ": " + disks.toString());
}
// 把n个盘子从当前Tower移到destination Tower,借助bufferTower
public void moveDisks(int n, Tower destination, Tower buffer){
if (n > 0) {
String tag = "move_" + n + "_disks_from_" + this.index + "_to_" + destination.index + "_with_buffer_" + buffer.index;
System.out.println("<" + tag + ">");
moveDisks(n - 1, buffer, destination); // 先把最上面的n-1个盘借助destination Tower移到buffer Tower
System.out.println("<move_top_from_" + this.index + "_to_" + destination.index + ">");
System.out.println("<before>");
System.out.println("<source_print>");
this.print();
System.out.println("</source_print>");
System.out.println("<destination_print>");
destination.print();
System.out.println("</destination_print>");
System.out.println("</before>");
moveTopTo(destination); // 然后把当前Tower的最底层一个盘直接移到destination上
System.out.println("<after>");
System.out.println("<source_print>");
this.print();
System.out.println("</source_print>");
System.out.println("<destination_print>");
destination.print();
System.out.println("</destination_print>");
System.out.println("</after>");
System.out.println("</move_top_from_" + this.index + "_to_" + destination.index + ">");
buffer.moveDisks(n - 1, destination, this); // 最后借助当前Tower,把在buffer Tower的n-1个盘移到destination Tower
System.out.println("</" + tag + ">");
}
}
}
public static void main(String[] args) {
// Set up code.
int n = 5;
Tower[] towers = new Tower[3];
for (int i = 0; i < 3; i++) {
towers[i] = new Tower(i);
}
for (int i = n - 1; i >= 0; i--) {
towers[0].add(i);
}
// Copy and paste output into a .XML file and open it with internet explorer.
//towers[0].print();
towers[0].moveDisks(n, towers[2], towers[1]);
//towers[2].print();
}
}
分享到:
相关推荐
Stack_Queue_Stack_源码
c++stack_和_queue用法,很好的介绍了STL中stack和queue的用法,及其使用方法
前端大厂最新面试题-stack_queue
Data structure: Stack->Queue Example
本源码实现了两个类,一个是带有最大值的栈和一个是带有最大值的队列。栈利用了两个C++的stack,队列利用了C++的queue。
实现栈,队列,链表的简单操作,其中链表包括单链表,双链表,循环链表。
Java_Stack_Queue Java中使用链表的堆栈和队列实现
Pro_MERN_Stack_Full_Stack_Web_App_Development_with_Mongo,_Express,_React,_and_Node
Lists_Stack_Queue_PriorityQueue.java
TI公司提供2015年11月最新基于ZigBee无线智能家居开发协议(Z_Stack_Home_1.2.2a.exe) 由于只能上传小于60MB文件,将150MB原文件分割3个部分上传,分别为: Z_Stack_Home_1.2.2a.exe.part1.rar Z_Stack_Home_1.2.2a....
stack_queue_p2pchat_practice:只是使用Stack和Queue技术的Java实践聊天应用程序
NXP 的 LIN 协议栈,之前一直用的 4.5.7 的版本,使用过程中有好几个问题都是手动修复的。最近在官网上看见了 4.6.6 的版本,下载测试了一遍,发现之前手动修复的几个问题都已经 OK 了。
tcpip_stack_v1_2_TCP,IP_TCP_IP_udpmac_UDP_tcp.zip
飞思卡尔官方最新LIN栈源码,可用于LIN应用开发参考和LIN的学习
常用的C++数据结构算法,包括队列、堆栈、链表...等.以模板类型式实现
TI公司提供2015年11月最新基于ZigBee无线智能家居开发协议(Z_Stack_Home_1.2.2a.exe) 由于只能上传小于60MB文件,将150MB原文件分割3个部分上传,分别为: Z_Stack_Home_1.2.2a.exe.part1.rar Z_Stack_Home_1.2.2a....
TI公司提供2015年最新基于ZigBee无线智能家居开发协议(Z_Stack_Home_1.2.2.exe) 由于只能上传小于60MB文件,将140MB原文件分割3个部分上传,分别为: Z_Stack_Home_1.2.2.exe.part1.rar Z_Stack_Home_1.2.2.exe.part...
一个完整的LIN代码程序,使用NXP提供的驱动开发
stack_queue