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

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

Бейсик

Visual Basic
12345678 DECLARE SUB F(n)SUB F(n) IF n > 2 THEN PRINT n F(n - 3) F(n – 4) END IFEND SUB

Python

Python
12345 def F(n): if n > 2: print(n) F(n - 3) F(n – 4)

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

12345678 алг F(цел n)нач если n > 2 то вывод n, нс F(n - 3) F(n – 4) всекон

Паскаль

Delphi/Pascal
12345678 procedure F(n: integer);begin if n > 2 then begin writeln(n); F(n - 3); F(n – 4) endend;

Си

C
1234567 void F(int n) { if (n > 2) { printf("%d\n", n); F(n - 3); F(n – 4); }}

Чему равна сумма напечатанных на экране чисел при выполнении вызова
F(10)?

Демонстрационный вариант Единый государственный экзамен ЕГЭ 2017 г. – задание №11

Решение:

После каждого вызова на экран выводится значение параметра функции, если выполняется условие n>2.

Запишем все вызовы в виде таблицы.

F10
F7 F6
F4 F3 F3 F2
F1 F0 F0 F-1 F0 F-1 F-1 F-2

Складываем все значения параметров, которые больше 2.

10+7+6+4+3+3 = 33

Ответ: 33

Демонстрационный вариант Единый государственный экзамен ЕГЭ 2016 г. – задание №11

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

Бейсик

Visual Basic
1234567891011 DECLARE SUB F(n) DECLARE SUB G(n) SUB F(n)    IF n > 0 THEN G(n - 1) END SUB SUB G(n)    PRINT "*"    IF n > 1 THEN F(n - 3) END SUB

Python

Python
1234567 def F(n):    if n > 0:        G(n - 1)def G(n):    print("*")    if n > 1:        F(n - 3)

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

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

Паскаль

Delphi/Pascal
123456789101112131415 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;

Си

C
12345678910111213 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)?

Решение:

Рассмотрим задачу на языке Питон:

Python
1234567 def F(n):    if n > 0:        G(n - 1)def G(n):    print("*")    if n > 1:        F(n - 3)

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

F(11) вызывает G(10), G(10) вызывает F(7) и тд. до вызова F(-1) (так как n = -1 не больше 0, следовательно действие программы прекращается).

При каждом вызове функции G(n) печатается *. Таким образом количество звездочек равно количеству вызовов функции G(). В данном случае функция G() вызывается 3 раза.

Ответ: 3

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

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

F(1) = 1

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

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

Решение:

F(5)=F(5-1)*(5+2)=F(4)*7 = 120*7 = 840

F(4)=F(4-1)*(4+2)=F(3)*6 = 20*6 = 120

F(3)=F(3-1)*(3+2)=F(2)*5 = 4*5 = 20

F(2)=F(2-1)*(2+2)=F(1)*4 = 1*4 = 4

Ответ: 840

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

Дан рекурсивный алгоритм:

Python

Python
1234567 def F(n):  if n > 0:     print('*')     F(n-2)     F(n-1)     F(n-1)  print('*')

 

Паскаль

Delphi/Pascal
12345678910 procedure F(n: integer);begin if n > 0 then begin    writeln('*');    F(n-2);    F(n-1);    F(n-1); end; writeln('*');end;

Си

C
12345678910 void  F(int n){ if (n > 0) {    printf(″*″);    F(n-2);    F(n-1);    F(n-1); } printf(″*″);}

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

Решение:

Ответ: 197

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

F(1) = 4; F(2) = 5;

F(w) = 4*F(w–l)- 3*F(w-2) при w > 2.

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

Решение:

F(1) = 4; F(2) = 5;

F3 = 4.F2 – 3.F1 = 4.5 – 3.4 = 8

F4 = 4.F3 – 3.F2 = 4.8 – 3.5 = 17

F5 = 4.F4 – 3.F3 = 4.17 – 3.8 = 44

F6 = 4.F5 – 3.F4 = 4.44 – 3.17= 125

F7 = 4.F6 – 3.F5 = 4.125 – 3.44= 368

F8 = 4.F7 – 3.F6 = 4.368 – 3.125 = 1097

Ответ: 1097

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

F(1) = 1; Q(1) = 1;

F(w) = F(w-1) + 2*Q(w-1) при w > 1

Q(w) = Q(w-1) – 2*F(w-1) при w > 1.

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

Решение:

F(1) = 1; Q(1) = 1;

F2 = F1 + 2.Q1 = 1 + 2.1 = 3

Q2 = Q1 – 2.F1 = 1-2.1 = -1

