java - 使用递归 Java 移动河内顶部圆盘塔

Question

每当我的程序尝试解决汉诺塔难题时，我都会遇到这个奇怪的问题。每当它试图解决这个问题时，它都会将前两个圆盘移至终点极(极点一直向右)，但会将其余的圆盘移回起始极。例如，如果我有一个包含 10 个圆盘的汉诺塔，它会将前几个圆盘从起始杆移动，但只有最上面的 2 个才能到达终点杆。其余的圆盘最终回到第一个杆上。当它这样做时，它会给我一个索引越界错误。我不确定它出了什么问题，任何帮助将不胜感激。提前致谢。

public class TowerOfHanoi
{
private int[] towerOne;
  private int[] towerTwo;
  private int[] towerThree;
  private int discOne;
  private int discTwo;
  private int discThree;    

/* Construct the Towers of Hanoi (3 towers) with aNumDisc
 * on the first tower. Each tower can be identified by an
 * integer number (0 for the first tower, 1 for the second
 * tower, and 2 for the third tower). Each disc can be identified
 * by an integer number starting from 0 (for the smallest disc)
 * and (aNumDisc - 1) for the largest disc.
 */
public TowerOfHanoi(int aNumDiscs)
{
    towerOne = new int[aNumDiscs];
        for(int i = 0; i < aNumDiscs; i++){
            towerOne[i] = aNumDiscs - 1 - i;
        }
        towerTwo = new int[aNumDiscs];
        towerTwo[0] = aNumDiscs;
        towerThree = new int[aNumDiscs];
        towerThree[0] = aNumDiscs;
        discOne = aNumDiscs;
        discTwo = 0;
        discThree = 0;  
}

/* Returns an array of integer representing the order of
 * discs on the tower (from bottom up). The bottom disc should
 * be the first element in the array and the top disc should be
 * the last element of the array. The size of the array MUST
 * be the number of discs on the tower. For example, suppose
 * the tower 0 contains the following discs 0,1,4,6,7,8 (from top
 * to bottom). This method should return the array [8,7,6,4,1,0]
 * (from first to last). 
 * @param tower the integer identify the tower number.
 * @return an array of integer representing the order of discs.
 */
public int[] getArrayOfDiscs(int tower)
{
    int[] tempTower;
        if(tower == 0){
            tempTower = new int[discOne];
             for(int i = 0; i < discOne; i++){
                    tempTower[i] = towerOne[i];
             }
             return tempTower;
        }
        if(tower == 1){
            tempTower = new int[discTwo];
            for(int i = 0; i < discTwo; i++){
                tempTower[i] = towerTwo[i];
            }
            return tempTower;    
        }
        if(tower == 2){
            tempTower = new int[discThree];
             for(int i = 0; i < discThree; i++){
                    tempTower[i] = towerThree[i];
             }
             return tempTower;
        }
        return towerOne;    
}

/* Gets the total number of discs in this Towers of Hanoi
 * @return the total number of discs in this Towers of Hanoi
 */
public int getNumberOfDiscs()
{
    return discOne+discTwo+discThree; 
}

/* Gets the number of discs on a tower.
 * @param tower the tower identifier (0, 1, or 2)
 * @return the number of discs on the tower.
 */
public int getNumberOfDiscs(int tower)
{
    if(tower == 0){
            return discOne;
        }
        if(tower == 1){
             return discTwo;
        }
        if(tower == 2){
             return discThree;
        }
        return 0;
}

/* Moves the top disc from fromTower to toTower. Note that
 * this operation has to follow the rule of the Tower of Hanoi
 * puzzle. First fromTower must have at least one disc and second
 * the top disc of toTower must not be smaller than the top disc
 * of the fromTower.
 * @param fromTower the source tower
 * @param toTower the destination tower
 * @return true if successfully move the top disc from
 *         fromTower to toTower.
 */
public boolean moveTopDisc(int fromTower, int toTower)
{
        if((fromTower == 0 && discOne == 0)||(fromTower == 1 && discTwo == 0) || (fromTower == 2 && discThree == 0)){
                return false;
            }
            if(fromTower == 0){
                if(toTower == 1){
                        if(discTwo != 0&&towerOne[discOne-1]>towerTwo[discTwo-1]){
                        return false;
                    }
                    else{
                        towerTwo[discTwo]=towerOne[discOne-1];
                        towerOne[discOne-1] = 0;
                        discOne--;
                        discTwo++;
                        return true;
                    }
                }
                if(toTower == 2){
                    if(discThree != 0&&towerOne[discOne-1] > towerThree[discThree-1]){
                        return false;
                    }
                    else{
                        towerThree[discThree] = towerOne[discOne-1];
                        towerOne[discOne-1] = 0;
                        discOne--;
                        discThree++;
                        return true;
                    }
                    }
                }
            if(fromTower == 1){
                if(toTower == 0){
                    if(discOne != 0&&towerTwo[discTwo-1]>towerOne[discOne-1]){
                        return false;
                    }
                    else{
                        towerOne[discOne]=towerTwo[discTwo-1];
                        towerTwo[discTwo-1] = 0;
                        discTwo--;
                        discOne++;
                        return true;
                    }
                }
                    if(toTower == 2){
                    if(discThree!= 0&&towerTwo[discTwo-1] > towerThree[discThree-1]){
                        return false;
                    }
                    else{
                        towerThree[discThree] = towerTwo[discTwo-1];
                        towerTwo[discTwo-1] = 0;
                        discTwo--;
                        discThree++;
                        return true;
                    }
                    }

                }

            if(fromTower == 2){
                if(toTower == 0){
                    if(discOne !=0 && towerOne[discOne-1]>towerTwo[discTwo-1]){
                        return false;
                    }
                    else{
                        towerOne[discOne]=towerThree[discThree-1];
                        towerThree[discThree-1] = 0;
                        discThree--;
                        discOne++;
                        return true;
                    }
                }
                if(toTower == 1){
                    if(discThree !=0&&towerThree[discThree-1] > towerTwo[discTwo-1]){
                        return false;
                    }
                    else{
                        towerTwo[discTwo] = towerThree[discThree-1];
                        towerThree[discThree-1] = 0;
                        discThree--;
                        discTwo++;
                        return true;
                    }
                    }
                }

                return false;
}
}

