Задание 13 ЕГЭ по информатике · EC38B4
С обязательным пунктом траекторииПовышеннаяКЭС 3.1КЭС 3.2
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
Показать ответ
26
Подсказки (3)
- Разбейте программу на две части: от 2 до 14 и от 14 до 29.
- Число программ до каждого значения можно считать по рекуррентному правилу: количество способов попасть в число равно сумме способов попасть в него из предыдущего числа командой «прибавить 1» и из числа вдвое меньшего командой «умножить на 2».
- От 2 до 14 существует 13 программ. От 14 до 29 возможны только два варианта: 14, 15, ..., 29 и 14, 28, 29. Перемножьте количества вариантов.
Решение
1. Обозначим через f(n) количество программ, переводящих число 2 в число n. Для нечётного n последняя команда может быть только «прибавить 1», а для чётного возможны обе команды.
f(n)=f(n−1)+fn2 при чётном n;f(n)=f(n−1) при нечётном n
2. Последовательно получаем значения до числа 14: f(2)=1, f(3)=1, f(4)=2, f(6)=3, f(8)=5, f(10)=7, f(12)=10, f(14)=13.
3. После достижения числа 14 до числа 29 можно пройти только двумя способами: прибавлять по 1 до 29 или выполнить команды «умножить на 2», «прибавить 1», то есть перейти по траектории 14→28→29.
4. Так как траектория содержит число 14 ровно один раз, общее количество программ равно произведению количества вариантов двух частей.
13⋅2=26
f(n)=f(n−1)+fn2 при чётном n;f(n)=f(n−1) при нечётном n
2. Последовательно получаем значения до числа 14: f(2)=1, f(3)=1, f(4)=2, f(6)=3, f(8)=5, f(10)=7, f(12)=10, f(14)=13.
3. После достижения числа 14 до числа 29 можно пройти только двумя способами: прибавлять по 1 до 29 или выполнить команды «умножить на 2», «прибавить 1», то есть перейти по траектории 14→28→29.
4. Так как траектория содержит число 14 ровно один раз, общее количество программ равно произведению количества вариантов двух частей.
13⋅2=26
Частые ошибки
- Не учитывать, что программа обязательно проходит через число 14.
- Сложить, а не перемножить количества вариантов до 14 и после 14.
- Посчитать переход из 14 в 29 несколькими умножениями на 2, хотя после умножения число уже превысит 29.
Похожие задания
131. Вычти 1 2. Найди целую часть от деления на 2 Первая из них уменьшает число на экране на 1, вторая заменяет…С обязательным пунктом траектории · 9A65F5131. Вычти 1 2. Найди целую часть от деления на 2 Первая из них уменьшает число на экране на 1, вторая заменяет…С обязательным пунктом траектории · 43B305131. Вычти 1 2. Найди целую часть от деления на 2 Первая из них уменьшает число на экране на 1, вторая заменяет…С обязательным пунктом траектории · C2EB01131. Вычти 1 2. Найди целую часть от деления на 2 Первая из них уменьшает число на экране на 1, вторая заменяет…С обязательным пунктом траектории · E9000D131. Вычти 1 2. Найди целую часть от деления на 2 Первая из них уменьшает число на экране на 1, вторая заменяет…С обязательным пунктом траектории · 018811131. Вычти 1 2. Найди целую часть от деления на 2 Первая из них уменьшает число на экране на 1, вторая заменяет…С обязательным пунктом траектории · C0C817131. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2.…С обязательным пунктом траектории · B3D150131. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2.…С обязательным пунктом траектории · D785AA
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.