Задание 13 ЕГЭ по информатике · E8F933
С исключаемым пунктом траекторииВысокаяКЭС 3.1КЭС 3.2
Исполнитель Аллегро преобразует число на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 3
Первая команда увеличивает число на экране на 1, вторая увеличивает число на 2, третья умножает его на 3.
Программа для исполнителя Аллегро — это последовательность команд.
Сколько существует программ, для которых при исходном числе 4 результатом является число 22 и при этом траектория вычислений содержит число 10, но не содержит число 20?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 8, 10, 30.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 3
Первая команда увеличивает число на экране на 1, вторая увеличивает число на 2, третья умножает его на 3.
Программа для исполнителя Аллегро — это последовательность команд.
Сколько существует программ, для которых при исходном числе 4 результатом является число 22 и при этом траектория вычислений содержит число 10, но не содержит число 20?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 8, 10, 30.
Показать ответ
715
Подсказки (3)
- Разбейте каждую подходящую программу по моменту первого достижения числа 10.
- Посчитайте число способов перехода из 4 в 10, затем из 10 в 22, исключив пути, проходящие через 20.
- Число путей из 4 в 10 равно 13, из 10 в 22 — 233, а из 10 в 22 через 20 — 89⋅2=178. Поэтому ответ равен 13⋅(233−178).
Решение
1. Обозначим через f(n) число программ, переводящих число 4 в число n. Для каждого числа учитываем последние команды: прибавление 1, прибавление 2 и умножение на 3. f(n)=f(n−1)+f(n−2)+f(n/3),еслиnделитсяна3 2. Число программ, переводящих 4 в 10, равно 13. 3. После достижения 10 умножение на 3 сразу даёт число больше 22, поэтому до 22 используются только команды прибавить 1 и прибавить 2. Число путей из 10 в 22 равно числу последовательностей шагов 1 и 2: 233. 4. Из них нужно исключить пути, проходящие через 20. Число путей из 10 в 20 равно 89, а из 20 в 22 — 2, поэтому таких путей 89⋅2=178. 5. Искомое число программ равно произведению числа путей до 10 и числа допустимых путей после 10. 13⋅(233−178)=13⋅55=715
Частые ошибки
- Не исключают программы, траектория которых содержит число 20.
- Считают программы, достигающие 22 без обязательного прохождения через 10.
- Забывают, что траектория содержит результаты после выполнения команд, а не исходное число.
Похожие задания
13Исполнитель Вычислитель преобразует число на экране. У исполнителя есть две команды, которым присвоены…С исключаемым пунктом траектории · 24EE4813Исполнитель Вычислитель преобразует число на экране. У исполнителя есть две команды, которым присвоены…С исключаемым пунктом траектории · 0A180B13Исполнитель Вычислитель преобразует число на экране. У исполнителя есть две команды, которым присвоены…С исключаемым пунктом траектории · 69FC6613Исполнитель Кантата преобразует число на экране. У исполнителя есть три команды, которым присвоены номера: 1.…С исключаемым пунктом траектории · DE68DA13Исполнитель Кантата преобразует число на экране. У исполнителя есть три команды, которым присвоены номера: 1.…С исключаемым пунктом траектории · 0CCF9C13Прибавить 1 B. Прибавить 3 C. Умножить на 3 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · D5434F13Прибавить 2 B. Прибавить 3 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 765FFF13Вычесть 1 B. Вычесть 4 C. Найти целую часть от деления на 3 Программа для исполнителя — это…С исключаемым пунктом траектории · B17D75
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.