Заметили ошибку ?
Выделите это место и нажмите Ctrl + Q

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


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


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


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


Задача (Стандартная)

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


БейсикPython
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!


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


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

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


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


Ответ: 4725147


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

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


БейсикPython
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 на экран стоит до условия, и она сработает в любом случае, если запустилась процедура! Условие только либо даёт запустится другим процедурам, либо нет.


ЕГЭ по информатике - задание 11 (рекурсивная функция графический метод)

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


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


Ответ: 4322322


Задача (Сколько звёздочек)

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

БейсикPython
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 не проходит условие. Значит, такие процедуры не запускают новых процедур. Оранжевым цветом показан ход выполнения программы.


ЕГЭ по информатике - задание 11 (количество звёздочек)

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


Ответ: 13


Задача (С двумя функциями F и G)

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


БейсикPython
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.


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


ЕГЭ по информатике - задание 11 (С двумя функциями F и G)

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


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


Ответ: 9


Задача (Нужно знать!)

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


F(n) = F(n - 1) + n - 2, при n > 1
F(1) = 2

Чему равно значение функции F(7) ?
В ответе запишите только натуральное число.

Решение:

F(7) = F(6) + 7 - 2 = F(5) + 6 - 2 + 7 - 2 = F(4) + 5 - 2 + 6 - 2 + 7 - 2 =

= F(3) + 4 - 2 + 5 - 2 + 6 - 2 + 7 - 2 = F(2) + 3 - 2 + 4 - 2 + 5 - 2 + 6 - 2 + 7 - 2 =

= F(1) + 2 - 2 + 3 - 2 + 4 - 2 + 5 - 2 + 6 - 2 + 7 - 2 =

= 2 + 2 - 2 + 3 - 2 + 4 - 2 + 5 - 2 + 6 - 2 + 7 - 2 = 17

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


Ответ: 17




23-06-2020 в 09:49:22





Похожая статья:

ЕГЭ по информатике - Задание 2 (Мощнейший метод)

Сегодня разберём, как решать второе задание из ЕГЭ по информатике 202...

Категория: ЕГЭ  Подкатегория: -
Дата: 15-01-2018 в 16:47:34 0



Оставить коментарий:



Напишите email, чтобы получать сообщения о новых комментариях (необязательно):


Задача против робота. Расположите картинки горизонтально:


Последние
видео:



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





Давайте
дружить!


Группа Вконтакте Code-Enjoy

Твиттер Александра Калужского

YouTube канал Code-Enjoy