Задание 13 ЕГЭ по информатике · DE68DA
С исключаемым пунктом траекторииВысокаяКЭС 3.1КЭС 3.2
Исполнитель Кантата преобразует число на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 3
Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает его на 3.
Программа для исполнителя Кантата — это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 19 и при этом траектория вычислений содержит число 9, но не содержит число 12?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 8, 10, 30.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 3
Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает его на 3.
Программа для исполнителя Кантата — это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 19 и при этом траектория вычислений содержит число 9, но не содержит число 12?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 8, 10, 30.
Показать ответ
650
Подсказки (3)
- Разделите программу на две части: путь от 2 до 9 и путь от 9 до 19.
- Для подсчёта количества путей используйте рекуррентное правило: число путей в n равно сумме чисел путей в n−1, n−2 и, если n делится на 3, в n/3.
- Получается N(2→9)=25. Число путей из 9 в 19, не проходящих через 12, равно 26. Перемножьте эти количества.
Решение
1. Поскольку все команды увеличивают число, любая программа, проходящая через 9, сначала достигает 9, а затем движется к 19. Поэтому количество подходящих программ равно произведению числа путей от 2 до 9 и числа путей от 9 до 19, не проходящих через 12.
N=N2→9⋅N9→19
2. Обозначим через f(n) количество способов получить число n из 2. Используем переход по последней команде: прибавление 1, прибавление 2 или умножение на 3.
f(n)=f(n−1)+f(n−2)+{f(n/3),&n кратно 3; 0,&иначе
3. Последовательное вычисление даёт f(9)=25, то есть существует 25 путей от 2 до 9.
4. Для путей от 9 до 19 запрещаем состояние 12, принимая число путей в 12 равным нулю. Последовательность количеств для чисел от 9 до 19 имеет вид 1,1,2,0,2,2,4,6,10,16,26.
N9→19=26
5. Перемножаем количества вариантов двух частей программы.
N=25⋅26=650
N=N2→9⋅N9→19
2. Обозначим через f(n) количество способов получить число n из 2. Используем переход по последней команде: прибавление 1, прибавление 2 или умножение на 3.
f(n)=f(n−1)+f(n−2)+{f(n/3),&n кратно 3; 0,&иначе
3. Последовательное вычисление даёт f(9)=25, то есть существует 25 путей от 2 до 9.
4. Для путей от 9 до 19 запрещаем состояние 12, принимая число путей в 12 равным нулю. Последовательность количеств для чисел от 9 до 19 имеет вид 1,1,2,0,2,2,4,6,10,16,26.
N9→19=26
5. Перемножаем количества вариантов двух частей программы.
N=25⋅26=650
Частые ошибки
- Не исключают пути, проходящие через число 12.
- Складывают количество путей вместо умножения количества вариантов до 9 и после 9.
- Забывают учитывать команду умножения на 3.
Похожие задания
13Исполнитель Аллегро преобразует число на экране. У исполнителя есть три команды, которым присвоены номера: 1.…С исключаемым пунктом траектории · E8F93313Исполнитель Вычислитель преобразует число на экране. У исполнителя есть две команды, которым присвоены…С исключаемым пунктом траектории · 24EE4813Исполнитель Вычислитель преобразует число на экране. У исполнителя есть две команды, которым присвоены…С исключаемым пунктом траектории · 0A180B13Исполнитель Вычислитель преобразует число на экране. У исполнителя есть две команды, которым присвоены…С исключаемым пунктом траектории · 69FC6613Исполнитель Кантата преобразует число на экране. У исполнителя есть три команды, которым присвоены номера: 1.…С исключаемым пунктом траектории · 0CCF9C13Прибавить 1 B. Прибавить 3 C. Умножить на 3 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · D5434F13Прибавить 2 B. Прибавить 3 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 765FFF13Вычесть 1 B. Вычесть 4 C. Найти целую часть от деления на 3 Программа для исполнителя — это…С исключаемым пунктом траектории · B17D75
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.