Блог

У меня есть код ханойской башни, и мне нужно уметь подсчитывать шаги, сделанные перед печатью решения, поэтому использование переменной count неприменимо.

Моя программа использует базовый рекурсивный метод для печати результата на каждом шаге рекурсии. Единственное решение, которое пришло мне в голову, состояло в том, чтобы вместо печати на каждом шаге хранить решение в строке, но это вызвало бы проблему с памятью для большого количества дисков. У вас есть какие-нибудь советы для достижения этой цели? Спасибо.

Я знаю, что минимальное количество ходов, необходимое для решения задачи с 3 башнями, равно 2^n — 1, но я знаю, что это не обязательно то, чего достигнет моя программа, и я также не математик, чтобы вычислить формулу для задачи с 4 башнями.

Это всего лишь базовый рекурсивный код, но на всякий случай, если вы хотите знать, это то, что у меня сейчас есть:

 private static void Hanoi(int n, char source, char destination, char inter1, char inter2){
    if (n == 0)
      return;
    if (n == 1) {
      StdOut.println("Disk "   n   " to tower "   destination);
      count  ;
      return;
    }

    Hanoi(n - 2, source, inter1, inter2, destination);

    StdOut.println("Disk "   (n - 1)   " to tower "   inter2);
    count  ;
    StdOut.println("Disk "   n   " to tower "   destination);
    count  ;
    StdOut.println("Disk "   (n - 1)   " to tower "   destination);
    count  ;

    Hanoi(n - 2, inter1, destination, source , inter2);
  }