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

Выполняя первую из них, Калькулятор прибавляет к числу на экране 1, выполняя вторую — прибавляет 2, а выполняя третью, утраивает число на экране.
Сколько существует программ, для которых при исходном числе 1 результатом является число 35 и при этом траектория вычислений обязательно содержит число 15 и не содержит число 26?
K(n)=K(n-1)+K(n-2)+K(n/3) – если n делится на 3
K(n)=K(n-1)+K(n-2) – если n не делится на 3
Начиная считать с 15-ти считаем, что все предыдущие ячейки нулевые
Скорей всего, в задании ошибка. Уж больно большие числа получаются!!!
Ответ: 2892856

Обозначим через $$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$$