Информатика егэ 22 задание – Пособие по подготовке к ЕГЭ «Задание 22 ЕГЭ по информатике 2017 без вывода рекуррентных формул» — ЕГЭ — Информатика

Задание 22 ЕГЭ по информатике

Задание 22 ЕГЭ по информатике

Условие задачи сводятся к тому, что существует некий исполнитель, который умеет выполнять несколько команд (система команд исполнителя – СКИ). Необходимо найти количество программ, преобразующих число А в число В.

Задание 22 претерпело изменения на протяжении нескольких лет присутствия в КИМ ЕГЭ по информатике.

На данный момент задачи можно разделить на несколько групп:

1. Задачи без ограничения условий (приведенный выше вариант).

2. Задачи с ограничением первого типа: траектория прохождения содержит число N.

3. Задачи с ограничением второго типа: траектория вычислений не содержит число M.

4. Задачи с ограничением первого и второго типов: траектория прохождения содержит число N и не содержит число M.

На своих уроках все эти типы задач я стараюсь разобрать на одном примере. Просто так получается быстрее, так как часть задачи уже решена, и нагляднее. Я не претендую на свою методику решения данных задач, а просто хочу обобщить свой опыт, который, надеюсь, может кому-то пригодится. При подготовке учащихся к сдаче ЕГЭ пользуюсь материалами сайта К.Ю. Полякова.

Задачу, которая приводится ниже , взяла из книги Крылов С.С., Чуркина Т.Е., ЕГЭ 2017. Информатика и ИКТ. Типовые экзаменационные варианты. 10 вариантов

Задача

Исполнитель Счетчик преобразует число на экране.

У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 2

2. Умножить на 2

Первая команда увеличивает число на экране на 2, вторая умножает его на 2. Программа для исполнителя Счетчик это последовательность команд.

Сколько существует программ, для которых при исходном числе 2 результатом является число 44 и при этом траектория вычислений содержит число 18 и не содержит числа 34?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 4 траектория будет состоять из чисел 6, 12, 14.

K_{N– количество разных программ для получения числа N из начального числа.}

Построим рекуррентную формулу, связывающую K_N с предыдущими элементами последовательности K₁, K₂, K₃,…, K_N-1, то есть с решениями таких же задач для меньших N.

Число N могло быть получено одной из двух операций:

Рекуррентная формула: K_{N= KN-2 + KN/2}

Я задаю одну рекуррентную формулу и для четных и для нечетных чисел, т.к. можно считать, что для чисел нечетных K_N/2 = 0. То же самое можно сказать и про K_N при N меньших начального числа (K

N = 0).

В нашем примере нечетные числа мы вообще получить не можем.

Будем решать данную задачу в несколько этапов, рассматривая следующие варианты:

1. 2 – 44

2. 2 – 44, содержит 18

3. 2 – 44, не содержит 34

4. 2 – 44, содержит 18 и не содержит 34.

На самом деле, это 4 разных задачи. Просто их удобно рассматривать вместе.

1. Задача 1: 2 – 44

По рекуррентной формуле имеем:

K₂ = 1

K₄ = K₂ + K₂ = 1 + 1 + 2

K₆ = K₄ + K₃ = 2 + 0 = 2

K₈ = K₆ + K₄ = 2 + 2 = 4

K₁₀ = K₈ + K₃ = 4 + 0 = 4

K₁₂ = K₁₀ + K₆ = 4 + 2 = 6 = K₁₄

K₁₆ = K₁₄ + K₈ = 6 + 4 = 10 = K₁₈

K₂₀ = K

18 + K₁₀ = 10 + 4 = 14 = K₂₂

K₂₄ = K₂₂ + K₁₂ = 14 + 6 = 20 = K₂₆

K_{28= K26 + K14 = 20 + 6 = 26 = K30}

K_{32= K30 + K16 = 26 + 10 = 36 = K34}

K₃₆ = K₃₄ + K₁₈ = 36 + 10 = 46 = K₃₈

K₄₀ = K₃₈ + K₂₀ = 46 + 14 = 60 = K₄₂

K_{44= K42 + K22 = 60 + 14 = 76}

1. Задача 2: 2 – 44, содержит 18

Эта задача разбивается на две задачи: 2 – 18 и 18 – 44.

