Разбор номера 23 — ЕГЭ Информатика

📋 Условие

Задание 23 проверяет умение анализировать алгоритмы и подсчитывать количество программ, преобразующих одно число в другое.

🔍 Подробное решение

Задание 23 проверяет умение анализировать алгоритмы и подсчитывать количество программ, преобразующих одно число в другое.

Структура задачи:

Исполнитель Вычислитель имеет команды:
- Прибавить 1
- Прибавить 2
- Умножить на 2

Необходимо определить, сколько существует программ, которые преобразуют число X в число Y.

Решение:

```python
def count_programs(start, target):
dp = [0] * (target + 1)
dp[start] = 1

for i in range(start, target + 1):
if dp[i] == 0:
continue
# Команда 1: +1
if i + 1 <= target:
dp[i + 1] += dp[i]
# Команда 2: +2
if i + 2 <= target:
dp[i + 2] += dp[i]
# Команда 3: *2
if i * 2 <= target:
dp[i * 2] += dp[i]

return dp[target]
```

Ключевые моменты:

- Порядок команд важен (программы A→B→C и C→B→A — разные)
- Нельзя превышать целевое значение
- Используем динамическое программирование снизу вверх

📚 Теория

Подсчёт траекторий. Рекурсия с мемоизацией.

🐍 Шаблон Python

Python

# Базовый
def f(x, y):
    if x > y: return 0
    if x == y: return 1
    return f(x+1, y) + f(x*2, y)

# Промежуточные числа — перемножаем
print(f(4,8) * f(8,10) * f(10,15))

# С ограничением (запрет числа)
def f(x, y):
    if x < y or x == 20: return 0
    if x == y: return 1
    return f(x-2, y) + f(x-3, y) + f(x//5, y)

🐍 Альтернативный способ

Способ 2

# С последней командой
def f(x, y, z):
    if x > y: return 0
    if x == y and z[-1] == 'A': return 1
    if x == y: return 0
    return f(x+2,y,z+'A') + f(x+3,y,z+'B')

# Не более K команд подряд
from functools import lru_cache
@lru_cache(None)
def f(x, y, last, cnt):
    if x > y: return 0
    if x == y: return 1
    r = 0
    for cmd, nx in [('A', x+1), ('B', x*2)]:
        c = cnt+1 if cmd == last else 1
        if c <= 3:  # не более 3 подряд
            r += f(nx, y, cmd, c)
    return r

🔗 Полезные ссылки