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

1. Обозначим через f(n) количество программ, переводящих число n в число 1. Для n>1 последняя команда может быть A или B, поэтому используем рекуррентный подсчёт.
f(n)=f(n−1)+f(⌊n/2⌋),f(1)=1

2. Последовательно вычисляя значения, получаем:
f(1),…,f(10)=1,2,3,5,7,10,13,18,23,30

3. Следовательно, количество программ, переводящих 10 в 1, равно 30.

4. Теперь считаем количество путей из 32 в 10. Пусть g(n) — число путей из n в 10, причём g(10)=1. Для чисел больше 10:
g(n)=g(n−1)+g(⌊n/2⌋),g(k)=0 при k<10

5. Вычисления от 10 до 32 дают g(32)=14. Каждая программа, проходящая через 10, однозначно состоит из пути от 32 до 10 и пути от 10 до 1.
14⋅30=420