河內塔計劃 - 計數器

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; 
        } 
       } 
      } 
     } 

    } 

}