L/O/G/O Тема 10. Рекурсия и диалоговые программы 1 Алгоритмизация и основы программирования Лектор: Шаймерденова Л.Е. - презентация

1 L/O/G/O Тема 10. Рекурсия и диалоговые программы 1 Алгоритмизация и основы программирования Лектор: Шаймерденова Л.Е.

2 Определения Рекурсия это такой способ организации вспомогательного алгоритма (подпрограммы), при котором эта подпрограмма (процедура или функция) в ходе выполнения ее операторов обращается сама к себе. Рекурсивным называется любой объект, который частично определяется через себя. В рекурсивном определении должно присутствовать ограничение, граничное условие, при выходе на которое дальнейшая инициация рекурсивных обращений прекращается.

3 3 Рекурсивные объекты Рекурсивті объект деп - бір объект немесе дәл осындай бірнеше объект арқылы анықталатын объектіні айтады. Примеры: Факториал: если Рекурсивная картинка:

4 4 Дерево Пифагора N уровневое дерево Пифагора – это ствол и симметричные ветки из ствола, каждая ветка дерева в 2 раза короче предыдущей ветки, а угол между ветками равен 90 o. 6 уровень: Как доказать, что это рекурсивная фигура? ?

5 5 Дерево Пифагора Особенности : Когда остановить? Угол наклона ветки - разный Қалған деңгейлердің саны нөлге тең болғанда! (x 1, y 1 ) (x 0, y 0 ) α α+45 o α-45 o L x 1 = x 0 + L · cos(α) y 1 = y 0 – L·sin(α) x 1 = x 0 + L · cos(α) y 1 = y 0 – L·sin(α) Угол наклона длочерних веток α + π/4 α – π/4 α + π/4 α – π/4

6 6 Процедура α угол Длина ветки procedure Pifagor(x0, y0, a, L: real; N: integer); const k = 0.6; { изменение длины } var x1, y1: real; { локальные переменные} begin if N > 0 then begin x1 := x0 + L*cos(a); y1 := y0 - L*sin(a); Line (round(x0), round(y0), round(x1), round(y1)); Pifagor (x1, y1, a+pi/4, L*k, N-1); Pifagor (x1, y1, a-pi/4, L*k, N-1); end; Рекурсивный вызов при N=0 завершить Рекурсивной процедурой называется процедура, которая во время выполнения вызывает сама себя.

7 7 Программа program qq; procedure Pifagor(x0, y0, a, L: real; N: integer);... end; begin Pifagor (250, 400, pi/2, 150, 8); end; α угол длина ветки Количество уровней x0x0 x0x0 y0y0 y0y0 Как наклонить ветку на 30 o вправо? ? Pifagor (250, 400, 2*pi/3, 150, 8);

8 Факториал Факториал определяется по формуле: n!=1*2*3*...*n. Факториал во-вторых можно определить: При этом граничным условием является :

9 Функция факториала {Функция на Pascal} Function Factorial(N:integer):Extended; Begin If N<=1 Then Factorial:=1 Else Factorial:=Factorial(N-1)*N End;

10 uses crt; var X, F : integer; {Функция на Pascal} Function Factorial(N:integer):integer; Begin If N<=1 Then Factorial:=1 Else Factorial:=Factorial(N-1)*N End; {основная программа} begin write ('введите число X='); read (X); F := factorial(X); writeln('Факториал ',x,' = ', F) end. Программа факториала При каком значении Х стек переполняется и программа начинает выдавать не верный ответ? Как устранить эту ошибку?

11 Подводя итог, заметим, что использование рекурсии является красивым приёмом программирования. В то же время в большинстве практических задач этот приём неэффективен с точки зрения расходования таких ресурсов ЭВМ, как память и время исполнения программы. Использование рекурсии увеличивает время исполнения программы и зачастую требует значительного объёма памяти для хранения копий подпрограммы на рекурсивном спуске. Поэтому на практике разумно заменять рекурсивные алгоритмы на итеративные.

12 12 "4": Разработайте следующие фигуры используя рекурсивную процедуру "5": Разработайте следующие фигуры используя рекурсивную процедуру Задания

13 Вопросы 1. Какой вспомогательный алгоритм (подпрограмма) называются рекурсивными? Приведите собственные примеры. 2. Что такое граничное условие, и каково его назначение в рекурсивной подпрограмме? 3. Что такое глубина рекурсии? Чему равна глубина рекурсии в приведённых выше примерах?

14 14 Диалоговые программы 1. Использование операторов Write (WriteLn) 2. Проверка ввода данных (например, на числовое содержание) с использованием функции ReadKey. 3. Использование подтверждения на вопрос. 4. Использование цветовых эффектов. 5. Ответы с заполнением бланков. 6. Построение меню Способы организации диалога

15 15 Использование операторов Write (WriteLn) : Write (Введите значение a b c ); Read (a,b,c); Простейшие ошибки в этом случае? -ввод переменных через запятую – использование запятой при вводе дробной части действительных чисел Диалоговые программы

16 16 Использование функции ReadKey : var ho : char; … Repeat ho:= ReadKey; If (ho>=#48) and (ho<=#57) {код цифры} or (ho=#46) {код точки} or (ho=#45) {код знака минус} then... Until ho = # 13 {код клавиши Enter} Диалоговые программы

17 17 Использование подтверждения на вопрос: var ch : char; … Write (Вы уверены? (Д/Н)); Write ( Вы проверили? (Д/Н)); Write ( Будете еще вводить данные? (Д/Н)); Read(ch); … If ch= Д then … … While ch = Д … Repeat … Until ch <> Д Диалоговые программы

18 18 Использование цветовых эффектов: Uses CRТ; Процедуры и функции модуля CRT: ClrScr GotoXY (x,y); TextBackGround ( color); {цвета от 0-7} TextColor (color); {цвета от 0-15} Delay (время в мс); Sound (частота звука в герц) NoSound Windows (x1,y1, x2,y2); Диалоговые программы

19 0Қара / black 1Көк / blue 2Жасыл/ green 3Бирюзовый 4Қызыл/ red 5Малина 6Қоңыр/ brown 7Ашық-сұр / gray 8Қою-сұр 9Ашық-көгілдір 10Ашық-жасыл 11Ашық-бирюзовый 12Ашық-қызыл 13Ашық-малина 14Сары / yellow 15Ақ / 128Жылтылдау / blink Цвета модуля CRT:

20 20 Ответы с заполнением бланков: _____________________ (фамилия имя отчество) ____/_____/________ (дата рождения) __________________ (национальность) Диалоговые программы

21 21 Построение меню: Диалоговые программы

22 Pascal ABC Forms Каждый компонент имеет свойства, методы и события.

23 Вопросы Что такое диалоговые программы? Перечислите способы организации диалоговых программ. Ошибки при использовании оператолров Write / read? Как можно их исправить?