23 номер егэ информатика через программу

Еще один способ решения данного задания написание программы. на примере первой задачи посмотрим несколько способов решения. задание 1 у

Еще один способ решения данного задания – написание программы.

На примере первой задачи посмотрим несколько способов решения.

Задание 1

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

1. прибавь 1

2. умножь на 3

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

В решении электронными таблицами мы получили формулы для расчетов:

Если число n НЕ делится на 3, количество программ для него

kn = kn-1

Если же число делится на 3, то

kn = kn-1 + kn / 3

их мы и будем использовать в данном задании.

1 способ решения. Заполнение списка.

Необходимые навыки:

  • работа со списками
  • условный оператор
  • цикл for

# +1 *3 1->20

a = [0] * 21 # создаем список из такого количества

# элементов, чтобы нам хватило индексов от 0 до 20

a[1] = 1 # заполняем элемент с индексом стартового числа

for i in range(2, 20 + 1): # перебираем остальные числа от 2 до 20

if i % 3 == 0: # если кратно 3, добавляем предыдущее и / 3

a[i] = a[i – 1] + a[ i // 3]

else: # если не кратно 3, добавляем только предыдущее

a[i] = a[i – 1]

print(a[20]) # выводим на экран значение конечного числа

Данное решение является самым частным и не всегда получится им хорошо решить. Потребуются дополнительные условия когда могут получаться отрицательные индексы.

2 вариант решения без инверсии команд

# +1 *3 1->20
a = [0] * 100 # создаем список из такого количества 
# элементов, чтобы нам хватило индексов от 0 до 20 * 3 (я взял сильно с запасом)
a[20] = 1 # заполняем элемент с индексом стартового числа
for i in range(19, 0, -1): # перебираем остальные числа от 2 до 20
	a[i] = a[i + 1] + a[i * 3]
print(a[1]) # выводим на экран значение конечного числа

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

3 вариант решения. Рекурсивная функция

# +1 *3 1->20
def f(n):
	if n > 20: # перепрыгнули 20
		return 0
	if n == 20: # попали в 20
		return 1
	return f(n + 1) + f(n * 3) # число до 20
	

print(f(1))

Задача 2. Все варианты решения

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

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

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

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 40 и при этом траектория вычислений содержит число 20 и не содержит число 8?

Разобьем решение со списком на два этапа

# +1 *2 2->40 v20 x8
a = [0] * 100 
a[20] = 1 # заполняем элемент с индексом стартового числа a[40] = 1 for i in range(19, 2 - 1, -1):  if i != 8: a[i] = a[i + 1] + a[i * 2] for i in range(39, 20 - 1, -1): a[i] = a[i + 1] + a[i * 2] print(a[2] * a[20]) # выводим на экран значение конечного числа

Усовершенствуем рекурсивный алгоритм: добавим в функцию еще один параметр. Теперь их два: из какого числа считаем и в какое.

# +1 *2 2->40 v20 x8
def f(n, finish):
	if n == finish:
		return 1
	if n > finish or n == 8:
		return 0
	return f(n + 1, finish) + f(n * 2, finish)
	
	
print(f(2, 20) * f(20, 40))

Решение задания программированием наиболее кратко получается с использованием рекурсивной функции. В целом, написание кода занимает время примерно равное решению в электронных таблицах, за исключением случаев когда дан большой диапазон чисел.

Следует рассматривать такой вариант решения как средство для проверки ручного решения.

В 2021 году экзамен по информатике кардинально изменился. Теперь он проходит в компьютерной форме. Полностью исчезли задания, требующие простого воспроизведения формул и терминов. В ЕГЭ нового типа нужно рассуждать и решать задачи. Часть выполняется на бумаге, в электронную форму вносится только ответ. Другая часть представляет собой работу в компьютерных программах. Изменения коснулись и номера 23 из ЕГЭ по информатике. Раньше это была задача на системы логических уравнений, которая вызывала у школьников затруднения. В нынешнем году ее убрали, заменив на вопрос с анализом результата исполнения алгоритма. Он относится к первой части и дает 1 балл. Разбираемся в теории и решении 23 задания в ЕГЭ по информатике. 

Теория

Задача 23 связана с алгоритмами. Алгоритм — полное и точное описание действий, приводящее к конечному результату. В информатике исходными и выходными данными является информация. Алгоритмы реализуются в компьютерных программах, они должны занимать определенный объем памяти и время. Алгоритм должен быть: 

  • теория по егэ информатика 23 задачадискретным (прерывным). Состоит из последовательности простых шагов;
  • детерминированным (определенным). В описании операций нет многозначности, исполнитель понимает их и может реализовать;
  • массовым. Позволяет решить не одну задачу, а группу аналогичных. В качестве возможных данных используются переменные;
  • результативным. Рассматривает все ситуации, дает конечный результат;
  • конечным. Имеется определенное количество шагов;
  • эффективным. Время выполнения алгоритма позволяет использовать его для реальных задач.

Алгоритм делят на базовые элементы (структуры). Структуры бывают трех типов: следование (последовательные действия), ветвление (программа проверяет условие и выбирает один из вариантов действия в зависимости от результата), цикл (несколько действий повторяются многократно). В задании 23 по информатике используются следующие способы записи алгоритмов: 

  • обычный язык. Текст с разделением на шаги;
  • блок-схема. Программа представляется графически, используются специальные блоки: 

Блок

Обозначение

Начало, конец

Ввод, вывод данных

Операция

Условие

Цикл с параметром

Обращение к дополнительным алгоритмам

  • Блок
  • Обозначение
  • Начало, конец
  • Ввод, вывод данных
  • Операция
  • Условие
  • Цикл с параметром
  • Обращение к дополнительным алгоритмам
  • языки программирования. Имеют строгие правила записи, включающие в себя символы и зашифрованные слова;
  • псевдокод. Объединение обычного языка и языка программирования. Нет строгих правил, но есть неизменяемые слова, задающие алгоритм. Например, «нач» — начало, «кон» — конец, «рез» — результат.   

Примеры из ЕГЭ

Чтобы хорошо подготовиться к экзамену, нужно решить практические задачи по 23 заданию. Номер основан на динамическом программировании — решении сложных задач путем приведения к более простым. То есть, для выполнения конечного алгоритма нужно разобраться с подзадачами. 

Для решения могут применяться графический и табличный способ. 

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

1. прибавить 3

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

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

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

Решение. Решим графическим способом. Начнем выполнять с конца. Итоговый результат получается двумя способами — прибавлением к числу Х тройки или умножением числа Y на 2. 25 — нечетное число, вариант с умножением отпадает. Следовательно, перед 25 в алгоритме стояло 25-3=22.

Число 22 получается и умножением, и сложением. Алгоритм разделяется на 2: в одном число 22:2=11, а в другом 22-3=19. Каждое из этих чисел анализируем по той же схеме. Нужно «разворачивать» алгоритм до тех пор, пока каждая из ветвей не закончится единицей. Рисунок выглядит так: 

задача 23 по информатике пример 1

Ответ: 9.

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

1. прибавить 1

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

Сколько существует программ, преобразующих исходное число 2 в число 9?

Решение. Воспользуемся таблицей. В этом случае решаем в прямом порядке. В первой строке таблицы записываем все целые числа от исходного до итогового. Во второй пишем число, к которому нужно прибавить 1 для получения цифры из первой строки. В третьей строке аналогично, но с умножением. Четвертая строка — количество разных команд, которые могут привести к получению числа. 

 

2

3

4

5

6

7

8

9

+1

— 

2

3

4

5

6

7

8

•2

— 

— 

2

— 

3

— 

4

— 

Кол-во программ

1

1

2

2

3

3

5

5

На примере восьмерки: 

задача 23 егэ информатика пример 2

Ответ: 5.

Итак, мы изучили теорию 23 номера и провели его разбор. Конечно, это непростое задание, и далеко не все могут понять его самостоятельно. Если оно показалось вам сложным, можно записаться на курсы подготовки к ЕГЭ, где о выполнении задач будут рассказывать опытные преподаватели. А мы желаем вам удачи в сдаче ЕГЭ и поступлении в вуз!

Здравствуйте! Сегодня речь пойдёт о 23 задании из ЕГЭ по информатике 2021.

Двадцать третье задание является последним заданием из первой части ЕГЭ по информатике 2021.

Давайте познакомимся с примерными задачами 23 задания из ЕГЭ по информатике 2021.

Задача (классическая)

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

1. прибавить 3,
2. умножить на 2.

Первая из них увеличивает число на экране на 3, вторая — удваивает его.

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

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

Решение:

1 Способ (Графический)

Начинаем рассматривать задачку с конца. Если число нечётное, то оно может быть получено только с помощью первой команды. Если число чётное, то оно может быть получено с помощью двух команд.

ЕГЭ по информатике - задание 22 (Исполнитель удвоитель)

Видим, что количество программ получается 9!

2 Способ (С помощью таблицы)

Некоторое число i можно получить только двумя способами: либо c помощью первой команды, либо с помощью второй команды. Тогда количество программ для некоторого числа i будет складываться из двух чисел: количества программ для числа i-3 и количества программ для числа i / 2 (Если i — чётное).

Числа 1 2 3 4 5 6 7 8 9 10
+3 1 2 3 4 5 6 7
*2 1 2 3 4 5
Кол.
Прог.
1 1 0 2 1 0 2 3 0 3
Числа 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
+3 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
*2 6 7 8 9 10 11 12
Кол.
Прог.
3 0 3 5 0 6 5 0 6 8 0 9 8 0 9

В первой строке пишутся числа от 1 до 25 (до того числа, которое нужно получить).

Во второй строке пишутся числа, которые в сумме с 3 (тройкой) дают числа, написанные в первой строке. (Прим. начиная с 4, числа идут по порядку.)

В третьей строке пишутся числа, которые при умножении на 2 дают числа, написанные в первой строке. (Прим. числа так же идут по порядку через одну пустую ячейку.)

В четвёртой строке для единицы ставим 1. Для остальных ячеек: смотрим, какие числа участвуют во второй и третьей строке для конкретной ячейки. Затем, эти числа ищем в первой строке и пишем сумму количеств программ для этих чисел (Т.е. пишем сумму уже известных значений из четвёртой строки для этих чисел).

Таким образом, основная идея 23 задания из ЕГЭ по информатике заключается в том, что результат каждого шага опирается на результаты предыдущих шагов!

Получаем ответ 9!

Ответ: 9

Задача (с избегаемым узлом)

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

1. прибавь 1

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

Первая из этих команд увеличивает число x на экране на 1, вторая переводит число x в число 2x+1. Например, вторая команда переводит число 10 в число 21. Программа для исполнителя НечетМ — это последовательность команд. Сколько существует таких программ, которые число 1 преобразуют в число 25, причём траектория вычислений не содержит число 24? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 17, 18.

Источник: Тренировочная работа по ИНФОРМАТИКЕ 11 класс 18 января 2017 года Вариант ИН10304

Решение:

Мы не может получать число 24! Значит, единственным способом добраться до числа 25 будет вторая команда.

Получается, что сначала нужно получить число 12, тогда 2 * 12 + 1 = 25 (2x+1). Это единственный путь!

Каждое число можем получить только 2 способами (Либо с помощью первой команды, либо с помощью второй команды). Поэтому количество программ для некоторого числа i будет равно сумме количеств команд для числа i-1 и для числа (i — 1) / 2 (Если число нечётное.) Если число i — чётное, то до числа i можно добраться единственным способом (с помощью первой команды).

Если записать с помощью массива:

A[i]=A[i-1] — если i — четное.
A[i]=A[i-1] + A[(i-1)/2] — если i нечетное;

Числа 1 2 3 4 5 6 7 8 9 10 11 12
2x+1 1 2 3 4 5
+1 1 2 3 4 5 6 7 8 9 10 11
Кол.
Прог.
1 1 2 2 3 3 5 5 7 7 10 10

Ответ: 10

Задача (ЕГЭ по информатике, Москва, 2019)

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

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

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

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

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

Решение:

От числа 11 до числа 12 можно добраться единственным путём (11 + 1 = 12).

От числа 9 до числа 11 можно добраться двумя способами (9 + 1 + 1 = 11, 9 + 2 = 11).

Найдём сколькими способами можно попасть от числа 2 до числа 9.

Числа 2 3 4 5 6 7 8 9
+1 2 3 4 5 6 7 8
*3 2 3
+2 2 3 4 5 6 7
Кол-во
программ
1 1 2 3 6 9 15 25

Учитывая, что от 9 до 11 двумя способами можно добраться, то 25 * 2 = 50 — это и будет ответ.

Ответ: 50

Задача ( ЕГЭ по информатике, Москва, 2020)

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

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

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

Сколько существует программ, которые преобразуют исходное число 3 в число 14 и при этом траектория вычислений содержит число 9?

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

Решение:

Последней командой для получении любого числа из траектории программы может быть одна из трёх выше указанных команд!

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

Получается, что мы будем использовать основной принцип 23 задания из ЕГЭ по информатике: результат для некоторого числа опирается на результаты предыдущих чисел. Т.к. траектория вычислений программ обязательно должна проходить через число 9, то при вычислении результата для чисел больших 9, мы не можем опираться на результаты для чисел меньших 9 (Иначе мы пропустим число 9).

Числа 3 4 5 6 7 8 9 10 11 12 13 14
+1 3 4 5 6 7 8 9 10 11 12 13
*3 3
+2 3 4 5 6 7 9 10 11 12
Кол-во
программ
1 1 2 3 5 8 14 14 28 42 70 112

Ответ: 112

Посмотрим следующую задачу из 23 задания ЕГЭ по информатике 2021

Задача (с обязательным узлом, закрепление)

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

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

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

Первая команда увеличивает число на экране на 1, вторая увеличивает его на 3. Программа для исполнителя Май17 — это последовательность команд.

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

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

Решение:

Любое число может получится в результате двух команд! Тогда количество программ для числа i будет складываться из количеств команд для числа i — 1 и для числа i — 3.

Если написать на языке массива

A[i] := A[i-1] + A[i-3], при i > 3.

Числа 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
+1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
+3 1 2 3 4 5 6 9 10 11 12 13 14
Кол-во
программ
1 1 1 2 3 4 6 9 13 13 13 26 39 52 78 117 169

При составлении значения для числа 10, мы не имеем право «заглядывать» за число 9, иначе число 9 будет пропущено! Поэтому для следующих трёх чисел (9, 9 + 1, 9 + 1 + 1), начиная с 9, будет 13 программ.

Для числа 17 получается ответ 169.

Ответ: 169

За это задание ты можешь получить 1 балл. На решение дается около 10 минут. Уровень сложности: высокий.
Средний процент выполнения: 25.4%
Ответом к заданию 23 по информатике может быть цифра (число) или слово.

Задачи для практики

Задача 1

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

1. Прибавь 2,

2. Увеличь цифру в старшем разряде числа на 1.

Первая из них увеличивает данное число на 2, вторая — увеличивает цифру в старшем разряде числа на 1, например, число 34 с помощью этой команды превратится в число 44. Программа для исполнителя Увеличитель — это последовательность команд.

Определите количество программ, которые число 20 преобразуют в число 44.

Решение

Будем решать поставленную задачу последовательно для чисел 20, 21, 22, . . . , 44 (то есть для каждого из чисел определим, сколько программ исполнителя существует для его получения). Количество программ, которые преобразуют число 20 в число n, будем обозначать через R(n). Будем считать, что R(20) = 1. Заметим, что команда 2 для чисел, меньших 90, соответствует условию «прибавь 10». С помощью каждой из команд 1 и 2, применяя их последовательно к числам, получаемым из числа 29, можно получить только чётные числа. Числа 20, 22, . . . , 28 можно получить из предыдущего числа только с помощью команды 1. Значит, количество искомых программ для каждого из таких чисел равно количеству программ для предыдущего числа: R(i) = R(i − 2), i—чётное, 22 ≤ i ≤ 28.

Получаем R(20) = R(22) = · · · = R(28) = 1. Для чисел, больших 28 и не превосходящих 44, вариантов последней команды два: прибавь 2 и прибавь 10, то есть R(i) = R(i − 2) + R(i − 10), i — чётное, 30 ≤ i ≤ 44. Заполним соответствующую таблицу по приведённым формулам слева направо:

20 22 24 26 28 30 32 34 36 38 40 42 44
1 1 1 1 1 2 3 4 5 6 8 11 15

Ответ: 15

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

Полный курс

Задача 2

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

1. прибавь 2,

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

Первая из них увеличивает данное число на 2, вторая — увеличивает его в 5 раз. Программа для исполнителя Удвоитель — это последовательность команд.

Определите количество программ, которые число 1 преобразуют в число 37.

Решение

Заметим, что все числа, получаемые с помощью заданных команд из числа 1, — нечётные. Будем решать поставленную задачу последовательно для чисел 1, 3, 5, . . . , 37 (то есть для каждого нечётного числа определим, сколько программ исполнителя существует для его получения). Количество программ, которые преобразуют число 1 в число n, будем обозначать через R(n). Будем считать, что R(1) = 1. Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на 5, то оно может быть получено только из предыдущего с помощью команды прибавь 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего числа: R(i) = R(i − 2), i — нечётное. Если число на 5 делится, то вариантов последней команды два: прибавь 2 и умножь на 5, тогда R(i) = R(i−2)+R(i/5), i — нечётное. Заполним соответствующую таблицу по приведенным формулам слева направо:

1 3 5 7 9 11 13 15 17 19 21 23 25 27
1 1 2 2 2 2 2 3 3 3 3 3 5 5
29 31 33 35 37                  
5 5 5 7 7                  

Ответ: 7

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

Полный курс

Задача 3

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

1. Прибавь 1

2. Прибавь 5

3. Умножь на 7

Первая из них увеличивает число на экране на 1, вторая — на 5, а третья — в 7 раз. Программа для исполнителя X157 — это последовательность команд.

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

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

Полный курс

Задача 4

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

1. Прибавь 1

2. Прибавь 3

3. Умножь на 5

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

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

Полный курс

Задача 5

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

1. Прибавь 2

2. Умножь на 3

Первая из них увеличивает число на экране на 2, вторая — увеличивает его в 3 раза. Программа для исполнителя Увеличитель—это последовательность команд.

Определите количество программ, которые число 1 преобразуют в число 37.

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

Полный курс

Задача 6

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

1. Прибавь 1

2. Прибавь 7

Первая из них увеличивает число на экране на 1, вторая — на 7. Программа для исполнителя X17—это последовательность команд.

Сколько существует программ, которые число 5 преобразуют в число 26, и при этом траектория вычислений содержит число 12?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.Например, для программы 1221 при исходном числе 3 траектория будет состоять из чисел 4, 11, 18, 19.

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

Полный курс

Задача 7

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

1. Прибавь 1

2. Умножь на 2

3. Умножь на 5

Первая из них увеличивает число на экране на 1, вторая — в 2 раза, а третья — в 5 раз. Программа для исполнителя X125 — это последовательность команд.

Сколько существует программ, которые число 1 преобразуют в число 38, и при этом траектория вычислений содержит числа 10 и 20? Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 2231 при исходном числе 5 траектория будет состоять из чисел 10, 20, 100, 101.

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

Полный курс

Задача 8

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

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

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

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

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.Например, для программы 1323 при исходном числе 4 траектория будет состоять из чисел 5, 10, 13, 26.

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

Полный курс

Задача 9

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

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

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

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.Например, для программы 1211 при исходном числе 2 траектория будет состоять из чисел 3, 5, 6, 7.

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

Полный курс

Задача 10

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

1. Прибавь 1
2. Прибавь 2
3. Прибавь 5

Первая из них увеличивает число на экране на 1, вторая — на 2, а третья — на 5. Программа для исполнителя A125 — это последовательность команд.

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

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы.Например, для программы 231 при исходном числе 5 траектория будет состоять из чисел 7, 12, 13.

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

Полный курс

На уроке рассмотрен разбор 23 задания ЕГЭ по информатике: дается подробное объяснение и решение заданий демоверсий и досрочных вариантов разных годов

23-е задание: «Динамическое программирование и анализ работы алгоритма»

Уровень сложности

— повышенный,

Требуется использование специализированного программного обеспечения

— нет,

Максимальный балл

— 1,

Примерное время выполнения

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

До ЕГЭ 2021 года — это было задание № 22 ЕГЭ

Рекомендации по выполнению:

«Один из распространенных способов выполнения этого задания – выписать последовательность
рекуррентных формул, определяющих, сколькими способами можно получить текущее число из ближайших предшественников, одновременно производя вычисления по этим формулам. «Ближайших» в данном случае означает тех, из которых текущее число получается в результате применения программы, состоящей из одной команды. Когда текущее число сравняется с заданным, количество таких способов и будет искомым числом программ»

Типичные ошибки и рекомендации по их предотвращению:

«Не стоит пытаться перечислить все пути в явном виде, это слишком трудоёмко и, скорее всего, в итоге приведёт к ошибке. Распространённая ошибка – экзаменуемые в процессе рекуррентных вычислений забывают о том, что траектория обязана содержать или не содержать указанные в условии числа»

ФГБНУ «Федеральный институт педагогических измерений»

Объяснение темы «Динамическое программирование»

  • Динамическое программирование – это способ или техника решения сложных задач путем приведения их к более простым подзадачам того же типа.
  • Динамическое программирование позволяет решать задачи, которые требуют полного перебора вариантов. Задание может звучать так:
  • «подсчитайте количество способов…»;
  • «как оптимально распределить…»;
  • «найдите оптимальный маршрут…».
  • Динамическое программирование позволяет увеличить скорость выполнения программы за счет эффективного использования памяти; полный перебор всех вариантов не требуется, поскольку запоминаются и используются решения всех подзадач с меньшими значениями параметров.

Более подробное знакомство с динамическим программированием доступно по ссылке.

Решение 23 заданий ЕГЭ по информатике

Плейлист видеоразборов задания на YouTube: 23 номер егэ информатика через программу
Задание демонстрационного варианта 2022 года ФИПИ


23.4: Разбор досрочного ЕГЭ по информатике 2019:

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

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

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

✍ Решение:

📹 Подробный разбор смотрите на видео:

📹 Видеорешение на RuTube здесь

23.1: Разбор 23 (22) задания ЕГЭ по информатике 2017 года ФИПИ вариант 10 (Крылов С.С., Чуркина Т.Е.):

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

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

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

Сколько существует программ, для которых при исходном числе 5 результатом является число 250, и при этом траектория вычислений содержит число 35 и не содержит числа 105?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 4 траектория будет состоять из чисел 9, 45, 50.

✍ Решение:

  • Так как общая траектория 5 -> 250 содержит в себе и те отрезки, которые должны быть удалены (содержащие 105), то разобьем ее на несколько отрезков, отображенных на луче:
  • решение 23 задания егэ

  1. 5 -> 35 — обязательная часть, т.е. расчет количества программ по данной части траектории должен быть включен в результат;
  2. 35 -> 250 — отрезок, из которого нужно будет вычесть часть «ненужной» траектории («ненужная» траектория — которая включает число 105);
  3. 35 -> 105 — «ненужная» часть траектории;
  4. 105 -> 250 — тоже «ненужная» часть.
  • Чтобы вычислить результат, т.е. количество программ, необходимо:
  • траектория 1 * (траектория 2 - (траектория 3 * траектория 4))
    
    полученные значения в каждом отрезке общей траектории необходимо перемножить, но при этом вычесть результат произведения значений "ненужных" траекторий
    
  • Перед тем, как рассчитывать каждый отрезок, условимся брать только числа кратные 5, так как на траектории получения числа 250 из числа 5 командами умножить на 5 или прибавить 5 будут встречаться только числа кратные 5! (5+5=10, 5*5 = 25; 10+5 = 15, 10*5=50 и т.п.).
  • Кроме того, будем использовать метод решения с конца, т.е. двигаясь от наибольших подходящих чисел к наименьшим.
  • Расчет отрезка 1: 5 -> 35
    • Возьмем такое наименьшее число, кратное 5 и, находящееся в интервале от 5 до 35, для которого применима только одна команда:
    5 не подходит: применимы две команды в интервале до 35: 
    5 + 5 = 10 и 5 * 5 = 25
    10 подходит: применима только одна команда:
    10 + 5 = 15, а 10 * 5 = 50 - больше 35
    
  • Отобразим число 10 на графе, указав и саму команду и результат. Красным цветом обозначим количество команд для получения конкретного числа, а в круг будем обводить итоговое суммарное количество команд. То есть из 10 мы можем получить число 15, используя одну команду (10 + 5 = 15):
  • решение 23 задание на графах

  • Далее рассмотрим следующее, меньшее десяти число: это 5. Для него можно использовать 2 команды (5+5=10 и 5*5=25):
  • 1_1

  • Итого получили две программы.
  • Результат: 2

  • Расчет отрезка 2: 35 -> 250
  • Возьмем такое наименьшее число, кратное 5, и, находящееся в интервале от 35 до 250, для которого применима только одна команда:
  • 55 
    т.к. 55 * 5 = 275 - это больше числа 250
    
  • Затем будем последовательно брать подходящие меньшие числа
  • 1_11

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

  • для числа 45 мы взяли результат, полученный для числа 50 (2);
  • для числа 40 мы взяли результат, полученный для числа 45 (3);
  • для числа 35 мы взяли результат, полученный для числа 40 (4);
  • Результат: 5

  • Расчет отрезка 3: 35 -> 105
  • Возьмем такое наименьшее число кратное 5 и находящееся в интервале от 35 до 105, для которого применима только одна команда:
  • 35 
    т.к. 35 * 5 = 175 - больше числа 105
    

    2

    Результат: 1

  • Расчет траектории 4: 105 -> 250
  • 1
    Результат: 1

  • Посчитаем результат, согласно полученной формуле:
  • траектория 1 * (траектория 2 - (траектория 3 * траектория 4))
    2 * (5 - 1 * 1) = 8
    

    Результат: 8

    23.2: Разбор 23 (22) задания ЕГЭ по информатике 2017 года ФИПИ вариант 15 (Крылов С.С., Чуркина Т.Е.):

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

    1. прибавь 1
    2. умножь на 4

    Первая из них увеличивает число на экране на 1, вторая умножает его на 4.

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

    Сколько есть программ, которые число 3 преобразуют в число 44?

    ✍ Решение:

    Использование графов

    • Возьмем такое наименьшее число, находящееся в интервале от 3 до 44, для которого применима только одна команда:
    12 
    к нему применима только команда - прибавь 1 
    12 * 4 = 48 - это больше, чем 44 
    
  • Отобразим число 12 на графе, указав и саму команду и результат. То есть для 12 можно использовать только одну команду (12 + 1 = 13):
  • 1
    Пояснение: Красным цветом будем выделять количество команд для получения конкретного числа, а в круг обводить итоговое суммарное количество команд.

  • Дальше будем использовать метод решения с конца, т.е. двигаясь от наибольших подходящих чисел (в конкретном случае с 12) — к наименьшим.
  • разбор 33 задания егэ
    Пояснение: поскольку это задача динамического программирования, то полученные промежуточные результаты, используются для дальнейших вычислений:

    • для 11 взят результат, полученный для 12 (1);
    • для 10 взят результат, полученный для числа 11 (2);
    • для 9 взят результат, полученный для 10 (3);
    • и т.д.
  • Для последнего числа 3 получено 10 команд.
  • Результат: 10

    📹 Предлагаем посмотреть видео с решением данного 23 задания (теоретическое решение):

    📹 Видеорешение на RuTube здесь (теоретический способ)

    23.3: 23 (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
  • очевидно, что это две программы:
  • 2

  • 10 -> 12 = 2
  • 1

  • Выполним произведение полученных результатов:
  • 15 * 2 * 2 = 60
    

    Результат: 60

    📹 Подробное решение 23 (теоретическое) задания демоверсии ЕГЭ 2018 доступно на видео:

    📹 Видеорешение на RuTube здесь