Первая у нас уже решена выше. Мы можем получить число 18 десятью способами.

Дальше мы решаем вторую задачу: 18 – 44, считая, что всех предыдущих вычислений не было. Т.е. все K_{N для N}

K₁₈ =10

K₂₀ = K₁₈ + K₁₀ = 10 + 0 = 10 = K₂₂

K₂₄ = K₂₂ + K₁₂ = 10 + 0 = 10 = K₂₆

K₂₈ = K₂₆ + K₁₄ = 10 + 0 = 10 = K₃₀

K₃₂ = K₃₀ + K₁₆ = 10 + 0 = 10 = K₃₄

K₃₆ = K₃₄ + K₁₈ = 10 + 10 = 20 = K₃₈

K₄₀ = K₃₈ + K₂₀ = 20 + 10 = 30 = K₄₂

K₄₄ = K₄₂ + K₂₂ = 30 + 10 = 40

1. Задача 3: 2 – 44, не содержит 34

В э той задаче траектория не может проходить через число 34, поэтому считаем, что K₃₄ = 0 Дальше вычисления ведем обычным способом.

Использую первую задачу, получим:

K₃₂ = K₃₀ + K₁₆ = 26 + 10 = 36

K₃₄ = 0

K₃₆

= K₃₄ + K₁₈ = 0 + 10 = 10 = K₃₈

K₄₀ = K₃₈ + K₂₀ = 10 + 14 = 24 = K₄₂

K₄₄ = K₄₂ + K₂₂ = 24 + 14 = 38

1. Задача 4: 2 – 44, содержит 18 и не содержит 34

Объединяем задачи 2 и 3. Доходим до получения 18 из 2, обнуляем все предыдущие значения, потом из 18 получаем 32, обнуляем K₃₄ , и далее считаем обычным образом.

K₁₈ =10

K₂₀ = K₁₈ + K₁₀ = 10 + 0 = 10 = K₂₂

K₂₄ = K₂₂ + K₁₂ = 10 + 0 = 10 = K₂₆

K₂₈ = K₂₆ + K₁₄ = 10 + 0 = 10 = K₃₀

K₃₂ = K₃₀ + K₁₆ = 10 + 0 = 10

K₃₄ = 0

K₃₆ = K₃₄ + K₁₈ = 0 + 10 = 10 = K₃₈

K₄₀ = K₃₈ + K₂₀

= 10 + 10 = 20 = K₄₂

K₄₄ = K₄₂ + K₂₂ = 20 + 10 = 30

Мы рассмотрели все 4 варианта данной задачи.

В 2017 году в задании 22 появился еще один тип задач. В условие задачи говорится о том, что предпоследней командой является какая-то определенная команда из СКИ.

Следующую задачу я взяла с сайта К.Ю. Полякова. Задача № 51, задание 22.

Задача

Исполнитель Калькулятор преобразует целое число, записанное на экране. У исполнителя две команды, каждой команде присвоен номер:

1. Прибавь 1

2. Умножь на 2

Первая команда увеличивает число на экране на 1, вторая увеличивает это число в 2 раза. Сколько существует программ, которые число 5 преобразуют в число 32 и в которых предпоследняя команда 1?

Решение

В условии задачи сказано, что предпоследняя команда 1. Последняя команда может быть любая – 1 или 2. Это означает, что нужно рассмотреть и получить количество всех команд вида «*11» и «*12» . Звездочка означает любую последовательность команд.

Если две последние команды «11», то до выполнения этих команд у нас было число 32 – 1 – 1 = 30. Это значит, что нам нужно получить количество команд преобразующих 5 в 30.

Если две последние команды «12», то до выполнения этих команд у нас было число 32/2 – 1 = 15. Это значит, что нам нужно получить количество команд преобразующих 5 в 15.

Число N могло быть получено одной из двух операций:

Запишем общую рекуррентную формулу: K_{N= KN-1 + KN/2}

Если N нечетное, то считаем, что K_N/2 = 0.

Далее решаем задачу обычным способом: 5 – 30

K₅ = 1

K₆ = K₅ + K₃ = 1 + 0 = 1 = K

7

K₈ = K₇ + K₄ = 1 + 0 = 1 = K₉

