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

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

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

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

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

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

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

Решение 1

a = [0] * 25
a[4] = 1
for i in range(5, 25):
    a[i] = a[i - 1] + a[i - 5] + a[i // 2] * (i % 2 == 0)
    if i == 11 or i == 17:
        for j in range(i):
            a[j] = 0
print(a[24])

Решение 2

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

$R(n ) = R (n − 1) + R (n − 5)$ — если число не делится на 2.

$R(n ) = R (n − 1) + R (n − 5) + R (n : 2)$ — если число делится на 2.

Заполним таблицу по данным формулам до 11:

---------------------------- |4 |5 |6 |7 |8 |9 |10 |11 | |---|--|--|--|--|--|---|---| -1---1--1--1--2--3---5---6--

По условию траектория должна проходить через число 11, значит $R (12) = 6$ , так как число 12 можно получить только из числа 11 (соблюдая траекторию). Заполним таблицу до 18:

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

Аналагично $R(19) = 24$ , так как число 19 можно получить только из 18, соблюдая траекторию. Заполним таблицу до конца:

|--|--|--|--|---|--|---|---|---|---|----|---|---|---|----|---|---|---|---|----|---| |4 |5 |6 |7 |8 |9 |10 |11 |12 |13 | 14 |15 |16 |17 |18 |19 |20 |21 |22 |23 |24 | |1-|1-|1-|1-|2--|3-|5--|6--|-6-|-6-|-6--|6--|12-|18-|24--|24-|24-|24-|24-|48--|72-| ----------------------------------------------------------------------------------|

Отсюда получаем ответ: 72.

Ответ: 72