Задание 13 ЕГЭ по информатике · 4DC91D
С обязательным пунктом траекторииПовышеннаяКЭС 3.1КЭС 3.2
Исполнитель Вычислитель преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Умножить на 3
2. Прибавить 2
3. Прибавить 3
Первая из них умножает число на экране на 3, вторая увеличивает его на 2, третья увеличивает его на 3.
Программа для Вычислителя — это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число 2 в число 21 и при этом траектория вычислений программы содержит число 12?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 21, 23, 26.
У исполнителя есть три команды, которым присвоены номера:
1. Умножить на 3
2. Прибавить 2
3. Прибавить 3
Первая из них умножает число на экране на 3, вторая увеличивает его на 2, третья увеличивает его на 3.
Программа для Вычислителя — это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число 2 в число 21 и при этом траектория вычислений программы содержит число 12?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 21, 23, 26.
Показать ответ
50
Подсказки (3)
- Разбейте программу в точке, когда на экране впервые появляется число 12.
- Посчитайте отдельно количество программ из 2 в 12 и из 12 в 21, используя рекуррентное правило: число программ в текущую точку равно сумме чисел программ из точек, из которых в неё можно попасть.
- Из 2 в 12 можно попасть 10 способами, а из 12 в 21 — 5 способами. Общее число программ равно 10⋅5.
Решение
1. Поскольку все команды увеличивают число, число 12 в траектории может встретиться только один раз. Поэтому число искомых программ равно произведению числа программ из 2 в 12 и числа программ из 12 в 21.
N=N2→12⋅N12→21
2. Для подсчёта используем динамическое программирование. Для каждой точки складываем количества способов попасть в неё командами «прибавить 2», «прибавить 3» и «умножить на 3», если соответствующий переход возможен.
f(x)=f(x−2)+f(x−3)+{f(x/3),&x⋮3; 0,&иначе
3. Количество программ из 2 в 12 равно 10.
N2→12=10
4. Количество программ из 12 в 21 равно 5.
N12→21=5
5. Перемножаем количества вариантов двух независимых частей программы.
N=10⋅5=50
N=N2→12⋅N12→21
2. Для подсчёта используем динамическое программирование. Для каждой точки складываем количества способов попасть в неё командами «прибавить 2», «прибавить 3» и «умножить на 3», если соответствующий переход возможен.
f(x)=f(x−2)+f(x−3)+{f(x/3),&x⋮3; 0,&иначе
3. Количество программ из 2 в 12 равно 10.
N2→12=10
4. Количество программ из 12 в 21 равно 5.
N12→21=5
5. Перемножаем количества вариантов двух независимых частей программы.
N=10⋅5=50
Частые ошибки
- Складывают количество программ вместо умножения.
- Не учитывают переходы командой «умножить на 3».
- Считают программы, которые не проходят через число 12.
Похожие задания
13Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · E9714A13Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · F27CB913Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · 634A1213Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · 12172013Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · 1FC32213Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · 28BCD813Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · AAEAA013Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · 3F3DA7
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.