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

Рассмотрим вариант решения задания из учебника Босова 9 класс, Просвещение: 88. Для подсчета минимального числа ходов в задаче «Ханойская башня» используется функция S(n), которая вычисляется по следующему алгоритму: Ha основании приведенного выше рекурсивного алгоритма опишите последовательность действий исполнителя при решении задачи в случае пирамиды из 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.

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

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