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

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

Исполнитель Вычислитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2.

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

Сколько существует программ, для которых при исходном числе 1 результатом является число 22 и при этом траектория вычислений содержит число 10 и не содержит числа 15?

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

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

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

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

Разбейте программу на две части: путь от 1 до 10 и путь от 10 до 22.
Для подсчёта числа путей используйте рекуррентное соотношение: количество путей в число n равно сумме количества путей в n−1 и, если n чётное, в n/2.
До числа 10 существует 14 программ. Из числа 10 в число 22 существует 3 пути, но один из них проходит через 15, поэтому подходят 2 пути. Итог: 14⋅2=28.

Решение

1. Обозначим через f(n) количество программ, переводящих число 1 в число n. Последняя команда перед получением n могла быть прибавлением 1 или умножением на 2.
f(n)=f(n−1)+f(n/2) при чётном n;f(n)=f(n−1) при нечётном n

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

3. Так как все команды увеличивают число, после прохождения числа 10 траектория уже не может вернуться к нему. Посчитаем пути от 10 до 22. Всего их 3: два проходят через последовательный переход к 20 и один использует переход 11→22.
g(22)=g(21)+g(11)=2+1=3

4. Один из трёх путей проходит через число 15, поэтому допустимых путей от 10 до 22 остаётся 2.
3−1=2

5. Перемножаем количество вариантов первой и второй частей программы.
14⋅2=28

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

Не учитывать, что для числа 2 существуют две разные последние команды: прибавить 1 и умножить на 2.
Не разделять траекторию на участок от 1 до 10 и участок от 10 до 22.
Не исключить путь, проходящий через число 15.

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

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

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

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

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

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

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

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

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

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

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