Презентация "Рекурсивные алгоритмы"

Рекурсивные алгоритмы Задание № 11 ЕГЭ (базовый уровень, время – 5 мин)

Автор – Коротун О.В.,

учитель информатики МОУ «СОШ № 71»

Содержание:

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

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

Рекурсивный герб России

В программировании рекурсия — вызов функции из неё же самой, непосредственно или через другие функции, например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии. В программировании рекурсия — вызов функции из неё же самой, непосредственно или через другие функции, например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.

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

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

Решение с помощью дерева вызовов:

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

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

1

Пример задания: Дан рекурсивный алгоритм: 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

Пример задания: Дан рекурсивный алгоритм: 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

Пример задания: Дан рекурсивный алгоритм: 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

Пример № 2:

15

Дан рекурсивный алгоритм: 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

Аналогичная задача, которую можно решать с помощью дерева:

Пример № 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

 

Пример № 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

Пример № 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, а символ *

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

*

Пример № 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)=

Пример № 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

Пример № 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 на экране появляются «звездочки».

Пример № 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 на экране появляются «звездочки».

Пример № 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)=

Пример № 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

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

Ответ: 34

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

Ответ: 58

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

Ответ: 15

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

Ответ: 55

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

Ответ: 97

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

Ответ: 31

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

Ответ: 81

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

Ответ: 77

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

Ответ: 148

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

Ответ: 197

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

Ответ: 88

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

Ответ: 33

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

Ответ: 30

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

Ответ: 53

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

Ответ: 42

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

Ответ: 44

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

Ответ: 81

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

Ответ: 103

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

Ответ: 79

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

Ответ: 36

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

Ответ: 50

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

Ответ: 425

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

Ответ: 530

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

Ответ: 169

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

Ответ: 426