Какой алгоритм перемещения? JS

176

20 декабря 2018, 15:20

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

● плиты размещаются на автомобилях одна над другой (от 3 до 8 штук в высоту), и отсортированы по весу (от тяжелых - снизу, к легким - сверху)

● кран может снимать и перемещать только самую верхнюю плиту с грузовика, и при разгрузке не может устанавливать более тяжелые плиты на более легкие

● перенос груза с загруженного автомобиля на пустой нужно осуществить используя только одно дополнительное место для временного хранения плит

Входящие параметры: Количество плит на автомобиле, который требуется разгрузить (от 3 до 8)

Пример:
[3,2,1]
[]      
[]
---
[3,2]
[]
[1]
---
[3]
[2]
[1]
---
[3]
[2,1]
[]
---
[]
[21]
[3]
---
[1]
[2]
[3]
---
[1]
[]
[3,2]
---
[]
[]
[3,2,1]

Не могу найти правильный алгоритм перемещения

Answer 1

Решайте по аналогии с ханойскими башнями.

Вот блок-схема решения данной задачи рекурсивным методом:

Существует несколько подходов к решению, все они дают идентичные результаты.

Рекурсивное решение

Рекурсивно решаем задачу «перенести башню из n−1 диска на 2-й штырь». Затем переносим самый большой диск на 3-й штырь, и рекурсивно решаем задачу «перенеси башню из n−1 диска на 3-й штырь».

Отсюда методом математической индукции заключаем, что минимальное число ходов, необходимое для решения головоломки, равно 2n − 1, где n — число дисков2[3].

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

«Треугольное» решение

Расположим штыри в виде треугольника. Начнём с самого маленького кольца и переложим его на любую отметку.

В дальнейшем это кольцо нужно перемещать в том же направлении, что и при первом перекладывании.

Затем перенесём какое-нибудь из оставшихся колец (такой ход единственный), после чего снова переложим самое маленькое кольцо и т. д.

(Интересно заметить, что перенумеровав «кольца» по порядку, мы добьёмся неожиданного эффекта: чётные кольца будут перемещаться из одной вершины треугольника в другую в одном направлении, а нечётные — в противоположном направлении.)

Циклическое решение

Обозначим через «1-2» такое действие: переложить диск или с 1-го штыря на 2-й, или со 2-го на 1-й, в зависимости от того, где он меньше.

Тогда, чтобы решить головоломку с чётным количеством дисков, надо многократно повторять действия: 1-2, 1-3, 2-3. Если число дисков нечётно — 1-3, 1-2, 2-3.

Ссылка на описание решения