Задание 13 ЕГЭ по информатике · 63A59E
С исключаемым пунктом траекторииВысокаяКЭС 3.1КЭС 3.2
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Умножить на 2
C. Умножить на 3
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 25, при этом траектория вычислений содержит число 11 и не содержит 15?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы CBA при исходном числе 7 траектория будет состоять из чисел 21, 42, 43.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Умножить на 2
C. Умножить на 3
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 25, при этом траектория вычислений содержит число 11 и не содержит 15?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы CBA при исходном числе 7 траектория будет состоять из чисел 21, 42, 43.
Показать ответ
46
Подсказки (3)
- Разбейте программу на участок от 1 до 11 и участок от 11 до 25.
- Для каждого числа посчитайте количество способов получить его командами +1, ×2 и ×3, исключая траектории, проходящие через 15.
- Сначала найдите число путей из 1 в 11, затем число допустимых продолжений из 11 в 25 и перемножьте полученные количества.
Решение
1. Введём динамическое программирование: для каждого числа считаем количество программ, которые приводят к нему. Последний шаг в такую точку мог быть выполнен командами +1, ×2 или ×3. 2. Посчитаем количество способов попасть из 1 в 11. Для числа n учитываются переходы из n−1, n/2 и n/3, если соответствующие значения являются целыми. 3. Затем подсчитаем допустимые продолжения от 11 до 25, исключив все пути, в которых встречается число 15. 4. Перемножение количества способов попасть в 11 и количества допустимых продолжений до 25 даёт число программ, удовлетворяющих условию.
Частые ошибки
- Учитывают программы, проходящие через число 15.
- Считают только одну последовательность команд, не учитывая разные варианты порядка команд.
- Не разделяют траекторию на участки до и после числа 11.
Похожие задания
13Прибавить 1 B. Прибавить 3 C. Умножить на 3 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 209B5313Прибавить 1 B. Прибавить 2 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 8F2A5313Прибавить 1 B. Прибавить 3 C. Умножить на 3 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 9229A513Прибавить 2 B. Прибавить 3 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 0B189413Прибавить 1 B. Умножить на 2 C. Умножить на 3 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 18C08F13Прибавить 1 B. Прибавить 2 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · A1A48913Вычесть 1 B. Вычесть 3 C. Найти целую часть от деления на 2 Программа для исполнителя - это…С исключаемым пунктом траектории13Прибавить 1 B. Умножить на 2 C. Умножить на 3 Программа для исполнителя – это последовательность команд.…С исключаемым пунктом траектории
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.