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