Задание 11. Анализ программ. Рекурсия. ЕГЭ 2020 по информатике

За это задание ты можешь получить 1 балл. На решение дается около 5 минут. Уровень сложности: базовый.
Средний процент выполнения: 57.5%
Ответом к заданию 11 по информатике может быть последовательность цифр, чисел или слов. Порядок записи имеет значение.

Что нужно знать, чтобы решить задание 11:

  1. Арифметические операции в вашем языке программирования
  2. Условный оператор
  3. Функции и процедуры

Теория к 11 заданию: читать

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

Задача 1

На рисунке на различных языках программирования записан рекурсивный алгоритм F. Определите, сколько чисел будет напечатано на экране при выполнении вызова F(26).

Решение

На рисунке представлена схема выполнения вызова процедуры F(26) в виде дерева.

Согласно алгоритма, вывод чисел на экран осуществляется, когда остаток от деления n на 3 не равен 1.

Количество чисел напечатанных на экране (26, 21, 15, 9, 3) : 5

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

Задача 2

На рисунке на различных языках программирования записан рекурсивный алгоритм F.

Определите, сколько чисел будет напечатано на экране при выполнении вызова F(6).

Решение

При вызове функции F(6) выполняется подпрограмма, в которой переменная n принимает значение 6. Каждый раз при вызове процедур F(n - 2) и F(n - 3) в качестве фактического параметра n в них передаётся текущее значение этой переменной. На рисунке участки, ограниченные пунктиром, демонстрируют область видимости соответствующего значения переменной n.

Каждый раз, возвращаясь из процедуры, переменная n принимает значение, которое было до вызова данной процедуры. Например, если процедура F(n - 2) была вызвана при n = 6, то, попадая в процедуру, переменная n примет значение 4(= 6 − 2). После выхода из этой процедуры значение переменной n вновь будет равно 6.

На рисунке представлена схема выполнения вызова процедуры F(6) в виде дерева.

В данном случае осуществляется вертикальный обход дерева в прямом (префиксном) порядке. То есть сначала просматривается вершина, затем правое поддерево, затем левое поддерево.

Согласно алгоритму, сразу после входа в процедуру осуществляется вывод на экран переменной n. Следовательно, при выполнении вызова F(6) на экране будет отображена последовательность чисел: 6 4 2 0 -1 1 3 1 0. На экране будет напечатано 9 чисел.

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

Задача 3

На картинке на различных языках программирования записан рекурсивный алгоритм F. Чему равно последнее число, напечатанное на экране при выполнении вызова F(9)?

Решение
Ответ: 32
Показать решение

Задача 4

На картинке на различных языках программирования записаны рекурсивные алгоритмы процедур F и G. Чему равна сумма чисел, напечатанных на экране при выполнении вызова F(13)?

Решение
Ответ: 40
Показать решение

Задача 5

На картинке на различных языках программирования записаны рекурсивные алгоритмы процедур F и G. Чему равна сумма чисел, напечатанных на экране при выполнении вызова F(111)?

Решение
Ответ: 299
Показать решение

Задача 6

На картинке на различных языках программирования записаны рекурсивные алгоритмы процедур F и G. Чему равна сумма чисел, напечатанных на экране при выполнении вызова F(102)?

Решение
Ответ: 81
Показать решение

Задача 7

Ниже на различных языках программирования записан рекурсивный алгоритм F.

Чему равна сумма чисел, напечатанных на экране при выполнении вызова F(7)?

Решение
Ответ: 39
Показать решение

Задача 8

Ниже на различных языках программирования записан рекурсивный алгоритм F.

Чему равна сумма чисел, напечатанных на экране при выполнении вызова F(6)?

Решение
Ответ: 34
Показать решение

Задача 9

Ниже на различных языках программирования записан рекурсивный алгоритм F.

Чему равна сумма чисел, напечатанных на экране при выполнении вызова F(5)?

Решение
Ответ: 23
Показать решение

Задача 10

Ниже на различных языках программирования записан рекурсивный алгоритм F.

Запишите подряд без пробелов и разделителей последние пять чисел, которые будут напечатаны на экране при выполнении вызова F(2). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

Решение
Ответ: 74252
Показать решение

Задача 11

Ниже на различных языках программирования записан рекурсивный алгоритм F.

Запишите подряд без пробелов и разделителей последние пять чисел, которые будут напечатаны на экране при выполнении вызова F(7). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

Решение
Ответ: 13071
Показать решение

Задача 12

На картинке на различных языках программирования записан рекурсивный алгоритм F. Сколько раз на экране будет напечатано число 2 при выполнении вызова F(6)?

Решение
Ответ: 5
Показать решение

Задача 13

Ниже на различных языках программирования записан рекурсивный алгоритм F. Сколько раз на экране будет напечатано число 4 при выполнении вызова F(12)?

Решение
Ответ: 3
Показать решение

Задача 14

Ниже на различных языках программирования записан рекурсивный алгоритм F.

Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(7). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

Решение
Ответ: 1312147
Показать решение

Задача 15

Ниже на различных языках программирования записан рекурсивный алгоритм F.

Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(8). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

Решение
Ответ: 864
Показать решение

Задача 16

На картинке на различных языках программирования записан рекурсивный алгоритм F.

Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(6). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

Решение
Ответ: 6423
Показать решение

Задача 17

На рисунке на различных языках программирования записан рекурсивный алгоритм F.

