Задание 13 ЕГЭ по информатике · DE8735
С обязательным пунктом траекторииПовышеннаяКЭС 3.1КЭС 3.2
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавь 2
2. Умножь на 2
Первая из них увеличивает число на экране на 2, вторая увеличивает число на экране в два раза.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 52, и при этом траектория вычислений содержит число 18?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 121 при исходном числе 3 траектория будет состоять из чисел 5, 10, 12.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавь 2
2. Умножь на 2
Первая из них увеличивает число на экране на 2, вторая увеличивает число на экране в два раза.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 52, и при этом траектория вычислений содержит число 18?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 121 при исходном числе 3 траектория будет состоять из чисел 5, 10, 12.
Показать ответ
96
Подсказки (3)
- Разбейте программу на две части: от 1 до 18 и от 18 до 52.
- Для подсчёта числа программ используйте рекуррентную формулу: f(n)=f(n−2)+f(n/2) для чётных n, а для нечётных f(n)=f(n−2).
- Число программ из 1 в 18 равно 16, а из 18 в 52 — 6. Перемножьте эти количества.
Решение
1. Обозначим через f(n) количество программ, переводящих исходное число 1 в число n. Последняя команда программы может быть «Прибавь 2» или, если n чётно, «Умножь на 2». Поэтому f(n)=f(n−2)+f(n/2) для чётных n и f(n)=f(n−2) для нечётных n.
f(n)=f(n−2)+{f(n/2),&n чётно,; 0,&n нечётно.
2. Последовательно вычисляя значения от 1 до 18, получаем f(18)=16. Это число программ, которые переводят 1 в 18.
3. Теперь считаем число программ от 18 до 52 по той же рекуррентной формуле, положив g(18)=1 и g(n)=0 для n<18. Получаем g(52)=6.
4. Любая программа, траектория которой содержит 18, однозначно состоит из программы от 1 до 18 и программы от 18 до 52. Поэтому количества перемножаются.
16⋅6=96Частые ошибки
- Не учитывать обе возможные последние команды при чётном значении.
- Сложить, а не перемножить количество программ до 18 и после 18.
- Посчитать только программы из 1 в 52, не требуя прохождения через 18.
Похожие задания
131. Вычти 1 2. Найди целую часть от деления на 2 Первая из них уменьшает число на экране на 1, вторая заменяет…С обязательным пунктом траектории · C0C817131. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2.…С обязательным пунктом траектории · B3D150131. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2.…С обязательным пунктом траектории · D785AA131. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2.…С обязательным пунктом траектории13Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены…С обязательным пунктом траектории13Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которые обозначены…С обязательным пунктом траектории · DD7C7213Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены…С обязательным пунктом траектории · 31362113Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены…С обязательным пунктом траектории · 0288EE
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.