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

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

   На основании приведенного выше рекурсивного алгоритма опишите последовательность действий исполнителя при решении задачи в случае пирамиды из 5 дисков.

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

Проверим по шагам:

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

Для пирамиды из 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$$.

Ответ: $$S(7)=127$$; для 5 дисков: $$1,\,3,\,7,\,15,\,31$$.