Презентация "Рекурсия" 9 класс

Скачать материал

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

Рекурсия

Презентация к уроку информатики
Тема: программирование на языке PascalABC
Автор: Юдин Андрей Борисович
МКОУ Плесская СОШ

Часть 1

Рекурсия — это такой способ организации вспомогательного алгоритма (подпрограммы), при котором эта подпрограмма (процедура или функция) в ходе выполнения ее операторов обращается сама к себе.

Рекурсивным называется любой объект, который частично определяется через себя.

Определение рекурсии 1

Уроборос – змей, пожирающий свой хвост.
Рисунок из алхимического трактата «Synosius» Теодора Пелеканоса (1478г).

Определение рекурсии 2

Program n1;
uses crt;
procedure Rec(i: integer);
begin
if i>1 then Rec(i-1);
writeln(i);
end;
begin
clrscr;
Rec(5);
end.

рекурсивный подъём

Процедура закрывается и выводится i

Пока i больше 1 вызываем следующую процедуру

Определение рекурсии 3

Вызов Rec(5)

Вызов Rec(4)

Вызов Rec(3)

Вызов Rec(2)

Вызов Rec(1)
Вывод (1)

Вывод (2)

Вывод (3)

Вывод (4)

Вывод (5)

i>1

i

Rec(i-1)

5

4

3

2

1

5>1 Да

4>1 Да

3>1 Да

2>1 Да

1>1 Нет

Rec(4)

Rec(3)

Rec(2)

Rec(1)

Вывод(1)

Определение рекурсии 4

Процедура 5

Процедура 4

Процедура 3

Процедура 2

Процедура 1

Вывод 5

Вывод 4

Вывод 3

Вывод 2

Вывод 1

Пока i>1 то вызываем очередную
процедуру

Рекурсивный подъем

Определение рекурсии 5

Program n2;
uses crt;
procedure Rec(i: integer);
begin
writeln(i);
if i>1 then Rec(i-1);
end;
begin
clrscr;
Rec(5);
end.

рекурсивный спуск

Вывод

Переход к следующей процедуре

Определение рекурсии 6

i>1

Вывод i

Rec(i-1)

5

4

3

2

1

5>1 Да

4>1 Да

3>1 Да

2>1 Да

1>1 Нет

Rec(4)

Rec(3)

Rec(2)

Rec(1)

Rec(i)

Rec(5)

Rec(4)

Rec(3)

Rec(2)

Rec(1)

Определение рекурсии 7

Процедура 4

Процедура 3

Процедура 2

Процедура 1

Процедура 5

Вывод 5

Вывод 4

Вывод 3

Вывод 2

Вывод 1

Пока i>1 то вызываем очередную
процедуру

Рекурсивный спуск

Определение рекурсии 8

Program n3;
Uses crt;
Procedure Print(n:integer);
Begin
Writeln ('У попа была собака,');
Writeln ('Он ее любил.');
Writeln ('Она съела кусок мяса —');
Writeln ('Он ее убил.');
Writeln ('Убил и закопал');
Writeln ('И на могиле написал:');
if n>1 then Print(n-1);
End;
BEGIN
Print(4);
END.

рекурсивный спуск

Вывод

Переход к следующей процедуре

Определение рекурсии 9

Program n4;
uses crt;
procedure Rec(i: integer);
begin
writeln(i);
if i>1 then Rec(i-1);
writeln(i);
end;
begin
clrscr;
Rec(5);
end.

рекурсивный спуск,
и рекурсивный подъем

Спуск

Подъем

Определение рекурсии 10

Задача. Заполнить массив из 5 элементов порядковыми номерами элементов массива. И найти сумму элементов массива.

Program n4;
uses crt;
var s,i:integer;
a:array[1..5] of integer;
begin
clrscr; S:=0;
for i:=1 to 5 do begin
a[i]:=i;
writeln(a[i]);
S:=S+a[i];
end;
writeln('Cумма =',s);
end.

Сумма итеративно

Определение рекурсии 11

