Задание 13 ЕГЭ по информатике · CD3814
С исключаемым пунктом траекторииВысокаяКЭС 3.1КЭС 3.2
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Прибавить 2
C. Умножить на 2
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 17, при этом траектория вычислений содержит число 9 и не содержит 12?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы CBA при исходном числе 7 траектория будет состоять из чисел 14, 16, 17.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Прибавить 2
C. Умножить на 2
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 17, при этом траектория вычислений содержит число 9 и не содержит 12?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы CBA при исходном числе 7 траектория будет состоять из чисел 14, 16, 17.
Показать ответ
350
Подсказки (3)
- Разбейте программу в точке, когда впервые получено число 9. Сколько способов ведёт от 2 к 9 и сколько — от 9 к 17 без числа 12?
- Для подсчёта числа программ используйте рекуррентное соотношение: число способов попасть в n равно сумме способов попасть в n−1, n−2 и n/2, если n чётно.
- Получается N2→9=35, а число способов пройти от 9 до 17, не попадая в 12, равно 10. Перемножьте эти количества.
Решение
1. Так как все команды увеличивают число, число 9 в траектории достигается ровно один раз. Поэтому программы можно разбить на две независимые части: от 2 до 9 и от 9 до 17. 2. Обозначим через f(n) число программ, переводящих 2 в n. Для последнего шага возможны команды A, B и C, поэтому f(n)=f(n−1)+f(n−2)+f(n/2) для чётного n, а для нечётного n последнее слагаемое отсутствует. 3. Последовательно получаем: f(2)=1, f(3)=1, f(4)=3, f(5)=4, f(6)=8, f(7)=12, f(8)=23, f(9)=35. 4. Теперь считаем число способов перейти от 9 к 17, не попадая в 12. Значения числа способов для конечных чисел: g(9)=1, g(10)=1, g(11)=2, g(12)=0, g(13)=2, g(14)=2, g(15)=4, g(16)=6, g(17)=10. 5. Общее число программ равно произведению количества вариантов двух частей: 35⋅10=350.
Частые ошибки
- Учитывают программы, проходящие через число 12.
- Не разбивают траекторию в точке 9.
- Забывают, что команда C может быть последним шагом только при чётном конечном числе.
Похожие задания
13Прибавить 1 B. Прибавить 3 C. Умножить на 3 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · D5434F13Прибавить 2 B. Прибавить 3 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 765FFF13Вычесть 1 B. Вычесть 4 C. Найти целую часть от деления на 3 Программа для исполнителя — это…С исключаемым пунктом траектории · B17D7513Вычесть 1 B. Вычесть 3 C. Найти целую часть от деления на 2 Программа для исполнителя — это…С исключаемым пунктом траектории · DE167D13Вычесть 1 B. Вычесть 4 C. Найти целую часть от деления на 3 Программа для исполнителя — это…С исключаемым пунктом траектории · 064F2013Прибавить 1 B. Умножить на 2 C. Возвести в квадрат Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 6DB42113Прибавить 1 B. Прибавить 2 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 6C2CD513Прибавить 1 B. Прибавить 3 C. Умножить на 3 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 209B53
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.