Презентация для подготовки к ЕГЭ по информатике по теме "Рекурсивные алгоритмы"
презентация к уроку по информатике и икт (11 класс) на тему

Слайд 1

Задание № 11 ЕГЭ (базовый уровень, время – 5 мин) Рекурсивные алгоритмы . Автор – Коротун О.В., учитель информатики МОУ «СОШ № 71»

Слайд 2

Содержание: Определение рекурсии Примеры решения задач Пример 1 Пример 2 Пример 3 Пример 4 Задания для тренировки

Слайд 3

Что нужно знать: Реку́рсия — в определении, описании, изображении какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя . Герб Российской Федерации является рекурсивно-определённым графическим объектом: в правой лапе изображённого на нём двуглавого орла зажат скипетр, который венчается уменьшенной копией герба. Так как на этом гербе в правой лапе орла также находится скипетр, получается бесконечная рекурсия. Рекурсивный герб России

Слайд 5

В программировании рекурсия — вызов функции из неё же самой, непосредственно или через другие функции, например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии . пример рекурсии: Если у вас жирное пятно на платье,не переживайте. Пятна от масла убираются бензином.Пятно от бензина раствором щёлочи.Щелочь убирается эссенцией.След от эссенции потрите маслом.Hу,а как убрать пятна от масла,вы уже знаете!

Слайд 6

Пример задания: Дан рекурсивный алгоритм : procedure F(n: integer); begin writeln (n); if n < 5 then begin F(n + 1); F(n + 3) end end ; Найдите сумму чисел, которые будут выведены при вызове F(1). Решение с помощью дерева вызовов: в начале каждого вызова на экран выводится значение единственного параметра функции

Слайд 7

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

Слайд 8

Пример задания: Дан рекурсивный алгоритм : procedure F(n: integer); begin writeln (n); if n < 5 then begin F(n + 1) ; F(n + 3) end end ; Найдите сумму чисел, которые будут выведены при вызове F(1). при n<5 выполняется два рекурсивных вызова, и на экране появляются следующие значения параметра: 1 4 2 +1 +3

Слайд 9

Пример задания: Дан рекурсивный алгоритм : procedure F(n: integer); begin writeln (n); if n < 5 then begin F(n + 1) ; F(n + 3) end end ; Найдите сумму чисел, которые будут выведены при вызове F(1). Продолжаем до тех пор, пока условие n<5 не станет ложным для узловых параметров. Получаем следующие значения: 1 2 4 5 3 4 5 7 6 5 7

Слайд 10

Пример задания: Дан рекурсивный алгоритм : procedure F(n: integer); begin writeln (n); if n < 5 then begin F(n + 1); F(n + 3) end end ; Найдите сумму чисел , которые будут выведены при вызове F(1). Продолжаем до тех пор, пока условие n<5 не станет ложным для узловых параметров. Получаем следующие значения: 1 2 4 5 3 4 5 7 6 5 7 Складывая все эти числа, получаем 49

Слайд 11

15 Пример № 2: Дан рекурсивный алгоритм: procedure F(n: integer); begin writeln (n); if n < 6 then begin F(n+2); F(n*3) end end ; Найдите сумму чисел, которые будут выведены при вызове F(1). 1 3 3 9 5 7 15 5 9 Складывая все эти числа, получаем 79 7 + 2 * 3 Аналогичная задача, которую можно решать с помощью дерева:

Слайд 12

Пример № 2: Дан рекурсивный алгоритм: procedure F(n: integer); begin writeln (n); if n < 6 then begin F(n+2); F(n*3) end end ; Найдите сумму чисел, которые будут выведены при вызове F(1). А можно обойтись и без дерева! Пусть S(n) – это сумма чисел, которые будут выведены при вызове F(n). Тогда n+S (n+2)+S(n*3), n<6 S(n) = n, n Выполняем вычисления: S(1)=1+S(3)+S(3) S(3)=3+S(5)+S(9)=12+S(5) S(5)=5+S(7)+S(15)=5+7+15=27 Делаем обратный ход: S(3)=12+27=39 S(1)=1+39+39= 79

Слайд 13

Пример № 3: Дан рекурсивный алгоритм: procedure F(n: integer ); begin writeln ('*') ; if n > 0 then begin F(n-2); F(n div 2) end end ; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)? 7 5 3 2 3 1 1 1 1 В этом примере на экран выводятся не значения параметра n , а символ * -2 div 2 1 0 -1 0 -1 0 -1 -1 -1 0 0 0

Слайд 14

Пример № 3: Дан рекурсивный алгоритм: procedure F(n: integer ); begin writeln ('*'); if n > 0 then begin F(n-2); F(n div 2) end end ; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7 )? * Подсчитав количество «звездочек», получаем 21 В этом примере на экран выводятся не значения параметра n , а символ * * * * * * * * * * * * * * * * * * * * *

Слайд 15

Пример № 3: Дан рекурсивный алгоритм: procedure F(n: integer ); begin writeln ('*'); if n > 0 then begin F(n-2); F(n div 2) end end ; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7 )? Решим задачу без дерева. Пусть S(n) – это количество «звездочек», которые будут выведены при вызове F(n). Тогда 1+S(n-2 )+ S(n div 2), n>0 1 , n Нам нужно узнать S(7). S( 7 )= 1 +S( 5 )+ S(3) S( 5 )= 1 +S( 3 )+S( 2 ) S( 3 )= 1 +S( 1 )+S( 1) S(2)=1+S(0)+S(1)=1+1+S(1)=2+S(1) S( 1 )= 1+ S(-1)+S(0)=1+1+1=3 Делаем обратный ход : S(2)=2+3=5 S(3)=1+3+3=7 S(5)=1+7+5=13 S(7)=1+13+7= 21 S (n)=

