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