Упр.3.88 ГДЗ Сборник упражнений Босова 7-9 класс (Информатика)
Решение #1
Рассмотрим вариант решения задания из учебника Босова, Аквилянов 9 класс, Просвещение:
3.88. Для подсчета минимального числа ходов в задаче «Ханойская башня» используется функция S(n), которая вычисляется по следующему алгоритму:
S(1) = 1,
S(n) = 2 * S(n — 1) + 1 при натуральном n > 1
Чему равно значение функции S(7)?
Вычисления фиксируйте в таблице:
На основании приведенного выше рекурсивного алгоритма опишите последовательность действий исполнителя при решении задачи в случае пирамиды из 5 дисков.
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.
Популярные решебники 9 класс Все решебники
*К сожалению, временные проблемы с публикацией комментариев с мобильных устройств.