Задание 13 ЕГЭ по информатике · C0C817
С обязательным пунктом траекторииВысокаяКЭС 3.1КЭС 3.2
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Вычти 1
2. Найди целую часть от деления на 2
Первая из них уменьшает число на экране на 1, вторая заменяет число на экране на целую часть от деления числа на 2.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 30 результатом является число 1, и при этом траектория вычислений содержит число 13?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 122 при исходном числе 10 траектория состоит из чисел 9, 4, 2.
У исполнителя есть две команды, которым присвоены номера:
1. Вычти 1
2. Найди целую часть от деления на 2
Первая из них уменьшает число на экране на 1, вторая заменяет число на экране на целую часть от деления числа на 2.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 30 результатом является число 1, и при этом траектория вычислений содержит число 13?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 122 при исходном числе 10 траектория состоит из чисел 9, 4, 2.
Показать ответ
342
Подсказки (3)
- Разбейте программу в точке, где впервые получено число 13: отдельно посчитайте пути от 30 до 13 и от 13 до 1.
- Для подсчёта числа путей используйте рекуррентное соотношение: количество путей из числа n равно сумме количеств путей из чисел n−1 и ⌊n/2⌋.
- Из 30 в 13 можно попасть 6 способами, а из 13 в 1 — 57 способами. Общее число программ равно 6⋅57.
Решение
1. Так как обе команды уменьшают число, траектория может содержать число 13 не более одного раза. Поэтому программы можно однозначно разделить на часть от 30 до 13 и часть от 13 до 1.
2. Подсчитаем количество способов попасть из 30 в 13. Возможны последовательные вычитания, а также переходы делением на 2 из чисел 30, 29, 28, 27 и 26. Динамическим подсчётом получаем 6 способов.
N30→13=6
3. Пусть f(n) — количество программ, переводящих число n в 1. Тогда f(1)=1, а для n>1 выполняется рекуррентное соотношение f(n)=f(n−1)+f(⌊n/2⌋).
f(13)=57
4. Перемножаем количество вариантов для двух независимых частей программы.
6⋅57=342
2. Подсчитаем количество способов попасть из 30 в 13. Возможны последовательные вычитания, а также переходы делением на 2 из чисел 30, 29, 28, 27 и 26. Динамическим подсчётом получаем 6 способов.
N30→13=6
3. Пусть f(n) — количество программ, переводящих число n в 1. Тогда f(1)=1, а для n>1 выполняется рекуррентное соотношение f(n)=f(n−1)+f(⌊n/2⌋).
f(13)=57
4. Перемножаем количество вариантов для двух независимых частей программы.
6⋅57=342
Частые ошибки
- Не учитывать переходы делением на 2 из чисел 26 и 27 в число 13.
- Считать только одну последовательность команд и не использовать динамический подсчёт.
- Сложить, а не перемножить количество способов для частей траектории до 13 и после 13.
Похожие задания
131. Вычти 1 2. Найди целую часть от деления на 2 Первая из них уменьшает число на экране на 1, вторая заменяет…С обязательным пунктом траектории · C2EB01131. Вычти 1 2. Найди целую часть от деления на 2 Первая из них уменьшает число на экране на 1, вторая заменяет…С обязательным пунктом траектории · E9000D131. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2.…С обязательным пунктом траектории · EC38B4131. Вычти 1 2. Найди целую часть от деления на 2 Первая из них уменьшает число на экране на 1, вторая заменяет…С обязательным пунктом траектории · 018811131. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2.…С обязательным пунктом траектории · B3D150131. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2.…С обязательным пунктом траектории · D785AA131. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2.…С обязательным пунктом траектории131. Прибавь 2 2. Умножь на 2 Первая из них увеличивает число на экране на 2, вторая увеличивает число на…С обязательным пунктом траектории · DE8735
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.