K₁₀ = K₉ + K₅ = 1 + 1 = 2 = K₁₁

K₁₂ = K₁₁ + K₆ = 2 + 1 = 3 = K₁₃

K₁₄ = K₁₃ + K₇ = 3 + 1 = 4 = K₁₅

K₁₆ = K₁₅ + K₈ = 4 + 1 = 5 = K₁₇

K₁₈ = K₁₇ + K₉ = 5 + 1 = 6 = K₁₉

K₂₀ = K₁₉ + K₁₀ = 6 + 2 = 8 = K₂₁

K₂₂ = K₂₁ + K₁₁ = 8 + 2 = 10 = K₂₃

K₂₄ = K₂₃ + K₁₂ = 10 + 3 = 13 = K₂₅

K₂₆ = K₂₅ + K₁₃ = 13 + 3 = 16 = K₂₇

K₂₈ = K₂₇ + K₁₄ = 16 + 4 = 20 = K₂₉

K₃₀ = K₂₉ + K₁₅ = 20 + 4 = 24

Решая эту задачу, мы решили и вторую задачу: узнали, что число 15 мы можем получить 4 способами.

Складываем полученные результаты: 24 + 4 = 28.

Ответ: существует 28 программ, которые число 5 преобразуют в число 32 и в которых предпоследняя команда 1.

multiurok.ru

Разбор 22 задания ЕГЭ 2016 по информатике из демоверсии

Разбор 22 задания ЕГЭ 2016 года по информатике из демоверсии. Это задание на умение анализировать результат исполнения алгоритма (уметь cтроить информационные модели объектов, систем и процессов в виде алгоритмов). Это задание повышенного уровня сложности. Примерное время выполнения задания 7 минут.

Задание 22:

Исполнитель Май 15 преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2.
Программа для исполнителя Май 15 – это последовательность команд.
Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14 и не содержит числа 25?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Ответ: ________

Разбор 22 задания ЕГЭ 2016:

Решим нашу задачу в два этапа:
1 этап. Найдем количество программ Получить из 2 — 14
2 этап. Найдем количество программ Получить из 14 — 29, не проходя число 25

Найдем минимальное число, из которого существует два способа получения числа 14:
14/2 = 7 (это число 7)
Все числа, большие 7 имеют только один способ получения числа 14 (с помощью команды +1)

Рассмотрим числа, меньшие 7:

6: *2=12 (1 способ) или +1=7 (2 способа) Итого: 3

5: *2=10 (1 способ) или +1=6 (3 способа) Итого: 4

4: *2=8 (1 способ) или +1=5 (4 способа) Итого: 5

3: *2=6 (3 способа) или +1=4 (5 способов) Итого: 8

2: *2=4 (5 способов) или +1=3 (8 способов) Итого: 13

Итого, у числа 2 есть 13 способов получения числа 14.

Для того, чтобы перескочить число 25, нужно использовать команду *2.
Минимальное число, к которому можно применить эту команду равно 14 (14*2=28).
Есть только один спобоб получения числа 29 из 28: 28 + 1

Вывод: Количество решений равно: 13*1 = 13

Ответ: 13

infedu.ru

Разбор 22 задания ЕГЭ 2017 по информатике из демоверсии

Разбор 22 задания ЕГЭ 2017 года по информатике из демоверсии. Это задание повышенного уровня сложности. Примерное время выполнения задания 7 минут.

Проверяемые элементы содержания:
— умение анализировать результат исполнения алгоритма.

Элементы содержания, проверяемые на ЕГЭ:
— вычислимость,
— эквивалентность алгоритмических моделей.

Задание 22

Исполнитель А16 преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 2
Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает его на 2.
Программа для исполнителя А16 – это последовательность команд.
Сколько существует таких программ, которые исходное число 3 преобразуют в число 12 и при этом траектория вычислений программы содержит число 10?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 16, 18.

Ответ: ________

Разбор 22 задания ЕГЭ 2017

Для начала разобьем нашу задачу на 2 этапа:

1 этап — получить из числа 3 число 10,
2 этап — получить из числа 10 число 12.

Получить из числа9 число 10 можно только одним способом (с помощью команды «+1»)

Поэтому рассмотрим числа ≤ 8:

