по возрастанию. Рис.
по возрастанию.
Рис. 1.
Шаг алгоритма состоит из двух последовательных стековых операций:
Pop (i) и Push (j), где i, j ? {left, middle, right} & i ? j, и в исходном состоянии i = left.
Тот факт, что задача разрешима, мы здесь не станем доказывать, а пока лишь продемонстрируем идею решения на примерах. Заметим при этом, что процесс перекладывания 64, согласно условию, дисков займет очень много времени, поэтому имеет смысл уменьшить их количество N.
Для N=2 последовательность шагов такова:
Номер шага алгоритма Содержимое стека Left Содержимое стека Middle Содержимое стека Right
0 1 2 Пусто Пусто
1 2 1 Пусто
2 Пусто 1 2
3 Пусто Пусто 1 2
Для N=3:
Номер шага алгоритма Содержимое стека Left Содержимое стека Middle Содержимое стека Right
0 1 2 3 Пусто Пусто
1 2 3 Пусто 1
2 3 2 1
3 3 1 2 Пусто
4 Пусто 1 2 3
5 1 2 3
6 1 Пусто 2 3
7 Пусто Пусто 1 2 3
Каково же количество шагов M алгоритма в общем случае?
Учитывая,
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
