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

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

Исполнитель ЕЩЕНКО преобразует целое число, записанное на экране.
У исполнителя две команды, которым присвоены номера:
1. Прибавь 2,
2. Умножь на 10.
Первая из них увеличивает число на экране на 2, второе — увеличивает его в 10 раз.
Программа для Калькулятора — это последовательность команд.
Сколько есть программ, которые преобразуют число 2 в число 40?

Решение рекурсией:

def f(x, y):
    if x > y:
        return 0
    if x == y:
        return 1
    return f(x + 2, y) + f(x * 10, y)

print(f(2, 40))

Решение динамикой:

a = [0] * 100
a[2] = 1
for i in range(3, 41):
    a[i] = a[i - 2]
    if i % 10 == 0:
        a[i] += a[i // 10]
print(a[40])

Решение аналитикой:

Количество программ, которые преобразуют число 2 в число n, обозначим $R (n)$ . Число 2 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 2. Значит, $R (2) = 1$ . Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на десять, то оно может быть получено только из предыдущего с помощью команды прибавь 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего возможного числа: $R (n) = R (n − 2)$ .
Если число делится на 10, то вариантов последней команды два: прибавь 2 и умножь на 10, тогда $R (n) = R (n − 2) + R(n : 10 )$ . Заполним таблицу по данной формуле:

|--|--|--|--|----|---|---|---|----|---|---|---|---|----|---|---|---|---|----|---| |2 |4 |6 |8 |10 |12 |14 |16 |18 |20 |22 |24 |26 |28 |30 |32 |34 |36 | 38 |40 | |1-|1-|1-|1-|-1--|1--|1--|-1-|-1--|2--|2--|-2-|-2-|-2--|2--|2--|-2-|-2-|-2--|3--| --------------------------------------------------------------------------------|

Отсюда получаем искомое количество программ — 3.

Ответ: 3