Слайд 16

Пример № 4: 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)? В ответе запишите только целое число. 6 5 4 3 4 3 2 эта задача по сути такая же, как и предыдущая: для n < 3 функция выводит одну звездочку, а для бóльших n продолжаем рисовать дерево -1 -2 4 -2 3 2

Слайд 17

Пример № 4: 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)? В ответе запишите только целое число. 6 5 4 3 4 3 * -1 -2 4 -2 3 * Вторая и третья ветви абсолютно одинаковые, поэтому будем рисовать одну, а количество «звездочек» потом умножим на 2. При условии n<3 на экране появляются «звездочки».

Слайд 18

Пример № 4: 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)? В ответе запишите только целое число. 6 5 4 3 4 3 -1 -2 4 -2 3 ** 3 ** *** *** *** *** Получаем по первой ветви 11 «звездочек», по третьей, а значит и по второй – по 5. Всего – 21 При условии n<3 на экране появляются «звездочки».

Слайд 19

Пример № 4: 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)? В ответе запишите только целое число. Решим задачу без дерева. Пусть S(n) – это количество «звездочек», которые будут выведены при вызове F(n). Тогда S(n-1)+S(n-2)+S(n-2), n 1 , n ИЛИ S(n-1)+ 2* S(n-2) , n 1 , n S (n)= S (n)=

Слайд 20

Пример № 4: 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)? В ответе запишите только целое число. S(n-1)+ 2* S(n-2) , n 1 , n S (n)= Нам нужно узнать S( 6 ). S( 6 )=S( 5 )+ 2* S( 4 ) S( 5 )=S( 4 )+ 2* S( 3 ) S( 4 )=S( 3 )+ 2* S( 2) S( 3 )=S( 2 )+ 2* S( 0 )=S( 2 )+2*1=S( 2 )+2 S( 2 )= 1 Делаем обратный ход: S(3)=1+2=3 S(4)=3+2*1=5 S(5)=5+2*3=11 S(6)=11+2*5= 21

Слайд 21

Задания для тренировки

Слайд 22

Задача 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)? Ответ: 34

Слайд 23

Задача 2: Дан рекурсивный алгоритм : 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)? Ответ: 58

Слайд 24

Задача 3: Дан рекурсивный алгоритм : procedure F(n: integer); begin writeln('*'); if n > 0 then begin F(n-3); F(n div 2); end end ; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)? Ответ: 15

Слайд 25

Задача 4: Дан рекурсивный алгоритм : 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)? Ответ: 55

Слайд 26

Задача 5: Дан рекурсивный алгоритм : 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)? Ответ: 97

Слайд 27

Задача 6: Дан рекурсивный алгоритм : procedure F(n: integer); begin writeln('*'); if n > 0 then begin writeln('*'); F(n-2); F(n div 2); end end ; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)? Ответ: 31

Слайд 28

Задача 7: Дан рекурсивный алгоритм : 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)? Ответ: 81

Слайд 29

Задача 8: Дан рекурсивный алгоритм : 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)? Ответ: 77

Слайд 30

Задача 9: Дан рекурсивный алгоритм : procedure F(n: integer); begin if n > 0 then begin F(n-2); F(n-1); F(n-1); end; writeln('*'); end ; Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(5)? Ответ: 148

Слайд 31

Задача 10: Дан рекурсивный алгоритм : 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)? Ответ: 197

Слайд 32

Задача 11: Дан рекурсивный алгоритм : 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)? Ответ: 88

Слайд 33

Задача 12: Дан рекурсивный алгоритм : 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)? Ответ: 33

Слайд 34

Задача 13: Дан рекурсивный алгоритм : procedure F ( n : integer ); begin writeln(n); if n < 6 then begin F(n+2); F(n*3) end end ; Найдите сумму чисел, которые будут выведены при вызове F(2). Ответ: 30

Слайд 35

Задача 14: Дан рекурсивный алгоритм : procedure F ( n : integer ); begin writeln(n); if n < 5 then begin F(n+2); F(n* 2 ) end end ; Найдите сумму чисел, которые будут выведены при вызове F(1). Ответ: 53

Слайд 36

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

Слайд 37

Задача 16: Дан рекурсивный алгоритм : procedure F ( n : integer ); begin writeln(n); if n < 7 then begin F(n+ 3 ); F(n* 2 ) end end ; Найдите сумму чисел, которые будут выведены при вызове F(2). Ответ: 44

Слайд 38

Задача 17: Дан рекурсивный алгоритм : procedure F ( n : integer ); begin writeln(n); if n < 7 then begin F(n+ 2 ); F(n +3 ) end end ; Найдите сумму чисел, которые будут выведены при вызове F(1). Ответ: 81

Слайд 39

Задача 18: Дан рекурсивный алгоритм : 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). Ответ: 103

Слайд 40

Задача 19: Дан рекурсивный алгоритм : 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). Ответ: 79

Слайд 41

Задача 20: Дан рекурсивный алгоритм : procedure F ( n : integer ); begin writeln(n); if n < 6 then begin writeln(n); F(n+2); F(n*3) end end ; Найдите сумму чисел, которые будут выведены при вызове F(2). Ответ: 36

Слайд 42

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

Слайд 43

Задача 22: Дан рекурсивный алгоритм : 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). Ответ: 425

Слайд 44

Задача 23: Дан рекурсивный алгоритм : 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). Ответ: 530

Слайд 45

Задача 24: Дан рекурсивный алгоритм : 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). Ответ: 169

Слайд 46

Задача 25: Дан рекурсивный алгоритм : 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). Ответ: 426