- 浏览: 248132 次
- 性别:
- 来自: 南京
文章分类
最新评论
-
mabusyao:
漠北空城 写道请问下,你这个是JDK版本是多少呢?!忘记了,应 ...
HashMap 源码解读 -
漠北空城:
请问下,你这个是JDK版本是多少呢?!
HashMap 源码解读 -
schumee:
完美团队~
项目沉思录 - 1.1 -
winie:
整理下 搞成引擎嘛 国产需要这样的engine
简单工作流引擎 -
mabusyao:
某位同学给我提供的堪称完美的解决方案:1. 将三个int数组放 ...
CraneWork
1. 有三根柱子,在一根柱子上从下往上按大小顺序摞着n片圆盘。要求把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
2. 有四根柱子,在一根柱子上从下往上按大小顺序摞着n片圆盘。要求把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在四根柱子之间一次只能移动一个圆盘。
3. 有三根柱子,在一根柱子上从下往上按大小顺序摞着m片圆盘, 另一根柱子上从下往上按大小顺序摞着n片圆盘,要求把圆盘从下面开始按大小顺序重新摆放在最后一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
4. 有三根柱子,在三根柱子上从下往上按大小顺序分别摞着m,n,l片圆盘, 要求把圆盘从下面开始按大小顺序重新摆放在最后一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
最后两道题两个并做一个写,太jb复杂了,回头看看别人有没什么好办法
最近做了些思路上的转变,并对汉诺塔有了新的理解,回想之前的复杂汉诺塔的程序,觉得还是可以改进很多的。
现在看起来比上一个程序简单明了了许多,但是其实步数是一样的,性能并没有增加。
不过基本上这已经算是最优的解法了。
package hanoi; /** * formulas: * T0 = 0 * Tn = Tn-1 + 1 * * closed form: * Tn = 2(n) -1 * * @author yaoh * */ public class SimpleHanoi { public static int count = 0; public static void hanoi(String a, String b, String c, int n) { if(n <= 0) System.out.println("No move needed."); if(n == 1) { System.out.println("Step "+ ++count+": move "+n+" from "+a+" to "+c); } else { hanoi(a, c, b, n - 1); System.out.println("Step "+ ++count+ ": move "+n+" from "+a+" to "+c); hanoi(b, a, c, n - 1); } } public static void main(String[] args) { hanoi("a", "b", "c", 5); System.out.println("Overall steps: " + count); } }
2. 有四根柱子,在一根柱子上从下往上按大小顺序摞着n片圆盘。要求把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在四根柱子之间一次只能移动一个圆盘。
package hanoi; /** * formula * T1 = 1 * T2 = 3 * Tn = 2T(n-2) + 3 * * closed form: * * * @author yaoh * */ public class FourHanoi { public static int count = 0; public static void hanoi(String a, String b, String c, String d, int n) { if(n == 1) { System.out.println("Step " + ++count + ": move " + n + " from " + a + " to " + d); }else if(n == 2) { System.out.println("Step " + ++count + ": move " + (n - 1) + " from " + a + " to " + b); System.out.println("Step " + ++count + ": move " + n + " from " + a + " to " + d); System.out.println("Step " + ++count + ": move " + (n - 1) + " from " + b + " to " + d); } else { hanoi(a, b, d, c, n - 2); System.out.println("Step " + ++count + ": move " + (n - 1) + " from " + a + " to " + b); System.out.println("Step " + ++count + ": move " + n + " from " + a + " to " + d); System.out.println("Step " + ++count + ": move " + (n - 1) + " from " + b + " to " + d); hanoi(c, a, b, d, n - 2); } } public static void main(String[] args) { hanoi("a", "b", "c", "d", 6); System.out.println("Overall steps: " + count); } }
3. 有三根柱子,在一根柱子上从下往上按大小顺序摞着m片圆盘, 另一根柱子上从下往上按大小顺序摞着n片圆盘,要求把圆盘从下面开始按大小顺序重新摆放在最后一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
4. 有三根柱子,在三根柱子上从下往上按大小顺序分别摞着m,n,l片圆盘, 要求把圆盘从下面开始按大小顺序重新摆放在最后一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
最后两道题两个并做一个写,太jb复杂了,回头看看别人有没什么好办法
/*Problem Statement There are three stacks of crates - two of them outside of the warehouse, and one inside the warehouse. We have a crane that can move one crate at a time, and we would like to move all of the crates to the stack inside the warehouse. A heavier crate can never be stacked on top of a lighter crate, and all three initial stacks obey that rule. Create a class CraneWork that contains a method moves that is given int[]s stack1, stack2, and warehouse containing the initial three stacks, and returns the minimum number of moves required to move all the crates into the warehouse stack. The elements of stack1, stack2, and warehouse represent the weights of the crates and are given from top to bottom (and thus in non-decreasing order of weight). Definition Class: CraneWork Method: moves Parameters: int[], int[], int[] Returns: int Method signature: int moves(int[] stack1, int[] stack2, int[] warehouse) (be sure your method is public) Constraints stack1, stack2, and warehouse will each contain between 0 and 20 elements, inclusive. The total number of elements in the three stacks will be between 1 and 20, inclusive. Each element in the three stacks will be between 1 and 200, inclusive. stack1, stack2, and warehouse will each be in non-decreasing order. Examples 0){3,50} {} {1,2,50,50,50} Returns: 12 Move 3 to stack2, 1 to stack1, 2 to stack2, 1 to stack2, 50 to warehouse, 1 to warehouse, 2 to stack1, 1 to stack1, 3 to warehouse, 1 to stack2, 2 to warehouse, 1 to warehouse. 1){50} {50} {10,20,30} Returns: 17 Start by moving 50 from stack2 to stack1. It then takes 7 moves to transfer the 10,20,30 to stack 2, 2 moves to transfer the 2 50's to the warehouse, and 7 more to transfer the 10,20,30 to the warehouse. 2){} {} {2,5,6,7} Returns: 0 All the crates are already in the warehouse. 3){1,2,3} {} {} Returns: 7 Move 1 from stack1 to warehouse, 2 from stack1 to stack2, 1 from warehouse to stack2, 3 from stack1 to warehouse, 1 from stack2 to stack1, 2 from stack2 to warehouse, 1 from stack1 to warehouse. This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved. */ package cranework_2; public class CraneWork { public static void moves(int[] stack_1, int[] stack_2, int[] ware_house) throws Exception{ CrateStack stack1 = new CrateStack(stack_1); CrateStack stack2 = new CrateStack(stack_2); CrateStack warehouse = new CrateStack(ware_house); show(stack1, stack2, warehouse); moves(stack1, 0, stack2, 0, warehouse, 0); } /** * @param stack1 * @param cursor1 * @param stack2 * @param cursor2 * @param stack3 * @param cursor3 * @throws Exception */ public static void moves(CrateStack stack1, int cursor1, CrateStack stack2, int cursor2, CrateStack stack3, int cursor3) throws Exception{ if(cursor1 == stack1.root && cursor2 == stack2.root) return; if(cursor1 == stack1.root) { if(cursor3 == stack3.root) { moves(stack2, cursor2 + 1, stack3, stack3.root, stack1, stack1.root); stack3.pushCrate(stack2.popCrate()); show(stack1, stack2, stack3); moves(stack1, cursor1, stack2, stack2.root, stack3, stack3.root); } else if (stack2.getValue(cursor2) > stack3.getValue(cursor3)) { moves(stack2, cursor2 + 1, stack3, cursor3, stack1, stack1.root); stack3.pushCrate(stack2.popCrate()); show(stack1, stack2, stack3); moves(stack1, cursor1, stack2, stack2.root, stack3, stack3.root); }else { cursor3 = stack3.find(stack2.getValue(cursor2)); moves(stack2, cursor2 + 1, stack3, cursor3, stack1, stack1.root); stack3.pushCrate(stack2.popCrate()); show(stack1, stack2, stack3); moves(stack1, cursor1, stack2, stack2.root, stack3, stack3.root); } } else if(cursor2 == stack2.root) { if(cursor3 == stack3.root) { moves(stack1, cursor1 + 1, stack3, stack3.root, stack2, stack2.root); stack3.pushCrate(stack1.popCrate()); show(stack1, stack2, stack3); moves(stack2, cursor2, stack1, stack1.root, stack3, stack3.root); } else if (stack1.getValue(cursor1) > stack3.getValue(cursor3)) { moves(stack1, cursor1 + 1, stack3, cursor3, stack2, stack2.root); stack3.pushCrate(stack1.popCrate()); show(stack1, stack2, stack3); moves(stack2, cursor2, stack1, stack1.root, stack3, stack3.root); }else { cursor3 = stack3.find(stack1.getValue(cursor1)); moves(stack1, cursor1 + 1, stack3, cursor3, stack2, stack2.root); stack3.pushCrate(stack1.popCrate()); show(stack1, stack2, stack3); moves(stack2, cursor2, stack1, stack1.root, stack3, stack3.root); } } else if(cursor3 == stack3.root) { if (stack1.getValue(cursor1) > stack2.getValue(cursor2)) { moves(stack1, cursor1 + 1, stack3, stack3.root, stack2, cursor2); stack3.pushCrate(stack1.popCrate()); show(stack1, stack2, stack3); moves(stack2, cursor2, stack1, stack1.root, stack3, stack3.root); } else { moves(stack2, cursor2 + 1, stack3, stack3.root, stack1, cursor1); stack3.pushCrate(stack2.popCrate()); show(stack1, stack2, stack3); moves(stack1, cursor1, stack2, stack2.root, stack3, stack3.root); } } else if (stack3.getValue(cursor3) > stack2.getValue(cursor2) && stack3.getValue(cursor3) > stack1.getValue(cursor1)) { if (stack1.getValue(cursor1) > stack2.getValue(cursor2)) { cursor3 = stack3.find(stack1.getValue(cursor1)); moves(stack1, cursor1 + 1, stack3, cursor3, stack2, cursor2); stack3.pushCrate(stack1.popCrate()); show(stack1, stack2, stack3); moves(stack2, cursor2, stack1, stack1.root, stack3, stack3.root); } else { cursor3 = stack3.find(stack2.getValue(cursor2)); moves(stack2, cursor2 + 1, stack3, cursor3, stack1, cursor1); stack3.pushCrate(stack2.popCrate()); show(stack1, stack2, stack3); moves(stack1, cursor1, stack2, stack2.root, stack3, stack3.root); } } else { if (stack1.getValue(cursor1) > stack2.getValue(cursor2)) { moves(stack1, cursor1 + 1, stack3, cursor3, stack2, cursor2); stack3.pushCrate(stack1.popCrate()); show(stack1, stack2, stack3); moves(stack2, cursor2, stack1, stack1.root, stack3, stack3.root); } else { moves(stack2, cursor2 + 1, stack3, cursor3, stack1, cursor1); stack3.pushCrate(stack2.popCrate()); show(stack1, stack2, stack3); moves(stack1, cursor1, stack2, stack2.root, stack3, stack3.root); } } } public static void show(CrateStack stack1, CrateStack stack2, CrateStack stack3){ System.out.println("Round:"); stack1.showStack(); stack2.showStack(); stack3.showStack(); //System.out.print("\n " + cursor1.weight + " " + cursor2.weight + " " + cursor3.weight); System.out.println("\n"); } } class CrateStack { private int[] stack = new int[20]; public int root = 0; public CrateStack(int weight) { stack[0] = weight; root++; } public CrateStack(int[] array) { for(int i = 0; i < array.length; i++) { stack[i] = array[i]; } root = array.length; } //Push a Value into Stack public void pushCrate(int value) { stack[root] = value; root++; } //Pop a Value into Stack public int popCrate() throws Exception{ if(root != 0) { root--; int result = stack[root]; stack[root] = 0; return result; } throw new NullPointerException(); } public boolean isTop(int cursor) { if(cursor == root - 1) return true; return false; } public void showStack() { try { if (root == 0) { System.out.print("{}"); } else { int temp = root - 1; System.out.print("{"); while (temp >= 0) { System.out.print(stack[temp] + ","); temp--; } System.out.print("}"); } } catch (Exception e) { // } } public int find (int temp) { int cursor = 0; if (temp != 0) { while(cursor != root) { if (stack[cursor] < temp) return cursor; cursor++; } } return root; } public int getValue(int index) { return stack[index]; } }
最近做了些思路上的转变,并对汉诺塔有了新的理解,回想之前的复杂汉诺塔的程序,觉得还是可以改进很多的。
package hanoi; import java.util.Stack; public class MultiHanoi { public static int count = 0; public static HanoiStack Largest(HanoiStack stackA, int locA, HanoiStack stackB, int locB, HanoiStack stackC, int locC) { if(stackA.get(locA) > stackB.get(locB) && stackA.get(locA) > stackC.get(locC)) return stackA; else if (stackB.get(locB) > stackA.get(locA) && stackB.get(locB) > stackC.get(locC)) return stackB; return stackC; } public static void multiHanoi(HanoiStack stackA, int locA,HanoiStack stackB, int locB, HanoiStack stackC, int locC) { if((stackA.size() == 0 || stackA.size() <= locA) && (stackB.size() == 0 || stackB.size() <= locB)) { return; } else if(stackA.size() == 0 || stackA.size() <= locA) { hanoi(stackB, locB, stackA, stackC); } else if(stackB.size() == 0 || stackB.size() <= locB) { hanoi(stackA, locA, stackB, stackC); } else { if(Largest(stackA, locA, stackB, locB, stackC, locC).name.equals(stackA.name)) { multiHanoi(stackA, locA + 1, stackC, locC, stackB, locB); int value = stackA.pop(); stackC.push(value); System.out.println("Step " + ++count + ": move " + value + " from " + stackA.name + " to " + stackC.name); hanoi(stackB, locB, stackA, stackC); } else if(Largest(stackA, locA, stackB, locB, stackC, locC).name.equals(stackB.name)) { multiHanoi(stackB, locB + 1, stackC, locC, stackA, locA); int value = stackB.pop(); stackC.push(value); System.out.println("Step " + ++count + ": move " + value + " from " + stackB.name + " to " + stackC.name); hanoi(stackA, locA, stackB, stackC); } else if(Largest(stackA, locA, stackB, locB, stackC, locC).name.equals(stackC.name)) { locC++; multiHanoi(stackA,locA, stackB, locB, stackC, locC); } } } public static void hanoi(HanoiStack sA, int locA, HanoiStack sB, HanoiStack sC) { if(sA.size() == locA + 1) { int value = sA.pop(); sC.push(value); System.out.println("Step "+ ++count+ ": move "+value+" from "+sA.name+" to "+sC.name); } else { int locB = sB.size(); hanoi(sA, locA + 1, sC, sB); int value = sA.pop(); sC.push(value); System.out.println("Step "+ ++count+ ": move "+value+" from "+sA.name+" to "+sC.name); hanoi(sB, locB, sA, sC); } } public static void main(String[] args) { HanoiStack stackA = new HanoiStack("A"); HanoiStack stackB = new HanoiStack("B"); HanoiStack stackC = new HanoiStack("C"); stackA.push(10); stackA.push(7); stackA.push(6); stackA.push(5); stackA.push(1); stackB.push(9); stackB.push(8); stackB.push(4); stackB.push(3); stackB.push(2); multiHanoi(stackA, 0, stackB, 0, stackC, 0); System.out.println("Overall steps: " + count); } } class HanoiStack { public String name; private Stack<Integer> stack; public HanoiStack(String name) { stack = new Stack<Integer>(); this.name = name; } public void push(int val) { stack.push(val); } public int pop() { if(stack.isEmpty()) return 0; return stack.pop(); } public int size() { return stack.size(); } public int get(int loc) { if(loc >= stack.size()) return Integer.MIN_VALUE; return stack.get(loc); } }
现在看起来比上一个程序简单明了了许多,但是其实步数是一样的,性能并没有增加。
不过基本上这已经算是最优的解法了。
发表评论
-
大数据下的实体解析
2016-07-07 12:03 671大数据时代的实体解析困境 <!--[if !sup ... -
中文相似度匹配算法
2015-12-30 14:44 1921基于音形码的中文字 ... -
各种语言写的wordcount
2015-09-24 16:07 0Java版本: String input ... -
数组双指针算法的研究
2015-07-14 16:59 2424双指针算法在数组/链 ... -
摩尔投票法
2015-06-30 20:13 18287摩尔投票法 提问: 给定一个int型数组,找出该数 ... -
(转)最长回文字串算法
2015-01-18 14:30 1404来自(http://blog.163.com/zhaohai ... -
STRUTS2 源码 - Logging System
2012-05-24 08:51 1367看了STRUTS2的源码,了解了它的logging系统,觉得还 ... -
在线词典的数据结构实现。
2012-05-18 08:37 0昨天在网上看到了一道百度的面试题: Baidu写道 ... -
存储中间计算结果的动态规划算法
2012-04-18 15:50 1183public class RodCutting { ... -
java写的四则运算器
2011-08-19 22:19 2665本打算做一个从RE到NFA的转换器,思路已经理清了,但是在动手 ... -
什么是最小二乘拟合
2007-09-14 21:27 926对于一个数据点(x1, y1), ... (xn, yn)的集 ... -
palindrome
2008-07-14 17:39 952package palindrome;/*Problem St ... -
CraneWork
2008-07-14 19:14 959/*Problem Statement There are ... -
SalesRouting
2008-07-15 10:53 744package salesRouting;/*Problem ... -
FactorialSystem
2008-07-21 19:36 824/*Problem StatementIn the facto ... -
RecurringNumbers
2008-07-22 09:41 888/*Problem StatementA rational n ... -
HardDuplicateRemover
2008-07-23 15:17 884/*Problem StatementWe have a se ... -
BlockStructure
2008-07-23 20:55 764/*Problem StatementA group of v ... -
SkipStones
2008-07-28 17:31 795/*Problem StatementWhen a stone ... -
TheaterVisit
2008-07-28 17:31 746/*Problem StatementYou want to ...
相关推荐
---汉诺塔源代码--- ---汉诺塔源代码--- ---汉诺塔源代码--- ---汉诺塔源代码--- ---汉诺塔源代码---
算法分析设计中三柱汉诺塔算法的拓展,四柱汉诺塔的设计算法代码
汉诺塔java源码汉诺塔java源码汉诺塔java源码汉诺塔java源码汉诺塔java源码汉诺塔java源码汉诺塔java源码
汉诺塔模拟程序汉诺塔模拟程序汉诺塔模拟程序汉诺塔模拟程序
简单汉诺塔游戏
这是一个关于汉诺塔的flash小游戏,适合做各种设计
汉诺塔演示程序汉诺塔演示程序汉诺塔演示程序汉诺塔演示程序汉诺塔演示程序汉诺塔演示程序汉诺塔演示程序汉诺塔演示程序汉诺塔演示程序汉诺塔演示程序
双色汉诺塔是由之前所介绍过的汉诺塔规则衍生而来。 盘子的颜色有两种
这是一个关于汉诺塔的flash小游戏,适合做各种设计
汉诺塔问题汉诺塔问题汉诺塔问题汉诺塔问题汉诺塔问题汉诺塔问题
汉诺塔C语言源代码汉诺塔C语言源代码汉诺塔C语言源代码汉诺塔C语言源代码汉诺塔C语言源代码汉诺塔C语言源代码汉诺塔C语言源代码
汉诺塔是传统的智力游戏,与华容道、魔方等类似。这是汉诺塔游戏的Python源代码,使用了基本的递归方式实现汉诺塔求解问题。 欢迎大家下载。
汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上安大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另...
汉诺塔 演示程序 二叉树 演示动画 实现动态的观看到汉诺塔的盘子移动过程,动态的观看到树的遍历过程,树的查找过程
C#汉诺塔 利用C#写的汉诺塔小游戏,游戏比较简陋,代码内容非常简单,但是相对简单,适合初学者。有疑问想学习者可加微信15290535019详细了解。
汉诺塔小游戏
汉诺塔Hannoi(java)源程序 包含汉诺塔6个类
汉诺塔源程序算法 汉诺塔源程序算法 汉诺塔源程序算法 汉诺塔源程序算法
汉诺塔课程设计报告与源码