Задание 13 ЕГЭ по информатике · 0288EE
С обязательным пунктом траекторииПовышеннаяКЭС 3.1КЭС 3.2
Исполнитель преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 3
Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает на 3.
Программа для исполнителя — это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число 2 в число 13 и при этом траектория вычислений программы содержит числа 9 и 11? Траектория должна содержать оба указанных числа.
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 24, 26.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 3
Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает на 3.
Программа для исполнителя — это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число 2 в число 13 и при этом траектория вычислений программы содержит числа 9 и 11? Траектория должна содержать оба указанных числа.
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 24, 26.
Показать ответ
100
Подсказки (3)
- Так как все команды увеличивают число, сначала траектория должна попасть в 9, а затем в 11.
- Обозначьте через f(n) число программ перехода из исходного числа 2 в число n. Учитывайте последние команды: прибавление 1, прибавление 2 и умножение на 3.
- Получается f(9)=25, число способов перейти из 9 в 11 равно 2, а из 11 в 13 — также 2. Перемножьте эти количества.
Решение
1. Поскольку все команды увеличивают число, числа 9 и 11 в траектории могут встретиться только в порядке 9, затем 11.
2. Посчитаем количество программ из 2 в каждое число до 9. Для числа n учитываем переходы из n−1, из n−2 и, если n кратно 3, из n/3.
f(2)=1, f(3)=1, f(4)=2, f(5)=3, f(6)=6, f(7)=9, f(8)=15, f(9)=15+9+1=25
3. Из 9 в 11 можно попасть двумя способами: выполнить команду «прибавить 2» или дважды выполнить команду «прибавить 1».
N9→11=2
4. Из 11 в 13 также существует два способа: «прибавить 2» или дважды «прибавить 1».
N11→13=2
5. Перемножаем количества независимых участков траектории.
25⋅2⋅2=100
2. Посчитаем количество программ из 2 в каждое число до 9. Для числа n учитываем переходы из n−1, из n−2 и, если n кратно 3, из n/3.
f(2)=1, f(3)=1, f(4)=2, f(5)=3, f(6)=6, f(7)=9, f(8)=15, f(9)=15+9+1=25
3. Из 9 в 11 можно попасть двумя способами: выполнить команду «прибавить 2» или дважды выполнить команду «прибавить 1».
N9→11=2
4. Из 11 в 13 также существует два способа: «прибавить 2» или дважды «прибавить 1».
N11→13=2
5. Перемножаем количества независимых участков траектории.
25⋅2⋅2=100
Частые ошибки
- Забывают, что умножение на 3 может быть последней командой на участке, например переход 3→9.
- Учитывают порядок 11 перед 9, хотя все команды только увеличивают число.
- Не перемножают количества способов построения отдельных участков траектории.
Похожие задания
131. Прибавь 2 2. Умножь на 2 Первая из них увеличивает число на экране на 2, вторая увеличивает число на…С обязательным пунктом траектории · DE873513Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены…С обязательным пунктом траектории13Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которые обозначены…С обязательным пунктом траектории · DD7C7213Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены…С обязательным пунктом траектории · 31362113Вычти 3 B. Вычти 8 C. Найди целую часть от деления на 2 Программа для исполнителя – это последовательность…С обязательным пунктом траектории13Прибавить 1 B. Прибавить 3 C. Умножить на 2 Программа для исполнителя – это последовательность команд.…С обязательным пунктом траектории13У исполнителя есть две команды, которые обозначены латинскими буквами: A. Вычти 1 B. Найди целую часть от…С обязательным пунктом траектории13У исполнителя есть две команды, которые обозначены латинскими буквами: A. Вычти 1 B. Найди целую часть от…С обязательным пунктом траектории
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.