1. Главная
2. Обучение
3. ЕГЭ информатика

---

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

Документы по теме:

Задания для самостоятельного решения

Задание 16.   Рекурсия. Рекурсивные процедуры и функции

Для того, чтобы задать рекурсивную функцию, нужно определить

• условие окончания рекурсии, то есть значения параметров функции, для которых значение функции известно или вычисляется без рекурсивных вызовов;
• рекуррентную формулу (или формулы), с помощью которых значение функции для заданных значений параметров вычисляется через значение (или значения) функции для других значений параметров (то есть, с помощью рекурсивных вызовов)
• задачи, в которых требуется найти значение заданной рекурсивной функции при известных значениях параметров можно решать с помощью ручных вычислений, используя электронные таблицы или с помощью своей программы; последние два способа обычно более эффективны
• функцию

F(n) = 1 при n <= 1

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

можно реализовать следующим образом в виде функций на языке программирования Паскаль:

function F( n: integer ): integer;

begin

  if n <= 1 then

    Result := 1;

  else

    Result := n + 1 + F(n-1);

end;

Слово Result в Паскале в используется для возврата результата из функции.

Иногда можно использовать ручной расчет результата по формуле, но вычисления будут многочисленными, решение задания потребует много времени.

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

                   F(n) = 1 при n = 1

              F(n) = n + F(n–1), если n чётно,

              F(n) =  2· F(n–2), если n > 1 и n нечётно.

Чему равно значение функции F(26)?

Решение (ручной счёт от последнего значения):

• чтобы вычислить F(26), используем формулу для чётных n:

F(26) = 26 + F(25)

• нам неизвестно значение F(25), поэтому, применяя формулу для нечётных n, находим

F(25) = 2 × F(23)

• далее так же придётся написать формулы для вычисления F(23), F(21), …, F(3), и в конце мы получим

F(3) = 2 × F(1)

• значение F(1) = 1 нам задано, подставляя его в предыдущую формулу, находим

F(3) = 2 × F(1) = 2

• теперь значение подставляем в формулу для F(5), потом найденное значение F(5) – в формулу для F(7), и т.д.
• после продолжительных вычислений получим F(26) = 2074
• Ответ: 4122.

Более эффективный способ - написать и выполнить программу на любом языке программирования ( в данном случае язык Паскаль):

function F( n: integer ): integer;

begin

  if n = 1 then begin

  F := 1;

    Exit;

  end;

  if n mod 2 = 0 then

   F := n + F(n-1)

  else

  F:= 2 * F(n-2);

end;

begin

  writeln( F(26) )

end.

Разбор некоторых заданий ЕГЭ 16 с сайта К.Ю. Полякова (используется язык Паскаль)

Задача 18.

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

                   F(1) = G(1) = 1

              F(n) = 2·F(n–1) + G(n–1) – 2, если n > 1

              G(n) = F(n–1) +2·G(n–1), если n > 1

Чему равно значение F(14) + G(14)?

Программа:

function G(n:integer):integer;forward;
function F(n:integer):integer;
begin
if n=1
   then F:=1
   else if n>1
        then f:=2*F(n-1)+G(n-1)-2;
end;
function G(n:integer):integer;
begin
if n=1
   then  G:=1
   else if n>1
        then G:=F(n-1)+2*G(n-1);
end;
begin
writeln (F(14)+G(14));
end.

Задача 26. Определите наименьшее значение n, при котором сумма чисел, которые будут выведены при вызове F(n), будет больше 1000000. Запишите в ответе сначала найденное значение n, а затем через пробел – соответствующую сумму выведенных чисел.

Паскаль

procedure F     ( n: integer ); begin   writeln(n+1);   if n > 1 then begin     writeln(n+5);     F(n-1);     F(n-2);   end; end;

Решение: Вывод чисел в процедуре закомментирован, чтобы уменьшить время выполнения  программы.

var s,n:integer;
procedure F ( n: integer );
begin
  //writeln(n+1);
  s:=s+n+1;
  if n > 1 then begin
    //writeln(n+5);
    s:=s+n+5;
    F(n-1);
    F(n-2);
  end;
end;
begin
n:=0;
repeat
n:=n+1;
s:=0;
F(n);
until s>1000000;
writeln( n, ' ',s);
end.

Задача 56. 

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

                   F(n) =  n · n · n + n при n > 20

              F(n) = 3 · F(n+1) + F(n+3), при чётных n <= 20

              F(n) = F(n+2) + 2 · F(n+3), при нечётных n <=20

Определите количество натуральных значений n из отрезка [1; 1000], при которых значение F(n) не содержит цифру 1.

 

begin
if n>20 Then F:=n*n*n+n
else if n mod 2 =0 then F:= 3*F(n+1)+F(n+3)
                    else F:=F(n+2)+2*F(n+3);
                    end;
 begin
   k:=0;
   For n:=1 to 1000 do begin
     x:=F(n);
     s:=1;
     while x>0 do begin
       if x mod 10= 1 then s:=0;
       x:=x div 10;
       end;
      k:=k+s;
       end;
       writeln(k)   
 end.

---

Форма отчёта обучающегося: Файл

Принимается Файл изображения, архива или офисного документа (в т.ч. и pdf) до 15 мегабайт