Задание 13 ЕГЭ по информатике · 20B163
С обязательным пунктом траекторииВысокаяКЭС 3.1КЭС 3.2
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Вычти 1
B. Найди целую часть от деления на 2
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 30 результатом является число 1 и при этом траектория вычислений содержит число 8?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы ABB при исходном числе 10 траектория состоит из чисел 9, 4, 2.
У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Вычти 1
B. Найди целую часть от деления на 2
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 30 результатом является число 1 и при этом траектория вычислений содержит число 8?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы ABB при исходном числе 10 траектория состоит из чисел 9, 4, 2.
Показать ответ
288
Подсказки (3)
- Разбейте программу в момент первого получения числа 8: посчитайте число способов попасть из 30 в 8 и число способов попасть из 8 в 1.
- Для подсчёта используйте рекуррентное соотношение f(n)=f(n−1)+f(⌊n/2⌋): последняя команда программы может быть A или B.
- Получается 16 способов перейти из 30 в 8 и 18 способов перейти из 8 в 1. Общее число программ равно 16⋅18.
Решение
1. Обозначим через f(n) число программ, переводящих число n в заданное конечное число. Последняя команда может быть A, тогда перед ней было n−1, или B, тогда перед ней было ⌊n/2⌋. f(n)=f(n−1)+f(⌊n/2⌋) 2. Для перехода из 30 в 8 вычисление рекуррентно даёт: f(8)=1, затем f(9),…,f(15)=1, f(16)=2, и далее f(30)=16. 3. Для перехода из 8 в 1 получаем последовательность значений: f(1)=1, f(2)=2, f(3)=3, f(4)=5, f(5)=7, f(6)=10, f(7)=13, f(8)=18. 4. Так как все команды уменьшают число, после получения 8 вернуться к нему невозможно. Поэтому части программы можно выбирать независимо. 16⋅18=288
Частые ошибки
- Не учитывать, что число 8 должно появиться именно в траектории, то есть после выполнения команды.
- Сложить числа способов вместо их перемножения.
- Забыть, что команда B выполняет целочисленное деление на 2.
Похожие задания
13У исполнителя есть две команды, которые обозначены латинскими буквами: A. Вычти 2 B. Найди целую часть от…С обязательным пунктом траектории · 8271BC13У исполнителя есть две команды, которые обозначены латинскими буквами: A. Вычти 2 B. Найди целую часть от…С обязательным пунктом траектории · B9331913У исполнителя есть две команды, которые обозначены латинскими буквами: A. Вычти 2 B. Найди целую часть от…С обязательным пунктом траектории · 8D4E1113У исполнителя есть две команды, которые обозначены латинскими буквами: A. Вычти 1 B. Найди целую часть от…С обязательным пунктом траектории · E3542213У исполнителя есть две команды, которые обозначены латинскими буквами: A. Вычти 1 B. Найди целую часть от…С обязательным пунктом траектории · ACD638131. Вычти 1 2. Найди целую часть от деления на 2 Первая из них уменьшает число на экране на 1, вторая заменяет…С обязательным пунктом траектории · 9A65F5131. Вычти 1 2. Найди целую часть от деления на 2 Первая из них уменьшает число на экране на 1, вторая заменяет…С обязательным пунктом траектории · 43B305131. Вычти 1 2. Найди целую часть от деления на 2 Первая из них уменьшает число на экране на 1, вторая заменяет…С обязательным пунктом траектории · C2EB01
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.