Задание 23 ЕГЭ по информатике
Задание 23 в ЕГЭ – это одно из заданий, проверяющих умение анализировать результат исполнения алгоритма, содержащего ветвление и цикл. Как правило, это задание не очень сложное и поэтому на него рекомендуется, на наш взгляд, обращать внимание всем учащимся, сдающим ЕГЭ по предмету «Информатика».
Основные способы решения задания 23 ЕГЭ по информатике.
1. Аналитический (с помощью дерева вариантов или таблицы)
2. Программный (рекурсия или динамическое программирование)
Рассмотрим пример задания.
Исполнитель преобразует число на экране.
У него две команды, которым присвоены номера:
2. Умножить на 2
Первая из них увеличивает число на экране на 1, а вторая – в два раза.
Программа исполнителя – это последовательность команд.
Траектория вычислений – это последовательность результатов выполнения всех команд программы. Например, для программы 1221 при исходном числе 5 траектория будет состоять из чисел 6, 12, 24, 25.
Информатика ЕГЭ задание 23 Тренировочный вариант №17 от 19.04.2021 «ЕГЭ 100БАЛЛОВ»
Сколько существует программ, которые число 2 преобразуют в число 32, причём траектория вычислений содержит число 10?
По сути, необходимо ответить на два вопроса.
А) Сколько существует программ, которые преобразуют число 2 в число 10?
Б) Сколько существует программ, которые преобразуют число 10 в число 32?
Для ответа на вопрос исходной задачи необходимо перемножить ответы на эти два вопроса, так как каждому способу получить из числа 2 число 10 может соответствовать любой из способов получения числа 32 из числа 10.
Приведём примеры решения задания выше.
А) С помощью дерева вариантов посчитаем количество способов получения из числа 2 числа 10. Таких способов 7 (по числу обведённых в кружочек конечных результатов).
Б) С помощью дерева вариантов посчитаем количество способов получения из числа 10 числа 32. Таких способов 8 (по числу обведённых в кружочек конечных результатов).
Итого 7 * 8 = 56 различных программ.
2. Программный способ (рекурсия). Пример решения дадим на языке Pascal (легко можно перенести решение на нужный вам язык). Число a – начальное, b – число после работы программы из условия задачи. На каждом шаге анализируем, какие числа можем получить за 1 ход из числа a.
function func(a, b : integer) : integer;
else if (b = a) then result := 1
else result := func(a+1, b) + func(2*a, b)
writeln ( func(2,10) * func(10,32) );
Замечание. Рассмотрим другой возможный вопрос в задаче.
Сколько существует программ, которые число 2 преобразует в число 32, причём траектория не содержит число 10?
Ученые обнаружили что мозг человека способен на нечто НЕВЕРОЯТНОЕ
Необходимо найти общее число программ, преобразующих число 2 в число 32, и вычесть количество программ, содержащих число 10, то есть вычислить результат по формуле func(2,32) — func(2,10)*func(10,32).
3*. Программный способ решения (с помощью динамического программирования). Последовательно вычисляем элементы в массиве элементы с индексами от a до b. В i-м элементе массива будет храниться число способов получить из начального числа a число i. Для каждого числа (индекса массива) смотрим, какие числа можно из него получить описанными операциями. Пример на языке Pascal (легко можно перенести решение на нужный вам язык).
var dp : array[ 1..32 ] of integer;
function func2 ( const a, b : integer) : integer;
Источник: www.legionr.ru
Траектория вычислений программы что это
Исполнитель Вычислитель преобразует число, записанное на экране.
У исполнителя есть две команды, которым присвоены номера:
- Вычти (1)
- Найди целую часть от деления на (2)
Первая команда уменьшает число на экране на (1), вторая число на экране на число, равное целой части от деления числа на экране на (2). Программа для Вычислителя — это последовательность команд. Сколько существует таких программ, которые преобразуют исходное число (30) в число (1) и при этом траектория вычислений программы содержит число (10)?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы (121) при исходном числе (18) траектория будет состоять из чисел (17), (8), (7).
Решение:
Python
def f(n, target): if n == target: return 1 elif n < target: return 0 else: return f(n-1, target) + f(n//2, target) print(f(30, 10)*f(10,1))
Ответ: 360
Источник: www.alex-math.ru
Решение. Задание 22. Досрочный ЕГЭ 2020 года, Информатика
Исполнитель Вычислитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для Вычислителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 21 и при этом траектория вычислений содержит число 10 и не содержит числа 18?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
Распишем, из каких чисел и сколькими способами может быть получено очередное число:
| Результат | Источник | Количество программ |
| 1 | — | 1 |
| 2 | 1,1 | 2 |
| 3 | 2 | 2 |
| 4 | 3,2 | 4 |
| 5 | 4 | 4 |
| 6 | 5,3 | 6 |
| 7 | 6 | 6 |
| 8 | 7,4 | 10 |
| 9 | 8 | 10 |
| 9,5 | 14 | |
| 11 | 10 | 14 |
| 12 | 11 | 14 |
| 13 | 12 | 14 |
| 14 | 13 | 14 |
| 15 | 14 | 14 |
| 16 | 15 | 14 |
| 17 | 16 | 14 |
| 18 | — | |
| 19 | — | |
| 20 | 10 | 14 |
| 21 | 20 | 14 |
Источник: ege-study.ru
Студия Компьютерного Мастерства
Задание 23. Умение анализировать результат исполнения алгоритма: все задания Ответом к заданию по информатике может быть целое число, десятичная дробь (записывайте её через запятую, вот так: 2,5), последовательность цифр или букв (пишите без пробелов: 97531).
- Количество программ с обязательным этапом
- Количество программ с избегаемым этапом
- Количество программ с обязательным и избегаемым этапами
- Поиск количества программ по заданному числу
- Поиск количества чисел по заданному числу команд
- Задачи Поляков ЕГЭ
DEMO вариант:
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
- Прибавить 1
- Умножить на 2
РЕШЕНИЕ:
Проверим решение программой (Python)
Количество программ с обязательным этапом
Исполнитель преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
- Прибавить 1 (увеличивает число на экране на 1)
- Прибавить 2 (увеличивает его на 2)
- Умножить на 2 (умножает его на 2)
Программа для исполнителя – это последовательность команд.
Сколько существует таких программ, которые исходное число 3 преобразуют в число 12 и при этом траектория вычислений программы содержит число 10?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 16, 18.
РЕШЕНИЕ:
Искомое количество программ равно произведению количества программ, получающих из числа 3 число 10, на количество программ, получающих из числа 10 число 12.
Пусть R(n) — количество программ, которые число 3 преобразуют в число n, а P(n) — количество программ, которые число 10 преобразуют в число n.
Для всех n > 5 верны следующие соотношения:
1. Если n не делится на 2, то тогда R(n) = R(n — 1) + R(n — 2), так как существует два способа получения n — прибавлением единицы или прибавлением двойки. Аналогично P(n) = P(n — 1) + P(n — 2)
2. Если n делится на 2, тогда R(n) = R(n — 1) + R(n — 2) + R(n / 2). Аналогично P(n) = P(n — 1) + P(n — 2) + P(n / 2)
Последовательно вычислим значения R(n):
R(5) = R(4) + R(3) = 1 + 1 = 2
R(6) = R(5) + R(4) + R(3) = 2 + 1 + 1 = 4
R(7) = R(6) + R(5) = 4 + 2 = 6
R(8) = R(7) + R(6) + R(4) = 6 + 4 + 1 = 11
R(9) = R(8) + R(7) = 11 + 6 = 17
R(10) = R(9) + R(8) + R(5) = 17 + 11 + 2 = 30
Теперь вычислим значения P(n):
P(12) = P(11) + P(10) = 2
Таким образом, количество программ, удовлетворяющих условию задачи, равно 30 · 2 = 60.
Источник: css-info.ru
Разбор задания №22 ЕГЭ-2019 по информатике и ИКТ
Предлагаем вашему вниманию разбор задания №22 ЕГЭ 2019 года по информатике и ИКТ. Этот материал содержит пояснения и подробный алгоритм решения, а также рекомендации по использованию справочников и пособий, которые могут понадобиться при подготовке к ЕГЭ.
26 марта 2019
Поделитесь в соц.сетях
ЕГЭ-2020. Информатика. Тематические тренировочные задания
Пособие содержит задания, максимально приближенные к реальным, используемым на ЕГЭ, но распределенные по темам в порядке их изучения в 10-11-х классах старшей школы. Работая с книгой, можно последовательно отработать каждую тему, устранить пробелы в знаниях, а также систематизировать изучаемый материал. Такая структура книги поможет эффективнее подготовиться к ЕГЭ.
Демоверсия КИМ ЕГЭ-2019 по информатике не претерпела никаких изменений по своей структуре по сравнению с 2018 годом. Это значимо упрощает работу педагога и, конечно, уже выстроенный (хочется на это рассчитывать) план подготовки к экзамену обучающегося.
Мы рассмотрим решение предлагаемого проекта (на момент написания статьи – пока еще проекта) КИМ ЕГЭ по информатике.
Часть 1
Ответами к заданиям 1–23 являются число, последовательность букв или цифр, которые следует записать в БЛАНК ОТВЕТОВ № 1 справа от номера соответствующего задания, начиная с первой клеточки, без пробелов, запятых и других дополнительных символов. Каждый символ пишите в отдельной клеточке в соответствии с приведёнными в бланке образцами.
Задание 22
Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
- Прибавить 2
- Умножить на 2
- Прибавить 3
Первая из них увеличивает число на экране на 2, вторая умножает его на 2, третья увеличивает его на 3.
Программа для Вычислителя – это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число 2 в число 22 и при этом траектория вычислений программы содержит число 11?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 9, 18, 21.
Решение
Для начала решим задачу просто, без учета дополнительного условия «содержит число 11»:
Программа короткая, а также она не дает в своей траектории вычисления значения 11. И тут стоит разбить задачу на две небольшие задачи: определить число путей от 2 до 11 и от 11 до 22. Итоговый результат, очевидно, будет соответствовать произведению этих двух значений. Построение сложных схем с деревьями – нерациональная трата времени на экзамене. Чисел в нашем диапазоне не так много, поэтому предлагаю рассмотреть следующий алгоритм:
Выпишем все числа от стартового и до последнего включительно. Под первым напишем 1. Двигаясь слева направо, рассмотрим число способов попадания в текущую позицию, используя данные нам команды.
Сразу можно убрать очевидные позиции, не влияющие на решение: 3 можно зачеркнуть – понятно, что в нее нельзя попасть из стартовой позиции, используя одну из доступных нам команд; 10 – через нее мы не можем никак попасть в нашу промежуточную, а главное, обязательную позицию 11.
В 4 мы можем попасть двумя путями-командами: х2 и +2, т.е. через 4 проходят 2 пути. Напишем это значение под 4. В 5 можно попасть единственным способом: +3. Напишем под 5 значение 1. В 6 можно попасть единственным путем – через 4. А под ней у нас указано значение 2. Соответственно, именно по этим двум путям, проходя 4, мы попадем из 2 в 6. Пишем под 6 значение 2. В 7 можно попасть из двух предыдущих позиций, используя имеющиеся у нас команды, и для получения числа путей, которые нам доступны для попадания в 7, мы сложим числа, которые указывали под этими предыдущими позициями. Т.е. в 7 мы попадаем 2 (из-под 4) + 1 (из-под 5) = 3 путями. Действуя по этой схеме и далее, получаем:
Перейдем в правую половину от условного центра – 11. Только теперь при расчете будем учитывать только те пути, которые проходят через этот центр.
Двигаясь и далее слева направо, мы получаем искомый результат – 100.
Ответ: 100.
Дибиров Магомедшапи Дибиргаджиевич
Заместитель генерального директора по ИКТ АНОО «Дом знаний», преподаватель по программированию Яндекс.Лицея (ДГУНХ, Махачкала), учитель высшей категории, финалист Всероссийского конкурса «Учитель года России 2010»
Источник: rosuchebnik.ru