22 задание. ЕГЭ по информатике:
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
3. Умножить на 3

Сколько существует программ, для которых при исходном числе 2 результатом является
число 30 и при этом траектория вычислений содержит число 15?

Так как все команды только увеличивают число, число \(15\) в траектории может встретиться не более одного раза. Поэтому отдельно посчитаем программы от \(2\) до \(15\), а затем — от \(15\) до \(30\).

Обозначим через \(P(n)\) число программ, которые переводят \(2\) в \(n\). Тогда:

\[P(n)=P(n-1)+P\left(\frac{n}{2}\right)+P\left(\frac{n}{3}\right)\]

Слагаемые с дробными числами не учитываются. Начальное значение: \(P(2)=1\). Последовательный подсчёт даёт \(P(15)=21\).

От \(15\) до \(30\) есть две программы: умножить на \(2\) или пятнадцать раз прибавить \(1\). Значит:

\[21\cdot2=42\]

Ответ: \(42\) программы.

0 0 Пожаловаться