Ностальгия по Ханойским башням
Помню, в 1993 году, на втором курсе мы изучали язык Паскаль и, наконец-то начали программировать на компьютерах. Правда, это были терминалы от больших компьютеров ЕС ЭВМ, которых мы называли гробами. Но наконец-то мы перешли от бумажного программирования к электронному.
И вот одной из задач, которая мне особо нравилась, была задача про Ханойские башни. Ее мы проходили, чтобы закрепить применение рекурсии в алгоритмических задачах:
По легенде, в одном из монастырей монахи перекладывают 64 диска и как только они это сделают, наступит Конец Света.
Мне эта задача нравилась тем, что я ход решения пускал на принтер. Диски отображал графически и распечатка на длинном рулоне бумаги выглядела как мультик.
Вот решил написать решение этой задачи на 1С. Но из спортивного интереса решил не подглядывать в гугл, а попытаться «вспомнить» решение задачи.
Я записал стрим, где показываю свои «мучения». Мне понадобилось 2 часа, большую часть времени я пытаюсь подобрать алгоритм и только малую — программирую. В итоге все получается, алгоритм оказывается очень простой.
Так и в жизни с 1С — бьешься, бьешься, а решение оказывается простым.
Прикладываю обработку для 1с8, которую я пишу в ходе решения этой задачи и текстовый файл с ходом решения на 6 блинов.
Ну а для тех, кто любит «подсматривать» решения, показываю, каким элегантным кодом решается задача:
Цель(КоличествоБлинов, 1, 3);
Процедура Цель(Уровень, СтерженьИсточник, СтерженьПриемник) //Пирамиду какого уровня на каком стержне хотим видеть
//Если уровень = 1, тогда просто ставим стержень туда куда нам надо
Если Уровень = 1 Тогда
Переставить(СтерженьИсточник, СтерженьПриемник); //Тогда просто переставляем…
Иначе
СтерженьИсключающий = Исключающий(СтерженьИсточник, СтерженьПриемник);
Цель(Уровень — 1, СтерженьИсточник, СтерженьИсключающий);
Переставить(СтерженьИсточник, СтерженьПриемник);
Цель(Уровень — 1, СтерженьИсключающий, СтерженьПриемник);
КонецЕсли;
КонецПроцедуры
Здесь исключающий стержень — это отличный от двух, переданных в процедуру.
Свежие комментарии