uses crt;
var s,i:integer;
a:array[1..5] of integer;
procedure summ(i: integer);
begin
if i>1 then summ(i-1);
begin
S:=S+a[i];
writeln(a[i]);
end;
end;
begin
clrscr;
for i:=1 to 5 do a[i]:=i;
summ(5);
writeln('Сумма=',s);
end.

Рекурсивная процедура

Определение рекурсии 12

Процедура

Вызов процедуры из основной программы

Program n5_2;
uses crt;
Var a:array[1..5] of integer;
I: integer;
Function Summ(i : integer) : Integer;
Begin
If i = 0 Then Summ := 0
Else Summ := A[i] + Summ(i - 1)
End;
Begin
clrscr;
for i:=1 to 5 do a[i]:=i;
WriteLn('Cумма = ', Summ(5))
End.

Рекурсивная функция

Определение рекурсии 13

Функция

Вызов функции из основной программы

Последовательность, каждый член которой, начиная со второго, равен предыдущему, сложенному с одним и тем же числом d, называется арифметической прогрессией. Число d - разность прогрессии. Таким образом, арифметическая прогрессия есть последовательность, заданная рекуррентно равенством:

Например:

Определение рекурсии 14

Program n6;
uses crt;
Var k,I: integer;
Function Progr(i,n,d : integer) : Integer;
Begin
If i = 1 Then Progr := n
Else Progr := d + Progr(i - 1,n,d);
End;
Begin
clrscr;
i:=4;
WriteLn(i,' член равен = ', Progr(i,2,3))
End.

Номер вычисляемого элемента

Первый элемент

Разность прогрессии

Определение рекурсии 15

Рекурсивно вызываем функцию

Факториа́л числа n (лат. factorialis — действующий, производящий, умножающий; обозначается n!, произносится эн факториа́л) — произведение всех натуральных чисел от 1 до n включительно.

если n=0 или n=1

если n>1

Например:

5!=1∙2∙3∙4∙5=120

Например:

1!=1
2!=1! ∙ 2=1 ∙ 2=2
3!=2! ∙3=2 ∙ 3=6
4!=3! ∙4=6 ∙ 4=24
5!=4! ∙5=24 ∙5=120

Определение рекурсии 16

uses crt;
var
fac: longint;
n, i: integer;
begin
clrscr;
write('n = '); readln(n);
fac := 1;
for i:=2 to n do fac := fac * i;
writeln(n,'! = ', fac);
end.

Начальное значение факториала

Циклом находим произведение от 2 до n

Определение рекурсии 17

Факториал итеративно

Факториал рекурсией

uses crt;
var n:integer;
function fac ( n : integer): integer;
begin
if (n = 1) or (n=0) then fac := 1
else fac:= n*fac(n-1);
end;
begin
clrscr;
write('n = '); readln(n);
writeln(n,'! = ', fac(n));
end.

Начальное значение факториала

Вызываем повторно функцию вычисления факториала

Определение рекурсии 18

Задачи для самостоятельного решения

1. Определим функцию K(n), которая возвращает количество цифр в заданном натуральном числе n. Составить программу определяющую количество цифр в числе с использованием рекурсии.

2. Разработать программу для нахождения наибольшего общего делителя (НОД) двух заданных натуральных чисел используя алгоритм Евклида

Определение рекурсии 19

Математиком Исследовательского центра корпорации IBM Бенуа Мандельбротом в 1975 году был введен термин “фрактал” (от латинского fractus – раздробленный, разбитый, состоящий из фрагментов), а в 1982 году опубликована основополагающая книга “Фрактальная геометрия природы”, где описаны фрактальные множества, их свойства, методы получения и изображения.

Фракталы 20

Фракталы 21

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

uses crt, graphabc;
var x,y,x2,y2,i:integer;
begin
clrscr;
x := random(640);
y := random(400);
for i:=1 to 25 do begin
x2 := random(640);
y2 := random(400);
line(x,y,x2,y2);
x:=x2;
y:=y2;
end;
textout(200,330,'n=25');
end.

Координаты начала первой линии

Цикл задающий количество звеньев

Координаты конца линии

Линия