8: «+1″=9 (1 способ) или «+2″=10 (1 способ) Итого: 2

7: «+1″=8 (2 способа) или «+2″=9 (1 способ) Итого: 3

6: «+1″=7 (3 способа) или «+2″=8 (2 способа) Итого: 5

5: «+1″=6 (5 способов) или «+2″=7 (3 способа) или «*2″=10 (1 способ) Итого: 9

4: «+1″=5 (9 способов) или «+2″=6 (5 способов) или «*2″=8 (2 способа) Итого: 16

3: «+1″=4 (16 способов) или «+2″=5 (9 способов) или «*2″=6 (5 способов) Итого: 30

Существует 2 способа получения числа 12 из числа 10: +1+1 или +2

Итого: 30*2 = 60 способов

Ответ: 60

infedu.ru

Разбор 22 задания егэ по информатике 2018

Задание 22. Динамическое программирование: Демонстрационный вариант ЕГЭ по информатике 2018; государственный выпускной экзамен 2018; тренировочные варианты ЕГЭ по информатике, тематические тестовые задания и задачи из тренажера по информатике 2018

*** КАНАЛ ЮТЬЮБ ***
 
ЕГЭ по информатике -> ЕГЭ 2018 -> ЕГЭ 2018 — 22
 

22 задание демоверсия ЕГЭ 2018 информатика:

Исполнитель М17 преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
 1. Прибавить 1
 2. Прибавить 2
 3. Умножить на 3

Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает на 3. Программа для исполнителя М17 – это последовательность команд.

Сколько существует таких программ, которые преобразуют исходное число 2 в число 12 и при этом траектория вычислений программы содержит числа 8 и 10? Траектория должна содержать оба указанных числа.

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 24, 26.

📹 Видеоразбор

Показать решение:  

• Изобразим траекторию в виде луча, на котором отложим отрезки:
• Поскольку 8 и 10 обязательно должны содержаться в расчете, то для поиска общего количества программ необходимо найти произведение количества программ отдельных отрезков:

1 * 2 * 3
или
(2 -> 8) * (8 -> 10) * (10 -> 12)

Найдем отдельно количество программ каждого из отрезков:

2 -> 8 = 15

На интервале от 2 до 8 возьмем число, для которого исполнима только одна из команд:

7
7 + 1 = 8
7 + 2 = 9 - нельзя, вне интервала

Рассмотрим все числа интервала, двигаясь от большего к меньшему:

8 -> 10 = 2

очевидно, что это две программы:

10 -> 12 = 2

Выполним произведение полученных результатов:

15 * 2 * 2 = 60

Результат: 60

Решение 22 задания ЕГЭ по информатике, вариант 4 (ФИПИ, «ЕГЭ информатика и ИКТ, типовые экзаменационные варианты 2018», 10 вариантов, С.С. Крылов, Т.Е. Чуркина):
Исполнитель Увеличитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. прибавить 1
2. прибавить 3
Первая команда увеличивает число на экране на 1, вторая — на 3.
Программа для исполнителя Увеличитель – это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 15 и при этом траектория вычислений содержит число 10 и не содержит число 12?

📹 Видеоразбор

Показать решение:

 
ЕГЭ по информатике -> ЕГЭ 2018 -> ЕГЭ 2018 — 22
 

labs.org.ru

Пособие по подготовке к ЕГЭ «Задание 22 ЕГЭ по информатике 2017 без вывода рекуррентных формул» — ЕГЭ — Информатика

Технические требования

Курс находится на сайте http://polyakovss.rork.ru

Поэтому для работы программы необходимо подключение к интернету.

На компьютере должен быть установлен

Adobe Flash Player для Internet Explorer. Именно для Internet Explorer!

Возможные проблемы и их устранение

Решение проблем по запуску приложения

«Пособие по подготовке к ЕГЭ «Задание 22 ЕГЭ по информатике 2017 без вывода рекуррентных формул»».

Этот документ предназначена для того, чтобы помочь Вам устранить возникшие у Вас проблемы при запуске программы z22ege2017.exe

Коротко:

Перейдите на мою страницу http://polyakovss.rork.ru/z22ege2017faq.php

и нажмите кнопку «Скачать Flash Player» в конце первого блока.

Скачайте, разархивируйте, запустите на выполнение.

