Задание 13 ЕГЭ по информатике · E9000D
С обязательным пунктом траекторииВысокаяКЭС 3.1КЭС 3.2
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Вычти 1
2. Найди целую часть от деления на 2
Первая из них уменьшает число на экране на 1, вторая заменяет число на экране на целую часть от деления числа на 2.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 32 результатом является число 1, и при этом траектория вычислений содержит число 11?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 122 при исходном числе 10 траектория состоит из чисел 9, 4, 2.
У исполнителя есть две команды, которым присвоены номера:
1. Вычти 1
2. Найди целую часть от деления на 2
Первая из них уменьшает число на экране на 1, вторая заменяет число на экране на целую часть от деления числа на 2.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 32 результатом является число 1, и при этом траектория вычислений содержит число 11?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 122 при исходном числе 10 траектория состоит из чисел 9, 4, 2.
Показать ответ
444
Подсказки (3)
- Разбейте программу в месте, где впервые появляется число 11: сначала посчитайте пути от 32 до 11, затем — от 11 до 1.
- Для числа n число программ до фиксированного результата можно считать рекуррентно: количество путей из n равно сумме количеств путей из n-1 и из ⌊n/2⌋.
- Получается 12 программ из 32 в 11 и 37 программ из 11 в 1. Общее число программ равно 12⋅37=444.
Решение
1. Обозначим через f(n) количество программ, переводящих число n в число 1. Для числа 1 имеем f(1)=1. Для остальных чисел последняя команда перед переходом из n может быть применена после получения числа n−1 или числа ⌊n/2⌋, поэтому f(n)=f(n−1)+f(⌊n/2⌋) 2. Последовательно вычисляя значения от 1 до 11, получаем f(11)=37. 3. Теперь обозначим через g(n) количество программ, переводящих число n в число 11. Для n<11 имеем g(n)=0, а g(11)=1. По той же рекуррентной формуле получаем: g(22)=2, g(23)=3, g(24)=4, ..., g(32)=12. 4. Любая программа, траектория которой содержит 11, однозначно распадается на часть от 32 до 11 и часть от 11 до 1. Поэтому количества способов перемножаются. 12⋅37=444
Частые ошибки
- Складывают, а не перемножают количество программ до 11 и после 11.
- Не учитывают оба возможных перехода: вычитание 1 и деление на 2 с взятием целой части.
- Считают только один способ достижения числа 11.
Похожие задания
13У исполнителя есть две команды, которые обозначены латинскими буквами: A. Вычти 1 B. Найди целую часть от…С обязательным пунктом траектории · ACD638131. Вычти 1 2. Найди целую часть от деления на 2 Первая из них уменьшает число на экране на 1, вторая заменяет…С обязательным пунктом траектории · 9A65F5131. Вычти 1 2. Найди целую часть от деления на 2 Первая из них уменьшает число на экране на 1, вторая заменяет…С обязательным пунктом траектории · 43B305131. Вычти 1 2. Найди целую часть от деления на 2 Первая из них уменьшает число на экране на 1, вторая заменяет…С обязательным пунктом траектории · C2EB01131. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2.…С обязательным пунктом траектории · EC38B4131. Вычти 1 2. Найди целую часть от деления на 2 Первая из них уменьшает число на экране на 1, вторая заменяет…С обязательным пунктом траектории · 018811131. Вычти 1 2. Найди целую часть от деления на 2 Первая из них уменьшает число на экране на 1, вторая заменяет…С обязательным пунктом траектории · C0C817131. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2.…С обязательным пунктом траектории · B3D150
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.