Задание 13 ЕГЭ по информатике · D785AA
С обязательным пунктом траекторииВысокаяКЭС 3.1КЭС 3.2
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 22 и при этом траектория вычислений содержит число 10?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2.
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 22 и при этом траектория вычислений содержит число 10?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
Показать ответ
42
Подсказки (3)
- Разбейте программу на две части: переход от 1 к 10 и переход от 10 к 22.
- Для каждого числа посчитайте количество способов получить его командами «прибавить 1» и «умножить на 2».
- Количество программ равно произведению числа способов добраться от 1 до 10 и числа способов добраться от 10 до 22: 14⋅3=42.
Решение
1. Обозначим через f(n) количество программ перехода из 1 в число n. Последняя команда перед получением n либо прибавляет 1, либо умножает число на 2. f(n)=f(n−1)+f(n/2) при чётном n 2. Последовательно вычисляя значения, получаем количество способов попасть из 1 в 10: f(1)=1, f(2)=2, f(3)=2, f(4)=4, f(5)=4, f(6)=6, f(7)=6, f(8)=10, f(9)=10, f(10)=14 3. Теперь считаем количество способов перейти от 10 к 22, не используя числа меньше 10. До числа 20 можно дойти двумя способами: через 19 или командой умножения числа 10 на 2. Поэтому: g(10)=1,…,g(19)=1, g(20)=2, g(21)=2, g(22)=3 4. Любая программа, траектория которой содержит 10, однозначно разбивается на участок от 1 до 10 и участок от 10 до 22. 14⋅3=42
Частые ошибки
- Не учитывают условие прохождения через число 10.
- Складывают количество способов вместо умножения.
- Разрешают переходы к числам меньше 10 после достижения числа 10.
Похожие задания
131. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2.…С обязательным пунктом траектории · EC38B4131. Вычти 1 2. Найди целую часть от деления на 2 Первая из них уменьшает число на экране на 1, вторая заменяет…С обязательным пунктом траектории · 018811131. Вычти 1 2. Найди целую часть от деления на 2 Первая из них уменьшает число на экране на 1, вторая заменяет…С обязательным пунктом траектории · C0C817131. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2.…С обязательным пунктом траектории · B3D150131. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2.…С обязательным пунктом траектории131. Прибавь 2 2. Умножь на 2 Первая из них увеличивает число на экране на 2, вторая увеличивает число на…С обязательным пунктом траектории · DE873513Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены…С обязательным пунктом траектории13Исполнитель преобразует число, записанное на экране. У исполнителя есть три команды, которые обозначены…С обязательным пунктом траектории · DD7C72
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.