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

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

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

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

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

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

Например, для программы ABB при исходном числе 13 траектория состоит из чисел 11, 5, 2.

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

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

Разбейте программу на две части: путь от 30 до 12 и путь от 12 до 1.
Для числа n посчитайте количество путей до нужного значения по рекуррентному правилу: число путей из n равно сумме числа путей после команд A и B.
До числа 12 из 30 существует 3 пути, а от 12 до 1 — 13 путей. Так как число 12 достигается один раз, общее количество программ равно 3⋅13=39.

Решение

1. Так как обе команды уменьшают число, траектория может содержать число 12 только один раз. Поэтому любую подходящую программу можно однозначно разделить на путь от 30 до 12 и путь от 12 до 1.

2. Обозначим через f(n) количество способов получить число 12 из числа n. Для n>12 имеем f(n)=f(n−2)+f(⌊n/2⌋), поскольку последней выполненной командой может быть A или B. Последовательное вычисление даёт f(30)=3.
f(30)=f(28)+f(15)=3

3. Обозначим через g(n) количество способов получить число 1 из числа n. Аналогично, g(n)=g(n−2)+g(⌊n/2⌋), а g(1)=1. Вычисление значений от 1 до 12 даёт g(12)=13.
g(12)=g(10)+g(6)=9+4=13

4. Перемножаем количество вариантов первой и второй частей программы.
3⋅13=39

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

Не разделяют траекторию на две части относительно числа 12.
Считают только количество способов дойти от 30 до 12 или только от 12 до 1.
Забывают, что после команды B получается целая часть от деления на 2.

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

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

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

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

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

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

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

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

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

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

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