Как решать задание 23 ЕГЭ по информатике (число программ, пути)?

Задание 23 — подсчёт количества программ исполнителя (команды вроде «прибавь 1», «умножь на 2»), переводящих число A в B. Иногда: с обязательным прохождением через промежуточное число C.

Метод — динамическое программирование «снизу вверх». Пусть K(n) — число программ из A в n. Тогда в n можно попасть из тех чисел, откуда есть ход в n:

• из n−1 (командой +1),
• из n/2 (командой ×2, если n чётное).

K(n) = K(n-1) + K(n/2 если n чётно), при этом K(A) = 1.

A, B = 3, 100
K = {A: 1}
for n in range(A+1, B+1):
    K[n] = K.get(n-1, 0)
    if n % 2 == 0:
        K[n] += K.get(n//2, 0)
print(K[B])

С промежуточной точкой C (программа обязана пройти через C): по правилу умножения

ответ = (число программ A→C) × (число программ C→B).

Считаешь два раза одной и той же функцией.

Частые ошибки:

• учитывать ×2 для нечётных n (нельзя: из дробного не придёшь);
• неверная база (K(A) = 1, а не 0);
• при условии «через C» забыть перемножить два участка, а не сложить.

Есть запрещённые числа? Просто ставь K = 0 для них — пути через них занулятся.