Рекурсивные алгоритмы

За правильное выполненное задание получишь 1 балл. На решение отводится примерно 5 минут.

Для выполнения задания 11 по информатике необходимо знать:

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

Чтобы определить рекурсию, нужно задать:

  1. условие остановки рекурсии (базовый случай или несколько базовых случаев)
  2. рекуррентную формулу

Любую рекурсивную процедуру можно запрограммировать с помощью цикла

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

Задачи для тренировки

Задача №1

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

Бейсик Python
DECLARE SUB F(n)
SUB F(n)
    IF n > 0 THEN
        PRINT n
        F(n - 3)
        F(n \ 3)
    END IF
END SUB
def F(n):
    if n > 0:
        print(n)
        F(n - 3)
        F(n // 3)
Паскаль Алгоритмический язык
procedure F(n: integer);
begin
    if n > 0 then begin
        writeln(n);
        F(n - 3);
        F(n div 3)
    end
end;
алг F(цел n)
нач
    если n > 0 то
        вывод n, нс
        F(n - 3)
        F(div(n, 3))
    все
кон
Си++
void F(int n) {
    if (n > 0) {
        std: :cout << n
        F(n - 3);
        F(n / 3);
    }
}

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

Задача №2

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

Паскаль  Си
 procedure F(n: integer);
 begin
   writeln('#');
   if n <= 6 then begin
        F(n*2); 
        F(n*2);
        F(n+2);
  end
   writeln('#'); 
end;
 
 void F(int n)                
 {
  std::cout <<"#";
  if (n <= 6) {
    F(n*2);
    F(n*2);
    F(n+2);
  }
  std::cout <<"#";
   }
 

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

Задача №3

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

Паскаль  С++
 procedure F(n: integer);
 begin
   writeln(n);
   if n < 5 then begin
         F(n+3); 
         F(n*2);
         F(n+1);
  end
   writeln(n);
   end;
 

 void F(int n)                
 {
  std::cout << n;  

    if (n < 5) {
     F(n+3);
     F(n*2);
     F(n+1);
  }
    std::cout << n;
     }
 

Найдите сумму чисел, которые будут выведены при вызове F(1).

Задача №4

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

Паскаль  С++
 procedure F(n: integer);
 begin
   writeln(n);
   if n < 5 then begin
         F(n + 7); 
         writeln(n);
         F(n + 3);
  end
   end;
 
 void F(int n)                
 {
  std::cout << n;
  if (n < 5) {
     F(n + 7);
     std::cout << n;
     F(n + 3);
  }
     }
 

Найдите сумму чисел, которые будут выведены при вызове F(-1).

Задача №5

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

Паскаль  С++

 procedure F(n: integer);
 begin
   writeln('#');
   if n > 0 then begin
        F(n-2); 
        F(n div 3);
        F(n-3); 
  end
 end;

 void F(int n)                
 {
  std::cout <<"#";
  if (n > 0) {
       F(n-2);
       F(n/3);
       F(n-3); 
  }
 }

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

Пройти тест

Начать