Задание 13 ЕГЭ по информатике · 6C2CD5
С исключаемым пунктом траекторииВысокаяКЭС 3.1КЭС 3.2
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Прибавить 2
C. Умножить на 2
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 4 результатом является число 19, при этом траектория вычислений содержит число 15 и не содержит 6?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы CBA при исходном числе 7 траектория будет состоять из чисел 14, 16, 17.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Прибавить 2
C. Умножить на 2
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 4 результатом является число 19, при этом траектория вычислений содержит число 15 и не содержит 6?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы CBA при исходном числе 7 траектория будет состоять из чисел 14, 16, 17.
Показать ответ
320
Подсказки (3)
- Разделите программу в момент первого достижения числа 15. Все команды увеличивают число, поэтому после достижения 15 вернуться к меньшему числу невозможно.
- Для каждого числа посчитайте количество способов попасть в него из 4, исключив переходы через 6. Используйте рекуррентное соотношение: количество способов попасть в n равно сумме способов попасть в n−1, n−2 и, если n чётное, в n/2.
- До числа 15 существует 64 допустимых программы, а из 15 в 19 — 5 программ. Перемножьте эти количества.
Решение
1. Обозначим через f(n) число способов получить число n из 4, не попадая в 6. Для числа 6 полагаем f(6)=0, так как траектория не должна содержать 6. 2. Последовательно получаем значения: f(4)=1, f(5)=1, f(6)=0, f(7)=1, f(8)=2, f(9)=3, f(10)=6, f(11)=9, f(12)=15, f(13)=24, f(14)=40, f(15)=64. 3. После достижения 15 считаем способы попасть из 15 в 19. Получаем: g(15)=1, g(16)=1, g(17)=2, g(18)=3, g(19)=5. 4. Каждая допустимая программа состоит из допустимого пути из 4 в 15 и пути из 15 в 19, поэтому количества перемножаются. 64⋅5=320
Частые ошибки
- Учитывают программы, проходящие через число 6.
- Считают только последовательности прибавлений и не учитывают команду умножения на 2.
- Складывают количество путей вместо перемножения количества частей пути до 15 и после 15.
Похожие задания
13Вычесть 1 B. Вычесть 3 C. Найти целую часть от деления на 2 Программа для исполнителя — это…С исключаемым пунктом траектории · DE167D13Прибавить 1 B. Прибавить 2 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · CD381413Вычесть 1 B. Вычесть 4 C. Найти целую часть от деления на 3 Программа для исполнителя — это…С исключаемым пунктом траектории · 064F2013Прибавить 1 B. Умножить на 2 C. Возвести в квадрат Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 6DB42113Прибавить 1 B. Прибавить 3 C. Умножить на 3 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 209B5313Прибавить 1 B. Прибавить 2 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 8F2A5313Прибавить 1 B. Прибавить 3 C. Умножить на 3 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 9229A513Прибавить 2 B. Прибавить 3 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 0B1894
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.