这是我用来运行上面的程序的类。

import javax.swing.JFrame;

public class THSolverFrame
{
public static void main(String[] args) throws InterruptedException
{
    int numberOfDiscs = 10;
    TowerOfHanoi towers = new TowerOfHanoi(numberOfDiscs);
    THComponent thc = new THComponent(towers);


    JFrame frame = new JFrame();
    frame.setTitle("Tower of Hanoi");
    frame.setSize(500,500);
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

    frame.add(thc);

    frame.setVisible(true);

    Thread.sleep(5000);

    solveTower(towers, thc, numberOfDiscs, 0, 1, 2);

    System.out.println("DONE!!!");
}

public static void solveTower(TowerOfHanoi towers, THComponent thc, int numberOfDiscs, int startPole, int tempPole, int endPole) throws InterruptedException
{
    if(numberOfDiscs == 1) {
        towers.moveTopDisc(startPole, endPole);
        thc.repaint();
        Thread.sleep(100);
    }

    else {
        solveTower(towers, thc, numberOfDiscs - 1, startPole, endPole, tempPole);
        towers.moveTopDisc(startPole, endPole);
        thc.repaint();
        Thread.sleep(100);
        solveTower(towers, thc, numberOfDiscs - 1, tempPole, startPole, endPole);

    }
}
}

Answer 1

我在您的 moveTopDisk() 方法中将其追踪到两行。第一个是这样的:

if(fromTower == 2){
            if(toTower == 0){
                if(discOne !=0 && towerOne[discOne-1]>towerTwo[discTwo-1]){ <---- HERE

这里的第三个 If 语句试图访问 towerTwo，而它应该使用 towerThree 和 DiscThree，所以我将其更改为:

    if (fromTower == 2) {
        if (toTower == 0) {
            if (discOne != 0 && towerOne[discOne - 1] > towerThree[discThree - 1]) {

和以前一样，代码试图从塔上拉出一张没有任何光盘的光盘并导致错误。再次运行后，我在同一区域发现了另一个这样的拼写错误。 :

if(toTower == 1){
                if(discThree !=0&&towerThree[discThree-1] > towerTwo[discTwo-1]){

第二个 If 语句的目标是discThree，而它应该使用discTwo。

if(toTower == 1){
                if(discTwo !=0&&towerThree[discThree-1] > towerTwo[discTwo-1]){

进行这些更改后，代码可以正常运行，没有错误。之后我遇到的唯一问题是它无法解决这个难题!该算法无法解决任何超过 3 个圆盘的难题。我用 3、4、5 和 10 尝试过，但只解决了 3 个问题。使用 4 和 5 时，程序停止了，但不是处于获胜配置，当我用 10 尝试时，它只能洗牌前 3 个光盘，从未得出解决方案(以防万一，我让它运行了整整 5 分钟)。

TL;DR 我唯一的建议是小心复制/粘贴，注意您是否使用零索引，并且您应该再次检查您的算法，看看它是否真的可以解决这个难题。我自己没有写过任何关于河内谜题的东西，所以我不熟悉如何在代码中实现它。我确实看到你有这个想法。也就是说，要解决 n 个圆盘的难题，您首先必须解决 n-1 个圆盘的难题。祝你接下来的工作一切顺利!