Как переместить элементы между стеками в рекурсии? - PullRequest
Новая
       22

Как переместить элементы между стеками в рекурсии?

0 голосов
/ 04 апреля 2019

У меня проблема с Ханойской башней.У меня есть три стека, и я хочу переместить элементы в определенном порядке в рекурсии с помощью метода, называемого move ().Я должен использовать методы pop () и push () в другом классе, который добавляет и удаляет элементы из стеков.

Я пытался реализовать этот метод, но он работает только для первого базового случая, например,если n == 1.

 public static void move(SpecialStack from, 
                         SpecialStack to, 
                         SpecialStack help, 
                         int n) {
   if (n == 1) {
 to.push(from.pop());
 }
   else {
     move(from, to, help, n-1);
     to.push(from.pop());
     move(help, to, from, n-1);
   }
 }

 public static void main(String[] args) {
    int size = 3;
    SpecialStack from = new SpecialStack(size);
    SpecialStack to = new SpecialStack();
    SpecialStack help = new SpecialStack();
    System.out.println("Start state");
    System.out.println("   From: " + from);
    System.out.println("   To:   " + to);
    System.out.println("   Help: " + help);
    move(from, to, help, size);
    System.out.println("End state");
    System.out.println("   From: " + from);
    System.out.println("   To:   " + to);
    System.out.println("   Help: " + help);

Я получаю ошибку от метода push () 'Number too high!'из другого класса SpecialStack: 


 import java.util.*;
import java.util.ArrayList;

public class SpecialStack {

  private ArrayList<Integer> specStack;

  public SpecialStack() {
    specStack = new ArrayList<Integer>();
  }

  public SpecialStack(int n) {         
    this.specStack = new ArrayList<Integer>(n);
      int i;
      for (i=0; i<n; i++) {
        specStack.add(i, n-i);
      }
    }


  public void push(int x) { 
    if (specStack.size() == 0) { 
      specStack.add(x);
    }
    else if (x > specStack.get(specStack.size() -1)) {
      throw new RuntimeException("Number too high");
    }
    else {
      specStack.add(x); 
    }
  }

  public int pop() { 
    if (specStack.size() == 0) {
      throw new RuntimeException("Empty stack");
    }
    else {
      int length = specStack.size() -1;
      int topNumber = specStack.get(length); 
      specStack.remove(length);
      return topNumber;
    }
  }

  public String toString() {
    String arrList = "[";
    int i;
    for (i = 0; i < specStack.size(); i++) { 
      if (i == specStack.size() -1) {
        arrList = arrList + specStack.get(i);
      } 
      else {
        arrList = arrList + specStack.get(i) + ",";}
    }
  arrList = arrList + "]";
  return arrList;
  }
}

Я не понимаю, почему я получаю эту ошибку.А также, правильный ли метод move ()?Спасибо за совет!

1 Ответ

0 голосов
/ 04 апреля 2019

У вас глупая ошибка в вашем коде.В другой части, когда n > 1, вы должны делать 

move(from, help, to, n-1);

вместо 

move(from, to, help, n-1);

Помните, что для чего-то большего, чем 1, вы рассматриваете свою очередь «помощи» длябыть вашей целевой (для) очереди для всех, кроме одного из ваших колышков.Как только это будет сделано, вы переместите свой нижний колышек в исходную очередь «to» и повторите шаги, считая вашу исходную «help» как «from», а исходную «from» как «help».Надеюсь, это поможет.

...