Рекурсия
презентация к уроку (7, 8, 9, 10 класс) на тему

Размещена презентация для проведения занятия по теме "Рекурсия" в дополнительном образовании для учащихся 7-10 классов и документ, построенный по материалам сайта учителя информатики 163 школы СПб Константина Полякова http://nsportal.ru/

Скачать:

Предварительный просмотр:


Подписи к слайдам:

Слайд 1

Рекурсия Презентация разработана Шороховой Евгенией Анатольевной (ДДЮТ «На Ленской», СПб) с применением материала с сайта http ://kpolyakov. spb . ru 27.12.2015

Слайд 2

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

Слайд 3

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

Слайд 4

Дан рекурсивный алгоритм : ( http ://kpolyakov. spb . ru ) procedure F( n : integer); begin writeln (n); if n < 5 then begin F(n + 1); F(n + 3) end end; Найдите сумму чисел, которые будут выведены при вызове F(1).

Слайд 5

1 2 4 5 3 4 5 7 6 5 7 + (5 +7) = writeln (n); if n < 5 then begin F(n + 1); F(n + 3) 49 1+ (2+4) = +(3+5)+ (5 +7) = + (4+6) = 7 27 37

Слайд 6

// снежинка Var Xc , Yc , R : integer; var i : integer const k1=1.8 ; k2=0.3; // коэффициенты // рекурсивная процедура procedure Elem ( x, y, r, p: integer); // x,y - rоординаты , r - радиус, // p - параметр для остановки рекурсии var x1,y1: integer;

Слайд 7

begin if p<=4 then begin DrawEllipse ( x-r, y-r, x+r , y+r ); Redraw; sleep(100); x1:= Round ( x+r * k1 * Cos( 0 )); y1:= Round (y+r * k1 * Sin( 0 )); Elem(x1, y1,Round( r *k2), p+1); // повторить вызов еще пять раз, чтобы // получилась снежинка, меняя угол от нуля до // 5 * Pi / 3 end;

Слайд 8

Begin // главная программа Window.Title := (' Рекурсия - снежинка'); Window.Init (400, 20, 800, 600); Window.clear ( clDarkBlue ); LockDrawing ; Xc := Window.Width div 2; Yc := Window.Height div 2; R := Window.Height div 6; SetPenColor ( clWhite ); Elem( Xc , Yc , R, 1); end.

Слайд 9

Результат работы программы Снежинка с рекурсивной процедурой Elem

Слайд 10

На компьютере сделать рекурсивную программу по любому алгоритму из файла “ege11.doc” показать Сделать снежинку показать Перевести любую рекурсию на циклы.



Предварительный просмотр:

© К. Поляков, 2012-2015

11 (базовый уровень, время – 5 мин)

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

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

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

Пример задания:

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

procedure F(n: integer);

begin

  writeln(n);

  if n < 5 then begin

    F(n + 1);

    F(n + 3)

  end

end;

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

Решение (вариант 1, построение дерева вызовов):

  1. поскольку в начале каждого вызова на экран выводится значение единственного параметра функции, достаточно определить порядок рекурсивных вызовов и сложить значения параметров
  2. поскольку при  выполняется два рекурсивных вызова, решать такую задачу «на бумажке» удобно в виде двоичного дерева (в узлах записаны значения параметров при вызове функции):

  1. складывая все эти числа, получаем 49
  2. ответ: 49.

Решение (вариант 2, подстановка):

  1. можно обойтись и без дерева, учитывая, что при каждом вызове с n < 5 происходит два рекурсивных вызова; сумму чисел, полученных при вызове , обозначим через :

  1. выполняем вычисления:

 

  1. теперь остаётся вычислить ответ «обратным ходом»:
  2. Ответ: 49.

Ещё пример задания:

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

procedure F(n: integer);

begin

 writeln(n);

 if n < 6 then begin

   F(n+2);

   F(n*3)

 end

end;

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

Решение (вариант 1, метод подстановки):

  1. сначала определим рекуррентную формулу; обозначим через G(n) сумму чисел, которая выводится при вызове F(n)
  2. при n >= 6 процедура выводит число n и заканчивает работу без рекурсивных вызовов:

G(n) = n при n >= 6

  1. при n < 6 процедура выводит число n и дважды вызывает сама себя:

G(n) = n + G(n+2) + G(3n) при n < 6

  1. в результате вызова F(1) получаем

G(1) = 1 + G(3) + G(3)

G(3) = 3 + G(5) + G(9) = 3 + G(5) + 9

G(5) = 5 + G(7) + G(15) = 5 + 7 + 15 = 27

  1. используем обратную подстановку:

G(3) = 3 + G(5) + 9  = 3 + 27 + 9 = 39

G(1) = 1 + 2*G(3) = 79

  1. Ответ: 79.

Решение (вариант 2, динамическое программирование):

  1. п. 1-3 такие же, как в первом варианте решения
  2. заполняем таблицу G(n) при n >= 6 (где G(n) = n)

n

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

G(n)

6

7

8

9

10

11

12

13

14

15

  1. остальные ячейки заполняем, начиная с n = 5 справа налево, используя формулу :

G(n) = n + G(n+2) + G(3n)

 n

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

G(n)

79

30

39

22

27

6

7

8

9

10

11

12

13

14

15

  1. ответ читаем в самой левой ячейке
  2. Ответ: 79.

Пример задания:

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

procedure F(n: integer);

begin

 writeln('*');

 if n > 0 then begin

   F(n-2);

   F(n div 2)

 end

end;

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

Решение (вариант 1, составление полной таблицы):

  1. сначала определим рекуррентную формулу; обозначим через G(n) количество звездочек, которые выводит программа при вызове F(n)
  2. из программы видим, что

G(n) = 1 при всех n <= 0

G(n) = 1 + G(n-2) + G(n div 2) при n > 0

  1. вспомним, что n div 2 – это частное от деления n на 2
  2. по этим формулам заполняем таблицу, начиная с нуля:

G(0) = 1

G(1) = 1 + G(-1) + G(0) = 1 + 1 + 1 = 3

G(2) = 1 + G(0) + G(1) = 1 + 1 + 3 = 5

G(3) = 1 + G(1) + G(1) = 1 + 3 + 3 = 7

G(4) = 1 + G(2) + G(2) = 1 + 5 + 5 = 11

G(5) = 1 + G(3) + G(2) = 1 + 7 + 5 = 13

G(6) = 1 + G(4) + G(3) = 1 + 11 + 7 = 19

G(7) = 1 + G(5) + G(3) = 1 + 13 + 7 = 21

n

0

1

2

3

4

5

6

7

G(n)

1

3

5

7

11

13

19

21

  1. Ответ: 21.

Решение (вариант 2, «с конца»):

  1. пп. 1-3 – как в варианте 1
  2. по формулам G(7) = 1+ G(5) + G(3), поэтому нужно найти G(5) и G(3)
  3. G(5) = 1 + G(3) + G(2), нужны G(3) и G(2)
  4. G(3) = 1 + G(1) + G(1), нужно G(1)
  5. G(2) = 1 + G(0) + G(1) = 2 + G(1), нужно G(1)
  6. G(1) = 1 + G(-1) + G(0) = 1 + 1 + 1 = 3
  7. теперь идем «обратным ходом»:

G(2) = 2 + G(1) = 5

G(3) = 1 + G(1) + G(1) = 1 + 3 + 3 = 7

G(5) = 1 + G(3) + G(2) = 1 + 7 + 5 = 13

G(7) = 1 + G(5) + G(3) = 1 + 13 + 7 = 21

  1. Ответ: 21.

Пример задания:

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

F(1) = 1; 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)?

