求programming 高手！关于Tower of hanoi

辣椒_小咖喱 · 发表于 20-8-2011 09:58 PM

本帖最后由辣椒_小咖喱于 23-11-2011 01:04 PM 编辑

我这里有tower of hanoi 的sample，但是我需要用linked stack 来完成

Tower.java
----------------------------------------------------------------------------------------------------

import java.util.Scanner;
public class Tower{
int count=0;
public void solveTower(int disks, int source, int destination, int temp){
++count;
if(disks==1){
System.out.printf("\n%d --> %d", source, destination);
return;
}
solveTower(disks-1, source, temp, destination);
System.out.printf("\n%d --> %d", source, destination);
solveTower(disks-1, temp, destination, source);
}
public static void main(String[]args){
System.out.println("Enter disks");
int disks = new Scanner(System.in).nextInt();
Tower t = new Tower();
t.solveTower(disks, 1,3,2);
System.out.println("\n"+t.count);
}
}

复制代码

------------------------------------------------------------------------------------------------------

这是linked stack 的interface

public interface Stack<E> {
/** Reinitialize the stack. */
public void clear();
/** Push an element onto the top of the stack.
@param it Element being pushed onto the stack.*/
public void push(E it);
/** Remove and return top element.
@return The element at the top of the stack.*/
public E pop();
/** @return A copy of the top element. */
public E topValue();
/** @return Number of elements in the stack. */
public int length();
};

复制代码

-------------------------------------------------------------------------------

class LStack<E> implements Stack<E> {
private Link<E> top;
private int size;
class Link<E> {
private E element;
private Link<E> next;
// Constructors
Link(E it, Link<E> nextval)
{ element = it; next = nextval; }
Link(Link<E> nextval) { next = nextval; }
Link<E> next() { return next; }
Link<E> setNext(Link<E> nextval)
{ return next = nextval; }
E element() { return element; }
E setElement(E it) { return element = it; }
}
public LStack() { top = null; size = 0; }
public LStack(int size) { top = null; size = 0;}
public int length() { return size; }
public void clear() { top = null; size = 0; }
/** @return Top value */
public E topValue() {
assert top != null : "Stack is empty";
return top.element();
}
/** Put "it" on stack */
public void push(E it) {
top = new Link<E>(it, top);
size++;
}
/** Remove "it" from stack */
public E pop() {
assert top != null : "Stack is empty";
E it = top.element();
top = top.next();
size--;
return it;
}
public static void main(String[] args)
{
}
}

复制代码

-------------------------------------------------------------------------------------
我要怎样把Tower.java用linked stack的方法来完成？

zblue89 · 发表于 23-8-2011 03:25 PM

我觉得概念上还是一样（如果你的solveTower是对的话）。。。
有点久没写java了，可能有点syntax error。。。

import java.util.Scanner;
public class Tower{
int count=0;
public void solveTower(int disks, LStack<int> source, LStack<int> destination, LStack<int> temp){
++count;
if(disks==1){
System.out.printf("\n%d --> %d", source, destination);
destination.push(source.pop());
return;
}
solveTower(disks-1, source, temp, destination);
System.out.printf("\n%d --> %d", source, destination);
destination.push(source.pop());
solveTower(disks-1, temp, destination, source);
}
public static void main(String[]args){
System.out.println("Enter disks");
int disks = new Scanner(System.in).nextInt();
Tower t = new Tower();
LStack<int> src = new LStack<int>();
LStack<int> dest = new LStack<int>();
LStack<int> tmp = new LStack<int>();
for(int i=1;i<=disks;i++){
src.push(i);
}
t.solveTower(disks, src,dest,tmp);
System.out.println("\n"+t.count);
}
}

复制代码

辣椒_小咖喱 · 发表于 3-9-2011 09:48 PM

本帖最后由辣椒_小咖喱于 3-9-2011 09:51 PM 编辑

你的用不到><
这是我另外做的以下。。。。