Координаты конца линии становятся координатами начала следующей линии

Фракталы 22

Фракталы 23

uses crt, graphabc;
procedure segment(x,y,x2,y2,n: integer );
begin
x2 := random(640);
y2 := random(400);
line(x,y,x2,y2);
if n > 1 then
segment(x2,y2,random(640),random(400),n-1);
end;
begin
clrscr;
segment(320,200, 0, 0, 25);
textout(200,330,'n=25');
end.

Координаты начала линии

Линия

Пока n>1 вызываем еще одну процедуру

Координаты начала звена

Координаты конца звена

Количество звеньев

Фракталы 24

Задача. Составить программу изображающую на экране спираль.

X

Y

x,y: real;
Начало линии

x2,y2: real;
Конец линии

Pi/2 угол поворота

Pi/2 угол под которым начинаем движение

Stwol длина одной линии

Фракталы 25

uses crt, graphabc;
procedure scroll(x,y,A,Stwol: real;n: integer );
var
x2, y2: real;
begin
x2 := x + Stwol * cos(A);
y2 := y - Stwol * sin(A);
line(round(x), round(y), round(x2), round(y2));
if n > 1 then
scroll( x2, y2, A+Pi/2, Stwol+5, n-1);
end;
begin
clrscr;
scroll(300, 200, Pi/2, 10, 50);
textout(200,330,'n=50');
end.

Вычисляем координаты конца линии

Рисуем линию

Пока n>1 вызываем процедуру рисования линии

Для каждой следующей линии поворачиваем на 90 градусов

Каждую новую линию удлиняем на 5 единиц

Фракталы 26

Угол начала движения Pi/4 (45 градусов)

Фракталы 27

Угол наклона линии Pi/4 (45 градусов)

Фракталы 28

Координаты корня
Координаты точки разветвления
Угол под которым растер ветка
Длина ствола
Количество разветвлений (рекурсивных вызовов)

Фракталы 29

Stwol: real; длина ствола

x2,y2: real; координаты точки разветвления

x,y: real;
координаты корня

а: real;
Угол под которым растет дерево
(Начальное Pi/2)

X

Y

A+pi/4 и A-pi/4 угол на который отклоняется новая ветка

Фракталы 30

procedure Tree(x,y,A,Stwol: real;n: integer );
var
x2, y2: real;
begin
x2 := x + Stwol * cos(A);
y2 := y - Stwol * sin(A);
line(round(x), round(y),round(x2), round(y2));
if n > 1 then
begin
Tree( x2, y2, A+Pi/4, 0.6*Stwol, n-1);
Tree( x2, y2, A-Pi/4, 0.6*Stwol, n-1);
end;
end;

Координаты точки разветвления

Рисуем одну ветвь

Пока n>1 два раза вызываем процедуру для правой и левой ветки

Фракталы 31

begin
clrscr;
Tree(175, 325, Pi/2, 120, 14);
textout(200,330,'n=14');
end.

Вызов рекурсивной процедуры из тела программы

Фракталы 32

Треугольник Серпинского

Фракталы 33

Задача. Составить программу изображающую на экране треугольник Серпинского .

X

Y

line(x,y,x2,y2)

line(x3,y3,x2,y2)

line(x,y,x3,y3)

(x,y)

(x2,y2)

(x3,y3)

(xa,ya)

(xb,yb)

(xc,yc)

x,y
xa, ya
xc, yc

x2,y2
xa, ya
xb, yb

x3,y3
xb, yb
xc, yc

Фракталы 34

procedure rec(x,y, x2,y2, x3,y3, n:integer);
var xa, ya, xb, yb, xc, yc:integer;
begin
if n >0 then
begin
line(x,y,x2,y2);
line(x3,y3,x2,y2);
line(x,y,x3,y3);
xa:=(x+x2) div 2; ya:=(y+y2) div 2;
xb:=(x3+x2) div 2; yb:=(y3+y2) div 2;
xc:=(x+x3) div 2; yc:=(y+y3) div 2;
rec(x,y,xa, ya, xc, yc, n-1);
rec(x2,y2,xa, ya, xb, yb, n-1);
rec(x3,y3,xb, yb, xc, yc, n-1);
end;
end;

