Задание 13 ЕГЭ по информатике · 064F20
С исключаемым пунктом траекторииВысокаяКЭС 3.3
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть 1
B. Вычесть 4
C. Найти целую часть от деления на 3
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 19 результатом является число 2, при этом траектория вычислений не содержит числа 9 и содержит 15?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы СBА при исходном числе 22 траектория состоит из чисел 7, 3, 2.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть 1
B. Вычесть 4
C. Найти целую часть от деления на 3
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 19 результатом является число 2, при этом траектория вычислений не содержит числа 9 и содержит 15?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы СBА при исходном числе 22 траектория состоит из чисел 7, 3, 2.
Показать ответ
70
Подсказки (3)
- Рассматривайте каждое промежуточное число как состояние. Исключайте переходы, приводящие к числу 9, и отдельно учитывайте, было ли достигнуто число 15.
- Для подсчёта используйте динамическое программирование по состояниям (n,f), где n — текущее число, а f показывает, встречалось ли уже число 15.
- Переберите допустимые переходы из 19 до 2 командами A, B и C, не добавляя траектории с числом 9. Сумма для состояний, заканчивающихся в 2 и содержащих 15, равна 70.
Решение
1. Из каждого текущего числа рассматриваем три возможных перехода: вычитание 1, вычитание 4 и деление на 3 с взятием целой части. Переходы, после которых получается 9, не учитываем.
A(n)=n−1,B(n)=n−4,C(n)=⌊n3⌋
2. Для каждого числа храним два значения: количество способов попасть в него без числа 9 и количество способов попасть в него с уже встречавшимся числом 15. При переходе в 15 способ переносится во вторую группу.
3. Последовательно заполняя значения для состояний, достижимых из 19, и суммируя только пути, заканчивающиеся в 2, получаем количество программ, траектория которых содержит 15 и не содержит 9.
A(n)=n−1,B(n)=n−4,C(n)=⌊n3⌋
2. Для каждого числа храним два значения: количество способов попасть в него без числа 9 и количество способов попасть в него с уже встречавшимся числом 15. При переходе в 15 способ переносится во вторую группу.
3. Последовательно заполняя значения для состояний, достижимых из 19, и суммируя только пути, заканчивающиеся в 2, получаем количество программ, траектория которых содержит 15 и не содержит 9.
Частые ошибки
- Не учитывать число 15, если оно является промежуточным результатом.
- Отбрасывать программы только при исходном числе 9, хотя 9 может появиться позже в траектории.
- Считать команды A, B и C одинаковыми при одинаковом результате.
Похожие задания
13Прибавить 2 B. Прибавить 3 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 765FFF13Вычесть 1 B. Вычесть 4 C. Найти целую часть от деления на 3 Программа для исполнителя — это…С исключаемым пунктом траектории · B17D7513Вычесть 1 B. Вычесть 3 C. Найти целую часть от деления на 2 Программа для исполнителя — это…С исключаемым пунктом траектории · DE167D13Прибавить 1 B. Прибавить 2 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · CD381413Прибавить 1 B. Умножить на 2 C. Возвести в квадрат Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 6DB42113Прибавить 1 B. Прибавить 2 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 6C2CD513Прибавить 1 B. Прибавить 3 C. Умножить на 3 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 209B5313Прибавить 1 B. Прибавить 2 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 8F2A53
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.