import java.util.Scanner;
public class tower{
private LStack<Integer> PoleA = new LStack<Integer>();
private LStack<Integer> PoleB = new LStack<Integer>();
private LStack<Integer> PoleC = new LStack<Integer>();
private int disk = 0;
private int numberOfMoves = 0;
public tower(){
}
public tower(int disk){
this.disk=disk;
init();
}
private void init(){
for(int i=disk;i>=1;i--)
PoleA.push(i); //i is the size of the disc
}
private void move(LStack<Integer> from, LStack<Integer> to){
to.push(from.pop());
//System.out.printf("\n%d --> %d", to.topValue(), from.topValue());
numberOfMoves++;
}
private void legalMove(LStack<Integer> PoleA, LStack<Integer> PoleB){
if(PoleC.length()==disk)
return; //skip if already completed toh
if(PoleB.length() == 0)
move(PoleA,PoleB);
else if(PoleA.length()==0 || PoleA.topValue() > PoleB.topValue())
move(PoleB,PoleA);
else
move(PoleA,PoleB);
}
private void solve(){
while(PoleC.length()!=disk)
if(disk%2==0) { //even number
legalMove(PoleA,PoleB);
legalMove(PoleA,PoleC);
legalMove(PoleB,PoleC);
} else {
legalMove(PoleA,PoleC);
legalMove(PoleA,PoleB);
legalMove(PoleB,PoleC);
}
}
public void solveTower(int disk, int source, int destination, int temp){
if(disk==1){
//destination.push(source.pop());
System.out.printf("\n%d --> %d", source, destination);
return;
}
solveTower(disk-1, source, temp, destination);
//System.out.println("\ndone 1");
System.out.printf("\n%d --> %d", source, destination);
//System.out.println("\ndone 2");
solveTower(disk-1, temp, destination, source);
//System.out.println("\ndone 3");
}
public static void main(String[] args){
tower game = new tower();
do{
try{
System.out.print("Enter disks:");
game = new tower(new Scanner(System.in).nextInt());
if(game.disk<1)
throw new Exception();
break;
}catch(Exception e){
System.out.println("Invalid value entered! Try again!");
}
}while(true);
game.solveTower(game.disk,1,2,3);
long t1 = System.nanoTime();
game.solve();
long t2 = System.nanoTime();
System.out.println("\nTotal number of moves:\t"+game.numberOfMoves);
System.out.println("Execution time:\t"+((t2-t1)*1e-6)+"ms");
}
}

复制代码

fyhao · 发表于 6-11-2011 01:00 PM

可以参考这个使用 JavaScript 设计的 Tower of Hanoi 问题。
http://fyhao.com/lab/math/hanoi/

algorithm · 发表于 6-11-2011 11:36 PM

本帖最后由 algorithm 于 6-11-2011 11:38 PM 编辑

以下是我根据你的Tower.java用java.util.stack改成的TowerStack.java。见笑见笑

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
public class TowerStack
{
static int movecount = 0;
static Stack stackA = new Stack();
static Stack stackB = new Stack();
static Stack stackC = new Stack();
public static void solve(int nDiscs, Stack source, Stack dest, Stack temp){
if(nDiscs <= 0){
return;
}
solve(nDiscs-1, source, temp, dest);
dest.push(source.pop());
movecount++;
printStacks();
solve(nDiscs-1, temp, dest, source);
}
public static void printStacks(){
System.out.println();
printStack(stackA);
System.out.print(" , ");
printStack(stackB);
System.out.print(" , ");
printStack(stackC);
}
public static void printStack(Stack s)
{
System.out.print(s.toString());
}
public static void main(String[] args)
{
try
{
while (true)
{
movecount = 0;
System.out.print("\nEnter the number of discs (-1 to exit): ");
int discCount = 0;
String inputString = "";
InputStreamReader input = new InputStreamReader(System.in);
BufferedReader reader = new BufferedReader(input);
inputString = reader.readLine();
discCount = Integer.parseInt(inputString);
if (discCount == -1)
{
System.out.println("System Exit!");
System.exit(0);
return;
}
for (int i = discCount; i >= 1; i--)
stackA.push(i);
printStacks();
solve(discCount, stackA, stackC, stackB);
System.out.println("Total Moves = " + movecount);
stackC.clear();
}
}
catch (Exception e)
{
e.printStackTrace();
System.exit(0);
}
}
}

复制代码

		自动登录	找回密码
密码			注册

求programming 高手！关于Tower of hanoi

所属分类: 电脑手机