Java开发网 - 向高手请教一个汉诺塔的问题

Topic: 向高手请教一个汉诺塔的问题

1.向高手请教一个汉诺塔的问题

Posted by: lucent6688
Posted on: 2005-04-17 22:56

被这个汉诺塔的源程序搞得头痛，好心的高手能告诉我如何理解这个汉诺塔吗
能告诉我其中的规律性吗? 小弟在此先谢了!
// Lab 3: TowersOfHanoi.java
// Program solves the Towers of Hanoi problem
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

public class TowersOfHanoi extends JApplet implements ActionListener {
JLabel label;
JTextField input;
JTextArea outputArea;
String output;

public void init()
{
output = "";

// create components
label = new JLabel( "Enter number of disks ( 1-9 ): " );
input = new JTextField( 5 );
input.addActionListener( this );
outputArea = new JTextArea( 15, 20 );
/* Write code that creates a JScrollPane and attach outputArea to it */
// outputArea.setText( output );
JScrollPane scroll = new JScrollPane(outputArea);

// add components to applet
Container container = getContentPane();
container.setLayout( new FlowLayout() );
/* Write code to add the components to the content pane */
input.addActionListener(this);

container.add(label);
container.add(input);
container.add(scroll);

}

// recusively move disks through towers
/* write header for method tower */
String tower(int n,String peg1,String peg2,String peg3)
{
/* Write code here that tests for the base case (i.e., one disk).
In this case, move the last disk from peg 1 to peg 3 and return. */

if(n==1)
return output+="\n"+peg1+"--->"+peg3;

// move ( disks - 1 ) disks from peg1 to peg2 recursively
/* Write a recursive call to method tower that moves
( disks - 1 ) disks from peg1 to peg2 */
else
{
tower(n-1,peg1,peg3,peg2);

// move last disk from peg1 to peg3 recursively
output += "\n" + peg1 + " --> " + peg3;

// move ( disks - 1 ) disks from peg2 to peg3 recursively
/* Write a recursive call to method tower that moves
( disks - 1 ) disks from peg2 to peg3 */
tower(n-1,peg2,peg1,peg3);
return output;

}
}

// actually sort the number of discs specified by user
public void actionPerformed( ActionEvent e )
{
output = "";

/* call method tower and pass it the number input by the user,
a starting peg of 1, an ending peg of 3 and a temporary peg of 2 */
int n=Integer.parseInt(input.getText());
String peg1="1";
String peg2="2";
String peg3="3";
output+=tower(n,peg1,peg2,peg3);

outputArea.setText( output );
}

} // end class TowersOfHanoi
当n=2时，监听器内调用tower(n,peg1,peg2,peg3)方法，当运行至tower(n-1,peg1,peg3,peg2)时，也就是tower(1,peg1,peg3,peg2);再次调用自身方法，这时就运行if(n==1)
return output+="\n"+peg1+"--->"+peg3;
也就是返回output=1-->2给调用者，程序也就结束了，可实际的答案是　１－－＞２，１－－＞３，
２－－＞３　应如何理解？各位大侠能帮个忙吗？

2.Re:向高手请教一个汉诺塔的问题 [Re: lucent6688]

Copy to clipboard

Posted by: Yach
Posted on: 2005-04-19 23:20

递归调用。其实汉诺塔的原理很简单。就是先想办法将n-1个盘移到第二个柱子。然后将第n个盘子移到第三个柱子上，然后下边的就是将剩下的n-1个盘子看成n-1个盘子的汉诺他在进行处理，这样递归下去。到最后所有的盘子都移动到第三个柱子上了。：）原理就是这个。你再好好看看，理解理解