Задание 13 ЕГЭ по информатике · DE167D
С исключаемым пунктом траекторииВысокаяКЭС 3.3
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть 1
B. Вычесть 3
C. Найти целую часть от деления на 2
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 19 результатом является число 3, при этом траектория вычислений не содержит числа 9 и содержит 12?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы CBA при исходном числе 13 траектория состоит из чисел 6, 3, 2.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть 1
B. Вычесть 3
C. Найти целую часть от деления на 2
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 19 результатом является число 3, при этом траектория вычислений не содержит числа 9 и содержит 12?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы CBA при исходном числе 13 траектория состоит из чисел 6, 3, 2.
Показать ответ
153
Подсказки (3)
- Разбейте программу на две части: путь от 19 до 12 и путь от 12 до 3.
- Используйте динамическое программирование: для каждого числа считайте количество способов попасть в него командами A, B и C, исключая переходы в число 9.
- Заполните таблицу количества путей от 19 до 12 и от 12 до 3, затем перемножьте число способов прохождения через 12. Получается 153.
Решение
1. Так как все команды уменьшают число, каждую программу можно рассматривать как путь от 19 к 3. Условие о наличии числа 12 позволяет разделить путь на участок от 19 до 12 и участок от 12 до 3. 2. Для каждого числа вычисляем количество способов попасть в него командами A, B и C. Переходы, приводящие в число 9, исключаем; переход C из числа n приводит в число ⌊n/2⌋. 3. Суммирование количества допустимых путей для всех возможных промежуточных чисел с обязательным прохождением через 12 даёт общее число программ. 4. После выполнения динамического подсчёта количество программ равно 153.
Частые ошибки
- Не учитывать, что число 12 должно входить в траекторию вычислений.
- Разрешать переход в число 9.
- Забывать, что команда C выполняет целочисленное деление на 2.
- Считать только различные траектории, а не последовательности команд.
Похожие задания
13Исполнитель Кантата преобразует число на экране. У исполнителя есть три команды, которым присвоены номера: 1.…С исключаемым пунктом траектории · 0CCF9C13Прибавить 1 B. Прибавить 3 C. Умножить на 3 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · D5434F13Прибавить 2 B. Прибавить 3 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 765FFF13Вычесть 1 B. Вычесть 4 C. Найти целую часть от деления на 3 Программа для исполнителя — это…С исключаемым пунктом траектории · B17D7513Прибавить 1 B. Прибавить 2 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · CD381413Вычесть 1 B. Вычесть 4 C. Найти целую часть от деления на 3 Программа для исполнителя — это…С исключаемым пунктом траектории · 064F2013Прибавить 1 B. Умножить на 2 C. Возвести в квадрат Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 6DB42113Прибавить 1 B. Прибавить 2 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 6C2CD5
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.