Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть три команды, обозначенные латинскими буквами: A — прибавить 1; B — умножить на 2; C — возвести в квадрат. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 20, при этом траектория вычислений не содержит числа 11? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 4 траектория будет состоять из чисел 16, 32, 33.
Условие как в банке ФИПИ — открыть и сверить
| Исполнитель преобразует число на экране. У исполнителя есть три команды, которые обозначены латинскими буквами: A. Прибавить 1 B. Умножить на 2 C. Возвести в квадрат Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 20, при этом траектория вычислений не содержит числа 11? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы CBA при исходном числе 4 траектория будет состоять из чисел 16, 32, 33. | |||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Посчитайте количество способов получить каждое число от 2 до 20, исключив число 11 из траекторий.
2Наводящая — какие числа считатьуровень 2 из 3
Для числа $n$ рассмотрите предыдущие числа $n-1$, $n/2$ при чётном $n$ и $\sqrt{n}$, если $n$ является полным квадратом.
3Прямая — фактически решениеуровень 3 из 3
Получается рекуррентное правило: $f(n)=f(n-1)+f(n/2)+f(\sqrt{n})$, если соответствующие предыдущие числа существуют; при этом $f(11)=0$.