Задание 13 ЕГЭ по информатике · 18C08F
С исключаемым пунктом траекторииВысокаяКЭС 3.3
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Умножить на 2
C. Умножить на 3
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является 39 и при этом траектория вычислений не содержит числа 14?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы ABC при исходном числе 7 траектория состоит из чисел 8, 16, 48.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Умножить на 2
C. Умножить на 3
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является 39 и при этом траектория вычислений не содержит числа 14?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы ABC при исходном числе 7 траектория состоит из чисел 8, 16, 48.
Показать ответ
188
Подсказки (3)
- Рассматривайте количество способов получить каждое число из предыдущих чисел.
- Для числа n возможны последние команды: прибавление 1 из n−1, умножение на 2 из n/2 и умножение на 3 из n/3.
- Вычислите значения динамически, положив f(14)=0: f(n)=f(n−1)+f(n/2)+f(n/3) для целых делений, а затем найдите f(39).
Решение
1. Пусть f(n) — количество программ, переводящих число 2 в число n без появления числа 14 в траектории. Начальное значение: f(2)=1, а для запрещённого числа полагаем f(14)=0. 2. Чтобы получить число n, последней могла быть команда прибавления 1, умножения на 2 или умножения на 3. Поэтому учитываются значения f(n−1), f(n/2) и f(n/3) только при целочисленном делении. 3. Последовательное вычисление даёт: f(12)=15, f(13)=15, f(14)=0, f(15)=2, f(18)=19, f(21)=32, f(24)=62, f(27)=84, f(30)=95, f(33)=112, f(36)=154, f(39)=188. 4. Следовательно, количество подходящих программ равно f(39)=188.
Частые ошибки
- Не исключают программы, в траектории которых встречается число 14.
- Учитывают переходы делением на 2 или 3, даже если результат не является целым числом.
- Считают только различные траектории, а не программы; разные последовательности команд должны учитываться отдельно.
Похожие задания
13Прибавить 1 B. Прибавить 2 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 8F2A5313Прибавить 1 B. Прибавить 3 C. Умножить на 3 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 9229A513Прибавить 2 B. Прибавить 3 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 0B189413Прибавить 1 B. Умножить на 2 C. Умножить на 3 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 63A59E13Прибавить 1 B. Прибавить 2 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · A1A48913Вычесть 1 B. Вычесть 3 C. Найти целую часть от деления на 2 Программа для исполнителя - это…С исключаемым пунктом траектории13Прибавить 1 B. Умножить на 2 C. Умножить на 3 Программа для исполнителя – это последовательность команд.…С исключаемым пунктом траектории13Вычесть 1 B. Вычесть 4 C. Найти целую часть от деления на 3 Программа для исполнителя – это…С исключаемым пунктом траектории
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.