Установится нужный Flash Player.

При запуске курса z22ege2017.exe компьютер должен быть подключен к

Интернету. Вот и всё.

Если проблемы остались, а текст ниже не помог тоже, напишите мне, используя форму обратной связи на указанной выше странице.

Никаких данных о себе, кроме e-mail (иначе как мне Вам ответить), писать нет необходимости.

Длинно:

Если при запуске программы появляется окно с предупреждением или файл просто не запускается,

кликните правой кнопкой мыши по файлу z22ege2017.exe. 

В появившемся меню выберите «Свойства» — «Общие». В нижней части окна может быть текст: «Осторожно. Этот файл получен с другого компьютера и, возможно, был заблокирован с целью защиты компьютера».

Рядом с этой надписью будет кнопка «Разблокировать». Нажмите её.

Если файл еще никто не скачивал или скачивали, но недостаточно много раз, Вы получите предупреждение, что файл может быть небезопасным. При запуске файла появляется окно с надписью: «Фильтр Windows SmartScreen предотвратил запуск неопознанного приложения, которое может подвергнуть ваш компьютер риску». 

В этом случае нажмите «Подробнее», а в раскрывшемся перечне действий – «Выполнить в любом случае».

При первом запуске программы z22ege2017.exe при запросе антивируса, установленного на Вашем компьютере, РАЗРЕШИТЕ ВЫПОЛНЕНИЕ ПРОГРАММЫ.

(Проверить на вирусы эту программу Вы можете до ее запуска на выполнение).

Программа запускается, но кроме рамки окна ничего нет.

Это означает, что на Вашем компьютере не установлены необходимые для работы программы компоненты Adobe Flash Player.

(Такая ситуация не должна возникнуть, если у Вас Windows 10 или Windows 8. Там нужный компонент встроен в саму систему).

Проще всего установить нужные компоненты, скачав программу установки с моего сайта по адресу:

http://polyakovss.rork.ru/files/install_flash_player_ax_23.00.162.zip 

или нажав кнопку «Скачать Flash Player» в конце первого блока страницы

http://polyakovss.rork.ru/z22ege2017faq.php

Скачайте, разархивируйте и запустите на выполнение. Всё.

Это на 19.09.2016 самая последняя официальная финальная версия 23.00.162 для Internet Explorer от Adobe, которая единственная и содержит необходимый для работы программы z22ege2017.exe компонент ActiveX. 

Более длинный способ, но зато с официального сайта:

Запустите на своем компьютере Internet Explorer. Именно Internet Explorer!

Перейдите на страницу https://get.adobe.com/ru/flashplayer/

и установите Flash Player.

(Не забудьте снять все галочки в разделе «Дополнительные предложения». При скачивании с моего сайта таких просто нет, так как мною скачано с этого же сайта то, что нужно).

Если у Вас по какой-либо причине нет Internet Explorer и у Вас Windows 7, Vista или XP, то

перейдите на страницу 

https://get.adobe.com/ru/flashplayer/otherversions/ 

В левом окне выберите Вашу операционную систему, а ниже выберите

FP 23 for Internet Explorer – ActiveX

Не забудьте снять все галочки в разделе «Дополнительные предложения». Загрузите и установите.

Программа запускается, можно увидеть первые два слайда, но курс не отображается.

Это возможно, если у Вашего компьютера нет соединения с Интернетом. Исправьте.

Очень редко мой сайт бывает недоступен, так как провайдеры проводят технические работы. В этом случае придется подождать.

Если что-то непонятно, спрашивайте через форму обратной связи

или по e—mail: polyakovss.feedback@gmail.com

С уважением, Сергей Сергеевич Поляков.

pedsovet.su

Репетитор по информатике | За­да­ние 22 ЕГЭ Информатика

 

 

 

За­да­ние 22 № 6818. У ис­пол­ни­те­ля Удво­и­тель две ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра:

 

 

1. при­бавь 2,

2. при­бавь 4.

 

Пер­вая из них уве­ли­чи­ва­ет на 2 число на экра­не, вто­рая уве­ли­чи­ва­ет это число на 4.

Про­грам­ма для Удво­и­те­ля — это по­сле­до­ва­тель­ность ко­манд. Сколь­ко су­ще­ству­ет про­грамм, ко­то­рые число 4 пре­об­ра­зу­ют в число 22?

 

