Задача к ЕГЭ по информатике на тему «количество программ из a в b где траектория вычислений не содержит число(-а)» №1

Просмотров 6 Комментарии 0

Исполнитель Крабомёт преобразует число на экране.

У исполнителя есть две команды, которым присвоены номера:

Прибавить $1$
Умножить на $2$

Первая команда увеличивает число на экране на $1$ , вторая увеличивает его в $2$ раза. Программа для исполнителя Программист — это последовательность команд.

Сколько существует программ, для которых при исходном числе $1$ результатом является число $19$ и при этом траектория вычислений не содержит число $14$ ? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы $121$ при исходном числе $7$ траектория будет состоять из чисел $8$ , $16$ , $17$ .

Решение 1

a = [0] * 20
a[1] = 1
for i in range(2, 20):
    a[i] = a[i - 1] + a[i // 2] * (i % 2 == 0)
    if i == 14:
        a[i] = 0
print(a[19])

Решение 2

a = [0] * 40
a[1] = 1
for i in range(1, 19):
    if i == 14:
        a[i] = 0
    a[i + 1] += a[i]
    a[i * 2] += a[i]
print(a[19])

Решение 3 Пусть $R(n)$ — количество программ, которые число 1 преобразуют в число $n$ . Тогда верно следующее утверждение:

$R(n ) = R (n − 1) + R (n : 2)$

Заполним таблицу по данной формуле до 13:

|1--|2-|3-|4-|5-|6-|7-|-8-|-9--|10-|11-|12-|13-| |---|--|--|--|--|--|--|---|----|---|---|---|---| -1---2--2--4--4--6--6--10--10---14--14--20--20--

Так как по условию сказано, что траектория не должна проходить через число 14, значит мы никак не можем его получить, что означает $R(14) = 0$ .

Заполним таблицу до конца:

|--|--|--|--|--|--|---|---|---|---|---|----|---|---|---|---|----|---|---| |1-|2-|3-|4-|5-|6-|7--|8--|9--|10-|11-|12--|13-|14-|15-|16-|-17-|18-|19-| -1--2--2--4--4--6--6---10--10--14--14--20---20--0----0--10---10--20--20--

Отсюда получаем ответ — 20.

Ответ: 20