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