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

1. Для подсчёта числа программ введём f(n) — количество способов получить число n из числа 2. Переходы к числу n могут выполняться командами A, B и C.
f(n)=f(n−1)+f(n−3)+{f(n/3),&n кратно 3,; 0,&иначе

2. При подсчёте значений до 16 исключаем число 12: количество путей, проходящих через 12, принимаем равным нулю. Получаем последовательность значений от 2 до 16: 1,1,1,2,4,5,7,12,17,24,0,17,41,43,60.
f(16)=60

3. Из числа 16 в число 20 можно попасть тремя способами: 16→17→18→19→20, 16→17→19→20 и 16→18→19→20.
g(20)=3

4. Каждая программа должна сначала попасть в 16, а затем из 16 в 20. Поэтому общее число программ равно произведению количества вариантов двух частей.
60⋅3=180