Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Рекурсивные алгоритмы
Содержание
- 1. Рекурсивные алгоритмы
- 2. Содержание:Определение рекурсииПримеры решения задачПример 1Пример 2Пример 3Пример 4Задания для тренировки
- 3. Что нужно знать:Реку́рсия — в определении, описании, изображении
- 4. Слайд 4
- 5. В программировании рекурсия — вызов функции из
- 6. Пример задания: Дан рекурсивный алгоритм:procedure F(n: integer);begin
- 7. Пример задания: Дан рекурсивный алгоритм:procedure F(n: integer);begin
- 8. Пример задания: Дан рекурсивный алгоритм:procedure F(n: integer);begin
- 9. Пример задания: Дан рекурсивный алгоритм:procedure F(n: integer);begin
- 10. Пример задания: Дан рекурсивный алгоритм:procedure F(n: integer);begin
- 11. 15Пример № 2:Дан рекурсивный алгоритм:procedure F(n: integer);begin
- 12. Пример № 2:Дан рекурсивный алгоритм:procedure F(n: integer);begin
- 13. Пример № 3:Дан рекурсивный алгоритм:procedure F(n: integer);begin
- 14. Пример № 3:Дан рекурсивный алгоритм:procedure F(n: integer);begin
- 15. Пример № 3:Дан рекурсивный алгоритм:procedure F(n: integer);begin
- 16. Пример № 4:procedure F(n: integer);begin if n
- 17. Пример № 4:procedure F(n: integer);begin if n
- 18. Пример № 4:procedure F(n: integer);begin if n
- 19. Пример № 4:procedure F(n: integer);begin if n
- 20. Пример № 4:procedure F(n: integer);begin if n
- 21. Задания для тренировки
- 22. Задача 1:Дан рекурсивный алгоритм: procedure F(n:
- 23. Задача 2:Дан рекурсивный алгоритм: procedure F(n:
- 24. Задача 3:Дан рекурсивный алгоритм: procedure F(n:
- 25. Задача 4:Дан рекурсивный алгоритм: procedure F(n:
- 26. Задача 5:Дан рекурсивный алгоритм: procedure F(n:
- 27. Задача 6:Дан рекурсивный алгоритм: procedure F(n:
- 28. Задача 7:Дан рекурсивный алгоритм: procedure F(n:
- 29. Задача 8:Дан рекурсивный алгоритм: procedure F(n:
- 30. Задача 9:Дан рекурсивный алгоритм: procedure F(n:
- 31. Задача 10:Дан рекурсивный алгоритм: procedure F(n:
- 32. Задача 11:Дан рекурсивный алгоритм: procedure F(n:
- 33. Задача 12:Дан рекурсивный алгоритм: procedure F(n:
- 34. Задача 13:Дан рекурсивный алгоритм: procedure F(n:
- 35. Задача 14:Дан рекурсивный алгоритм: procedure F(n:
- 36. Задача 15:Дан рекурсивный алгоритм: procedure F(n:
- 37. Задача 16:Дан рекурсивный алгоритм: procedure F(n:
- 38. Задача 17:Дан рекурсивный алгоритм: procedure F(n:
- 39. Задача 18:Дан рекурсивный алгоритм: procedure F(n:
- 40. Задача 19:Дан рекурсивный алгоритм: procedure F(n:
- 41. Задача 20:Дан рекурсивный алгоритм: procedure F(n:
- 42. Задача 21:Дан рекурсивный алгоритм: procedure F(n:
- 43. Задача 22:Дан рекурсивный алгоритм: procedure F(n:
- 44. Задача 23:Дан рекурсивный алгоритм: procedure F(n:
- 45. Задача 24:Дан рекурсивный алгоритм: procedure F(n:
- 46. Задача 25:Дан рекурсивный алгоритм: procedure F(n:
- 47. Скачать презентанцию
Содержание:Определение рекурсииПримеры решения задачПример 1Пример 2Пример 3Пример 4Задания для тренировки
Слайды и текст этой презентации
Слайд 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).
Слайд 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
+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 не станет ложным для узловых параметров. Получаем следующие значения:
Слайд 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 не станет ложным для узловых параметров. Получаем следующие значения:
Складывая все эти числа, получаем 49
Слайд 1115
Пример № 2:
Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln(n);
if n
< 6 then begin
F(n+2);
F(n*3)
end
end;
Найдите сумму
чисел, которые будут выведены при вызове F(1).Складывая все эти числа, получаем 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).
Слайд 13Пример № 3:
Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln('*');
if n
> 0 then begin
F(n-2);
F(n div 2)
endend;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?
В этом примере на экран выводятся не значения параметра 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)
endend;
Сколько символов "звездочка" будет напечатано на экране
при выполнении вызова F(7)?
Подсчитав количество «звездочек», получаем 21
В этом примере на экран выводятся не значения параметра n, а символ *
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
Слайд 15Пример № 3:
Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln('*');
if n
> 0 then begin
F(n-2);
F(n div 2)
endend;
Сколько символов "звездочка" будет напечатано на экране
при выполнении вызова F(7)?
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)? В ответе запишите только целое число.
эта задача по сути такая же, как и предыдущая: для 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)? В ответе запишите только целое число.
-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)? В ответе запишите только целое число.
-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)=
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)=
Нам нужно узнать 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
Слайд 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
