Задание 13 ЕГЭ по информатике · 6DB421
С исключаемым пунктом траекторииВысокаяКЭС 3.1КЭС 3.2
Исполнитель преобразует число на экране.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Умножить на 2
C. Возвести в квадрат
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 20, при этом траектория вычислений не содержит числа 11?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы CBA при исходном числе 4 траектория будет состоять из чисел 16, 32, 33.
У исполнителя есть три команды, которые обозначены латинскими буквами:
A. Прибавить 1
B. Умножить на 2
C. Возвести в квадрат
Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 20, при этом траектория вычислений не содержит числа 11?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.
Например, для программы CBA при исходном числе 4 траектория будет состоять из чисел 16, 32, 33.
Показать ответ
37
Подсказки (3)
- Посчитайте количество способов получить каждое число от 2 до 20, исключив число 11 из траекторий.
- Для числа n рассмотрите предыдущие числа n−1, n/2 при чётном n и , если n является полным квадратом.
- Получается рекуррентное правило: f(n)=f(n−1)+f(n/2)+f(), если соответствующие предыдущие числа существуют; при этом f(11)=0.
Решение
1. Обозначим через f(n) количество программ, переводящих число 2 в число n без попадания в 11. Для числа 2 имеем f(2)=1.
2. Число n можно получить командой A из n−1, командой B из n/2 при чётном n и командой C из , если n является полным квадратом.
3. Так как число 11 не должно входить в траекторию, принимаем f(11)=0. Последовательные значения для чисел от 2 до 20: 1,1,3,3,4,4,7,8,11,0,4,4,8,8,18,18,26,26,37.
4. Для числа 20 учитываются переходы из 19 и 10:
f(20)=f(19)+f(10)=26+11=37
2. Число n можно получить командой A из n−1, командой B из n/2 при чётном n и командой C из , если n является полным квадратом.
3. Так как число 11 не должно входить в траекторию, принимаем f(11)=0. Последовательные значения для чисел от 2 до 20: 1,1,3,3,4,4,7,8,11,0,4,4,8,8,18,18,26,26,37.
4. Для числа 20 учитываются переходы из 19 и 10:
f(20)=f(19)+f(10)=26+11=37
Частые ошибки
- Не учитывать команду C при получении полных квадратов.
- Считать программы, проходящие через число 11.
- Запретить число 11 только как конечный результат, а не как промежуточный.
Похожие задания
13Вычесть 1 B. Вычесть 4 C. Найти целую часть от деления на 3 Программа для исполнителя — это…С исключаемым пунктом траектории · B17D7513Вычесть 1 B. Вычесть 3 C. Найти целую часть от деления на 2 Программа для исполнителя — это…С исключаемым пунктом траектории · DE167D13Прибавить 1 B. Прибавить 2 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · CD381413Вычесть 1 B. Вычесть 4 C. Найти целую часть от деления на 3 Программа для исполнителя — это…С исключаемым пунктом траектории · 064F2013Прибавить 1 B. Прибавить 2 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 6C2CD513Прибавить 1 B. Прибавить 3 C. Умножить на 3 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 209B5313Прибавить 1 B. Прибавить 2 C. Умножить на 2 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 8F2A5313Прибавить 1 B. Прибавить 3 C. Умножить на 3 Программа для исполнителя — это последовательность команд.…С исключаемым пунктом траектории · 9229A5
Нужен репетитор по информатике?
Посмотрите репетиторов, которые ведут занятия в Precettore, или оставьте заявку — подберём сами.
Готовьтесь к ЕГЭ по информатике в Precettore
Варианты с автопроверкой, домашние задания от репетитора, онлайн-доска и разбор ошибок — в одном кабинете. Регистрация бесплатная.