Тема урока. «Рекурсивные алгоритмы» Словарик: Самоподобный объект Рекурсия Фрактал Кто вечно хнычет И скучает, Тот ничего Не замечает. Кто ничего Не замечает, - презентация

1 Тема урока. «Рекурсивные алгоритмы» Словарик: Самоподобный объект Рекурсия Фрактал Кто вечно хнычет И скучает, Тот ничего Не замечает. Кто ничего Не замечает, Тот ничего Не изучает. Кто ничего Не изучает, Тот вечно хнычет И скучает. Автор: Лимаренко Андрей Иванович, учитель информатики гимназии 446, Санкт-Петербург, Колпино

2 Сегодня на уроке Цель урока: Повторение понятия рекурсии. Повторение понятия фрактала и фрактальной геометрии построение фрактала с помощью рекурсивного алгоритма. Повторение графических возможностей среды быстрой разработки программ Pascal_ABC_Net Пример самоподобной геометрической фигуры

3 Повторение рекурсии Рекурсия это … процесс повторения элементов самоподобным образом. Самоподобный объект это объект, … в точности или приближённо совпадающий с частью себя самого (то есть целое имеет ту же форму, что и одна или более частей). Шли Из Африки В Саратов Семь Отчаянных Пиратов Не дошли До Душанбе - Видят надпись на столбе: "Шли Из Африки В Саратов..." (По Б.Заходеру. Рекурсия.) ПРИМЕРЫ: Приведите свои примеры рекурсии: - из литературы - из физики - из химии Приведите свои примеры рекурсии: - из литературы - из физики - из химии

4 Примеры рекурсии Какие из предложенных объектов являются рекурсией, а какие - нет Шёл по пустыне караван, Два ишака один баран. Вам эту песню не понять, И я начну её опять. Шел по пустыне караван…

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

6 Алгоритм, использующий рекурсию 1. Нарисовать окружность радиуса R с центром в точке (X,Y) 2. Нарисовать окружности радиусом R/2 с новыми координатами: (X+R; Y), (X; Y+R), (X-R; Y), (X; Y-R) 3. Для каждой из 4-х окружностей повторить п. 2 Глубина рекурсии алгоритма равна 3 (X,Y) Y (Y-R) (X+R) (X-R)X (Y+R)

7 Рекурсивный алгоритм Какова глубина рекурсии на картинке?

8 Пример рекурсивного алгоритма Классический пример - определение факториала. С одной стороны, факториал определяется так: n! = 1 · 2 · 3 · … · n С другой стороны, факториал можно определить следующим образом: Составьте словесный алгоритм вычисления факториала числа 5 n!= 1, если n1

9 Порядок вычисления факториала при n=5 Из определения факториала видно, что для вычисления факториала числа 5, необходимо знать значения факториала числа..., для вычисления факториала числа... необходимо знать значения факториала числа... и т.д. Вставьте в текст пропущенные слова n!= 1, если n1

10 Пример программы с рекурсией (факториал) 1. Program Rekurcia; 2. var 3. f: longint; 4. n: integer; 5. function factorial(n: integer):longint; 6. begin 7. if (n=0) or (n=1) then factorial:=1 8. else factorial:= factorial(n-1)*n; 9. end; 10. begin 11. write(n=); readln(n); 12. f:=factorial(n); 13. writeln (n,! =, f); 14. readln; 15. end. В какой строке программы содержится: 1. Вызов функции? 2. Рекурсия? В какой строке программы содержится: 1. Вызов функции? 2. Рекурсия? n!= 1, если n1

11 Как работает рекурсия в Паскале? Подставьте слова в текст... процедуры ничем не отличается от... другой процедуры. Что происходит, если одна процедура вызывает другую: в памяти размещаются..., передаваемые процедуре в другом месте памяти сохраняются... внутренних переменных вызывающей процедуры; запоминается... возврата в вызывающую процедуру;... передается вызванной процедуре. Если процедуру вызвать из нее самой, то будет выполняться тот же код, но работать он будет с другими значениями параметров. самовызов вызова параметры значения адрес управление

12 Фрактал и фрактальная геометрия Определение фрактала: Фрактал (лат. fractus дробленый, состоящий из фрагментов) термин, означающий геометрическую фигуру, обладающую свойством самоподобия, то есть составленную из нескольких частей, каждая из которых подобна всей фигуре целиком. Какую связь Вы заметили между фракталом и рекурсией?

13 Примеры рекурсивных алгоритмов на Паскале Как на практике использовать полученные теоретические знания? Попробуем применить рекурсивный алгоритм, чтобы из примитивного геометрического объекта получить объект, похожий на реальный природный. Эти объекты будут состоять из фрагментов, которые подобны самой фигуре (такие объекты как раз и называют фракталами). Можно ли применить рекурсивный алгоритм для создания геометрических фракталов? Программа на PascalABC

14 Что надо изменить в алгоритме, чтобы: 1. дерево рисовалось не слева направо, а наоборот? 2. увеличилась (уменьшилась) высота дерева? 3. увеличить количество веток? 4. наклонить дерево влево (вправо)? x, y - координаты начала линии alfa - угол наклона линии m - начальная длина линии v - количество ветвлений

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

16 Самое главное на уроке: Итак, давайте проанализируем нашу с вами совместную деятельность на уроке. О каких понятиях вы сегодня впервые услышали ? Какие дополнительные знания вы получили об уже знакомых вам понятиях (факториал)? Какое практическое применение имеют полученные вами знания? Назовите учебные предметы, где можно использовать знания о рекурсии и рекурсивных алгоритмах?

17 Спасибо за внимание!