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