Алгоритм Фрейма-Стюарта для p=5

Рассмотрим теперь случай пяти подставок. Аналогично случаю с четырьмя подставками можно составить таблицу 5 зависимости числа ходов в методе Фрейма-Стюарта от количества дисков. Имеем:

table5.png

Как видите сценарий тот же что и в случае с четырьмя подставками, только скачки +21, +22, +23 происходят при переходе через другие значения, а именно, когда n=4,10,20,.... Чтобы понять эти значения запишем эти значения следующим образом так, как это сделано в таблице 

table6.png

Каждое новое число получается добавлением к предыдущему соответствующего треугольного числа. Такие числа носят название тетраэдрических и их значения равны C3k+1.

Можно вывести явную формулу для вычисления значения F(n,5) [6]

image011.png

где k – номер тетраэдрического числа, такого, чтоimage013.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.