Чему равна сумма чисел, напечатанных на экране при выполнении вызова F(1)?

Решение
Ответ: 39
Показать решение

Задача 18

На рисунке на различных языках программирования записаны рекурсивные алгоритмы процедур F и G. Чему равна сумма чисел, напечатанных на экране при выполнении вызова F(112)?

Решение
Ответ: 25
Показать решение

Задача 19

Ниже на различных языках программирования записаны рекурсивные алгоритмы процедур F и G.

Сколько символов «*» будет напечатано на экране при выполнении вызова F(26)?

Решение
Ответ: 7
Показать решение

Задача 20

На рисунке на различных языках программирования записан рекурсивный алгоритм F.

Чему равна сумма чисел, напечатанных на экране при выполнении вызова F(5)?

Решение
Ответ: 33
Показать решение
Показать еще

Теория для 11 задания ЕГЭ по информатике


Для начала разберёмся с понятием Рекурсия.

Рекурсия — вызов функции внутри самой себя.

Давайте разберёмся на примере. Предположим, вы где-то работаете и вам каждый день платят по 1000 рублей. Вы хотите узнать, сколько у вас сейчас денег. Давайте попробуем их посчитать через рекурсию.

Сегодняшняя сумма ваших денег — это вчерашняя сумма, увеличенная на 1000 рублей.
А вчерашняя сумма денег — это позавчерашняя сумма, увеличенная на 1000 рублей.
И так можно продолжать до бесконечности. Ситуацию можно описать формулой:
F(n) = F(n-1)+1000, где F(n) — сумма денег в n-ый день, а F(n-1) — сумма денег в предыдущий n-1-ый день. Такая формула называется рекуррентной.

Но так мы можем считать до бесконечности. Сумма, которая была у нас 451 день назад = сумме, которая была 452 назад, увеличенной на 1000. Именно поэтому нам необходимо условие выхода из рекурсии:
Предположим, что в 1-ый день у нас было 0 рублей. А сейчас 100-ый день, тогда если n > 1, то нашу сумму можно посчитать по формуле
F(n) = F(n-1)+1000,
а если n = 1, то
F(n) = 0 — это и есть условие выхода из рекурсии.

В виде кода (язык Python) это можно записать как:
def f(n):
ᅠif n > 1:
ᅠᅠreturn f(n-1)+1000
ᅠelse:
ᅠᅠreturn 0

Практика

Пример

На рисунке записан рекурсивный алгоритм F. Чему равна сумма чисел, напечатанных на экране при выполнении вызова F(4)?

Решение

Обратим внимание, что вывод значения на экран происходит в тот момент, когда запускается наша процедура. Следовательно, как только мы вызвали F(4), на экране появилось первое число. Консоль вывода будет выглядеть так: | 4

Далее проверяется условие n > 1. 4 явно больше 1, значит заходим внутрь условного оператора, оказываемся на строчке f(n-1). Эта строчка запускает процедуру f(n-1). Важный момент: сейчас текущая процедура f(n) встала на паузу и ждёт, пока процедура f(n-1) полностью завершит свою работу. Это как в Марио попасть с основного уровня на бонусный. Пока мы на бонусном уровне, основной уровень стоит на паузе.

Схему проще всего представлять в виде дерева:

Теперь запустилась процедура F(3). Сразу же в консоль отправляется число «3». Теперь в консоли мы наблюдаем:
| 4 3

Далее проверяется условие n > 1. 3 больше, чем 1, значит вновь оказываемся на строчке f(n-1) и запускаем f(2):

F(2) выводит на экран число «2»:
| 4 3 2

2 > 1, значит F(2) запускает F(n-1), то есть F(1):

F(1) выводит на экран число «1»:
| 4 3 2 1

Проверка условия n > 1 даёт нам False. 1 не больше, чем 1. Значит процедура F(1) завершает свою работу. Возвращаемся в процедуру F(2). Там мы остановились на строчке F(n-1), которая только что успешно завершила свою работу. Переходит к следующей строчке: F(n-2), которая вызовет F(0):

F(0) выведет на экран 0 и тут же завершит свою работу, не пройдя условие n > 1:
| 4 3 2 1 0

Больше в F(2) делать нечего, она тоже завершает свою работу. Мы возвращаемся в F(3), где остановились на строчке F(n-1). Теперь переходим к строчке F(n-2) и вызываем F(1):

Мы уже вызывали F(1) ранее, но сейчас он вызывается заново, выводит на экран «1» и завершается, не пройдя условие n > 1:
| 4 3 2 1 0 1

Возвращаемся в F(3), она завершила свою работу. Теперь возвращаемся в самое начало — процедуру F(4). Напоминаю, что в ней мы остановились на строчке F(n-1). Теперь, когда она полностью завершила свою работу, мы приступаем к следующей строке F(n-2) и вызываем F(2). Ранее мы уже вызывали F(2) и знаем, что дерево выглядеть будет так:

И выведет поочередно «2» «1» «0»:
| 4 3 2 1 0 1 2 1 0

После чего все процедуры завершат свою работу, а значит и программа завершит свою работу. Осталось сложить числа, выведенные на экран, согласно условию:
4+3+2+1+0+1+2+1+0=14

Ответ: 14

Готовим к ЕГЭ на 85+ баллов и побеждаем лень

Каждый месяц 12 онлайн-занятий в дружелюбной атмосфере + 16 домашних работ с жесткими сроками.
Не готовишься — вылетаешь.

Подробнее о курсе