F3 = F2 + 2.Q2 = 3 + 2.-1 = 1

Q3 = Q2 – 2.F2 = -1-2.3 = -7

F4 = F3 + 2.Q3 = 1 + 2.-7 = -13

Q4 = Q3 – 2.F3 = -7-2.1 = -9

F5 = F4 + 2.Q4 = -13 + 2.-9 = -31

Q5 = Q4 – 2.F4 = -9-2.-13 = 17

F(5)+Q(5) = -31+17 = -14

Ответ: -14

Дан рекурсивный алгоритм:

Паскаль Cи Python
procedure F(n: integer);
begin
writeln(‘*’);
if n > 0 then begin
F(n-2);
F(n div 2);
F(n div 2);
end
end;		 void F(int n)
{
printf(″*″);
if (n > 0) {
F(n-2);
F(n / 2);
F(n / 2);
}
}		 def F(n):
print(‘*’)
if n > 0:
F(n-2)
F(n // 2)
F(n // 2)

Сколько символов “звездочка” будет напечатано на экране при выполнении вызова F(5)?

Решение:

F5 (33+1=34) => F3 (13), F2 (10), F2 (10)

F3 (12+1) => F1 (4), F1 (4), F1 (4)

F2 (9+1) => F0 (1), F1 (4), F1 (4)

F1 (3+1) => F-1 (1), F0 (1), F0 (1)

Ответ: 34

Дан рекурсивный алгоритм:

Паскаль Cи Python
procedure F(n: integer);
begin
writeln(n);
if n < 7 then begin
F(n+3);
F(n*2)
end
end;		 void F(int n)
{
printf(″%d\n″,n);
if (n < 7){
F(n+3);
F(n*2);
}
}		 def F(n):
print(n)
if n < 7:
F(n+3)
F(n*2)

 

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

Решение:

 

F2 => F5, F4

F5 => F8, F10

F4 => F7, F8

2+5+4+8+10+7+8 = 44

Ответ: 44

Дан рекурсивный алгоритм:

Паскаль Cи Python
procedure F(n: integer);
begin
writeln(n);
if n < 6 then begin
writeln(n);
F(n+1);
F(n+2);
F(n*2)
end
end;		 void F(int n)
{
printf(″%d\n″,n);
if (n < 6 ){
printf(″%d\n″,n);
F(n+1);
F(n+2);
F(n*2);
}
}		 def F(n):
print(n)
if n < 6:
print(n)
F(n+1)
F(n+2)
F(n*2)

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

Решение:

F1 (1+1+214+100+214=530) => F2 (214), F3 (100), F2 (214)

F2 (2+2+100+55+55=214) => F3 (100), F4 (55), F4 (55)

F3 (3+3+55+33+6=100)=> F4 (55), F5 (33), F6 (6)

F4 (4+4+33+6+8=55) => F5 (33), F6 (6), F8 (8)

F5 (5+5+6+7+10=33)=> F6 (6), F7 (7), F10 (10)

F6 (6)

Ответ: 530

Дан рекурсивный алгоритм:

Паскаль Cи Python
function F(n: integer): integer;
begin
if n > 3 then
F:= F(n – 1) * F(n – 2)
else
F:= n;
end;		 int F(int n)
{
if (n > 3 )
return F(n – 1) * F(n – 2);
else
return n;
}		 def F(n):
if n > 3:
return F(n – 1) * F(n – 2)
else:
return n

Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(6)?

Решение:

 

F6 (108) => F5 (18) * F4 (6)

F5 (18) => F4 (6) * F3 (3)

F4 (6) => F3 (3) * F2 (2)

Ответ: 108

Ниже записаны две рекурсивные процедуры, F и G:

Паскаль Cи Python
procedure F(n: integer); forward;
procedure G(n: integer); forward;
procedure F(n: integer);
begin
writeln(‘*’);
if n > 0 then
G(n – 1);
end;
procedure G(n: integer);
begin
writeln(‘*’);
if n > 1 then
F(n – 2);
end;		  int F(int n)
{
printf(″*″);
if (n > 0)
G(n – 1);
}
int G(int n)
{
printf(″*″);
if (n > 1)
F(n – 2);
}		 def F(n):
print(‘*’)
if n > 0:
G(n – 1)

def G(n):
print(‘*’)
if n > 1:
F(n – 2)

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

Решение:

 

F13 (*)  => G12 (*)  => F10 (*)  => G9 (*)  => F7 (*)  => G6 (*)  => F4 (*)  => G3 (*)  => F1 (*) => G0 (*)

Ответ: 10