В ответе запишите только целое число.

Решение:

  1. фактически рекуррентная формула задана для пары (F(n); G(n))
  2. замечаем, что F(n) – это разность предыдущей пары, а G(n) – сумма тех же значений
  3. заполняем таблицу, начиная с известной первой пары

n

1

2

3

4

5

F(n)

1

0

–2

–4

–4

G(n)

1

2

2

0

–4

  1. искомое значение F(5)/G(5) равно 1
  2. ответ: 1.

Ещё пример задания:

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

задан следующими соотношениями:

F(1) = 1

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

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

В ответе запишите только целое число.

Решение:

  1. используя заданную рекуррентную формулу, находим, что

F(5) = F(4) * 5

  1. применив формулу еще несколько раз, получаем

F(5) = F(3) * 4 * 5 = F(2) * 3 * 4 * 5 = F(1) * 2 * 3 * 4 * 5

  1. мы дошли до базового случая, который останавливает рекурсию, так как определяет значение F(1) = 1
  2. окончательно F(5) = 1 * 2 * 3 * 4 * 5 = 120
  3. ответ: 120.

Ещё пример задания:

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

procedure F(n: integer);

begin

  if n < 3 then

    write('*')

  else begin

    F(n-1);

    F(n-2);

    F(n-2)

  end;

end;

Сколько звездочек напечатает эта процедура при вызове F(6)? В ответе запишите только целое число.

Решение:

  1. эта задача по сути такая же, как и предыдущая, но «завёрнута» в другой фантик: для n < 3 (то есть, для 1 и 2) функция выводит одну звездочку

F(1) = F(2) = 1

а для бóльших n имеем рекуррентную формулу

 F(n) = F(n-1) + F(n-2) + F(n-2)

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

  1. запишем в таблицу базовые случаи

n

1

2

3

4

5

6

F(n)

1

1

  1. заполняем таблицу, используя рекуррентную формулу:

n

1

2

3

4

5

6

F(n)

1

1

3

5

11

21

F(3) = F(2) + 2*F(1) = 3

F(4) = F(3) + 2*F(2) = 5

F(5) = F(4) + 2*F(3) = 11

F(6) = F(5) + 2*F(4) = 21

  1. ответ: 21.

Задачи для тренировки[1]:

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

F(1) = 1

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

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

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

F(1) = 1

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

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

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

F(1) = 1

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

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

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

F(1) = 1

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

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

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

F(1) = 1

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

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

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

