Задание 13 ЕГЭ по информатике · 8271BC
С обязательным пунктом траекторииВысокаяКЭС 3.1КЭС 3.2
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Вычти 2
B. Найди целую часть от деления на 2
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 38 результатом является число 2, и при этом траектория вычислений содержит число 16?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы ABB при исходном числе 13 траектория состоит из чисел 11, 5, 2.
У исполнителя есть две команды, которые обозначены латинскими буквами:
A. Вычти 2
B. Найди целую часть от деления на 2
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 38 результатом является число 2, и при этом траектория вычислений содержит число 16?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы ABB при исходном числе 13 траектория состоит из чисел 11, 5, 2.
Показать ответ
36
Подсказки (3)
- Разбейте программу в момент первого достижения числа 16: отдельно посчитайте пути из 38 в 16 и из 16 в 2.
- Для числа n число подходящих программ можно находить рекуррентно: количество путей из n равно сумме количеств путей после команд A и B.
- Из 38 в 16 существует 3 программы, а из 16 в 2 — 12 программ. Перемножьте эти количества: 3⋅12=36.
Решение
1. Рассмотрим сначала программы, переводящие число 38 в число 16. Обозначим через f(n) количество способов попасть из n в 16. Для каждого числа учитываем переходы n→n−2 и n→⌊n/2⌋.
f(n)=f(n−2)+f⌊n2⌋
2. Последовательное вычисление значений от 16 до 38 даёт: f(18)=1, f(20)=1, f(22)=1, f(24)=1, f(26)=1, f(28)=1, f(30)=1, f(32)=2, f(34)=2, f(36)=3, f(38)=3. Значит, из 38 в 16 можно попасть 3 способами.
3. Теперь обозначим через g(n) количество способов попасть из n в 2. По той же рекуррентной формуле получаем g(2)=1, g(4)=2, g(6)=2, g(8)=4, g(10)=5, g(12)=7, g(14)=8, g(16)=12.
4. Любая программа, проходящая через 16, составляется из программы перехода 38 в 16 и программы перехода 16 в 2. Поэтому количества способов перемножаются.
3⋅12=36
f(n)=f(n−2)+f⌊n2⌋
2. Последовательное вычисление значений от 16 до 38 даёт: f(18)=1, f(20)=1, f(22)=1, f(24)=1, f(26)=1, f(28)=1, f(30)=1, f(32)=2, f(34)=2, f(36)=3, f(38)=3. Значит, из 38 в 16 можно попасть 3 способами.
3. Теперь обозначим через g(n) количество способов попасть из n в 2. По той же рекуррентной формуле получаем g(2)=1, g(4)=2, g(6)=2, g(8)=4, g(10)=5, g(12)=7, g(14)=8, g(16)=12.
4. Любая программа, проходящая через 16, составляется из программы перехода 38 в 16 и программы перехода 16 в 2. Поэтому количества способов перемножаются.
3⋅12=36
Частые ошибки
- Складывают, а не перемножают количество путей до 16 и после 16.
- Не учитывают обе команды при построении рекуррентной формулы.
- Считают программы, которые достигают числа 2, но не проходят через 16.
Похожие задания
13Исполнитель М17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены…С обязательным пунктом траектории · B976F313Исполнитель М17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены…С обязательным пунктом траектории · 94AB7713Исполнитель Соло преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1.…С обязательным пунктом траектории · 2FC2EB13У исполнителя есть две команды, которые обозначены латинскими буквами: A. Вычти 2 B. Найди целую часть от…С обязательным пунктом траектории · 6CF4FF13У исполнителя есть две команды, которые обозначены латинскими буквами: A. Вычти 2 B. Найди целую часть от…С обязательным пунктом траектории · B9331913У исполнителя есть две команды, которые обозначены латинскими буквами: A. Вычти 2 B. Найди целую часть от…С обязательным пунктом траектории · 8D4E1113У исполнителя есть две команды, которые обозначены латинскими буквами: A. Вычти 1 B. Найди целую часть от…С обязательным пунктом траектории · E3542213У исполнителя есть две команды, которые обозначены латинскими буквами: A. Вычти 1 B. Найди целую часть от…С обязательным пунктом траектории · 20B163
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.