chapter18n4.java

JAVA源代码程序aashjkjhkjhkjhjkhkj

/**
 * an iterative solution to the Towers of Hanoi
 */

import java.lancs.* ;

class PegException extends Exception
    {
    public PegException() {}
    }

class Peg
    {
    private static final int MAX_NO_DISKS = 100 ;

    private String name ;
    private int[] disks = new int[MAX_NO_DISKS] ;
    private int noDisks ;

    public Peg successor ;

    public Peg(String n)
	{
	name = n ;
	noDisks = 0 ;
	} // end of constructor method

    public String toString()
	{
	return name ;
	} // end of method toString

    public int remove() throws PegException
	{
	if (noDisks == 0)
	    throw new PegException() ;
	int temp = disks[noDisks - 1] ;
	noDisks-- ;
	return temp ;
	} // end of method remove

    public void add(int d)
	{
	disks[noDisks] = d ;
	noDisks++ ;
	} // end of method add

    public int top()
	{
	if (noDisks == 0)
	    return  MAX_NO_DISKS + 1 ;
	return disks[noDisks - 1] ;
	} // end of method top

    public int noOfDisks()
	{
	return noDisks ;
	} // end of method noOfDisks
    } // end of class Peg

public class Chapter18n4
    {
    static int noMoves ;

    public static void main(String[] args) throws Exception
	{
	Peg pegA = new Peg("A"),
	    pegB = new Peg("B"),
	    pegC = new Peg("C") ;

	BasicIo.prompt("number of disks? ") ;
	int n = BasicIo.readInteger() ;
	for (int i = 0 ; i < n ; i++)
	    pegA.add(n - i) ;

	noMoves = 0 ;
	hanoi(n, pegA, pegB, pegC) ;
	System.out.println("\nno of moves for " + n + " disks is " + noMoves) ;
	} // end of main method

    public static void moveDisk(Peg fromPeg, Peg toPeg)
        {
	try {
	    int d = fromPeg.remove() ;
	    toPeg.add(d) ;
	    System.out.println("Move disk " + d + " from " + fromPeg +
							" to " + toPeg) ;
	    noMoves++ ;
	    }
	catch(PegException e)
	    {
	    System.out.println("major peg problem") ;
	    System.exit(1) ;
	    }
	} // end of method moveDisk

    public static void hanoi(int n, Peg fromPeg, Peg toPeg, Peg helpPeg)
	{
	if (n % 2 == 1)
	    {
	    fromPeg.successor = toPeg ;
	    toPeg.successor = helpPeg ;
	    helpPeg.successor = fromPeg ;
	    }
	else
	    {
	    fromPeg.successor = helpPeg ;
	    helpPeg.successor = toPeg ;
	    toPeg.successor = fromPeg ;
	    }

	while (true)
	    {
	    Peg smallest = fromPeg ;
	    if (toPeg.top() < smallest.top())
		smallest = toPeg ;
	    if (helpPeg.top() < smallest.top())
		smallest = helpPeg ;
	    Peg newSmallest = smallest.successor ;
	    Peg otherPeg = newSmallest.successor ;

	    moveDisk(smallest, newSmallest) ;
	    if (toPeg.noOfDisks() == n)
		break ;
	    if (smallest.top() < otherPeg.top())
		moveDisk(smallest, otherPeg) ;
	    else
		moveDisk(otherPeg, smallest) ;
	    }
	} // end of method hanoi

    } // end of class Chapter18n4