F(0) = 1, F(1) = 1

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

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

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

F(0) = 1, F(1) = 1

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

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

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

F(0) = 1, F(1) = 1

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

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

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

F(0) = 1, F(1) = 1

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

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

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

F(0) = 1, F(1) = 1

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

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

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

F(0) = 1, F(1) = 1

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

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

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

F(1) = 1, F(2) = 1

F(n) = F(n-2)*n, при n > 2

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

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

F(1) = 1, F(2) = 1

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

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

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

F(1) = 1, F(2) = 1

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

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

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

F(1) = 1, F(2) = 1

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

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

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

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

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

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

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

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

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

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

  1. (http://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)?

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

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

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

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

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

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

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

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

  1. (http://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)?

  1. (http://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)?

  1. Алгоритм вычисления значений функций 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)? В ответе запишите только целое число.

  1. Алгоритм вычисления значений функций 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)? В ответе запишите только целое число.

  1. Алгоритм вычисления значений функций 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)? В ответе запишите только целое число.

  1. Алгоритм вычисления значений функций 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)? В ответе запишите только целое число.

  1. Алгоритм вычисления значений функций 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)? В ответе запишите только целое число.

  1. Алгоритм вычисления значений функций 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)? В ответе запишите только целое число.

  1. Алгоритм вычисления значений функций 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)? В ответе запишите только целое число.

  1. Алгоритм вычисления значений функций 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)? В ответе запишите только целое число.

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

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

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

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

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

procedure F(n: integer);

begin

 writeln('*');

 if n > 0 then begin

   F(n-3);

   F(n div 2);

 end

end;

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

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

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

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

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

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

procedure F(n: integer);

begin

writeln('*');

 if n > 0 then begin

   writeln('*');

   F(n-2);

   F(n div 2);

 end

end;

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

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

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

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

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

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

procedure F(n: integer);

begin

 if n > 0 then begin

    F(n-2);

    F(n-1);

    F(n-1);

 end;

 writeln('*');

end;

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

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

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

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

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

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

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

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

F(1) = 1,

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

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

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

procedure F(n: integer);

begin

 writeln(n);

 if n < 6 then begin

   F(n+2);

   F(n*3)

 end

end;

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

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

procedure F(n: integer);

begin

 writeln(n);

 if n < 5 then begin

   F(n+2);

   F(n*2)

 end

end;

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

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

procedure F(n: integer);

begin

 writeln(n);

 if n < 5 then begin

   F(n+3);

   F(n*3)

 end

end;

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

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

procedure F(n: integer);

begin

 writeln(n);

 if n < 7 then begin

   F(n+3);

   F(n*2)

 end

end;

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

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

procedure F(n: integer);

begin

 writeln(n);

 if n < 7 then begin

   F(n+2);

   F(n+3)

 end

end;

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

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

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).

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

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).

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

procedure F(n: integer);

begin

 writeln(n);

 if n < 6 then begin

   writeln(n);

   F(n+2);

   F(n*3)

 end

end;

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

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

procedure F(n: integer);

begin

 writeln(n);

 if n < 5 then begin

   writeln(n);

   F(n+3);

   F(n*3)

 end

end;

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

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

procedure F(n: integer);

begin

 writeln(n);

 if n < 6 then begin

   writeln(n);

   F(n+2);

   F(n+3)

 end

end;

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

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

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).

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

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).

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

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).

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

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).

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

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

F(n) = F(n-2)*(n+2) при n > 2.

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

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

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

F(n) = F(n-2)*(n+1) при n > 2.

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

                http://kpolyakov.spb.ru


[1] Источники заданий:

  1. Демонстрационные варианты ЕГЭ 2013 гг.
  2. Проверочные работы МИОО.

По теме: методические разработки, презентации и конспекты

Основы программирования: ТЕМА 10. РЕКУРСИЯ.

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

Понятие рекурсии. Построение рекурсивных алгоритмов в среде исполнителя

Открытый урок по теме "Алгоритмизация" для 9-х классов. К описанию урока приложена презентация с примерами результатов работы рекурсивных алгоритмов в среде "kTurtle" и подробное описание хода урока (...

Презентация к урокам информатики и ИКТ по теме «Алгоритмизация. Рекурсии в алгоритмах»

Рекомендуется к работе с учащимися средней школы при изучении темы «Алгоритмизация. Рекурсии в алгоритмах». В презентации даны подробные объяснения, практические задания и присутствует иллюстративный ...

Что такое рекурсия

Презентация является дополнением  к уроку по теме "Рекурсия". В презентации представлены примеры из различных областей знаний по теме "Рекурсия"....

Рекурсия для исполнителя Робот в системе программирования КУМИР

Разработка содержит презентацию к уроку "Рекурсия для исполнителя Робот в системе программирования КУМИР", а также стартовые обстановки и программы для рассматриваемых задач (пример, практическая рабо...

Использование языка программирования Python для решения задачи 16 ЕГЭ по информатике (Рекурсия)

В статье приводится пример решения задачи 16 ЕГЭ по информатике (Рекурсия), которое успешно решается с помощью программы на языке программирования Python....