ЕГЭ по информатике - Задание 11 (Рекурсия)

Новое 11 задание 2023-го года можете посмотреть в этой статье.

Одиннадцатое задание из ЕГЭ по информатике обычно даётся на рекурсию.

В программировании рекурсией называется процесс, когда функция (процедура) вызывает сама себя или, когда две функции попарно вызывают друг друга.

Переходим к задачам 11 задания из ЕГЭ по информатике

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

SUB F(n)
    IF n < 8 THEN
         F(2 * n)
         PRINT N
         F(n + 3)
    END IF
 END SUB

def F(n):
    if n < 8:
        F(2 * n)
        print(n)
        F(n + 3)

procedure F(n: integer);
begin
    if n < 8 then begin
        F(2 * n);
        write(n);
        F(n + 3);
    end
end;

алг F(цел n)
нач
    если n < 8 то 
        F(2 * n)
        вывод n
        F(n + 3)
    все
кон

void F (int n)
{
     if (n < 8) {
        F (2 * n);
        std::cout << n;
        F (n + 3);
    }
}

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

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

В начале, в процедуру F передаётся переменная n, значение которой равно 1.

Первом делом в процедуре переменная n проходит проверку: меньше ли переменная n восьми (n < 8).

Т.к. n < 8, то процедура запускает ещё процедуру F(2 * n), которой передаётся значение 2*n! Т.е. запускается процедура F(2) (Т.к. n = 1).

Теперь программа будет выполнять сначала процедуру F(2), прежде чем завершит первоначальную функцию F(1)!.

При анализе процедуры F(2), мы всё равно смотрим на ту же самую процедуру, начинаем её анализировать с начала, но c другим параметром n = 2. Снова n проходит проверку, что она меньше 8. Успешно пройдя это условие (2 < 8), процедура F(2) запускает ещё одну функцию F(4)! Эффект матрёшки!

Процедура F(2) так же не полностью завершилась, потому что сначала нужно сделать вновь запущенную процедуру F(4).

Начинаем процедуру F(4) c проверки условия (4 < 8). Условие переменная n проходит, значит, запускаем процедуру F(8), переходим выполнять её.

При анализе процедуры F(8) понимаем, что переменная n не проходит условие (8 не меньше 8!). Значит, процедура F при n = 8 не запустит новых процедур, а завершиться, ничего не сделав больше.

После того, как процедура F(8) полностью завершиться, нужно закончить процедуру F(4). В процедуре F(4) напечатается переменная n. Т.е. напечатается первое число 4. Дальше процедура F(4) запустит процедуру F(n+3), т.е. запустится процедура F(7).

В процедуре F(7) переменная n = 7 успешно пройдёт условие (7 < 8). После этого запустится процедура F(2 * 7), но переменная n в ней не пройдёт условие (14 не меньше 8!), и она не даст никакого результата. Затем, F(7) напечатает 7, и промежуточный ответ будет: 47. Далее, запустится процедура F(7+3), но в ней переменная снова не пройдёт условие (10 не меньше 8), поэтому F(10) ничего не даст!

Здесь процедура F(7) будет завершена! После чего завершиться и F(4)!

Теперь нужно доделать процедуру F(2). Печатаем 2. Теперь промежуточный ответ будет 472. И запускаем процедуру F(2+3).

В процедуре F(5) переменная n проходит условие (5 < 8), и запускает новую процедуру F(2 * 5), которая не даст никакого результата (10 не меньше 8!). Затем, в процедуре F(5) печатается 5. Промежуточный ответ получается 4725. И запускается процедура F(5 + 3), в которой переменная n тоже не пройдёт условие (8 не меньше 8!), и процедура F(5 + 3) не принесёт никаких плодов.

На этом завершается процедура F(5), а после этого завершается и процедура F(2).

Вот теперь мы вернулись к первоначальной процедуре F(1). Следующая команда в процедуре F(1) будет: печать 1. В общий ответ записываем ещё одно число 47251

Процедура F(1) запускает ещё одну процедуру F(1+3).

В этой процедуре F(4) переменная n легко удовлетворяет условию (4 < 8), и запускает F(2 * 4), которая не даст ни новых процедур, ни новых чисел в ответ (8 не меньше 8!). Процедура F(4) прибавит к ответу число 4, который станет 472514.

Процедура F(4) запустит ещё одну процедуру F(4 + 3).

Процедура F(7) выполнится в полном объёме, потому что 7 < 8. От F(7) запустится процедура F(2* 7), но она не даст никакого эффекта (14 не меньше 8). Напечатается 7. Строчка, которую хотим записать в ответе, станет равна 4725147. Запустится ещё одна процедура F(7 + 3), но снова (10 не меньше 8!). На этом F(7) завершится.

