Головоломка Ханойские башни (или Ханойская башня, или Towers of Hanoi) – классический пример задачи, в которой лучшее и самое наглядное решение основывается на рекурсии. Кроме того, эта задача иногда встречается на собеседованиях. Тем удивительнее, что последняя статья (хотя и весьма обстоятельная), посвященная этой задаче на Хабре датируется 2013-м годом и решение приводится на Delphi. Давайте исправим эту печальную ситуацию!
В чем суть задачи?
Задача про Ханойские башни была придумана в 19-м веке французским математиком Эдуардом Люка, и представляет собой, по сути, детскую пирамидку. Вот суровая картинка с Википедии, но в Интернете можно без труда отыскать массу более разноцветных версий:
Имеются набор дисков разного размера и три стержня (они же штыри, колышки, или башни), на которые эти стержни можно надеть. Изначально диски надеты на один из стержней, их размер убывает снизу вверх, образуя ту самую детскую пирамидку, два оставшихся стержня – пустые.
Задача состоит в том, чтобы переместить диски на другой стержень, придерживаясь следующих правил:
За ход можно перемещать лишь один диск;
Каждый ход заключается в снятии верхнего диска со стержня и помещении его на другой стержень, возможно, поверх уже находящихся там дисков;
Нельзя помещать диск большего размера поверх диска меньшего размера (т.е., форма пирамидки на любом из стержней не должна нарушаться).
Алгоритм
Для решения этой задачи с помощью рекурсии рассмотрим некоторые варианты перемещения дисков.
Самый простой вариант – нам нужно переместить всего один диск. Мы просто берем диск со стержня-источника (назовем его From) и кладем на нужный стержень (пусть он называется To)
Если рассматривать это с точки зрения рекурсии, то перемещение одного диска будет нашим базовым случаем (base case), при наступлении которого цепочка вызовов рекурсивной функции прекращается.
Если у нас два диска – нам понадобится вспомогательный стержень Aux:
Перемещаем верхний диск на вспомогательный стержень, затем перекладываем нижний диск на стержень To, и сверху кладем маленький диск, сняв его со вспомогательного стержня Aux.
При добавлении третьего диска начинает вырисовываться некоторая закономерность:
Чтобы переместить 3 диска, нам нужно сперва переместить 2 верхних диска на вспомогательный стержень (точно также, как в предыдущем рассмотренном нами случае перемещения двух дисков, только целью будет вспомогательный стержень Aux), затем переместить один нижний диск на свободный стержень To и после поместить поверх него два диска со стержня Aux, используя стержень From в качестве вспомогательного:
Теперь можно подумать: что нам требуется сделать, чтобы переместить N дисков со стержня From на стержень To? Фактически, нам нужно каким-то образом переместить N - 1 дисков со стержня From на стержень Aux: переместить один, самый большой диск (с номером N) на стержень To и затем перенести диски, ранее помещенные нами на стержень Aux, поверх него.
Как же нам перенести N - 1 дисков на стержень Aux? Переместить N-2 дисков на стержень To. Затем переместить диск под номером N - 1 со стержня From на стержень Aux. И переместить диски, помещенные нами на стержень To, поверх него. Повторять, пока задача не сведется к перемещению одного, самого верхнего, диска на какой-то из стержней (какой именно – определится само в процессе раскручивания рекурсии). Т.е., до наступления того самого базового случая перемещения одного диска.
Или более формально:
Если число дисков = 1, то перемещаем диск со стержня From на целевой стержень To.
Иначе перемещаем N - 1 дисков на вспомогательный стержень Aux, используя целевой стержень To в качестве вспомогательного.
Перемещаем диск N со стержня From на целевой стержень To.
Перемещаем N - 1 дисков со стержня Aux на стержень To, используя диск From как вспомогательный. Для каждого из этих перемещений повторяем тот же алгоритм по цепочке до тех пор, пока все не сведется к перемещению одного, верхнего, диска.
Рекурсивный алгоритм готов. Закодируем его!
Код
К написанию этой статьи меня сподвигло решение, приведенное в книге Narasimha Karumanchi “Data Structures And Algorithms.Made Easy In JAVA” (книгу очень рекомендую к прочтению!).
Вот оно:
public void TowersOfHanoi(int n, char frompeg, char topeg, char auxpeg) { /* If only 1 disk, make the move and return */ if(n==1) { System.out.println("Move disk 1 from peg "+ frompeg + " to peg " + topeg); return; } /* Move top n-1 disks from A to B, using C as auxiliary */ TowersOfHanoi(n-1,frompeg,auxpeg,topeg); /* Move remaining disks from A to C */ System.out.println("Move disk from peg " + frompeg +" to peg " + topeg); /* Move n-1 disks from B to C using A as auxiliary */ TowersOfHanoi(n-1,auxpeg,topeg,frompeg); }
А вот вывод для трех дисков:
Move disk 1 from peg A to peg B
Move disk from peg A to peg C
Move disk 1 from peg B to peg C
Move disk from peg A to peg B
Move disk 1 from peg C to peg A
Move disk from peg C to peg B
Move disk 1 from peg A to peg B
Думаю, если вы воспроизведете этот код в ходе технического интервью, ваш ответ будет засчитан, как правильный. Но у меня вывод решения в такой форме оставил сомнения, действительно ли головоломка в итоге решается, и не читерит ли программа, по ходу решения складывая большие диски на меньшие или каким-либо другим способом.
Поэтому давайте используем мощь объектно-ориентированного подхода, воплощенного в современный язык Java, и повторим алгоритм в более наглядном виде.
Для начала опишем диск. В контексте задачи нас интересует лишь его радиус, который в процессе остается неизменным, так что можно смело использовать record.
public record Disk(int r) {}
Заодно добавим исключение, которое будем выбрасывать, если что-то пойдет не так, и больший диск окажется поверх меньшего:
public class WrongDiskSizeException extends RuntimeException{ public WrongDiskSizeException(String message) { super(message); } }
И включим интерфейс, который должен будет отображать происходящее с нашими дисками и стержнями. Не то, чтобы он был тут необходим, но вдруг кто-то решит в будущем заменить мою консольную реализацию на качественную 3D-анимацию?
public interface PegPrinter { void draw(); }
Теперь напишем класс для стержня, он будет побольше предыдущих.
У стержня будет имя (достаточно одного символа char) и LinkedList, содержащий помещенные на стержень диски. Диски будут создаваться и помещаться на стержень в конструкторе, начиная с самого большого.
public class Peg { private final LinkedList<Disk> disks = new LinkedList<>(); private final char name; public Peg(int diskAmount, char name) { // Помещаем на стержень заданное количество дисков начиная с самого большого for (int i = diskAmount; i>0; i--) { Disk disk = new Disk(i); disks.addLast(disk); } this.name = name; }
Добавим полезных геттеров:
public int getDiskStackSize() { return disks.size(); } public char getName() { return name; } public List getDisks() { return disks; }
А также, метод, помещающий на стержень новый диск (а также проверяющий, чтобы он не был больше уже находящихся на этом стержне дисков):
public void push(Disk disk) { System.out.printf("Диск %d помещен на стержень %c%n", disk.r(), name); if (!disks.isEmpty() && disk.r()>disks.getLast().r()) { throw new WrongDiskSizeException( String.format( "Диск размером %d, помещаемый на стержень %c, " + " больше предыдущего диска размером %d", disk.r(), name, disks.getLast().r())); } disks.addLast(disk); }
И метод, снимающий со стержня верхний диск:
public Disk pop() { if (disks.isEmpty()) { throw new IllegalStateException("На стержне не осталось дисков!"); } Disk disk = disks.removeLast(); System.out.printf("Диск %d снят со стержня %c%n", disk.r(), name); return disk; }
Теперь то, ради чего все это и затевалось – класс, предоставляющий рекурсивный метод для переноса дисков между стержнями! Передадим в его конструктор реализацию созданного нами ранее интерфейс�� для отрисовки:
public class RecursiveDiskMover { private final PegPrinter printer; public RecursiveDiskMover(PegPrinter printer) { this.printer = printer; // объект, отображающий состояние стержней и дисков }
И напишем рекурсивный метод для перемещения дисков:
public void moveDisks(Peg from, Peg to, Peg aux, int n) { // Если нужно переместить 1 диск - просто перекладываем его на нужный стержень if (n==1) { Disk disk = from.pop(); to.push(disk); printer.draw(); } else { // Если перемещается больше одного диска moveDisks(from, aux, to, n - 1); // переносим n-1 диск на вспомогательный стержень moveDisks(from, to, aux, 1); // переносим 1 диск на конечный стержень moveDisks(aux, to, from, n - 1); // переносим диски со вспомогательного на конечный стержень } }
Самое главное выполнено! Осталось добавить громоздкий класс, который будет показывать нам, что же происходит по ходу выполнения рекурсивных вызовов. Наверное, мою реализацию можно сделать намного более изящной, с удовольствием выслушаю ваши предложения!
Если коротко, мы создаем массив символов такого размера, в который гарантированно поместятся все наши диски и стержни, изображающий стойку, на которой все это расставлено, заполняем его пробелами и выбранным нами символом, отображающим стержни и диски, и затем построчно выводим его на экран в методе draw():
public class ConsolePegPrinter implements PegPrinter { private final char[][] display; // массив, формирующий картинку со стержнями и дисками на них private final char PEG_SYMBOL = '▓'; // Символ, который используется при отрисовке всего private final int high, width; private final int peg1Position, peg2Position, peg3Position; // Позиции стержней по оси x private final Peg peg1, peg2, peg3; private final StringBuilder sb = new StringBuilder(); public ConsolePegPrinter(Peg peg1, Peg peg2, Peg peg3) { // Создаем массив с высотой, равной числу дисков и шириной, равной тройной ширине самого широкого диска int diskStackSize = peg1.getDiskStackSize() + peg2.getDiskStackSize() + peg3.getDiskStackSize(); //Высота картинки - общее количество дисков + одна строка для имен стержней high = diskStackSize+1; //Ширина картинки = высота x 2 (чтобы не пересекались диски на соседних стойках) // x на три стойки плюс два промежутка между стойками с дисками width = high*2*3+2; display = new char[high][width]; // картинка со стержнями и дисками peg1Position = width/6; peg2Position = peg1Position + width/3; peg3Position = peg2Position + width/3; this.peg1 = peg1; this.peg2 = peg2; this.peg3 = peg3; draw(); } /** * Отобразить стержни с дисками в консоли */ public void draw() { initArray(); drawPegs(); drawDisks(peg1Position, peg1); drawDisks(peg2Position, peg2); drawDisks(peg3Position, peg3); print(); }
Сам метод draw вызывает несколько приватных методов, отрисовывающих разные части картинки:
// Очищает массив для отрисовки изменившейся картинки private void initArray() { for (int i = 0; i<high; i++) { for (int j = 0; j < width; j++) { display[i][j] = ' '; } } } // Отрисовывает стержни private void drawPegs() { for (int i = 0; i < high; i++) { // В верхней строке располагаем имена стержней if ((i==0)) { display[i][peg1Position] = peg1.getName(); display[i][peg2Position] = peg2.getName(); display[i][peg3Position] = peg3.getName(); } else { display[i][peg1Position] = PEG_SYMBOL; display[i][peg2Position] = PEG_SYMBOL; display[i][peg3Position] = PEG_SYMBOL; } } } // Отрисовывает диски на заданном стержне private void drawDisks(int pegPosition, Peg peg) { if (!peg.getDisks().isEmpty()) { int size = peg.getDisks().size(); List<Disk> disks = peg.getDisks(); for (int i = 0; i<size; i++) { for (int j = 0; j<=disks.get(i).r(); j++) { display[high-1-i][pegPosition-j] = PEG_SYMBOL; // рисуем диск слева display[high-1-i][pegPosition+j] = PEG_SYMBOL; // и справа от стержня } } } } // Выводит картинку со стрежнями и дисками в консоль private void print() { for (int i = 0; i < high; i++) { for (int j = 0; j < width; j++) { sb.append(display[i][j]); // помещаем содержимое строки массива в StringBuilder } System.out.println(sb); // выводим строку на экран sb.setLength(0); // очищаем StringBuilder для новой строки } }
На этом практически все! Осталось дописать класс Main, который все это запускает, и любоваться перестановками дисков. Сделаем так, чтобы число дисков можно было задать через аргументы при запуске программы. Если ничего не передано, пусть будет 5 дисков:
public class Main { public static void main(String[] args) { int diskNumber; // количество дисков, которые нужно переместить между стержнями if (args.length> 0) { diskNumber = Integer.getInteger(args[0]); } else { diskNumber = 5; }
Создадим три стержня, один с дисками, два пустых:
Peg peg1 = new Peg(diskNumber, 'A'); // Создаем стержень с заданным числом дисков и два пустых Peg peg2 = new Peg(0, 'B'); Peg peg3 = new Peg(0, 'C');
Добавим объект, который будет отрисовывать нашу стойку с дисками:
PegPrinter pg = new ConsolePegPrinter(peg1, peg2, peg3); // Создаем объект для отображения состояния стойкиу
И наконец запустим рекурсию:
RecursiveDiskMover mover = new RecursiveDiskMover(pg); mover.moveDisks(peg1, peg3, peg2, diskNumber);
Для двух дисков получим такой вывод:
Отлично, программа работает и наглядно показывает все операции, которые требуется провести с дисками для достижения результата!
Полностью код можно посмотреть и скачать по ссылке.
