Башни Ханойской программы - счетчик

Question

Я делаю программу Tower of Hanoi - есть 3 штифта и стопка дисков на колышке 1 в порядке наибольшего размера к самому маленькому (наибольший на дне, самый маленький сверху). Теперь вам нужно переместить все диски с привязки 1 на привязку 3, вы можете использовать привязку 2 в качестве места для хранения других дисков. До сих пор я получил правильное размещение дисков для работы (каждый диск перемещается правильно), теперь мне нужно создать переменную счетчика, чтобы показать, сколько ходов потребовалось для определенного количества дисков, введенных пользователем. Например, 3 диска занимают минимум 7 ходов.

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

Вы можете видеть, что я какой-то прокомментировал некоторые Moves ++, но везде, где я размещаю счетчик никогда не похоже на работу.

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 заявлений, поскольку те представляют собой один шаг делается. Далее вам нужно вернуть Moves from your Answers. Место return Moves в конце метода. И когда вы вызываете метод do Moves = Answer(numOfDisks - 1, Peg1, Peg3, Peg2, Moves);

Answer 2

Одна проблема, с которой вы сталкиваетесь, заключается в том, что вы используете рекурсию и нажимаете счетчик движения в новый вызов Answer, не возвращая ничего. При возврате счетчика перемещений будет восстановлено его предыдущее значение.

Это можно решить, вернув значение или лучшее решение с моей точки зрения, введя переменную-член. Удалите его из списка параметров и используйте открытый элемент. Затем вы можете добавить TOH.moves в конце вашего кода.

После этого вы получите согласованное количество очков и сможете поиграть с местом размещения, но оно кажется правильным, не присмотревшись к вашему коду.

Answer 3

Чтобы перенести самый нижний диск (n'th) с p1 на p3, вам сначала нужно переместить n-1-й диск из p1 в p2 (и очистить). Затем вы переместите p1 в p3, а затем переместите остальные из p2 в p3.

Из этого текстового описания очевидно, что вы действительно делаете движение только в разделе «move p1 to p3». Здесь вы должны увеличить свой счетчик движения.

Чтобы показать это в компактной форме, здесь очень короткая версия башен из hanoi (рассмотрите этот быстрый прототип для вашей 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, есть визуализация Towers Of Hanoi на основе this iterative program, которая продемонстрировала, что решает проблему с минимальным количеством шагов.

Я знаю, что это не в JAVA, но вы увидите, что портирование программы не слишком сложно.

Answer 5

Non Итерационной башня решения Ханоя

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

    } 

}