Как это вообще сделать?

Вопрос по задаче

Ханойские башни

Java Collections, 4 уровень, 2 лекция

Обсуждается

Я вообще не понимаю как это делается...

Комментарии (3)

популярные
новые
старые

Для того, чтобы оставить комментарий Вы должны авторизоваться

hidden #598481

Уровень 27

29 мая 2019, 11:45

Я не видел самой задачи, но попробую объяснить. Допустим, у тебя есть три списка: source, result и buffer. Даже не списка, а стека (стопки) - особого вида коллекций, реализующих принцип LIFO (Last in - first out), т.е. позволяющих тебе добавить элемент наверх (в конец стека) и взять последний добавленный элемент (с верха стека). Тебе нужно переместить все элементы стека source в стек result, сохранив исходный порядок. Как это сделать? Рассмотрим вырожденный случай, когда в стеке source один элемент. Мы берем последний элемент из source и помещаем в result. Бам, задача решена. Следующий случай, в source два элемента: 2 и 1. Как переместить? Очевидно, сначала поместить элемент "1" в buffer, получим доступ к элементу "2". Вторым шагом переместить элемент "2" в result. В source больше не осталось элементов. Третий ход - перемещение элемента из buffer в result. Теперь в result элементы 2 и 1. Готово. Третий случай: в исходном стеке элементы 3, 2, 1. Тут стоит взять паузу и подумать. Как получить доступ к основанию пирамиды? Нужно убрать все остальные элементы в buffer. Как это сделать? А по сути нам нужно решить предыдущий случай, только роль списка result у нас будет выполнять список buffer. Повторяем предыдущие действия для списка buffer и получаем:

source: 3; result: -; buffer: 2, 1

. Мы получили доступ к основанию пирамиды, осталось переместить элементы из buffer в result. Решаем еще раз задачу для двух элементов, где источник - стек buffer, а приемник - стек result. Теперь давай рассмотрим еще раз внимательно предыдущий случай для двух элементов. По сути, что мы сделали? Мы увидели, что элемент "1" нам мешает, чтобы взять элемент "2", который является основанием пирамиды, поэтому мы выполнили предыдущий шаг (решение задачи для одного элемента) для другого стека (buffer), т.е. решили мини-задачу по переносу одного элемента в стек buffer.

hidden #598481

Уровень 27

29 мая 2019, 11:45

Исходя из этого уже можно сформулировать общее правило, как нужно осуществить перенос (как должен работать метод для стека размером count): - если count = 1, перенести элемент в стек-получатель (result). - в противном случае выполнить этот метод для значения count-1, где роль стека-получателя исполнит тот стек, который в настоящий момент пустой. Второе действие другими словами: перенести все элементы кроме последнего в пустой стек, чтобы получить доступ к последнему элементу. То есть задача разбивается на подзадачи и решается рекурсивно с пошаговым уменьшением числа элементов, с которыми происходит операция. Почему тут сказано именно про "пустой стек", а не указано прямо стек buffer, так это потому, что роли стеков тоже меняются. Решая пошагово задачу для четырех элементов, ты в определенный момент столкнешься с таким положением:

source: 4, result: -, buffer: 3, 2, 1

То есть когда ты решишь задачу по переносу трех элементов в стек buffer, ты сможешь перенести основание пирамиды в result:

source: -, result: 4, buffer: 3, 2, 1

Как перенести эту башню в result? Выполнить подзадачу для трех элементов, где buffer будет являться источником, result-приемником, а source-буфером. Ну раз уж начал расписывать, распишу дальше. Чтобы это сделать, нужно перенести два элемента в source, то есть решить задачу для двух элементов, где источник - buffer, приемник - source, а буфер - result. Как в свою очередь это сделать? Решить подзадачу для одного элемента, где источник buffer - источник, result - приемник, source - буфер. А это уже атомарная операция, где мы берем и перемещаем один элемент из buffer в result:

source: -, result: 4, 1, buffer: 3, 2

hidden #598481

Уровень 27

29 мая 2019, 11:45

И дальше рекурсии начинают захлопываться одна за другой, думаю объяснять дальше не надо. Просто приведу состояние списков:

source: 2; result: 4, 1; buffer: 3.
source: 2, 1; result: 4; buffer: 3.
source: 2, 1; result: 4, 3; buffer: -.
source: 2; result: 4, 3; buffer: 1.
source: -; result: 4, 3, 2; buffer: 1.
source: -; result: 4, 3, 2, 1; buffer: -

Решено. Вместо резюме. Как решить задачу для такого стека из 10 элементов?

source: 10, 9, 8, 7, 6, 5, 4, 3, 2, 1; result: -; buffer: -

Согласно сформулированному правилу, сначала решить задачу для count-1, где приемник - это buffer: приходим к такой ситуации

source: 10; result: -; buffer: 9, 8, 7, 6, 5, 4, 3, 2, 1

Как прийти к такой ситуации? Ну ты понял, решить задачу для восьми элементов.