Задание 13 ЕГЭ по информатике · 24EE48

1. Сначала подсчитаем количество программ, переводящих число 2 в число 14. Обозначим это количество через f(n). Для команды «Прибавить 1» используется переход из n−1, а для команды «Умножить на 2» — из n/2, если n чётно.
f(n)=f(n−1)+f(n/2) при чётном n;f(n)=f(n−1) при нечётном n

2. Последовательно получаем: f(2)=1, f(3)=1, f(4)=2, f(5)=2, f(6)=3, f(7)=3, f(8)=5, f(9)=5, f(10)=7, f(11)=7, f(12)=10, f(13)=10, f(14)=13.

3. Из 14 в 30 можно попасть двумя способами, не посещая число 25: прибавлять 1 до 30 или перейти из 14 в 28 умножением на 2, а затем дважды прибавить 1. Путь через 25 исключается.
14→15→16→…→30;14→28→29→30

4. Выбор пути от 2 до 14 и пути от 14 до 30 независим, поэтому перемножаем количества вариантов.
13⋅2=26