У ис­пол­ни­те­ля че­ты­ре ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра:

 

 

1. при­бавь 1

2. сде­лай чётное

3. сде­лай не­чет­ное

4. умножь на 10

 

Пер­вая из них уве­ли­чи­ва­ет на 1 ис­ход­ное число x, вто­рая умно­жа­ет это число на 2, тре­тья пе­ре­во­дит число x в число 2x+1, чет­вер­тая умно­жа­ет его на 10. На­при­мер, вто­рая ко­ман­да пе­ре­во­дит число 10 в число 20, а тре­тья пе­ре­во­дит число 10 в число 21.

Про­грам­ма для ис­пол­ни­те­ля — это по­сле­до­ва­тель­ность ко­манд.

Сколь­ко су­ще­ству­ет про­грамм, ко­то­рые число 1 пре­об­ра­зу­ют в число 14?

 

По­яс­не­ние.

Обо­зна­чим R(n) — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 2 в число n.

Верны сле­ду­ю­щие со­от­но­ше­ния:

1. Если n нечётное, то тогда R(n) = R(n − 1) + R((n − 1) / 2), (если n > 3) так как есть два спо­со­ба по­лу­че­ния n: при­бав­ле­ни­ем еди­ни­цы или ис­поль­зо­ва­ни­ем ко­ман­ды 3.

2. Если n чётное, но не де­лит­ся на 10, то тогда R(n) = R(n − 1) + R(n / 2), (если n > 2) так как есть два спо­со­ба по­лу­че­ния n: при­бав­ле­ни­ем еди­ни­цы или ис­поль­зо­ва­ни­ем ко­ман­ды 2.

3. Если n чётное и де­лит­ся на 10, то тогда R(n) = R(n − 1) + R(n / 2) + R(n / 10), так как есть три спо­со­ба по­лу­че­ния n: при­бав­ле­ни­ем еди­ни­цы, ис­поль­зо­ва­ни­ем ко­ман­ды 2 или ис­поль­зо­ва­ни­ем ко­ман­ды 4.

До­ста­точ­но вы­чис­лить зна­че­ния R(n) для всех чисел не пре­вос­хо­дя­щих 14.

Имеем:

R(1) = 1.

R(2) = R(1) + R(1) = 2,

R(3) = R(2) + R(1) = 3,

R(4) = R(3) + R(2) = 5,

R(5) = R(4) + R(2) = 5 + 2 = 7,

R(6) = R(5) + R(3) = 7+ 3 = 10,

R(7) = R(6) + R(3) = 10 + 3 = 13,

R(8) = R(7) + R(4) = 13 + 5 = 18,

R(9) = R(8) + R(4) = 18 + 5 = 23,

R(10) = R(9) + R(5) + R(1) = 23 + 7 +1 = 31,

R(11) = R(10) + R(5) = 31 + 7 = 38,

R(12) = R(11) + R(6) = 38 + 10 = 48,

R(13) = R(12) + R(6) = 48 + 10 = 58,

R(14) = R(13) + R(7) = 58 + 13 = 71.

 

Ответ: 71.

 

За­да­ние 22 № 7767. Ис­пол­ни­тель Уве­ли­чи­тель245 пре­об­ра­зу­ет число, за­пи­сан­ное на экра­не. У ис­пол­ни­те­ля три ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра:

 

1. При­бавь 2

2. При­бавь 4

3. При­бавь 5

Пер­вая из них уве­ли­чи­ва­ет число на экра­не на 2, вто­рая уве­ли­чи­ва­ет это число на 4, а тре­тья — на 5. Про­грам­ма для ис­пол­ни­те­ля Уве­ли­чи­тель245 — это по­сле­до­ва­тель­ность ко­манд. Сколь­ко есть про­грамм, ко­то­рые число 31 пре­об­ра­зу­ют в число 51?

 

По­яс­не­ние.

Для сло­же­ния спра­вед­лив пе­ре­ме­сти­тель­ный (ком­му­та­тив­ный) закон, зна­чит, по­ря­док ко­манд в про­грам­ме не имеет зна­че­ния для ре­зуль­та­та.