И на этом завершится первоначальная процедура F(1). В ответе напишем 4725147!

Графический метод решения

Оранжевым -показан ход выполнения программы.

Красным - отмечены процедуры, в которых переменная n не прошла проверку (n < 8), и такая процедура не будет выполнять какие-либо команды более.

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

SUB F(n)
    PRINT N
    IF n >= 3 THEN
      F(n - 1)
      F(n - 1)
    END IF
END SUB

def F(n):
    print(n)
    if n >= 3:
      F(n - 1)
      F(n - 1)

procedure F(n: integer);
begin
    write(n);
    if n >= 3 then begin
      F(n - 1);
      F(n - 1)
    end
end;

алг F(цел n)
нач
    вывод n
    если n >= 3 то
      F(n - 1)
      F(n - 1)
    все
кон

void F(int n)
{
    std::cout << n;
    if (n >= 3) {
      F(n - 1);
      F(n - 1);
    }
}

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

Основным моментом этой задачи из реального ЕГЭ по информатике является то, что команда выведения переменной n на экран стоит до условия, и она сработает в любом случае, если запустилась процедура! Условие только либо даёт запустится другим процедурам, либо нет.

Пометка красного креста под процедурой означает, что в данной процедуре переменная n не прошла проверку условия ( n >= 3 ).

Как видно из графического решения ответ будет 4322322.

Определите, сколько звёздочек будет напечатано в результате вызова F(5) приведённой программы:

SUB F(n)
    IF n > 1 THEN
      F(n \ 2)
      F(n - 1)
    END IF
    PRINT "*"
END SUB

def F(n):
    if n > 1:
      F(n // 2)
      F(n - 1)
    print("*")

procedure F(n: integer);
begin
    if n > 1 then
    begin
      F(n div 2);
      F(n - 1)
    end;
    write('*');
end;

алг F(цел n)
нач
    если n > 1 то
      F(div(n, 2))
      F(n - 1)
    все
    вывод '*'
кон 

void F(int n) {
    if (n > 1) {
      F(n / 2);
      F(n - 1);
    }
    std::cout << "*";
}

В этой задачке в любом случае печатается звёздочка, если процедура была запущена, т.к. сама печать на входит в условие! Если условие (n > 1) выполняется, то процедура запускает ещё две процедуры.

Красным цветом отмечены процедуры, в которых переменная n не проходит условие. Значит, такие процедуры не запускают новых процедур. Оранжевым цветом показан ход выполнения программы.

Теперь не сложно подсчитать количество команд печати! В ответе напишем 13.

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

SUB F(n)
    IF n > 0 THEN
      G(n - 2)
    END IF
END SUB
SUB G(n)
    PRINT n
    IF n > 1 THEN
      F(n - 1)
    END IF
END SUB

def F(n):
    if n > 0:
      G(n - 2)
def G(n):
    print(n)
    if n > 1:
      F(n - 1)

procedure G(n: integer); forward;
procedure F(n: integer);
begin
    if n > 0 then G(n - 2)
 end;
procedure G(n: integer);
begin
    writeln(n);
    if n > 1 then F(n - 1)
end;

агл F(цел n)
нач
    если n > 0 то
      G(n - 2)
   все
кон
алг G(цел n)
нач
    вывод n
    если n > 1 то
      F(n - 1)
    все
кон

void F(int n);
void G(int n);
void F(int n) {
    if (n > 0)
      G(n -  2);
}
void G(int n) {
    std::cout << n << endl;
    if(n > 1)
      F(n -  1);
}

Решаем данную задачу из тренировочного варианта ЕГЭ по информатике, как всегда, на языке паскаль.

Слово forward обозначает, что мы объявляем процедуру, но не прописываем сразу тело процедуры. Ведь внутри этой процедуры мы хотим вызывать вторую процедуру, которая ещё не описана. Поэтому применяется такой приём: мы обозначаем процедуру G, но тело процедуры прописываем, когда уже есть вторая процедура F.

Ничего нет сложного, когда работаем с двумя процедурами, которые вызывают друг друга. Действуем так же!

Процедура G(0) не вызовет процедуру F, т.к. не выполнится условие (n > 1), но данная процедура напечатает своё число, потому что команда печати не входит в условие.

Ответ напишем 6 + 3 + 0 = 9.

Алгоритм вычисления значения функции F(n), где n - натуральное число, задан следующими соотношениями:

Ответ в данной задачке получился 17.