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

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

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

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

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

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

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

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

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

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

Сначала посчитайте количество способов получить каждое число от 1 до 10.
Для числа n количество способов равно сумме способов получить n−1 и, если n чётное, n/2.
До числа 10 можно добраться 14 способами. Из 10 в 21 без попадания в 18 можно перейти только по маршруту 10→20→21.

Решение

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

2. Последовательно получаем значения: 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 необходимо попасть в 21, не проходя через 18. Последовательность прибавлений от 10 до 21 невозможна, поскольку содержит 18. Единственный допустимый путь: 10→20→21.

4. Каждому из 14 способов достичь числа 10 соответствует ровно один допустимый способ продолжить программу до 21.
14⋅1=14

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

Учитывают программы, в которых число 18 встречается до числа 10.
Считают путь последовательного прибавления от 10 до 21 допустимым, хотя он проходит через 18.
Забывают, что после достижения 10 остаётся только один допустимый маршрут до 21.

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

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

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

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

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

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

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

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

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

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

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