Задание 4. Тип заданий 11: рекурсивные алгоритмы.
  • Задание:

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

    Бейсик Python
    Procedure F(n: integer);
    begin
    if n mod 2 = 0 then
       writeln(‘*’)
    else
       writeln(‘**’);
    if n>0 then
       F(n-1);
    end;

    def F(n):
        if n > 0:
           G(n — 1)

    def G(n):
        print("*")
        if n > 1:
           F(n — 3)

    Алгоритмический язык Паскаль

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

    алг G(цел n)
    нач
       вывод "*"
       если n > 1 то
          F(n — 3)
       все
    кон

    procedure F(n: integer); forward;
    procedure G(n: integer); forward;

    procedure F(n: integer);
    begin
       if n > 0 then
          G(n — 1);
    end;

    procedure G(n: integer);
    begin
       writeln('*');
       if n > 1 then
          F(n — 3);
    end;

    Си

    void F(int n);
    void G(int n);

    void F(int n){
       if (n > 0)
          G(n — 1);
    }

    void G(int n){
       printf("*");
       if (n > 1)
          F(n — 3);
    }

    Сколько символов "звёздочка" будет напечатано на экране после выполнения вызова F(11)?

    Источник: демоверсия ФИПИ по информатике и ИКТ 2016-го года.

    В решении задания есть видеоразбор
  • Решение:

    Рекурсивная функция — это функция, вызывающая сама себя. Нам даны две процедуры со взаимной рекурсией, то есть процедура F вызывает процедуру G, а процедура G — процедуру F.

    Как мы видим, символ "звёздочка" выводится на экран при вызове процедуры G, при этом "звёздочка" печатается в любом случае, независимо от условия.

    То есть для решения задания нам достаточно определить, сколько раз будет вызвана процедура G при вызове F(11).

    Вызовы процедур мы можем записать так:

    F(11) -> G(10) -> F(7) -> G(6) -> F(3) -> G(2) -> F(-1)

    На процедуре F(-1) рекурсия завершится, так как условие n>0 перестанет выполняться.

    Осталось посчитать, сколько раз была вызвана процедура G:

    F(11) -> G(10) -> F(7) -> G(6) -> F(3) -> G(2) -> F(-1)

    Всего три раза.

    Ответ: 3

     

    Видеоразбор задания:

Поделиться:
 
Комментарии (2)
Олег Родин # 12 апреля 2016 в 15:52 0
В бейсике вроде код совсемм другой??????
Олег Родин # 12 апреля 2016 в 16:54 0
Добрый день. Все очень круто, понятно, СПАСИБО, но в последних "демках" вариант задания №11 вот такой. Можно представить такое-же понятное и простое решение как и в задачах Вашего раздела №11. да и собственно разместить его там. Еще раз большое спасибо!
Ниже на пяти языках программирования записаны рекурсивные функции F и G. (пусть будет Паскаль)
function F(n: integer):
integer;
begin
if n > 2 then
F := F(n-1)+G(n-1)+F(n-2)
else
F := n;
end;
function G(n: integer):
integer;
begin
if n > 2 then
G := G(n-1)+F(n-1)+G(n-2)
else
G := n+1;
end;
Чему будет равно значение, вычисленное при выполнении вызова G(5)?
Перевести число из в Результат: 510 = 1012