Задание 13 ЕГЭ по информатике · 1D7139
С обязательным пунктом траекторииПовышеннаяКЭС 3.1КЭС 3.2
Исполнитель К17 преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 2
Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает на 2.
Программа для исполнителя К17 — это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число 4 в число 13 и при этом траектория вычислений программы содержит числа 10 и 12? Траектория должна содержать оба указанных числа.
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 16, 18.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 2
Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает на 2.
Программа для исполнителя К17 — это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число 4 в число 13 и при этом траектория вычислений программы содержит числа 10 и 12? Траектория должна содержать оба указанных числа.
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 16, 18.
Показать ответ
32
Подсказки (3)
- Разбейте программу на три участка: переход от 4 к 10, от 10 к 12 и от 12 к 13.
- Для подсчёта числа способов перехода используйте рекуррентное соотношение: число способов попасть в число равно сумме числа способов попасть в него из предыдущих состояний командами «прибавить 1», «прибавить 2» и «умножить на 2».
- Число программ из 4 в 10 равно 16, из 10 в 12 — 2, из 12 в 13 — 1. Перемножьте эти количества.
Решение
1. Сначала подсчитаем количество программ, переводящих число 4 в число 10. Обозначим через f(n) число способов получить n из 4.
f(n)=f(n−1)+f(n−2)+f(n/2) при чётном n
2. Последовательно получаем: f(4)=1, f(5)=1, f(6)=2, f(7)=3, f(8)=6, f(9)=9, f(10)=16.
f(10)=f(9)+f(8)+f(5)=9+6+1=16
3. Из 10 в 12 можно попасть двумя способами: выполнить команду «прибавить 2» или дважды выполнить команду «прибавить 1».
N10→12=2
4. Из 12 в 13 существует только один способ — прибавить 1.
N12→13=1
5. Так как траектория должна содержать 10 и 12, количество программ равно произведению количеств способов на трёх участках.
N=16⋅2⋅1=32
f(n)=f(n−1)+f(n−2)+f(n/2) при чётном n
2. Последовательно получаем: f(4)=1, f(5)=1, f(6)=2, f(7)=3, f(8)=6, f(9)=9, f(10)=16.
f(10)=f(9)+f(8)+f(5)=9+6+1=16
3. Из 10 в 12 можно попасть двумя способами: выполнить команду «прибавить 2» или дважды выполнить команду «прибавить 1».
N10→12=2
4. Из 12 в 13 существует только один способ — прибавить 1.
N12→13=1
5. Так как траектория должна содержать 10 и 12, количество программ равно произведению количеств способов на трёх участках.
N=16⋅2⋅1=32
Частые ошибки
- Не учитывать, что траектория должна содержать оба числа — 10 и 12.
- Сложить количества способов вместо их перемножения.
- Учесть переходы, которые превышают число 13.
Похожие задания
13Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · E1D1CF13Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым…С обязательным пунктом траектории · A7793913Исполнитель К17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены…С обязательным пунктом траектории · C2A6B513Исполнитель К17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены…С обязательным пунктом траектории · F1FE6713Исполнитель К17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены…С обязательным пунктом траектории · 6A423213Исполнитель М17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены…С обязательным пунктом траектории · B976F313Исполнитель М17 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены…С обязательным пунктом траектории · 94AB7713Исполнитель Соло преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1.…С обязательным пунктом траектории · 2FC2EB
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.