Рисуем треугольник

Вычисляем координаты середин сторон треугольника

Рекурсивно рисуем три меньших треугольника

Фракталы 35

Begin
clrscr;
rec(100,350,300,50,500,350,7);
End.

Вызываем рекурсивную процедуру

Фракталы 36

Задачи для самостоятельного решения

1. Составьте программы выводящие на экран следующие изображения с использованием рекурсии:

Фракталы 37

Множество Кантора.

Снежинка

Задачи для самостоятельного решения

2. Составьте программы выводящие на экран следующие изображения с использованием рекурсии:

Фракталы 38

Задачи для самостоятельного решения

3. Составьте программы выводящие на экран следующие изображения с использованием рекурсии:

Фракталы 39

Задача. Необходимо составить программу для вычисления значений некоторого полинома (многочлена), определение которого имеет следующий вид:

40

function p(n:integer; x:real):real;
{ n - степень полинома, x- значение аргумента}
var p0,p1,p2:real; i:integer;
begin
if n=0 then p:=0
else if n=1 then p:=2*x
else begin
p0:=0;
p1:=2*x;
for i:=2 to n do begin
p2:=2*i/(i-1)*p1+(i-1)/(2*i)*p0;
p0:=p1;
p1:=p2;
end;
p:=p2;
end;
end;

Значения полинома при 0 и 1

Устанавливаем начальные значения

Вычисляем значения полинома до n используя цикл

Итеративная функция:

41

function p(n:integer; x:real):real;
{ n - степень полинома, x- значение аргумента}
begin
if n=0 then
p:=0
else
if n=1 then p:=2*x
else
p:=2*n/(n-1)*p(n-1,x)+(n-1)/(2*n)*p(n-2,x);
end;

Значения полинома при 0 и 1

Вызываем функцию повторно

Рекурсивная функция:

42

uses crt,Utils ;
var d1: DateTime;
function p(n:integer; x:real):real;
{определение функции}
begin
clrscr;
d1 := CurrentDateTime;
Writeln(' Время: ',d1.hour,':',d1.minute,
':',d1.second,':',d1.Milliseconds div 100);
writeln(p(35,5));
d1 := CurrentDateTime;
Writeln(' Время: ',d1.hour,':',d1.minute,
':',d1.second,':',d1.Milliseconds div 100);
end.

Здесь поместим одну из описанных выше функций

Переменная для хранения системного времени

Считываем системное время и выводим его на экран

Вызываем функцию

Считываем системное время и выводим его на экран

43

Рекурсивная функция:
n = 35
Время выполнения =
25,8 с

Итеративная функция:
n = 35
Время выполнения <1 мс

44

Тест скорости выполнения итеративной и рекурсивной программы

Light-bot - игра-головоломка для обучения программированию

Описание функции F1

Вызов функции F1 внутри функции F1

45

http://www.tvd-home.ru/recursion Персональная страничка Диканева Тараса Викторовича

http://comp-science.narod.ru/Progr/Rekursia.html Сайт Шестакова Александра Петровича

http://fraktalsworld.blogspot.ru/ Сайт «В мире фракталов» автор Александр Чернышев

http://www.cyberforum.ru/pascalabc/thread994987.html Ветвь форума по программированию. Автор ildwine.

Интернет ресурсы:

46

Златопольский Д.М. Программирование: типовые задачи, алгоритмы, методы. М.: БИНОМ. Лаборатория знаний, 2007

Бердж В. Методы рекурсивного программирования. Издательство: Машиностроение. 1983
Источник для скачивания книги: http://progbook.ru/technologiya-programmirovaniya/924-berdj-metody-rekursivnogo-programmirovaniya.html

Головешкин В.А., Ульянов М. В. Теория рекурсии для программистов. М.: ФИЗМАТЛИТ, 2006.

Список литературы:

47

Информатика - еще материалы к урокам:

Copyright © 2013-2024 "Учителя.com" | Обратная связь: [email protected]