Алгоритм Фрейма-Стюарта для произвольного p

Оказывается, что и дальше оптимальное число перекладываний алгоритмом Фрейма-Стюарта определяется аналогично предыдущим случаям, только теперь скачок от 2l до 2l+1 при подсчете ходов будет происходить при переходе через соответствующее симплициальное число дисков. Для 6 подставок, например, скачок в числе ходов будет происходить при переходе числа дисков через числа С4k+3.

Для произвольного числа подставок p также известны формулы для вычисления оптимального числа ходов методом Фрейма-Стюарта [6]:

image007.png

где k - номер (p−2)-симплициального числа, такого что

image009.pngimage011.pngimage015.png

Посмотреть видеоролик


[6] Klavžar, S. Simple Explicit Formulas for the Frame-Stewart Numbers//S. Klavžar, U. Milutinović/ Ann. of Comb. 6(2002), 157–167.