Задание 13 ЕГЭ по информатике · 0CCF9C
С исключаемым пунктом траекторииПовышеннаяКЭС 3.1КЭС 3.2
Исполнитель Кантата преобразует число на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
3. Умножить на 3
Первая команда увеличивает число на экране на 1, вторая умножает его на 2, третья умножает его на 3.
Программа для исполнителя Кантата — это последовательность команд.
Сколько существует программ, для которых при исходном числе 5 результатом является число 43 и при этом траектория вычислений содержит число 9, но не содержит число 27?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 8, 16, 48.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
3. Умножить на 3
Первая команда увеличивает число на экране на 1, вторая умножает его на 2, третья умножает его на 3.
Программа для исполнителя Кантата — это последовательность команд.
Сколько существует программ, для которых при исходном числе 5 результатом является число 43 и при этом траектория вычислений содержит число 9, но не содержит число 27?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 8, 16, 48.
Показать ответ
19
Подсказки (3)
- Разбейте программу на путь от 5 до 9 и путь от 9 до 43.
- Для каждой суммы используйте рекуррентное правило: число путей в x равно сумме числа путей в x−1, x/2 и x/3, если соответствующие деления выполняются. Для числа 27 установите число путей, равным нулю.
- Из 5 в 9 можно попасть единственным способом: четыре раза выполнить команду «прибавить 1». Подсчёт путей от 9 до 43 с запретом числа 27 даёт 19.
Решение
1. Из числа 5 в число 9 можно попасть только последовательным прибавлением единицы: 5→6→7→8→9. Поэтому начальный участок программы единственный.
N(5→9)=1
2. Обозначим через f(x) число способов попасть из 9 в x, не проходя через 27. Для остальных чисел используем динамическое программирование: последний шаг мог быть прибавлением 1, умножением на 2 или умножением на 3.
f(x)=f(x−1)+[2∣x]fx2+[3∣x]fx3
3. Так как траектория не должна содержать число 27, полагаем f(27)=0. Последовательный подсчёт значений до 43 даёт f(42)=19, а поскольку 43 получается из 42 прибавлением 1, f(43)=19.
f(43)=f(42)=19
4. Учитываем единственный способ попасть из 5 в 9.
N=1⋅19=19
N(5→9)=1
2. Обозначим через f(x) число способов попасть из 9 в x, не проходя через 27. Для остальных чисел используем динамическое программирование: последний шаг мог быть прибавлением 1, умножением на 2 или умножением на 3.
f(x)=f(x−1)+[2∣x]fx2+[3∣x]fx3
3. Так как траектория не должна содержать число 27, полагаем f(27)=0. Последовательный подсчёт значений до 43 даёт f(42)=19, а поскольку 43 получается из 42 прибавлением 1, f(43)=19.
f(43)=f(42)=19
4. Учитываем единственный способ попасть из 5 в 9.
N=1⋅19=19
Частые ошибки
- Учитывать программы, в траектории которых встречается число 27.
- Забывать, что траектория состоит из результатов после выполнения команд, поэтому число 9 должно быть получено в процессе вычислений.
- Не учитывать все три возможные последние команды при подсчёте количества программ.
Похожие задания
13Исполнитель Вычислитель преобразует число на экране. У исполнителя есть две команды, которым присвоены…С исключаемым пунктом траектории · 24EE4813Исполнитель Вычислитель преобразует число на экране. У исполнителя есть две команды, которым присвоены…С исключаемым пунктом траектории · 0A180B13Исполнитель Вычислитель преобразует число на экране. У исполнителя есть две команды, которым присвоены…С исключаемым пунктом траектории · 69FC6613Исполнитель Кантата преобразует число на экране. У исполнителя есть три команды, которым присвоены номера: 1.…С исключаемым пунктом траектории · DE68DA13Прибавить 1 B. Прибавить 3 C. Умножить на 3 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · D5434F13Прибавить 2 B. Прибавить 3 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 765FFF13Вычесть 1 B. Вычесть 4 C. Найти целую часть от деления на 3 Программа для исполнителя — это…С исключаемым пунктом траектории · B17D7513Вычесть 1 B. Вычесть 3 C. Найти целую часть от деления на 2 Программа для исполнителя — это…С исключаемым пунктом траектории · DE167D
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.