Задание 13 ЕГЭ по информатике · B17D75

С исключаемым пунктом траекторииВысокаяКЭС 3.3

Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Вычесть 1
B. Вычесть 4
C. Найти целую часть от деления на 3

Программа для исполнителя — это последовательность команд.

Сколько существует программ, для которых при исходном числе 19 результатом является число 2, при этом траектория вычислений не содержит числа 7 и содержит 13?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.

Например, для программы СBА при исходном числе 22 траектория состоит из чисел 7, 3, 2.

Показать ответ

Подсказки (3)

Разделите траекторию на два участка: от 19 до 13 и от 13 до 2. Число 7 должно быть запрещено на обоих участках.
Для каждого числа посчитайте количество способов попасть в него: используйте переходы из чисел n+1, n+4 и таких чисел m, для которых ⌊m/3⌋=n.
До числа 13 можно добраться из 19 четырьмя способами, а из 13 до 2 — семнадцатью способами. Перемножьте эти количества.

Решение

1. Так как все команды уменьшают число, траектория обязательно проходит через 13 ровно один раз. Поэтому количество подходящих программ равно произведению числа способов попасть из 19 в 13 и числа способов попасть из 13 в 2, избегая числа 7.

2. Обозначим через f(n) число способов попасть из n в 13. Для n>13 учитываем переходы n→n−1, n→n−4 и n→⌊n/3⌋. Число 7 не может быть промежуточным состоянием.
f(13)=1,f(14)=1,f(15)=1,f(16)=1,f(17)=2,f(18)=3,f(19)=4

3. Следовательно, из 19 в 13 можно попасть четырьмя способами.

4. Теперь обозначим через g(n) число способов попасть из n в 2, не проходя через 7. При g(2)=1, а для остальных допустимых состояний используем те же три перехода.
g(3)=1, g(4)=1, g(5)=1, g(6)=3, g(7)=0, g(8)=2, g(9)=4, g(10)=8, g(11)=9, g(12)=12, g(13)=17

5. Из 13 в 2 существует 17 допустимых способов. Общее число программ равно:
4⋅17=68

Частые ошибки

Не исключают траектории, проходящие через число 7.
Считают только число способов попасть из 19 в 2, не требуя прохождения через 13.
Забывают, что команда C задаёт переход к ⌊n/3⌋.

Предыдущее Следующее Все задания №13

Нужен репетитор по информатике?

Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.

Репетиторы по информатике

Готовьтесь к ЕГЭ по информатике в Precettore

Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.

Начать бесплатно Я репетитор

Задание 13 ЕГЭ по информатике · B17D75

Похожие задания

Нужен репетитор по информатике?

Готовьтесь к ЕГЭ по информатике в Precettore