Рекурсивные алгоритмы. (ЕГЭ Задание 11)

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

Что нужно знать:

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

существуют языки программирования, в которых рекурсия используется как один из основных приемов обработки данных

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

procedure F(n: integer);

begin

 writeln(n);

 if n < 6 then begin

   F(n+2);

   F(n*3)

 end

end;

Найдите сумму чисел, которые будут выведены при вызове F(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(wl)- 4*F(w-2) при w > 2.

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

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

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

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

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

18.  Алгоритм вычисления значений функций 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(wl)- 3*F(w-2) при w > 2.

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

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

F(1) = 1; F(2) = 2;

F(n) = 5*F(n-l)- 6*F(n-2) при n > 2.

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

22.  Алгоритм вычисления значения функции 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).