带有堆栈实现和递归的河内塔 (Java)

Question

我正在尝试通过递归解决汉诺塔问题，同时使用堆栈。输出应如下所示，使用 n # 个大小递增的磁盘。磁盘必须从 Pillar1 移动到 Pillar3，一次一个：

// assuming n = 3;

Pillar1: 3 2 1

Pillar2:

Pillar3: 

// "\n"

Pillar1: 3 2 

Pillar2:

Pillar3: 1

// "\n"

Pillar1: 3 

Pillar2: 2

Pillar3: 1


// "\n"

Pillar1: 3 

Pillar2: 2 1

Pillar3: 


// "\n"

Pillar1: 

Pillar2: 2 1

Pillar3: 3


// "\n"

Pillar1: 1

Pillar2: 2

Pillar3: 3

// "\n"

Pillar1: 1

Pillar2: 

Pillar3: 3 2


// "\n"

Pillar1: 

Pillar2: 

Pillar3: 3 2 1

我的代码在下面，我很难处理磁盘 > 1 的输出：

import java.util.*;
class TowersOfHanoiThree
{
   public static Stack<Integer>[] tower = new Stack[4];
   public static int temp;

   public static void TowersOfHanoiThree(int numDisk)
   {
      //adding disk to stack
      temp = numDisk;
      tower = new Stack[4];

      for(int a = 0; a <= 3; a++)
      {
         tower[a] = new Stack<Integer>();
      }

     for (int i = numDisk; i > 0; i--)
     {
        tower[1].push(numDisk);
        show();
     }
     solver(numDisk, 1, 3, 2);
 }

public static void show()
{
   //System.out.println("Pillar1: ");
   //System.out.println("Pillar2: ");
   //System.out.println("Pillar3: ");

   String Pillar1 = "Pillar1: ";
   String Pillar2 = "Pillar2: ";
   String Pillar3 = "Pillar3: ";

   for(int x = temp -1 ; x >= 0 ; x--)
   {
      String emptStr1 = "";
      String emptStr2 = "";
      String emptStr3 = "";

     try
     {
        emptStr1 = String.valueOf(tower[1].get(x));
     }
     catch(Exception e)
     {
     }

     try
     {
        emptStr2 = String.valueOf(tower[2].get(x));
     }
     catch(Exception e)
     {
     }

     try
     {
        emptStr3 = String.valueOf(tower[3].get(x));
     }
     catch(Exception e)
     {
     }
     System.out.print(Pillar1+emptStr1+"\n");
     System.out.print(Pillar2+emptStr2+"\n");
     System.out.print(Pillar3+emptStr3+"\n");
     System.out.print("\n");
  }
}//end show

public static void solver(int numDisk, int start, int middle, int end) 
{
   if(numDisk > 0) 
   {
      try
      {
         //sorting disks
         solver(numDisk - 1, start, end, middle);
         int dis = tower[start].pop(); //move disk top-most disk of start
         tower[middle].push(dis);
         show();
         solver(numDisk - 1, middle, start, end);
      }
      catch(Exception e)
      {
      }
   }
}

public static void main(String args[])
{
    tower[1] = new Stack<Integer>();
    tower[2] = new Stack<Integer>();
    tower[3] = new Stack<Integer>();

    TowersOfHanoiThree(2);
}
}

Answer 1

使用以下实现应该会为您提供所需的结果。我还放置了一些内联评论和所做的修改

public static void TowersOfHanoiThree(int numDisk)
{
  //adding disk to stack
  temp = numDisk;
  tower = new Stack[4];

  for(int a = 0; a <= 3; a++)
  {
     tower[a] = new Stack<Integer>();
  }

 for (int i = numDisk; i > 0; i--)
 {
    tower[1].push(i); // to show "1 2 3" i changed the value which was pushed in the stack
// from tower[1].push(numDisk) to tower[1].push(i)
 }
 show(); //In your example this method call was placed inside the for loop.
//Moving it outside will show the stacks only after the values are added
 solver(numDisk, 1, 3, 2);
}

 public static void show() {
    // System.out.println("Pillar1: ");
    // System.out.println("Pillar2: ");
    // System.out.println("Pillar3: ");

    String Pillar1 = "Pillar1: ";
    String Pillar2 = "Pillar2: ";
    String Pillar3 = "Pillar3: ";

    String emptStr1 = "";
    String emptStr2 = "";
    String emptStr3 = "";
//the empStr variable are moved outside the loop because only after the 
//loop has finished we know what values are in each pillar
    for (int x = 0; x <= temp - 1; x++) {

        try {
//here we just append the values from the pillar to string empStr1
            emptStr1 += String.valueOf(tower[1].get(x)) + " ";
        } catch (Exception e) {
        }

        try {
            emptStr2 += String.valueOf(tower[2].get(x)) + " ";
        } catch (Exception e) {
        }

        try {
            emptStr3 += String.valueOf(tower[3].get(x)) + " ";
        } catch (Exception e) {
        }
    }
//finally when the loop is done we have the results
    System.out.print(Pillar1 + emptStr1 + "\n");
    System.out.print(Pillar2 + emptStr2 + "\n");
    System.out.print(Pillar3 + emptStr3 + "\n");
    System.out.print("\n");
}// end show

Answer 2

您需要解决一些问题。我会尽力解释它们并提供可能的解决方案。

首先，您总是在 TowersOfHanoiThree(int) 方法中将 numDisks 压入初始堆栈（支柱）。违规部分：

for (int i = numDisk; i > 0; i--) {
   tower[1].push(numDisk); // should be tower[1].push(i);
   show();
}

修复：

for (int i = numDisk; i > 0; i--) {
   tower[1].push(i); // fixed
   show();
}

其次，您的show()方法不正确，原因有很多：

您应该从索引 0 而不是最后一个索引 (temp - 1) 开始遍历数组 tower 中的每个堆栈，因为您希望从底部到顶部显示磁盘顶.
您应该在 for 循环之前声明您的字符串 emptStr1、emptStr2、emptStr3。目前，您在每次迭代时将它们重置为空字符串。
您需要将磁盘连接到字符串 emptStr1、emptStr2、emptStr3，而不是通过重新分配来覆盖它们。
您应该在 for 循环后输出字符串 emptStr1、emptStr2、emptStr3。

我建议完全重写 show()，例如：

public static void show() {
    for (int i = 1; i < tower.length; i++) { // iterate over your array of stacks
        String pillar = "Pillar " + i + ":"; // e.g. "Pillar 1: "
        for (int disk : tower[i]) { // iterate over the stack located at index i
            pillar += " " + disk; // concatenate the current disk to the String
        }
        System.out.println(pillar); // Display this pillar
    }
    System.out.println(); // Line break to seperate the show() calls
}

最后，solver(int, int, int, int)中的第二次递归调用不正确

违规行：

solver(numDisk - 1, middle, start, end);

这应该改为：

solver(numDisk - 1, end, middle, start);

此外，虽然不是失败的原因，但您的数组 tower 的容量为 4，但它应该是 3。您当前忽略索引 0 .我认为你是故意这样做的，因为你想将柱子显示为 1、2 和 3？无论如何，这可能会造成混淆。相反，当您显示支柱信息时，只需在索引中加 1。

带有堆栈实现和递归的河内塔 (Java)

Towers Of Hanoi with Stacks Implementation and Recursion (Java)

java

algorithm

recursion

stack

towers-of-hanoi