user_of_toster
@user_of_toster

Как решить задачу про ханойскую башню?

Ссылка на задачу https://acm.timus.ru/problem.aspx?space=1&num=1054

Пробовал реализовать "оптимальный алгоритм", который указан в задаче двумя способами:
  1. Создаем три массива (или стека), с ханойской башней в первом массиве. Далее hanoi(N, From, To, Temp) перекидывает верхний элемент из from в to. После запуска алгоритма получается, что в конце на диске с шириной 1 стоят диски с шириной 5,4,3,2. Т.е, 1-5-4-3-2, что противоречит условиям задачи
  2. Не создаем никаких массивов, делаем просто то, что указано в оптимальном алгоритме. При этом не понятно, как реализована Writeln(N, From, To); - если это просто вывод трех значений, то не понятно, какую роль они играют - я не получаю перенесенную с первого стержня на вторую ханойскую башню.
    1 1 2
    2 1 3
    1 2 3
    3 1 2
    1 3 1
    2 3 2
    1 1 1

Думаю, основная проблема заключается в не понимании оптимального алгоритма, который предоставлен в задаче. Что он делает? Оптимально переносит ханойскую башню из первого стержня во второй? Если да, то достаточно ли симулировать этот алгоритм и следить, получается ли необходимая комбинация или нет? И выводить количество шагов если да, -1 если нет.
  • Вопрос задан
  • 123 просмотра
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Writeln(N, From, To); говорит "перенесите диск N с шеста from на шест to". При этом по построению гарантируется, что на вершине from лежит именно диск N, а на to лежит что-то большее или ничего.

Алгоритм действительно оптимально переносит диски с заданного шеста на заданный.

Просто просимулировать его, конечно, можно, но это будет медленно. В алгоритме 2^N-1 шагов. Для N до 31 это 2 миллиарда шагов и в 1 секунду вряд ли уложится. Но можно немного подумать и решить задачу всего за N действий.

Подсказка: посмотрите где у вас лежит самый-самый большой диск во входной последовательности? В алгоритме он первую половину действа лежит на начальном шесте, а вторую половину - на конечном шесте. Он никогда не бывает на среднем. Уже можно сразу понять, в какой половине из 2^N позиций заданная конфигурация должна лежать.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
15 июн. 2021, в 17:21
150000 руб./за проект
15 июн. 2021, в 17:17
20000 руб./за проект
15 июн. 2021, в 16:58
15000 руб./за проект