Question

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

Answer 1

Ответ:

Объяснение:

Во вложении

Answer 2

Для вычисления значения функции S(n) для заданного n по алгоритму, нужно последовательно применить рекурсивную формулу, начиная с известного значения S(1).

S(1) = 1 (из условия) S(2) = 2 * S(1) + 1 = 2 * 1 + 1 = 3 S(3) = 2 * S(2) + 1 = 2 * 3 + 1 = 7 S(4) = 2 * S(3) + 1 = 2 * 7 + 1 = 15 S(5) = 2 * S(4) + 1 = 2 * 15 + 1 = 31 S(6) = 2 * S(5) + 1 = 2 * 31 + 1 = 63 S(7) = 2 * S(6) + 1 = 2 * 63 + 1 = 127 S(8) = 2 * S(7) + 1 = 2 * 127 + 1 = 255

Таким образом, значение функции S(8) равно 255.