Все ко­ман­ды уве­ли­чи­ва­ют ис­ход­ное число, по­это­му ко­ли­че­ство ко­манд не может пре­вос­хо­дить (51 − 31)/2 = 10. При этом ми­ни­маль­ное ко­ли­че­ство ко­манд — 4.

Таким об­ра­зом, ко­манд может быть 4, 5, 6, 7, 8, 9 или 10. По­ря­док ко­манд не имеет зна­че­ния.

Рас­смот­рим все воз­мож­ные на­бо­ры и вы­чис­лим ко­ли­че­ство ва­ри­ан­тов рас­спо­ло­же­ния ко­манд в них.

 

Набор 11 1111 1111 имеет один воз­мож­ный ва­ри­ант.

Набор 11 1111 112 — 9 ва­ри­ан­тов.

Набор 11 1111 22 — 28 воз­мож­ных ва­ри­ан­тов рас­по­ло­же­ния: это число пе­ре­ста­но­вок с по­вто­ре­ни­я­ми 8!/(6!·2!).

Набор 11 112 22 — 35 ва­ри­ан­тов.

Набор 11 22 22 — 15 ва­ри­ан­тов.

Набор 2 22 22 — 1 ва­ри­ант.

Набор 3 33 3 — 1 ва­ри­ант.

Набор 11111 33 — 21 ва­ри­ант.

Набор 22133 — 30 ва­ри­ан­тов.

Набор 211133 — 60 ва­ри­ан­тов.

 

 

Всего имеем: 1 + 9 + 28 + 35 + 15 + 1 + 1 + 21 + 30 + 60 = 201 про­грам­ма.

 

Ответ: 201.

 

За­да­ние 22 № 6313. У ис­пол­ни­те­ля Утро­и­тель две ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра:

 

 

1. при­бавь 1,

2. умножь на 3.

 

Пер­вая из них уве­ли­чи­ва­ет число на экра­не на 1, вто­рая утра­и­ва­ет его. Про­грам­ма для Утро­и­те­ля — это по­сле­до­ва­тель­ность ко­манд. Сколь­ко есть про­грамм, ко­то­рые число 3 пре­об­ра­зу­ют в число 38?

 

 

По­яс­не­ние.

Обо­зна­чим R(n) — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 2 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 2, не пре­вос­хо­дя­щее n. Верны сле­ду­ю­щие со­от­но­ше­ния:

1. Если n не де­лит­ся на 3, то тогда R(n) = R(t(n)), так как су­ще­ству­ет един­ствен­ный спо­соб по­лу­че­ния n из t(n) — при­бав­ле­ни­ем еди­ниц.

2. Пусть n де­лит­ся на 3. Тогда R(n) = R(n / 3) + R(n − 1) = R(n / 3) + R(n − 3) (если n > 3). При n = 6 R(n) = 1 (один спо­соб: при­бав­ле­ни­ем еди­ни­цы). По­это­му до­ста­точ­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 3 и не пре­вос­хо­дя­щих 34. Имеем:

 

R(6)= 1 = R(7),

R(9) = 2 = R(10),

R(12) = R(4) + R(11) = 1 + 2 = 3 = R(13),

R(15) = R(5) + R(14)= 1 + 3 = 4 = R(16),

R(18) = R(6) + R(17) = 1 + 4 = 5 = R(19),

R(21) = R(7) + R(20) = 1 + 5 = 6 = R(22),

R(24) = R(8) + R(23) = 1 + 6 = 7 = R(25),

R(27) = R(9) + R(26) = 2 + 7 = 9 = R(28),

R(30) = R(10) + R(29) = 2 + 9 = 11 = R(31),

R(33) = R(11) + R(32) = 2 + 11 = 13 = R(34),

R(36) = R(12) + R(32) = 3 + 13 = 16 = R(38).

 

Ответ: 16.

 

За­да­ние 22 № 6345. У ис­пол­ни­те­ля Удво­и­тель две ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра:

 

 

1. при­бавь 1,

2. умножь на 2.

 

Пер­вая из них уве­ли­чи­ва­ет число на экра­не на 1, вто­рая удва­и­ва­ет его. Про­грам­ма для Удво­и­те­ля — это по­сле­до­ва­тель­ность ко­манд. Сколь­ко есть про­грамм, ко­то­рые число 2 пре­об­ра­зу­ют в число 23?

 

 

