Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Рекурсия.
Рекурсия – это вывоз подпрограммой (процедурой или функцией) самой себя. Рассмотрим построение рекурсивной функции на примере вычисления N!. При правильно организованной рекурсивной подпрограммы осуществляется многократный переход от некоторого текущего уровня организации алгоритма к низшему уровню последовательно до тех пор, пока не будет получено тривиальное решение поставленной задачи. PROGRAM DEMO1; USES CRT; VAR M: BYTE; FUNCTION FAKT(N: BYTE): LONGINT; BEGIN IF N=1 THEN FAKT: =1 ELSE FAKT: =FAKT(N-1)*N; END; BEGIN CLRSCR; WRITE('N-'); READLN(M); WRITELN('N! =', FAKT(M)); READKEY; END. В нашем примере происходит так: в операторе печати вызывается функция FAKT с параметрам N, которая в свою очередь вызывает функцию FAKT с параметрам N-1, и так далее, пока не вызывается FAKT(1). Тогда это процесс останавливается, затем происходить извлечение результата в обратном порядке. Это хорошо видно на следующем примере программы:
Рекурсивная форма организации алгоритма обычно выглядит изящнее итерационной и дает более компактный текст программы, но при выполнении, как правили, медленнее и может вызвать переполнение стека. Стек – это специальная область памяти (конечное число ячеек), где сохраняется адреса возврата (адрес вызывающей программы, используется для передачи управления вызывающей программе). Стеки используются так же для передачи параметров в процедуры (для обычных параметров в стек заносятся их значения, для параметров-переменных – их адреса), размер стек ограничен. Стек можно представить в виде стопки книг. Если стопка достигла максимального размера, то при добавлении новой книги сверху – нижняя книга должна быть убрана. Нужно обязательно отслеживать в программе наполнение стека, то есть не допускать зацикливания рекурсии. Рекурсивный вызов может быть косвенным. В этом случае программа обращается к себе опосредованно, путем вызова другой программы, в которой содержится обращение к первой. При использовании такого подхода нужно использовать опережающее описание. Опережающее описание заключается в том, что объявляется лишь заголовок процедуры, а ее тело заменяется директивой FORWARD. После этого можно в другой процедуре использовать обращение к ней – ведь компилятор уже может правильным образом организовать ее вызов. Обратите внимание: тело второй процедуры описывается после первой и начинается заголовком, в котором уже не указываются описанные ранее формальные параметры. Пример: PROCEDURE B(J: BYTE); FORWARD; {тело процедуры заменено директивой FORWARD } PROCUDURE A(I: BYTE); BEGIN … B(I); … END; PROCEDURE B; BEGIN … A(J); … END;
Примеры программ с процедурами и функциями: При составлении программ обязательно использовать процедуры или функцию. · Найти разность двух факториалов F=m! – k!, используя функцию.
· Написать программу «Бегущие огни» с использованием процедуры рисования окружности.
Примеры программ с использованием рекурсий:
Написать рекурсивную функцию вычисления суммы 1+2+3+4+5+…+N: PROGRAM DEMO5; USES CRT; VAR M: WORD; FUNNCTION SUM(N: WORD): LONGINT; BEGIN IF N=1 THEN SUM: =1 ELSE SUM: =SUM(N-1)+N; END; BEGIN WRITE(‘N-‘); READLN(M); WRITELN(‘СУММА -’, SUM(M)); READKEY; END.
ТЕМА №7: ПРОГРАММИРОВАНИЕ НА ЯЗЫКЕ PASCAL (КОНСОЛЬНОЕ ПРИЛОЖЕНИЕ DELPHI). МАССИВЫ, ОДНОМЕРНЫЕ И ДВУХМЕРНЫЕ. СОСТАВЛЕНИЕ ПРОГРАММ С ИСПОЛЬЗОВАНИЕМ МАССИВОВ.
ПРОГРАММНО - ДИДАКТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ: ЭВМ типа IBM. Delphi (консольное приложение). ЦЕЛИ И ЗАДАЧИ: Знакомство с понятием массив и способами их обработки. Познакомиться с базовыми алгоритмами работы с массивами. Выработка навыков составления программ с использованием массивов. ТРЕБОВАНИЯ К ЗНАНИЯМ И УМЕНИЯМ: Учащиеся должны знать: - Что такое массив; - Какие бывают массивы; - Чем отличаются одномерные и двухмерные массивы; - Как описываются массивы в программе; - Как обратиться к заданному элементу массива; - Алгоритм нахождения максимума или минимума среди элементов массива; - Простейший алгоритм сортировки элементов одномерного массива. Учащиеся должны уметь: - Заполнять массивы с клавиатуры или случайными числами, произвольным или заданным образом; - Распечатывать одномерные массивы в виде строки; - Распечатывать двухмерные массивы в виде таблиц; - Находить заданные элементы массива; - Заменять заданные элементы массива или производить с ними арифметические операции; - Менять местами элементы массива; - Находить сумму, произведение или экстремальные элементы в массиве; - Сортировать одномерные массивы; - Составлять программы с использованием массивов.
ПЛАН-СОДЕРЖАНИЕ УРОКА Основные понятия
|