Задание 13 ЕГЭ по информатике · 3F3DA7
С обязательным пунктом траекторииПовышеннаяКЭС 3.1КЭС 3.2
Исполнитель Вычислитель преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 2
2. Умножить на 2
3. Прибавить 3
Первая из них увеличивает число на экране на 2, вторая умножает его на 2, третья увеличивает его на 3.
Программа для Вычислителя — это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число 2 в число 21 и при этом траектория вычислений программы содержит число 10?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 9, 18, 21.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 2
2. Умножить на 2
3. Прибавить 3
Первая из них увеличивает число на экране на 2, вторая умножает его на 2, третья увеличивает его на 3.
Программа для Вычислителя — это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число 2 в число 21 и при этом траектория вычислений программы содержит число 10?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 9, 18, 21.
Показать ответ
81
Подсказки (3)
- Разбейте программу на две части: от числа 2 до числа 10 и от числа 10 до числа 21.
- Для каждого промежуточного числа подсчитывайте количество способов получить его командами «прибавить 2», «умножить на 2» и «прибавить 3».
- Число программ с траекторией, содержащей 10, равно произведению количества способов попасть из 2 в 10 и количества способов попасть из 10 в 21: N=N2→10⋅N10→21=9⋅9=81.
Решение
1. Введём динамическое подсчитывание количества программ, ведущих из одного числа в другое. Для попадания в число x последняя команда могла быть одной из трёх: прибавление 2, умножение на 2 или прибавление 3. 2. Отдельно подсчитываем программы перехода от исходного числа 2 к числу 10 и программы перехода от числа 10 к числу 21. По рекуррентному подсчёту получаем по 9 программ для каждого участка. 3. Так как все команды увеличивают число, после прохождения числа 10 вернуться к нему невозможно. Поэтому любую подходящую программу можно однозначно разделить в месте получения числа 10. 4. Общее число программ равно произведению количества вариантов для двух участков. N=9⋅9=81
Частые ошибки
- Складывают, а не перемножают количество вариантов до числа 10 и после него.
- Не учитывают команду «умножить на 2» при подсчёте переходов.
- Считают программы, которые не содержат число 10 в траектории.
Похожие задания
13Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · 12172013Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · 1FC32213Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · 28BCD813Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · AAEAA013Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · 498BC013Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · E1D1CF13Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · A7793913Исполнитель К17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены…С обязательным пунктом траектории · C2A6B5
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.