Как назвать рекурсию с Ханойской Башней

Question

Я пытаюсь решить проблему Ханойской башни; Я написал этот код:

public class TowersOfHanoi {
   public static void main(String[] args) {
      move(5, 1, 3);
      }

   public static void move(int disks, int from, int to) {
      if (disks > 0) {
         int other = 6 - from - to; // sum of index 1+2+3=6
         System.out.println("Move disk from peg " + from + " to " + to);
         move(disks - 1, from, other);
         move(disks - 1, other, to);
         }
   }
}

но результат неверный. Решение в моей книге:

public class TowersOfHanoi {
   public static void main(String[] args) {
      move(5, 1, 3);
      }

   public static void move(int disks, int from, int to) {
      if (disks > 0) {
         int other = 6 - from - to; // sum of index 1+2+3=6
         move(disks - 1, from, other);
         System.out.println("Move disk from peg " + from + " to " + to);
         move(disks - 1, other, to);
         }
   }
}

почему это? Я не могу понять ПОРЯДОК этих выражений:

• первый запуск System.out.println()
• тогда он запускается move(disks - 1, from, other)
• теперь он снова запускается System.out.println() или move(disks - 1, other, to)?

и КОГДА ПЕРЕЗАПУСТИТЬ код блока? Thanx.

Answer 1

Ханойская башня работает таким образом, чтобы:

1. Сначала вы должны переместить n - 1 диск во второй колышек с первого с помощью 3.
2. Переместите последний n-й диск на 3-й колышек.
3. Переместите диски n-1 со 2-го колышка на 3-й колышек, используя 1st.

Книжное решение правильно. Ваше решение неверно, потому что вы переместили последний диск в начале, это против правила Ханойской башни. Я надеюсь, что вы поняли.

Немного более элегантный и понятный код после некоторой модификации, где он работает для любого произвольного n. (По крайней мере, для малых значений n из-за его экспоненциальной сложности)

public class TowersOfHanoi {
   public static void main(String[] args) {
      int first = 1, second = 2, third = 3;
      int disk = 5; // or take user input
      move(disk, first, third);
   }

   public static void move(int disks, int first, int second, int third) {
      if (disks > 0) {
              move(disks - 1, first, third, second); // source = first, dest = second
              System.out.println("Move disk from peg " + first+ " to " + third);
              move(disks - 1, second, first, third);  // source = second, dest = third
         }
   }
}

Answer 2

Итак, у нас есть n диски и 3 колышка, мы хотим переместить диски, помещенные в 1-й колышек (исходный колышек), в 3-й колышек (целевой колышек); Концепция рекурсии в этом случае:

1. Переместите все диски рекурсивно с 1 на n-1 над самым большим (называемым n) с 1-го на 2-й (запасной), , потому что мы хотим освободить место для самый большой диск и сможет поставить его в 3-й колышек. Это первое предложение move(disks - 1, from, other);

2. После перемещения всего диска выше самого большого мы перемещаем его на 3-й колышек: как Википедия говорит , это простой шаг и его второе предложение
   System.out.println("Move disk from peg " + from + " to " + to);

3. В конце переместите все n-1 диски со 2-го колышка на 3-й рекурсивно , чтобы воссоздать башню в 3-м колышке и ее последнее предложение move(disks - 1, other, to);

Этот алгоритм работает как с четными, так и с нечетными n дисками, потому что это g общая процедура решения , очевидно, что шаги будут меняться в зависимости от начального номера диска.

Answer 3

Идея правильного решения заключается в следующем:

1. Сначала вы должны рекурсивно переместить верхние n-1 диски из колышка "из" в колышек "другого".
2. Затем вы можете переместить нижний диск из колышка "из" в колышек "в" - это утверждение println.
3. Затем вы должны переместить n-1 диски (которые были перемещены на шаге 1) из привязки «прочее» в привязку «к» рекурсивно.

С другой стороны, в своем неправильном решении вы пытаетесь переместить нижний диск перед тем, как переместить все диски, уложенные над ним, что недопустимо.