Задание 13 ЕГЭ по информатике · B976F3
С обязательным пунктом траекторииПовышеннаяКЭС 3.1КЭС 3.2
Исполнитель М17 преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 3
Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает на 3.
Программа для исполнителя М17 — это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число 2 в число 12 и при этом траектория вычислений программы содержит числа 8 и 10? Траектория должна содержать оба указанных числа.
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 24, 26.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 3
Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает на 3.
Программа для исполнителя М17 — это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число 2 в число 12 и при этом траектория вычислений программы содержит числа 8 и 10? Траектория должна содержать оба указанных числа.
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 24, 26.
Показать ответ
60
Подсказки (3)
- Разбейте программу на три независимых участка: от 2 до 8, от 8 до 10 и от 10 до 12.
- Для подсчёта числа программ используйте рекуррентную формулу: количество способов попасть в число равно сумме способов попасть в него командами «прибавить 1», «прибавить 2» и «умножить на 3».
- Количество программ на трёх участках равно 15, 2 и 2. Перемножьте эти значения.
Решение
1. Так как все команды увеличивают число, сначала траектория проходит через 8, затем через 10.
N=N2→8⋅N8→10⋅N10→12
2. Обозначим через f(n) количество программ, переводящих 2 в n. Для чисел от 2 до 8 получаем: f(2)=1, f(3)=1, f(4)=2, f(5)=3, f(6)=6, f(7)=9, f(8)=15.
f(n)=f(n−1)+f(n−2)+f(n/3), если 3∣n
3. Из 8 в 10 можно попасть двумя способами: выполнить две команды «прибавить 1» или две команды «прибавить 2»? Первый вариант даёт траекторию 8, 9, 10, второй — 8, 10. Поэтому всего 2 программы.
N8→10=2
4. Из 10 в 12 также есть два способа: 10 → 11 → 12 и 10 → 12.
N10→12=2
5. Перемножаем количество вариантов на трёх участках.
N=15⋅2⋅2=60
N=N2→8⋅N8→10⋅N10→12
2. Обозначим через f(n) количество программ, переводящих 2 в n. Для чисел от 2 до 8 получаем: f(2)=1, f(3)=1, f(4)=2, f(5)=3, f(6)=6, f(7)=9, f(8)=15.
f(n)=f(n−1)+f(n−2)+f(n/3), если 3∣n
3. Из 8 в 10 можно попасть двумя способами: выполнить две команды «прибавить 1» или две команды «прибавить 2»? Первый вариант даёт траекторию 8, 9, 10, второй — 8, 10. Поэтому всего 2 программы.
N8→10=2
4. Из 10 в 12 также есть два способа: 10 → 11 → 12 и 10 → 12.
N10→12=2
5. Перемножаем количество вариантов на трёх участках.
N=15⋅2⋅2=60
Частые ошибки
- Не учитывать обязательный порядок прохождения чисел 8 и 10.
- Сложить, а не перемножить количество способов на отдельных участках.
- Ошибочно учитывать умножение на 3 там, где оно не приводит к нужному числу.
Похожие задания
13Исполнитель К17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены…С обязательным пунктом траектории · C2A6B513Исполнитель К17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены…С обязательным пунктом траектории · F1FE6713Исполнитель К17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены…С обязательным пунктом траектории · 1D713913Исполнитель К17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены…С обязательным пунктом траектории · 6A423213Исполнитель М17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены…С обязательным пунктом траектории · 94AB7713Исполнитель Соло преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1.…С обязательным пунктом траектории · 2FC2EB13У исполнителя есть две команды, которые обозначены латинскими буквами: A. Вычти 2 B. Найди целую часть от…С обязательным пунктом траектории · 6CF4FF13У исполнителя есть две команды, которые обозначены латинскими буквами: A. Вычти 2 B. Найди целую часть от…С обязательным пунктом траектории · 8271BC
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.