Подсчёт программ исполнителя
Исполнитель преобразует число на экране. У исполнителя есть две команды: 1. Прибавить 1. 2. Умножить на 2. Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
Условие как в банке ФИПИ — открыть и сверить
| Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14? Траектория вычислений программы это последовательность результатов выполнения всех команд программы. Например, для программы 121 | |||
| |
Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.
1Мягкая — с чего смотретьуровень 1 из 3
Разбейте программу на две части: от 2 до 14 и от 14 до 29.
2Наводящая — какие числа считатьуровень 2 из 3
Число программ до каждого значения можно считать по рекуррентному правилу: количество способов попасть в число равно сумме способов попасть в него из предыдущего числа командой «прибавить 1» и из числа вдвое меньшего командой «умножить на 2».
3Прямая — фактически решениеуровень 3 из 3
От 2 до 14 существует 13 программ. От 14 до 29 возможны только два варианта: 14, 15, ..., 29 и 14, 28, 29. Перемножьте количества вариантов.