Question

Для подсчета минимального числа ходов в задаче «Ханойская башня» используется функция S(n), которая вычисляется по следующему алгоритму:
s(1) = 1,
S(n) = 2 • S(n - 1) + 1 при натуральном п > 1.
Чему равно значение функции S(7)? Вычисления фиксируйте в таблице:
На основании приведенного выше рекурсивного алгоритма опишите последовательность действий исполнителя при решении задачи в случае пирамиды из 5 дисков.

Answer 1

Для подсчета минимального числа ходов в задаче «Ханойская башня» используется функция 5(л), которая вычисляется по следующему алгоритму:
S(l) = 1,
S(n) = 2 * S(n — 1) + 1 при натуральном n > 1
Чему равно значение функции S(7)? Вычисления фиксируйте в таблице:

На основании приведенного выше рекурсивного алгоритма опишите последовательность действий исполнителя при решении задачи в случае пирамиды из 5 дисков.
Второй диск будет равен выражению (2 * Значение первого диска + 1) = 3
Третий диск будет равен выражению (2 * Значение второго диска + 1) = 7
Четвертый диск будет равен выражению (2 * Значение третьего диска + 1) = 15
Пятый диск будет равен выражению (2 * Значение четвертого диска + 1) =31