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


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

  • Рекурсия
  • Презентация к уроку информатики
  • Тема: программирование на языке 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