使用递归移动河内塔顶圆盘 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;
}
}

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

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 语句试图在应该使用 towerThree 和 discThree 时访问 towerTwo，所以我将其更改为：

    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 我唯一的建议是要小心 copy/pasting，注意你是否使用了零索引，你应该再看看你的算法，看看它是否实际上可以解决这个难题。我自己没有写任何东西来做河内拼图，所以我不熟悉如何在代码中实现它。我确实看到你有这个想法。也就是说，要解决 n 个圆盘的难题，您首先必须解决 n-1 个圆盘。祝你接下来的工作顺利！

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

Moving Top Disc Tower Of Hanoi Using Recursion Java

java

recursion

puzzle