По­яс­не­ние.

Обо­зна­чим R(n) — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 2 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 2, не пре­вос­хо­дя­щее n. Верны сле­ду­ю­щие со­от­но­ше­ния:

1. Если n не де­лит­ся на 2, то тогда R(n) = R(t(n)), так как су­ще­ству­ет един­ствен­ный спо­соб по­лу­че­ния n из t(n) — при­бав­ле­ни­ем еди­ниц.

2. Пусть n де­лит­ся на 2. Тогда R(n) = R(n / 2) + R(n − 1) = R(n / 2) + R(n − 2) (если n > 2). Таким об­ра­зом, до­ста­точ­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 2 и не пре­вос­хо­дя­щих 23. Имеем:

 

R(2)= 1 = R(3),

R(4) = R(2) + R(3) = 1 + 1 = 2 = R(5),

R(6) = R(3) + R(5) = 1 + 2 = 3 = R(7),

R(8) = R(4) + R(7)= 2 + 3 = 5 = R(9),

R(10) = R(5) + R(9) = 2 + 5 = 7 = R(11),

R(12) = R(6) + R(11) = 3 + 7 = 10 = R(13),

R(14) = R(7) + R(13) = 3 + 10 = 13 = R(15),

R(16) = R(8) + R(15) = 5 + 13 = 18 = R(17),

R(18) = R(9) + R(17) = 5 + 18 = 23 = R(19),

R(20) = R(10) + R(19) = 7 + 23 = 30 = R(21),

R(22) = R(11) + R(21) = 7 + 30 = 37.

 

Ответ: 37.

sameface.ru

Разбор 22 задания ЕГЭ 2018 по информатике и ИКТ

Разбор 22 задания ЕГЭ 2018 по информатике и ИКТ из демоверсии. Это задание повышенного уровня сложности. Примерное время выполнения задания 7 минут.

Проверяемые элементы содержания:
— Умение анализировать результат исполнения алгоритма.

Элементы содержания, проверяемые на ЕГЭ:
— Вычислимость.
— Эквивалентность алгоритмических моделей.

Задание 22

Исполнитель М17 преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1
2. Прибавить 2
3. Умножить на 3

Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает на 3.
Программа для исполнителя М17 – это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число 2 в число 12 и при этом траектория вычислений программы содержит числа 8 и 10? Траектория должна содержать оба указанных числа.
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 24, 26.

Ответ: ________

Разбор 22 задания ЕГЭ 2018 по информатике

Искомое количество программ будет равно произведению количества программ, которые получают из числа 2 число 8, на количество программ, получающих из числа 8 число 10, и на количество программ, получающих из числа 10 число 12.

Эту задачу удобно решать с конца.

Число 12 из числа 10 можно получить двумя способами (10+1+1; 10+2).

Число 10 из числа 8 можно получить двумя способами (8+1+1; 8+2).

Остается узнать количество способов получения числа 8 из числа 2. Начнем свои рассуждения с числа 3, т.к. двойка это начальное число. Тройку можно получить только одним способом – прибавив 1. Четверку получим двумя способами – прибавив единицу к тройке или добавив двойку к двойке и т. д.

Запишем эти рассуждения в следующем виде:

R(2) = 1
R(3) = R(2) = 1
R(4) = R(3) + R(2) = 2
R(5) = R(4) + R(3) = 2 + 1 = 3
R(6) = R(5) + R(4) + R(2) = 3 + 2 + 1 = 6
R(7) = R(6) + R(5) = 6 + 3 = 9
R(8) = R(7) + R(6) = 9 + 6 = 15

Таким образом, количество программ, удовлетворяющих условию задачи равно

R(2) * R(8) * R(10) * R(12) = 1 * 15 * 2 * 2 = 60.

Ответ: 60

Аналогичное задание было в демонстрационном варианте 2017 года. Посмотреть его можно здесь — Разбор 22 задания ЕГЭ 2017 по информатике из демоверсии

Аналогичное задание было в демонстрационном варианте 2016 года. Посмотреть его можно здесь — Разбор 22 задания ЕГЭ 2016 по информатике из демоверсии

infedu.ru