Тема: рекурсивные алгоритмы.
Что нужно знать:
· рекурсия – это приём, позволяющий свести исходную задачу к одной или нескольким более простым задачам того же типа
· чтобы определить рекурсию, нужно задать
o условие остановки рекурсии (базовый случай или несколько базовых случаев)
o рекуррентную формулу
· любую рекурсивную процедуру можно запрограммировать с помощью цикла
· рекурсия позволяет заменить цикл и в некоторых сложных задачах делает решение более понятным, хотя часто менее эффективным
· существуют языки программирования, в которых рекурсия используется как один из основных приемов обработки данных (Lisp, Haskell)
Задачи для тренировки [1]:
1) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1
F(n) = F(n–1) * (n + 1), при n > 1
Чему равно значение функции F(5)? В ответе запишите только целое число.
2) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1
F(n) = F(n–1) * (n + 2), при n > 1
Чему равно значение функции F(5)? В ответе запишите только целое число.
3) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1
F(n) = F(n–1) * (2*n + 1), при n > 1
Чему равно значение функции F(4)? В ответе запишите только целое число.
4) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1
F(n) = F(n–1) * (2*n - 1), при n > 1
Чему равно значение функции F(5)? В ответе запишите только целое число.
5) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1
F(n) = F(n–1) * (3*n - 2), при n > 1
Чему равно значение функции F(4)? В ответе запишите только целое число.
6) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(0) = 1, F(1) = 1
F(n) = F(n–1) + F(n-2), при n > 1
Чему равно значение функции F(7)? В ответе запишите только целое число.
7) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(0) = 1, F(1) = 1
F(n) = 2*F(n–1) + F(n-2), при n > 1
Чему равно значение функции F(6)? В ответе запишите только целое число.
8) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(0) = 1, F(1) = 1
F(n) = F(n–1) + 2*F(n-2), при n > 1
Чему равно значение функции F(6)? В ответе запишите только целое число.
9) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(0) = 1, F(1) = 1
F(n) = 3*F(n–1) - F(n-2), при n > 1
Чему равно значение функции F(6)? В ответе запишите только целое число.
10) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(0) = 1, F(1) = 1
F(n) = F(n–1)*F(n-2)+1, при n > 1
Чему равно значение функции F(6)? В ответе запишите только целое число.
11) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(0) = 1, F(1) = 1
F(n) = F(n–1)*F(n-2)+2, при n > 1
Чему равно значение функции F(5)? В ответе запишите только целое число.
12) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1, F(2) = 1
F(n) = F(n-2)*n, при n > 2
Чему равно значение функции F(7)? В ответе запишите только целое число.
13) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1, F(2) = 1
F(n) = F(n-2)*n + 2, при n > 2
Чему равно значение функции F(8)? В ответе запишите только целое число.
14) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1, F(2) = 1
F(n) = F(n-2)*(n-1), при n > 2
Чему равно значение функции F(7)? В ответе запишите только целое число.
15) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1, F(2) = 1
F(n) = F(n-2)*(n-1) + 2, при n > 2
Чему равно значение функции F(8)? В ответе запишите только целое число.
16) Алгоритм вычисления значения функции F(w), где w - натуральное число, задан следующими соотношениями:
F(1) = 3; F(2) = 3;
F(w) = 5*F(w-l)- 4*F(w-2) при w > 2.
Чему равно значение функции F(15)?
17) Алгоритм вычисления значения функции F(w), где w - натуральное число, задан следующими соотношениями:
F(1) = 4; F(2) = 5;
F(w) = 4*F(w-l)- 3*F(w-2) при w > 2.
Чему равно значение функции F(8)?
18) (https://ege.yandex.ru) Алгоритм вычисления значений функций F(w) и Q(w), где w - натуральное число, задан следующими соотношениями:
F(1) = 1; Q(1) = 1;
F(w) = F(w-l) + 2*Q(w-1) при w > 1
Q(w) = Q(w-l) - 2*F(w-1) при w > 1.
Чему равно значение функции F(5)+Q(5)?
19) Алгоритм вычисления значения функции F(w), где w - натуральное число, задан следующими соотношениями:
F(1) = 1; F(2) = 2;
F(w) = 3*F(w-l)- 2*F(w-2) при w > 2.
Чему равно значение функции F(7)?
20) Алгоритм вычисления значения функции F(w), где w - натуральное число, задан следующими соотношениями:
F(1) = 2; F(2) = 4;
F(w) = 4*F(w-l)- 3*F(w-2) при w > 2.
Чему равно значение функции F(7)?
21) (https://ege.yandex.ru) Алгоритм вычисления значения функции F(n), где n - натуральное число, задан следующими соотношениями:
F(1) = 1; F(2) = 2;
F(n) = 5*F(n-l)- 6*F(n-2) при n > 2.
Чему равно значение функции F(7)?
22) (https://ege.yandex.ru) Алгоритм вычисления значения функции F(n), где n - натуральное число, задан следующими соотношениями:
F(1) = 1; F(2) = 2; F(3) = 3
F(n) = F(n-3)*(n-1)/3 при n > 3.
Чему равно значение функции F(16)?
23) Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 2; G(1) = 1;
F(n) = F(n–1) – G(n–1),
G(n) = F(n–1) + G(n–1), при n >=2
Чему равно значение величины F(5)/G(5)? В ответе запишите только целое число.
24) Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1; G(1) = 1;
F(n) = F(n–1) – G(n–1),
G(n) = F(n–1) + 2*G(n–1), при n >=2
Чему равно значение величины F(5)/G(5)? В ответе запишите только целое число.
25) Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1; G(1) = 1;
F(n) = F(n–1) – 2*G(n–1),
G(n) = F(n–1) + G(n–1), при n >=2
Чему равно значение величины G(5)/F(5)? В ответе запишите только целое число.
26) Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1; G(1) = 1;
F(n) = 2*F(n–1) – G(n–1),
G(n) = F(n–1) + 2*G(n–1), при n >=2
Чему равно значение величины G(5)+F(5)? В ответе запишите только целое число.
27) Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1; G(1) = 1;
F(n) = 2*F(n–1) – G(n–1),
G(n) = 2*F(n–1) + G(n–1), при n >=2
Чему равно значение величины F(5)-G(5)? В ответе запишите только целое число.
28) Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1; G(1) = 1;
F(n) = F(n–1) – 2*G(n–1),
G(n) = F(n–1) + 2*G(n–1), при n >=2
Чему равно значение величины G(5)-F(5)? В ответе запишите только целое число.
29) Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1; G(1) = 1;
F(n) = 3*F(n–1) – 2*G(n–1),
G(n) = F(n–1) + 2*G(n–1), при n >=2
Чему равно значение величины G(5)-F(5)? В ответе запишите только целое число.
30) Алгоритм вычисления значений функций F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1; G(1) = 1;
F(n) = 3*F(n–1) – 3*G(n–1),
G(n) = F(n–1) + 2*G(n–1), при n >=2
Чему равно значение величины F(5)-G(5)? В ответе запишите только целое число.
31) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln('*');
if n > 0 then begin
F(n-2);
F(n div 2);
F(n div 2);
End
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(5)?
32) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln('*');
if n > 0 then begin
F(n-2);
F(n-2);
F(n div 2);
End
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(6)?
33) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln('*');
if n > 0 then begin
F(n-3);
F(n div 2);
End
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?
34) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln('*');
if n > 0 then begin
F(n-3);
F(n-2);
F(n div 2);
End
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?
35) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln('*');
if n > 0 then begin
F(n-3);
F(n-2);
F(n div 2);
F(n div 2);
End
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(6)?
36) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln('*');
if n > 0 then begin
writeln('*');
F(n-2);
F(n div 2);
End
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?
37) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln('*');
if n > 0 then begin
writeln('*');
F(n-2);
F(n div 2);
F(n div 2);
End
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?
38) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln('*');
if n > 0 then begin
writeln('*');
F(n-2);
F(n-2);
F(n div 2);
End
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(6)?
39) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
if n > 0 then begin
F(n-2);
F(n-1);
F(n-1);
end;
writeln('*');
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(5)?
40) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
if n > 0 then begin
writeln('*');
F(n-2);
F(n-1);
F(n-1);
end;
writeln('*');
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(5)?
41) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
if n > 1 then begin
F(n-2);
F(n-1);
F(n div 2);
end;
writeln('*');
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?
42) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
if n > 2 then begin
writeln('*');
F(n-2);
F(n-1);
F(n div 2);
end;
writeln('*');
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(6)?
43) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1,
F(n) = F(n–1) + 2n-1, при n > 1
Чему равно значение функции F(12)? В ответе запишите только целое число.
44) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln(n);
if n < 6 then begin
F(n+2);
F(n*3)
End
end;
Найдите сумму чисел, которые будут выведены при вызове F(2).
45) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln(n);
if n < 5 then begin
F(n+2);
F(n*2)
End
end;
Найдите сумму чисел, которые будут выведены при вызове F(1).
46) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln(n);
if n < 5 then begin
F(n+3);
F(n*3)
End
end;
Найдите сумму чисел, которые будут выведены при вызове F(1).
47) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln(n);
if n < 7 then begin
F(n+3);
F(n*2)
End
end;
Найдите сумму чисел, которые будут выведены при вызове F(2).
48) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln(n);
if n < 7 then begin
F(n+2);
F(n+3)
End
end;
Найдите сумму чисел, которые будут выведены при вызове F(1).
49) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln(n);
if n < 5 then begin
F(n+2);
F(n+3);
F(n*2)
End
end;
Найдите сумму чисел, которые будут выведены при вызове F(1).
50) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln(n);
if n < 5 then begin
F(n+1);
F(n+2);
F(n*3)
End
end;
Найдите сумму чисел, которые будут выведены при вызове F(2).
51) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln(n);
if n < 6 then begin
writeln(n);
F(n+2);
F(n*3)
End
end;
Найдите сумму чисел, которые будут выведены при вызове F(2).
52) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln(n);
if n < 5 then begin
writeln(n);
F(n+3);
F(n*3)
End
end;
Найдите сумму чисел, которые будут выведены при вызове F(1).
53) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln(n);
if n < 6 then begin
writeln(n);
F(n+2);
F(n+3)
End
end;
Найдите сумму чисел, которые будут выведены при вызове F(1).
54) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln(n);
if n < 7 then begin
writeln(n);
F(n+1);
F(n+2);
F(n*3)
End
end;
Найдите сумму чисел, которые будут выведены при вызове F(2).
55) Дан рекурсивный алгоритм:
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;
Найдите сумму чисел, которые будут выведены при вызове F(1).
56) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln(n);
if n < 6 then begin
writeln(n);
F(n+1);
F(n*2);
F(n*3)
End
end;
Найдите сумму чисел, которые будут выведены при вызове F(2).
57) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln(n);
if n < 7 then begin
writeln(n);
F(n+2);
F(n*2);
F(n*3)
End
end;
Найдите сумму чисел, которые будут выведены при вызове F(1).
58) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 1 при n £ 2;
F(n) = F(n-2)*(n+2) при n > 2.
Чему равно значение функции F(8)?
59) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 1 при n £ 2;
F(n) = F(n-2)*(n+1) при n > 2.
Чему равно значение функции F(7)?
60) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln(n);
if n > 0 then begin
F(n-1);
F(n-3)
End
end;
Найдите сумму чисел, которые будут выведены при вызове F(5).
61) Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln(n);
if n > 1 then begin
F(n-3);
F(n-1)
End
end;
Найдите сумму чисел, которые будут выведены при вызове F(6).
62) Дан рекурсивный алгоритм:
function F(n: integer): integer;
Begin
if n > 2 then
F:= F(n - 1) + F(n - 2)
Else
F:= n;
end;
Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(5)?
63) (И. Тощенко) Дан рекурсивный алгоритм:
function F(n: integer): integer;
Begin
if n > 3 then
F:= F(n - 1) * F(n - 2)
Else
F:= n;
end;
Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(6)?
64) (И. Тощенко) Дан рекурсивный алгоритм:
function F(n: integer): integer;
Begin
if n >= 3 then
F:= F(n-3) + F(n-2)*F(n-1)
Else
F:= n;
end;
Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(7)?
65) (И. Тощенко) Дан рекурсивный алгоритм:
function F(n: integer): integer;
Begin
if n < 5 then
F:= F(n+2) + F(n+3) + F(n+1)
Else
F:= n;
end;
Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(2)?
66) (И. Тощенко) Дан рекурсивный алгоритм:
function F(n: integer): integer;
Begin
if n < 5 then
F:= F(n*3) + F(n+3) + F(n+1)
Else
F:= n div 2;
end;
Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(2)?
67) (И. Тощенко) Дан рекурсивный алгоритм:
function F(n: integer): integer;
Begin
if n < 5 then
F:= F(n+3) + F(2*n) + F(3*n div 2)
Else
F:= n + 2;
end;
Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(3)?
68) (И. Тощенко) Дан рекурсивный алгоритм:
function F(n: integer): integer;
Begin
if n < 6 then
F:= n+F(n+3) * F(2*n)
Else
F:= n*2;
end;
Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(3)?
69) (И. Тощенко) Дан рекурсивный алгоритм:
function F(n: integer): integer;
Begin
if n > 1 then
F:= 2*n + F(n-3) + F(n-2)
Else
F:= n + 5;
end;
Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(6)?
70) Ниже записаны две рекурсивные процедуры, F и G:
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 begin
writeln('*');
F(n - 2);
end;
end;
Сколько символов «звёздочка» будет напечатано на экране при выполнении
вызова F(13)?
71) Ниже записаны две рекурсивные процедуры, F и G:
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;
Сколько символов «звёздочка» будет напечатано на экране при выполнении
вызова F(13)?
72) Ниже записаны две рекурсивные процедуры, F и G:
procedure F(n: integer); forward;
procedure G(n: integer); forward;
procedure F(n: integer);
Begin
writeln('*');
if n > 0 then begin
writeln('*');
G(n - 1);
end;
end;
procedure G(n: integer);
Begin
writeln('*');
if n > 1 then
F(n - 2);
end;
Сколько символов «звёздочка» будет напечатано на экране при выполнении
вызова F(12)?
73) Ниже записаны две рекурсивные процедуры, F и G:
procedure F(n: integer); forward;
procedure G(n: integer); forward;
procedure F(n: integer);
Begin
writeln('*');
if n > 0 then begin
writeln('*');
G(n - 1);
end;
end;
procedure G(n: integer);
Begin
writeln('*');
if n > 1 then begin
writeln('*');
F(n - 2);
end;
end;
Сколько символов «звёздочка» будет напечатано на экране при выполнении
вызова F(12)?
74) Ниже на записан рекурсивный алгоритм F:
function F(n: integer): integer;
Begin
if n > 2 then
F:= F(n-1)+F(n-2)+F(n-3)
Else
F:= n;
end;
Чему будет равно значение, вычисленное алгоритмом при выполнении вызова F(6)?
75) Ниже записаны две рекурсивные процедуры, F и G:
procedure F(n: integer); forward;
procedure G(n: integer); forward;
procedure F(n: integer);
Begin
if n > 0 then begin
G(n - 1);
end;
end;
procedure G(n: integer);
Begin
writeln('*');
if n > 1 then begin
F(n - 3);
end;
end;
Сколько символов «звёздочка» будет напечатано на экране при выполнении
вызова F(11)?
76) Ниже записаны две рекурсивные функции, F и G:
function F(n: integer): integer;
Begin
if n > 2 then
F:= F(n - 1) + G(n - 2)
Else
F:= 1;
end;
function G(n: integer): integer;
Begin
if n > 2 then
G:= G(n - 1) + F(n - 2)
Else
G:= 1;
end;
Чему будет равно значение, вычисленное при выполнении вызова F(7)?
77) Ниже записаны две рекурсивные функции, F и G:
function F(n: integer): integer;
Begin
if n > 2 then
F:= F(n - 1) + G(n - 2)
Else
F:= n;
end;
function G(n: integer): integer;
Begin
if n > 2 then
G:= G(n - 1) + F(n - 2)
Else
G:= n+1;
end;
Чему будет равно значение, вычисленное при выполнении вызова F(6)?
[1] Источники заданий:
1. Демонстрационные варианты ЕГЭ 2013-2016 гг.
2. Диагностические работы МИОО и Статград.