Задание 2 Вариант 3 Самостоятельная работа 6 ГДЗ Рабочая тетрадь Босова 11 класс (Информатика)

1. У исполнителя «Калькулятор» три команды, которым присвоены номера: 1 — прибавь 1; 2 — прибавь 2; 3 — умножь на 3. Выполняя первую из них, «Калькулятор» прибавляет к числу на экране 1, выполняя вторую — прибавляет 2, а выполняя третью, утраивает число на экране. Сколько существует программ, для которых при исходном числе $$1$$ результатом является число $$35$$ и при этом траектория вычислений обязательно содержит число $$15$$ и не содержит число $$26$$?

Обозначим через $$K(n)$$ количество программ, которые переводят число $$1$$ в число $$n$$. Тогда для исполнителя с командами «$$+1$$», «$$+2$$», «$$\times 3$$» получаем рекуррентные соотношения:

если $$n$$ делится на $$3$$, то $$K(n)=K(n-1)+K(n-2)+K\!\left(\frac{n}{3}\right)$$;

если $$n$$ не делится на $$3$$, то $$K(n)=K(n-1)+K(n-2)$$.

Нужно найти число программ из $$1$$ в $$35$$, траектория которых обязательно проходит через $$15$$ и не проходит через $$26$$.

Сначала найдём значения $$K(n)$$ до $$35$$. По таблице получаем:

Так как траектория обязательно содержит число $$15$$, а число $$26$$ не должно встречаться, то в данном случае искомое количество программ совпадает с $$K(35)$$.

Следовательно, $$K(35)=2892856$$.

Ответ

$$2892856$$