7класс
Номер 3.88, ГДЗ по информатике за 9 класс к сборнику задач и упражнений Босовой
Номер 3.88. Для подсчета минимального числа ходов в задаче «Ханойская башня» используется функция S(n), которая вычисляется по следующему алгоритму:
S(1) = 1,
S(n) = 2 * S(n - 1) + 1 при натуральном n > 1
Чему равно значение функции S(7)?
Вычисления фиксируйте в таблице:
На основании приведенного выше рекурсивного алгоритма опишите последовательность действий исполнителя при решении задачи в случае пирамиды из 5 дисков.
S(1) = 1,
S(n) = 2 * S(n - 1) + 1 при натуральном n > 1
Чему равно значение функции S(7)?
Вычисления фиксируйте в таблице:
На основании приведенного выше рекурсивного алгоритма опишите последовательность действий исполнителя при решении задачи в случае пирамиды из 5 дисков.
n
1
2
3
4
5
6
7
S(n)
1
3
7
15
31
63
127
1. Вычислить S(1) =1.
2. Вычислить S(2) = 2* S(1)+1=2+1=3.
3. Вычислить S(3) = 2* S(2)+1 = 2*3+1=7.
4. Вычислить S(4) = 2* S(3)+1 = 2*7+1=15.
5. Вычислить S(5) = 2* S(4)+1 = 2*17+1=31.
