ハノータの変種
1.3本の柱があり、1本の柱にn枚の円盤を下から上へ大きさ順に積み重ねている.円盤を下から大きさ順に別の柱に並べ直すように要求します.また、小円盤では円盤を拡大することができず、3本の柱の間で一度に1つの円盤しか移動できないことが規定されている.
2.4本の柱があり、1本の柱に下から上へ大きさ順にn枚の円盤を積み重ねている.円盤を下から大きさ順に別の柱に並べ直すように要求します.また、小円盤では円盤を拡大することができず、4本の柱の間で一度に1つの円盤しか移動できないことが規定されている.
3.3本の柱があり、1本の柱に下から上へm枚の円盤を大小順に重ね、もう1本の柱に下から上へn枚の円盤を大小順に重ね、円盤を下から最後の柱に大きさ順に並べ直すように要求している.また、小円盤では円盤を拡大することができず、3本の柱の間で一度に1つの円盤しか移動できないことが規定されている.
4.3本の柱があり、3本の柱の上に下から上へ大きさ順にm,n,l枚の円盤がそれぞれ積み重ねられており、円盤を下から最後の柱に大きさ順に並べ直すように要求されている.また、小円盤では円盤を拡大することができず、3本の柱の間で一度に1つの円盤しか移動できないことが規定されている.
最后の2つの问题は2つ并んで1つ书いて、あまりに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.4本の柱があり、1本の柱に下から上へ大きさ順にn枚の円盤を積み重ねている.円盤を下から大きさ順に別の柱に並べ直すように要求します.また、小円盤では円盤を拡大することができず、4本の柱の間で一度に1つの円盤しか移動できないことが規定されている.
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.3本の柱があり、1本の柱に下から上へm枚の円盤を大小順に重ね、もう1本の柱に下から上へn枚の円盤を大小順に重ね、円盤を下から最後の柱に大きさ順に並べ直すように要求している.また、小円盤では円盤を拡大することができず、3本の柱の間で一度に1つの円盤しか移動できないことが規定されている.
4.3本の柱があり、3本の柱の上に下から上へ大きさ順にm,n,l枚の円盤がそれぞれ積み重ねられており、円盤を下から最後の柱に大きさ順に並べ直すように要求されている.また、小円盤では円盤を拡大することができず、3本の柱の間で一度に1つの円盤しか移動できないことが規定されている.
最后の2つの问题は2つ并んで1つ书いて、あまりに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("
" + cursor1.weight + " " + cursor2.weight + " " + cursor3.weight);
System.out.println("
");
}
}
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);
}
}今では前のプログラムよりずっと簡単に明らかになったように見えますが、実際にはステップ数は同じで、性能は増加していません.
しかし、基本的にはこれが最良の解法です.