Упр.3.88 ГДЗ Сборник упражнений Босова 7-9 класс (Информатика)

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

Вычислим значения функции по рекуррентной формуле:

Проверим вычисления:

$$S(1)=1$$
$$S(2)=2\cdot S(1)+1=2\cdot 1+1=3$$
$$S(3)=2\cdot S(2)+1=2\cdot 3+1=7$$
$$S(4)=2\cdot S(3)+1=2\cdot 7+1=15$$
$$S(5)=2\cdot S(4)+1=2\cdot 15+1=31$$
$$S(6)=2\cdot S(5)+1=2\cdot 31+1=63$$
$$S(7)=2\cdot S(6)+1=2\cdot 63+1=127$$

Ответ

$$S(7)=127$$

Для пирамиды из 5 дисков последовательность действий исполнителя соответствует вычислению $$S(5)$$:

1. Вычислить $$S(1)=1$$.
2. Вычислить $$S(2)=2\cdot S(1)+1=3$$.
3. Вычислить $$S(3)=2\cdot S(2)+1=7$$.
4. Вычислить $$S(4)=2\cdot S(3)+1=15$$.
5. Вычислить $$S(5)=2\cdot S(4)+1=31$$.