Precettore

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

С исключаемым пунктом траекторииВысокаяКЭС 3.1КЭС 3.2
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Прибавить 2
C. Умножить на 2

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

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

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

Например, для программы CBA при исходном числе 7 траектория будет состоять из чисел 14, 16, 17.

Показать ответ
308
Подсказки (3)
  1. Разделите программу на две части: путь от 3 до 8 и путь от 8 до 18. Для каждой конечной точки посчитайте число возможных программ.
  2. Если f(n) — число способов получить n, то f(n)=f(n−1)+f(n−2)+f(n/2) для чётных n, а для нечётных n последний член отсутствует. Для путей после числа 8 значение для числа 13 нужно считать равным нулю.
  3. От 3 до 8 существует 11 программ. От 8 до 18, не проходя через 13, существует 28 программ. Общее число программ равно 11⋅28=308.
Решение
1. Обозначим через f(n) число программ, переводящих число 3 в число n. Для получения n последняя команда может быть прибавлением 1, прибавлением 2 или умножением на 2.
f(n)=f(n−1)+f(n−2)+{f(n/2),&n чётно,; 0,&n нечётно.

2. Последовательно получаем значения до числа 8: f(3)=1, f(4)=1, f(5)=2, f(6)=4, f(7)=6, f(8)=11. Значит, существует 11 способов попасть из 3 в 8.

3. Теперь считаем число способов пройти от 8 до 18. Число 13 запрещено, поэтому полагаем g(13)=0, где g(n) — число способов попасть из 8 в n.
g(8)=1, g(9)=1, g(10)=2, g(11)=3, g(12)=5, g(13)=0, g(14)=5, g(15)=5, g(16)=11, g(17)=16, g(18)=28

4. Любая подходящая программа однозначно состоит из пути от 3 до 8 и пути от 8 до 18, не проходящего через 13.
11⋅28=308
Частые ошибки
  • Не учитывать запрет на появление числа 13 в траектории.
  • Считать только команды прибавления и забывать команду умножения на 2.
  • Сложить числа способов вместо их умножения при объединении двух частей пути.
ПредыдущееСледующееВсе задания №13

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

13Вычесть 1 B. Вычесть 4 C. Найти целую часть от деления на 3 Программа для исполнителя — это…С исключаемым пунктом траектории · 064F2013Прибавить 1 B. Умножить на 2 C. Возвести в квадрат Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 6DB42113Прибавить 1 B. Прибавить 2 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 6C2CD513Прибавить 1 B. Прибавить 3 C. Умножить на 3 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 209B5313Прибавить 1 B. Прибавить 3 C. Умножить на 3 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 9229A513Прибавить 2 B. Прибавить 3 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 0B189413Прибавить 1 B. Умножить на 2 C. Умножить на 3 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 63A59E13Прибавить 1 B. Умножить на 2 C. Умножить на 3 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 18C08F

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

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

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

Подбор репетитора

Напишите, что нужно, — команда Precettore подберёт репетитора и свяжется с вами.

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

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

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