java - 汉诺塔的堆栈实现和递归 (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