Задание 13 ЕГЭ по информатике · D5434F
С исключаемым пунктом траекторииВысокаяКЭС 3.1КЭС 3.2
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Прибавить 3
C. Умножить на 3
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 3 результатом является число 20, при этом траектория вычислений содержит число 14 и не содержит 15?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы CBA при исходном числе 7 траектория будет состоять из чисел 21, 24, 25.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Прибавить 3
C. Умножить на 3
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 3 результатом является число 20, при этом траектория вычислений содержит число 14 и не содержит 15?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы CBA при исходном числе 7 траектория будет состоять из чисел 21, 24, 25.
Показать ответ
92
Подсказки (3)
- Разбейте программу на две части: путь от 3 до 14 и путь от 14 до 20.
- Для подсчёта числа путей используйте рекуррентное соотношение: количество путей в число n равно сумме количеств путей в числа n−1, n−3 и n/3, если соответствующий переход возможен.
- Число путей из 3 в 14 равно 46. Из 14 в 20 без прохождения через 15 существует 2 пути, поэтому общее количество программ равно 46⋅2.
Решение
1. Обозначим через f(n) количество программ, переводящих число 3 в число n. Для последнего шага программы возможны команды A, B и C, поэтому учитываются переходы из n−1, n−3 и n/3. f(n)=f(n−1)+f(n−3)+f(n/3) 2. Последовательно вычисляя значения от 3 до 14, получаем количество программ, переводящих 3 в 14: f(14)=46 3. Теперь считаем программы от 14 до 20, не проходящие через 15. Возможны два пути: 14→17→20 и 14→17→18→19→20. g(20)=2 4. Так как число 14 должно встретиться в траектории, любую подходящую программу можно однозначно разбить на путь от 3 до 14 и путь от 14 до 20. 46⋅2=92
Частые ошибки
- Учитывают программы, проходящие через 15.
- Забывают, что число 14 должно быть результатом выполнения команды и входить в траекторию.
- Складывают количества программ вместо их перемножения.
Похожие задания
13Исполнитель Вычислитель преобразует число на экране. У исполнителя есть две команды, которым присвоены…С исключаемым пунктом траектории · 0A180B13Исполнитель Вычислитель преобразует число на экране. У исполнителя есть две команды, которым присвоены…С исключаемым пунктом траектории · 69FC6613Исполнитель Кантата преобразует число на экране. У исполнителя есть три команды, которым присвоены номера: 1.…С исключаемым пунктом траектории · DE68DA13Исполнитель Кантата преобразует число на экране. У исполнителя есть три команды, которым присвоены номера: 1.…С исключаемым пунктом траектории · 0CCF9C13Прибавить 2 B. Прибавить 3 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 765FFF13Вычесть 1 B. Вычесть 4 C. Найти целую часть от деления на 3 Программа для исполнителя — это…С исключаемым пунктом траектории · B17D7513Вычесть 1 B. Вычесть 3 C. Найти целую часть от деления на 2 Программа для исполнителя — это…С исключаемым пунктом траектории · DE167D13Прибавить 1 B. Прибавить 2 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · CD3814
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.