Задание 13 ЕГЭ по информатике · AAEAA0
С обязательным пунктом траекторииПовышеннаяКЭС 3.1КЭС 3.2
Исполнитель Вычислитель преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 2
2. Умножить на 2
3. Прибавить 3
Первая из них увеличивает число на экране на 2, вторая умножает его на 2, третья увеличивает его на 3.
Программа для Вычислителя — это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число 2 в число 22 и при этом траектория вычислений программы содержит число 11?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 9, 18, 21.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 2
2. Умножить на 2
3. Прибавить 3
Первая из них увеличивает число на экране на 2, вторая умножает его на 2, третья увеличивает его на 3.
Программа для Вычислителя — это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число 2 в число 22 и при этом траектория вычислений программы содержит число 11?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 9, 18, 21.
Показать ответ
100
Подсказки (3)
- Разбейте программу в точке, где впервые получается число 11: отдельно посчитайте пути из 2 в 11 и из 11 в 22.
- Для подсчёта числа путей используйте рекуррентное соотношение: количество путей в число n равно сумме количества путей в числа n−2, n−3 и, если n чётное, в число n/2.
- Из 2 в 11 существует 10 программ, а из 11 в 22 — тоже 10 программ. Перемножьте эти количества.
Решение
1. Посчитаем количество программ, переводящих число 2 в число 11. Для числа n учитываем последние команды «прибавить 2», «прибавить 3» и, при чётном n, «умножить на 2». Получаем f(11)=10.
f(n)=f(n−2)+f(n−3)+[n чётно]fn2
2. Аналогично посчитаем количество программ, переводящих число 11 в число 22. Получаем g(22)=10.
3. Любая подходящая программа однозначно разбивается на часть от 2 до 11 и часть от 11 до 22. Поэтому количества программ перемножаются.
10⋅10=100
f(n)=f(n−2)+f(n−3)+[n чётно]fn2
2. Аналогично посчитаем количество программ, переводящих число 11 в число 22. Получаем g(22)=10.
3. Любая подходящая программа однозначно разбивается на часть от 2 до 11 и часть от 11 до 22. Поэтому количества программ перемножаются.
10⋅10=100
Частые ошибки
- Не учитывать, что число 11 должно входить в траекторию после выполнения команды.
- Сложить количества программ вместо их перемножения.
- Разрешить переходы через число 11 без фиксации результата 11.
Похожие задания
13Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · 634A1213Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · 12172013Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · 1FC32213Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · 28BCD813Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · 3F3DA713Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · 498BC013Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · E1D1CF13Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · A77939
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.