Упр.88 ГДЗ Рабочая тетрадь Босова 9 класс (Информатика)

1. Для подсчёта минимального числа ходов в задаче «Ханойская башня» используется функция $$S(n)$$, которая вычисляется по следующему алгоритму. На основании приведённого выше рекурсивного алгоритма опишите последовательность действий исполнителя при решении задачи в случае пирамиды из 5 дисков.

По рекуррентной формуле:

$$S(1)=1,$$

$$S(n)=2\cdot S(n-1)+1 \quad \text{при } n>1.$$

Вычислим значения последовательно:

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.$$

Значит, для пирамиды из 5 дисков минимальное число ходов равно $$31$$.

Ответ

$$S(1)=1,\; S(2)=3,\; S(3)=7,\; S(4)=15,\; S(5)=31.$$