Ханойские башни с K-образными опорами

Загадка «Башни Ханоя» была опубликована в западном мире в 1883 году французским математиком Эдуардом Лукасом под псевдонимом Н. Лукас де Сиам. «Легенда», сопровождавшая игру, гласила, что в Бенаресе во времена правления императора Фо Хи был индийский храм с куполом, который обозначал центр мира (Каши Вишванат). Внутри купола (брамины) священники перемещали золотые диски между 3 алмазными иголками (изношенными столбами), высотой в локте и толщиной с тело пчелы. Бог (Брахма) поместил 64 золотых диска на одну иглу во время творения. (Диски были перемещены в соответствии с неизменными законами от Брахмы, чтобы перенести их с одного колышка на другой) Говорили, что когда они выполнят свою задачу, вселенная придет к концу. Легенда варьируется в зависимости от нескольких сайтов, но в целом она соответствует. «Законы», установленные Брахмой, таковы: 1) Одновременно можно перемещать только 1 диск. 2) Нельзя помещать диск на диск меньшего размера. 3) Только верхний диск можно извлечь, а затем поместить поверх другого. Колышек и его диски Игра заканчивается, когда весь стек дисков перемещен в другой колышек. Было быстро обнаружено, что решение с 3 колышками существует, но ни одно не решено для решения с 4 колышками. В 1939 году Американский математический ежемесячник провел конкурс по поиску дисков и дисков. Два года спустя Дж. С. Фрейм и Б. М. Стюарт опубликовали два отдельных (но позже доказавших, что они совпадают) алгоритма. И то, и другое еще не доказано правильно, хотя они, как правило, считаются правильными. Там не было никаких дальнейших достижений по правильному решению. ***** Это работает только для задач с 3 колышками ***** Минимальное количество ходов для башни из n дисков было быстро показано равным 2n− 1, при этом простое рекурсивное решение выглядит следующим образом: Пометьте начало трех колышков , цель и темп. Чтобы переместить n колышков от начального колышка к целевому штифту через временный колышек: для n> 1 (i) рекурсивно перемещайте верхние n − 1 дисков от начала к темпу через цель. (ii) Переместите n-й диск от начала до цели. (iii) Рекурсивно перемещать n − 1 дисков от темпов к цели через запуск. Это решение принимает 2n − 1 ходов: (1) Если n = 1, f (n) = 1 = 2n − 1 (2) Если n> 1, f (n) = 2 ∗ (2n − 1−1) +1 = 2n − 2 + 1 = 2n − 1 Простой способ решить эту проблему ... 1,3,7,15,31 - это решения первых нескольких n дисков. Рекурсивно это напоминает nk = 2nk-1 + 1. Отсюда можно сделать вывод, что n = 2n-1. Доказывая по индукции, я ухожу к вам. ***** Базовый алгоритм Фрейма / Стюарта ***** Для m peg и n дисков выберите l такой, что 0 ≤ l < n (тогда как l - это целое число, которое минимизирует шаги в следующей настройке) ... • Переместите верхние диски l из начального колышка в промежуточный колышек; это может быть выполнено за ходы Hk (l) (поскольку нижние n-l диски вообще не мешают движениям). • Переместите нижние n - l дисков от стартовой колышка до целевой колышка, используя ходы Hk − 1 (n − l). (Поскольку один колышек занят башней меньших дисков, на этом этапе его нельзя использовать.) • Переместите исходные диски l от промежуточного колышка к целевому колышку в ходах Hk (l). Так что по сути это Hk (n) = 2Hk (l) + Hk-1 (n-1) -----> l минимизировано ***** Легко, как пирог !! Нет! ***** Проверка того, что это работает против нашего решения с тремя колышками, должна быть легкой. Используя k = 2; положим H2 (0) = 0, H2 (1) = 1 и H2 (n> 1) = ∞. Для k = 3 мы можем положить l = n-1. (Это приводит к тому, что наша H2 (n-1) становится конечной) Это позволит нам написать H3 (n) = 2H3 (n-1) + H2 (1), что равно 2n − 1. Это немного игра слов, но это работает. ***** Несколько иное описание, чтобы помочь прояснить ***** Алгоритм Фрейма – Стюарта, дающий предположительно оптимальное решение для четырех (или даже более) колышков, описан ниже: Определите H (n, m) как минимальное количество ходов, необходимое для переноса n дисков с использованием меток. Алгоритм можно описать рекурсивно: 1. Для некоторого l, 1

`Option VBASupport 1
Option Explicit
Dim n as double
dim m as double
dim l as double
dim rx as double
dim rxtra as double
dim r as double
dim x as double
dim s1 as double
dim s2 as double
dim i as integer
dim a ()
dim b ()
dim c ()
dim d ()
dim aa as double
dim bb as double
dim cc as double
dim dd as double
dim total as double

Sub Hanoi
on error goto errorhandler

m=inputbox ("m# pegs=??")
n=inputbox ("n# discs=??")
x=-1
l=m-1
rx=1
s1=0
s2=0
aa=0

while n>rx
        x=x+1
        r=(l+x)/(x+1)
        rx=r*rx
wend
rx=1
for i=0 to x-1
        r=(l+i)/(i+1)
        rx=r*rx
        redim a (-1 to x)
        redim b (-1 to x)
        redim c (-1 to x)
        redim d (-1 to x)
            a(i)=rx
            b(i)=i
            bb=b(i)
            c(i)=rx-aa
            aa=a(i)
            cc=c(i)
            d(i)=cc*2^bb
            dd=d(i)
            s1=s1+dd
next

rxtra=n-aa
s2=rxtra*2^(bb+1)
total = 2*(s1+s2)-1
msgbox total

exit sub
errorhandler: msgbox "dang it!!"
'1, 3, 5, 9, 13, 17, 25, 33 first 8 answers for 4 peg
'16=161,25=577,32=1281,64=18433
End Sub`

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