河内塔计划 - 计数器

Question

我正在做一个河内塔计划 - 有3个挂钩和一堆挂在挂钩1上的磁盘，顺序从最大到最小（最大的在底部，最小的在顶部）。你现在要做的是将所有磁盘从挂钩1移到挂钩3，可以使用挂钩2作为其他磁盘的存储空间。到目前为止，我已经获得了正确放置磁盘的工作（每个磁盘都正确移动），现在我需要按顺序创建一个计数器变量，以显示用户输入的特定数量的磁盘需要多少移动。例如，3张光盘最少需要7次移动。

https://www.mathsisfun.com/games/towerofhanoi.html

你可以看到，我有些注释掉一些动作++，但是无论我放在柜台它似乎永远不会工作。

public class TowerOfHanoi 

    {//open class 

    public void Answer(int numOfDisks, String Peg1, String Peg2, String Peg3, int Moves) 
    {//open public void Answer 

     Moves++; 

     if (numOfDisks == 1) 
     {//open if 

      //Moves++;  
      System.out.println("\nNumber of Moves so far: " + Moves + "\nMove disk on Peg " + Peg1 + " to Peg " + Peg3); 

     }//close if 

     else 
     {//open else 

      //Moves++; 
      Answer(numOfDisks - 1, Peg1, Peg3, Peg2, Moves); 
      System.out.println("\nNumber of Moves so far: " + Moves + "\nMove disk on Peg " + Peg1 + " to Peg " + Peg3); 
      //Moves++; 
      Answer(numOfDisks - 1, Peg2, Peg1, Peg3, Moves); 

     }//close else 

    }//close public void Answer 

    public static void main (String[]args) 
    {//open main 

     TowerOfHanoi TOH = new TowerOfHanoi(); 
     String numOfDisks = JOptionPane.showInputDialog(null, "Enter a number!"); 
     int NumberOfDisks = Integer.parseInt(numOfDisks); 
     System.out.println("\nNumber of disks chosen: " + NumberOfDisks); 
     int Moves = 0; 
     TOH.Answer(NumberOfDisks, "1", "2", "3", Moves); 

    }//close main 

}//close TowerOfHanoi class 

Answer 1

增加移动每次你做每两个println语句的前面一招，即时间，因为这些代表正在作出一个举动。 接下来，您需要从Answers方法返回Move。在方法结尾处放置return Moves。当您调用该方法时，请执行Moves = Answer(numOfDisks - 1, Peg1, Peg3, Peg2, Moves);

Answer 2

您面临的一个问题是，您正在使用递归并将移动计数器推入Answer的新调用中，但不返回任何内容。移动计数器返回时将恢复其先前的值。

这可以通过引入成员变量来返回值或更好的解决方案来解决。从参数列表中删除它，并使用公共成员。然后，您可以在代码的末尾添加TOH.moves。

然后，您将获得一致的计数，并且可以在展示位置上玩耍，但它看起来是正确的，无需仔细查看代码。

Answer 3

为了将最底部的第（n'）个磁盘从p1移动到p3，首先需要将第n-1个磁盘从p1移动到p2（并清除）。然后您将p1移至p3，然后将其余的p2移至p3。

从这个文字描述中可以明显看出，你只是在“移动p1到p3”部分真的做了一个动作。这是你应该增加移动计数器的地方。

为了以紧凑的形式展示这里，这里有一个非常短的河内塔（认为这是你的Java程序的快速原型;）它还展示了如何使用函数的返回值来获得 - 这里是移动列表 - 在你的情况下，你的柜台。

let rec hanoi n p1 p2 p3 acc = 
    match n with 
    | 0 -> acc 
    | _ -> 
     hanoi (n-1) p1 p3 p2 acc 
     @ [p1,p3]     // this is where a move is added 
     @ hanoi (n-1) p2 p1 p3 acc 

hanoi 3 1 2 3 [] |> List.length 

为了使它更容易一点看，这里只计算版本：

let rec hanoi1 n p1 p2 p3 acc = 
    match n with 
    | 0 -> acc 
    | _ -> 
     hanoi1 (n-1) p1 p3 p2 acc 
     + 1     // this is where a move is added 
     + hanoi1 (n-1) p2 p1 p3 acc 

hanoi1 3 1 2 3 0 

Answer 4

我的两分钱： 你可以尝试迭代程序，所以它更容易处理的计数器。您可以take a look here，有一个基于this iterative program河内塔的可视化，这表明，解决问题的最小步数。

我知道它不是在JAVA中，但你会看到移植该程序并不难。

Answer 5

河内解决非迭代塔

import java.util.Arrays; 

public class TowerOfHanoi { 

    private static int SIZE = 5; 

    private class stack { 

     stack(int size) { 
      dataElements = new int[size]; 
     } 
     int[] dataElements; 

     int top = -1; 

     private void push(int element) { 
      dataElements[++top] = element; 
     } 

     private int pop() { 
      if(top==-1) { 
       return -1; 
      } 
      int topEle = dataElements[top]; 
      dataElements[top]=0; 
      top --; 
      return topEle; 
     } 

     private int top() { 
      if(top==-1) { 
       return -1; 
      } 
      return dataElements[top]; 
     } 

     private boolean isEmpty() { 
      return top == -1; 
     } 
    } 

    public static void main(String[] args) { 
     towerOfHanoi(SIZE); 
    } 

    private static void towerOfHanoi(int number) { 
     initialize(number); 
     if(number % 2 == 0) { 
      solveEven(number); 
     } else { 
      solveOdd(number); 
     } 
    } 

    private static int recentMoved = -1; 

    private static stack source = new TowerOfHanoi().new stack(SIZE); 
    private static stack intermediate = new TowerOfHanoi().new stack(SIZE); 
    private static stack destination = new TowerOfHanoi().new stack(SIZE); 

    private static void solveEven(int number) { 

     while(destination.top < number-1) { 
      if(!movePlates(source, intermediate, destination)) { 
       if(!movePlates(intermediate,destination,source)) { 
        if(!movePlates(destination, source, intermediate)){ 
         continue; 
        } 
       } 
      } 
     } 

    } 



    private static boolean movePlates(stack from , stack dest1 ,stack dest2) { 
     boolean movedPlate = false; 
     if(from.top()== recentMoved) { 
      return movedPlate; 
     } 
     if((!from.isEmpty()) && from.top()<(dest1.top()==-1?10000:dest1.top())) { 
      dest1.push(from.pop()); 
      recentMoved=dest1.top(); 
      movedPlate = true; 
     } 
     else if((!from.isEmpty()) && from.top()<(dest2.top()==-1?10000:dest2.top())){ 
      dest2.push(from.pop()); 
      recentMoved=dest2.top(); 
      movedPlate = true; 
     } 
     if(movedPlate) 
      display(); 
     return movedPlate; 
    } 

    private static void display() { 
     Arrays.stream(source.dataElements).forEach(System.out::print); 
     //.stream().fl.forEach(System.out::print); 
     System.out.print("\t"); 
     Arrays.stream(intermediate.dataElements).forEach(System.out::print); 
     System.out.print("\t"); 
     Arrays.stream(destination.dataElements).forEach(System.out::print); 
     System.out.print("\n"); 
    } 


    private static void initialize(int number) { 
     for(int i=number;i>0;i--) { 
      source.push(i); 
     } 
    } 

    private static void solveOdd(int number) { 
     while(destination.top < number-1) { 
      if(!movePlates(source, destination, intermediate)) { 
       if(!movePlates(destination,intermediate,source)) { 
        if(!movePlates(intermediate, source, destination)){ 
         continue; 
        } 
       } 
      } 
     } 

    } 

}