|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[19] Схема циклического взаимодействия процедур: прямая рекурсия раздел описания программы Pr 1 - раздел описания Pr 1 Вызов Pr 1 в процедуре Pr 1 Внешняя программа косвенная рекурсия Pr 2 - заголовок Pr 2 Forward; Pr 1 - раздел описания Pr 1 Вызов Pr 2 в процедуре Pr 1 Pr 2 - раздел описания Pr 2 Вызов Pr 1 в процедуре Pr 2 Внешняя программа Если процедура вызывает сама себя ( прямая рекурсия ), то она описывается как обычно. Рекурсия традиционно применяется для итерационного расчета значения функции с использованием результатов предыдущего шага. Например, для расчета выражений вида: X! ( X факториал ), XN ( X в степени N ), вычисляемых по формулам: XN= XN-1 * k, где k - постоянная или переменная величина. В общем случае рекурсия применяется при расчете функции от функции: FN(x) = FN-1(x). При этом процесс происходит в два этапа: обратное движение с запоминанием цепочки расчета в оперативной памяти и прямое движение - расчет с использованием полученной цепочки. Рекурсивные процедуры требуют больше памяти для запоминания промежуточных результатов, чем обычные циклические операторы, поэтому рекурсии используются реже. В случае рекурсивных процедур следует обязательно предусмотреть условие окончания вызова процедуры. Приведем пример традиционного использования рекурсии. Пусть требуется рассчитать число осколков, полученных в результате деления тела за "N" миллисекунд, если каждый осколок делится на два за одну миллисекунду. Тогда при N=0 число осколков = 1, при N>0 число осколков = 2N = 2*2(N-1). Функция, возвращающая число осколков, будет иметь вид: Function K O(N: word): Longint; begin if N=0 then K O:=1{условие окончания рекурсии} else K O:=2 *K O(N-1){рекурсивный вызов} Пример функции, возвращающей число осколков, без использования рекурсии: Function K O(N: word): Longint; var N 1: Longint; i: word; begin N 1:=1; for i:=1 to N do N 1:= 2*N 1; K 0:= N 1 Если к каждому осколку добавляется два осколка, то число осколков = (1+2)N= 3*3(N 1). Во внешней программе число осколков (переменная "NN") расчитывается вызовом функции: NN:= K O(t); где t - значение фактического параметра времени. Практическое задание N 1. 31 Написать и отладить программы с использованием функций: 1.Рассчитать число зерен, выращенных крестьянином за "N" лет, если он посадил 10 зерен, а годовой урожай составляет 22 зерна на каждое посаженное зерно. 2.Рассчитать число рыбок - самок, выращенных в аквариуме за "N" месяцев, если вначале была одна самка, а ежемесячный прирост от одной самки составляет три самки, причем все рыбки остаются живые. 3.Рассчитать число золотых монет, принесенных в дань господину, если "N+1" подданных последовательно передают монеты от первого к последнему. Причем, первый отдает одну монету, второй увеличивает число монет вдвое, третий - в три раза и т. д. 4.Рассчитать число рыбок, выращенных в аквариуме за "N" лет, если вначале было две рыбки, а число рыбок увеличивается пропорционально числу лет, т. е. 4, 12, 48 и т. д. 5.Рассчитать функцию y=sin(sin(sin(. . . (sin(x))))), в которой имя функции "sin" повторяется N раз. 6.Рассчитать функцию y=a/(b+(a/(b+(a/(b+(. . . +a/b)))))), в которой знак деления "/" повторяется N раз. Примечание: написать функцию для расчета с использованием прямой рекурсии и без рекурсивного вызова. Если обе процедуры вызывают в своих разделах выполнения друг друга ( косвенная рекурсия ), то каждая из процедур должна быть описана ранее другой, что невозможно. В этом случае в разделе описания основной программы используется предварительное описание одной из процедур: пишется только заголовок процедуры и служебное слово Forward. Далее приводится полное описание второй процедуры, а затем полное описание первой процедуры (причем, второй раз в заголовке процедуры список формальных параметров можно не указывать). Приведем пример использования рекурсии: Program Rek;{раздел описания основной программы} {--------------------------------------------------------------------- } Procedure pr 1(i:word); Forward; {предварительное описание процедуры pr 1} {----------------------------------------------------------------- } Procedure pr 2;{ полное описание процедуры pr 2} var ch: char; i: word; begin Writeln(Купите десять билетов - выиграете миллион !); Writeln(Нажмите "Y" или "N"); Readln(ch); i:=10; if( ch=Y) or ( ch=y) then Pr 1(i){ вызов процедуры} else Haltend; {----------------------------------------------------------------- } Procedure pr 1;{ полное описание процедуры pr 1} var n, n1: integer; if i=10 then begin Randomize; n1:= Random(900)+100 end; if (i = 0) then Pr 2{ условие окончания прямой рекурсии} else begin repeat writeln(введите трехзначный номер билета); Readln(n)until (n<1000) and (n>99); if (n<>n1) then begin writeln(билет без выигрыша); writeln( осталось , i-1, билетов); Pr 1(i-1){ прямая рекурсия}end else begin Writeln(Bu угадали, получите выигрыш в банке!); Pr 2{ косвенная рекурсия}end end; {----------------------------------------------------------------- } BEGIN PR 2{ раздел выполнения основной программы}End. Здесь процедура Pr 1 при первом вызове инициирует случайное трехзначное число "n1" - выигрышный номер. При каждом вызове процедура Pr 1 запрашивает ввод трехзначного номера билета "n". Если номер билета не совпал (n<>n1) и остались еще билеты (i<>0), то снова вызывается процедура Pr 1, иначе вызывается процедура Pr 2 (окончание рекурсивного вызова). Если номера совпали (n1=n), то выводится сообщение: Вы угадали, получите выигрыш в банке!. Процедура Pr 2 либо вызывает процедуру Pr 1, либо программа заканчивается (оператор Halt). В процедуре Pr 2 заголовок не имеет параметров, а в процедуре Pr 1 параметры указываются при первом описании. В данном случае приводится управляемая на каждом шаге рекурсия (процедура запрашивает номер билета). Включив тело процедуры Pr 2 в Pr 1 и введя операторы цикла, нетрудно избавиться от рекурсивного вызова процедур. Практическое задание N 1. 32 Написать и отладить программу с рекурсивным вызовом процедур: Ученики двух групп имеют порядковые номера от 1 до N в каждой группе. В процедуре P 1 функцией Random определяются два числа "a" и "b" от 1 до N. Если числа разные, то два участника с номерами "a" и "b" выбывают, оставшиеся ученики перенумеровываются от 1 до (N- 1) и играют дальше (процедура P 1 повторяется с новыми значениями "a" и "b"), иначе выводится значение совпавшего номера, ученики получают приз и процедура P 2 предлагает играть снова. 1. 13. Разработка модулей Известно, что откомпилированная программа размещается в отдельном сегменте памяти, т. е. не может превышать 64 Кбайта. Для создания больших программ в Турбо- Паскале предусмотрено подключение к основной программе откомпилированных модулей. Модуль включает в себя, как правило, большое число процедур, выполняющих однотипные операции, например, работа с графикой, операции с комплексными числами, матричные опера- |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||