Задание 13 ЕГЭ по информатике · E1D1CF
С обязательным пунктом траекторииПовышеннаяКЭС 3.1КЭС 3.2
Исполнитель Вычислитель преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 2
2. Умножить на 2
3. Прибавить 3
Первая из них увеличивает число на экране на 2, вторая умножает его на 2, третья увеличивает его на 3.
Программа для Вычислителя — это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число 1 в число 18 и при этом траектория вычислений программы содержит число 8?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 9, 18, 21.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 2
2. Умножить на 2
3. Прибавить 3
Первая из них увеличивает число на экране на 2, вторая умножает его на 2, третья увеличивает его на 3.
Программа для Вычислителя — это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число 1 в число 18 и при этом траектория вычислений программы содержит число 8?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 9, 18, 21.
Показать ответ
80
Подсказки (3)
- Разбейте программу на две части: от 1 до 8 и от 8 до 18.
- Для подсчёта числа программ используйте динамическое программирование: количество способов попасть в число складывается из количеств способов попасть в числа, из которых выполняется последняя команда.
- Посчитайте количество программ на участке от 1 до 8 и на участке от 8 до 18, затем перемножьте полученные количества: итоговое число программ равно 80.
Решение
1. Так как траектория должна содержать число 8, каждую программу можно однозначно разделить на участок от 1 до 8 и участок от 8 до 18.
N=N1→8⋅N8→18
2. Для каждого числа последовательно подсчитываем количество способов получить его с помощью команд «прибавить 2», «умножить на 2» и «прибавить 3», учитывая только допустимые переходы.
f(n)=f(n−2)+fn2+f(n−3)
3. После подсчёта количества программ на обоих участках и перемножения результатов получаем искомое число программ.
N1→8⋅N8→18=80
N=N1→8⋅N8→18
2. Для каждого числа последовательно подсчитываем количество способов получить его с помощью команд «прибавить 2», «умножить на 2» и «прибавить 3», учитывая только допустимые переходы.
f(n)=f(n−2)+fn2+f(n−3)
3. После подсчёта количества программ на обоих участках и перемножения результатов получаем искомое число программ.
N1→8⋅N8→18=80
Частые ошибки
- Не учитывать условие о прохождении траектории через число 8.
- Складывать, а не перемножать количества программ на двух участках.
- Учитывать умножение на 2 только для нечётных чисел.
Похожие задания
13Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · 28BCD813Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · AAEAA013Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · 3F3DA713Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · 498BC013Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · A7793913Исполнитель К17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены…С обязательным пунктом траектории · C2A6B513Исполнитель К17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены…С обязательным пунктом траектории · F1FE6713Исполнитель К17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены…С обязательным пунктом траектории · 1D7139
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.