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