Comments 22
Стиль и язык немного суховаты и годятся скорее для академических работ
Склонен не согласиться. Нельзя назвать суховатым то, что состоит из воды)
Для сравнения, попробуйте написать программу с использованием рекурсии, которая просчитывает положение уже хотя бы при перемещении сорокового диска.
Уверен, что вычислительных ресурсов большинства обычных компьютеров не хватит, рекурсивное приложение вылетит по таймауту или из-за нехватки памяти.
А при вышеуказанном подходе достаточно будет сделать около 40 циклов операций пусть с большими, но все еще доступными для машинной обработки обычным ПК числами.
Именно в этом и заключается ценность подобных теоретических оптимизаций.
Т.е. используя схему Грея можно узнать положение любого из дисков после любого из ходов, но это никак не упрощает задачу по переносу, т.к. количество перемещений дисков остаётся тем же. Т.е. для решения всей задачи всё-равно придётся на каждом ходе вычислять положение каждого диска и мы вернёмся всё к той же квадратичной сложности и «вылету по таймауту».
Отнюдь.
Рекурсивное решение для перемещения сорокового диска как минимум потребует переноса предыдущего диска, что приведет к необходимости совершить 
итераций.
В случае же теоретического решения достаточно будет высчитать номер первого хода, при котором будет перемещен 40-й диск — , далее максимальный номер хода для 39-го диска, для 38-го, для 37 и так далее, вплоть до диска 1.
Попутно для каждого из ходов будет получено количество перемещений для каждого из дисков, которое надо будет сводить по модулю 3 к одному из значений стержней f, t или r. Таким образом, будет произведено не более 200 вычислений высокого порядка.
Согласитесь, что порядок числа 200 много меньше порядка числа двойки в 39-й степени.
Естественно. Но за 200 шагов я сумею описать положение всех дисков для того хода, когда перенесен 40-й. Что практически недостижимо, если данную же задачу решать рекурсивным способом. Вчитайтесь, пожалуйста, в детали.
Не совсем так. У меня на выходе массив из 40 значений, в котором индекс — это номер диска, а само значение будет f,t или r.
Но даже если даже принимать Вашу интерпретацию, которая чуть уводит в сторону от самого назначения теоретического решения, то тем более получается значительная оптимизация: вместо хранения терабайтов информации предлагается использовать функциональный подход для описания ситуации с перемещениями, что много выгоднее хранения всех данных.
А то получается «как нарисовать сову». Вот башня, а вот положение при последнем шаге, когда осталось перенести один диск.
В принципе, всё ожидаемо: либо скорость (коды Грея), либо используемая память (рекурсия).
Т.е. если задача не в переносе, а в определении состояния на произвольном шаге, тот схема Грея тут на голову эффективнее, но для полной задачи разницы как бы и нет.
ходов.
Во-первых, не понял какую конкретно задачу вы решаете. Вы можете чётко сформулировать постановку задачи?
Во-вторых, в резюмирующей части статьи хотелось бы увидеть некий связный код, реализующий ваши теоретические рассуждения.
В-третьих, программа (с рекурсией) на C, которая принимает количество дисков и генерирует оптимальную последовательность перемещений, занимает порядка 20 строк кода. Тот монстр, написанный на Delphi, может и удобен для исследования задачи, но явно избыточен.
Приводится метод, который позволяет описать положение дисков при оптимальном решении для текущего хода без использования рекурсии.
Основная цитата дающая ключ к пониманию цели статьи:
Я попытаюсь продолжить это направление, раскрыв применение кода Грея для данной конкретной задачи.
Использование кода — дело вкуса и удобства тех, кто реализует теоретические наработки в своих решениях. Я продолжил иллюстрировать на Delphi/Pascal ввиду того, что в предыдущей/базовой статье, на которую ссылался, был приведен код на этом языке.
Использование кода — дело вкуса и удобства тех, кто реализует теоретические наработки в своих решениях.
В данном случае, проблема опять-таки в расплывчатом изложении. Если вы приведёте программу (функцию) на Pascal/C/псевдокоде в качестве иллюстрации предлагаемого алгоритма, то будет понятно что имеем на входе, что получаем на выходе и что делаем в процессе. Куски кода для программы из другой статьи ясности, к сожалению, не вносят. Или, как альтернатива, распишите ваш алгоритм по шагам, нарисуйте блок-схему в конце концов.
Ханойские башни — теоретическое решение без рекурсии