Основы программирования (947332), страница 29
Текст из файла (страница 29)
Если имена этих подпрограмм необходимо передавать через параметры, то надо описать собственную подпрограмму с указанием режима дальнего вызова, в теле которой будет находиться вызов стандартной подпрограммы, и использовать еевместо стандартной подпрограммы.Пример 5.10. Разработать подпрограмму, которая возвращает массивзначений произвольной функции при заданных интервале изменения аргумента [а,Ь] и количестве точек п.Имя функции будем передавать в подпрограмму через параметр процедурного типа.
Массив значений будем описывать как открытый:UnitSFun;InterfaceType func-functwn(x:real):real;Procedure TabFun(f:func;a,b:real;n:integer;Var Masf:array of real);ImplementationProcedure TabFun;Var h.real; i:integer;Beginh;=(b-a)/(n'l);for i:=0 to n-l do Masf[i]—f(a+h*i);End;EndОсновная программа должна описать конкретную функцию как функцию дальнего вызова.
Для функции sin создается специальная функция дальнего вызова.Program ex;Uses SFun;Var masFl: array[L, 10] of real; masF2: array[L. 20] of real;i: integer;function Fl(x:real):real; far;Begin Fl:-sin(x); end;function F2(x:real):real; far;Begin F2:-exp(x)+cos(x); end;BeginWriteLnC Таблица значений функции sin x:);TabFun(FIA2J0,masFI);167Часть 1. Основы алгоритмизации и процедурное программированиеfor i:=l to JO do Write(masFl[i]:7:l);Writeln;WriteLnC Таблица значений функции exp x+cos x:);TabFun(F2A2,20,masF2);for i:=l to 20 do Write(masF2[i]:7:l);Writeln;EndЗадания для самопроверкиЗадание 1. Разработайте процедуру вычисления производных функции у(х) поформулам Лагранжа в трех соседних точках, отстоящих на величину шага h:Уо' = (-ЗУо + 4У1 -У2У2Ь; УГ = (-Уо + У2У2Ь; Уг'= (Уо^У1+Зу2)/2Ь.Поместите процедуру в модуль.
Разработайте тестирующую программу.Задание 2. Разработайте процедуру определения корня функции на заданномотрезке. Поместите процедуру в модуль. Разработайте тестирующую программу.5.7. РекурсияВ математике строгое определение некоторых понятий может опиратьсяна то же понятие. Такие определения называют рекурсивными или индуктивными. Например, рекурсивно определяется факториал:N1=I 1,еслиЫ=0;I Nx(N-l)!,еслиК>0.Данное определение состоит из двух утверждений.
Первое утверждениеносит название базисного. Базисное утверждение нерекурсивно. Второе утверждение носит название рекурсивного или индуктивного. Оно строитсятак, чтобы полученная в результате повторных применений цепочка определений сходилась к базисному утверждению.В программировании/76?/cy/?cwe;/(9w называется подпрограмма, которая впроцессе выполнения вызывает сама себя.Различают два вида рекурсии подпрограмм:• прямая или явная рекурсия - характеризуется существованием в телеподпрограммы оператора обращения к самой себе;• косвенная или неявная рекурсия - образуется при наличии цепочкивызовов других подпрограмм, которые в конечном итоге приведут к вызовуисходной.1685.
Модульное программированиеКаждое обращение к рекурсивной подпрограмме вызывает независимую активацию 3tofi подпрограммы. Совокупность данных, необходимыхдля одной активации рекурсивной подпрограммы, называется фреймом акmueaifuu.Фрейм активации включает:• копии всех локальных переменных подпрограммы;• копии параметров-значений;• четырехбайтовые адреса параметров-переменных и параметров-констант;• копию строки результата (для функций типа string);• служебную информацию - около 12 байт, точный размер этой области зависит от способа вызова (ближний или дальний) и внутренней организации подпрограмм.Пример 5.11. Разработать программу определения наибольшего общегоделителя двух чисел, используя алгоритм Евклида.Нерекурсивный вариант этого алгоритма уже был рассмотрен в примере 1.2.
Рекурсивный вариант будем строить исходя из двух утверждений.Базисное утверэюдение: если два числа равны, то их наибольший общийделитель равен этим числам.Рекурсивное утверждение: наибольший общий делитель двух чисел равен наибольшему общему делителю их разности и меньшего из чисел.Рекурсивная подпрограмма может быть реализована и как процедура,и как функция.
При реализации в виде процедуры список параметров кромечисел А и В включает параметр-переменную R. Через этот параметр процедура возвращает результат (рис. 5.10, а). Текст программы, реализующий вариант с рекурсивной процедурой, представлен ниже.Гыос1(А,В) JПЧос1(А,ВД))данетА=ВдаА>ВданетR=AнетА-ВдаА>ВнетNod = ANod(А.В,ВД)Nod(A,B-A,R)Nod =Nod(A-B,B)I(ReturnjNod =Nod(A,B-A)I(Returnaj6Рис.
5.10. Схема алгоритма Евклида:а - с использованием рекурсивной процедуры; о - с использованием рекурсивной функции169Часть 1. Основы алгоритмизации и процедурное программированиеФреймактивациитретьеговызова1[_< Г1Служебная информацияАдрес возвратаАдресрезультатаЬ=4Фреймактивациивтороговызова1< Г1>Фреймактивациипервоговызова|_< Г1ч1VПараметры-значенияа~4N1Параметр-переменнаяСлужебная информацияАдрес возвратаАдресрезультатаЬ-8а=4Служебная информацияАдрес возвратаАдресрезультатаЬ«8а=12,]Параметр-переменнаяПараметры-значенияПараметр-переменнаяПараметры-значенияJ2 байтаРис. 5.11.
Заполнение стека при выполнении рекурсивнойподпрограммыProgram ex;Var a,b,r:integer;Procedure nod(a,b:inieger; var rnnteger);Begin ifa-b then r:-a{базис}else ifa>b then nod(a'b,b,r)else nod(a,lhayr)End;Begin ReadLn(a,b);nod(a,b,r);WriteLn(r);End,При выполнении программы фреймы активации будут размещаться встеке - специальным образом организованной памяти. Например, для а=12и Ь=8 в момент завершения нерекурсивной третьей активации стек будет выглядеть, как показано на рис. 5,11 (запись в стек идет словами, т. е. по 2 байта, как и изображено на рисунке).Если реализовать вариант с ре1^рсивной функцией (рис. 5.10, б), тофрейм активации уменьшится, так как сократится список параметров. Соответствующая программа будет выглядеть следующим образом:Program ex;Var а,b,r:integer;Function nod(a,b: integer) .integer;begin ifa=b then nod:'=a {базис}1705.
Модульноепрограммированиеelse{рекурсивный вызов}ifa>b thennod:=nod(a'b,b)elsenod:=nod(a,b'a)end;BeginReadLn(a,b);r:=nod(a,b);WriteLn(r);EndИтак, если подпрограмма обращается к себе несколько раз, образуетсянесколько одновременно существующих активаций и, соответственно, несколько фреймов активации. Все фреймы размещаются в стеке^ и при большом количестве вызовов возможно переполнение стека. Поэтому необходимо стремиться к уменьшению фрейма активации.Примечание. Размер стека устанавливается в настройках среды, по умолчанию он принимает размер 16 кб, и его размер не может превышать 64 кб.Пример 5.12.
Разработать рекурсивную подпрограмму «переворота»строки (первая буква должна стать последней, вторая - предпоследней ит.д.).Можно предложить два способа разворота строки.Первый способ заключается в последовательном отсечении начальногоэлемента и добавлении его в конец результирующей строки.Второй - базируется на последовательной перестановке элементов: первого с последним, второго - с предпоследним и т. д.
Перестановки должныпрекратиться, когда дойдем до середины строки, иначе вновь поставим элементы на исходные места.Вариант с о т с е ч е н и е м и д о п и с ы в а н и е м :Function reversel (const st: string): string;Begin iflength(st)=0 then reverserl:= "elsereverserl: = reversel (copy (st, 2, length(st)'l)) +stflj;End;Определим размер фрейма активации:V = 4 (адрес параметра) + 256 (результат-строка) ++ <размер служебной области > «270 (байт).171Часть I. Основы алгоритмизации и процедурное программированиеВариант с и с п о л ь з о в а н и е мперестановок:Procedure reverse2(var ss:string; ri:integer);Var temp:char;Begin ifn<=Iength{ss) div 2 thenbegin temp:'=ss[n];ssfnj: =ssflength(ss)' i+1];ss[length(ss) 'П+IJ: = ^emp;reverse2(ss, n+1);end;End;Размер фрейма активации для этого варианта:У=4(адрес 1-го параметра)-ь2(копия 2-го параметра) ++ 1(локальная переменная)+<размер служебной области>«17 (байт).Следовательно, второй вариант предпочтительнее.Одной из наиболее часто встречающихся ошибок при создании рекурсивных процедур является «зациклившаяся», или бесконечная, рекурсия, прикоторой базисное утверждение не достигается, и, соответственно, вновь ивновь вызывается рекурсивная подпрограмма.
От бесконечного цикла бесконечная рекурсия отличается тем, что каждая активация требует дополнительной памяти для размещения фрейма активации, и, следовательно, программа,содержащая бесконечную рекурсию, обычно завершается аварийно при переполнении стека.Причиной бесконечной рекурсии может быть не только ошибка в программе, но и обработка некорректных данных.Пример 5.13. Разработать программу определения корней уравненияу=х2-2 на заданном отрезке методом половинного деления.Метод половинного деления для непрерывных функций, так же как иметод хорд, рассмотренный в примере 3.7, позволяет находить корень функции только в случае, если функция имеет на концах заданного отрезка разные знаки, т.е. пересекает ось абсцисс.
Этот метод базируется на следующихутверждениях.Базисное утверждение: если абсолютная величина функции в серединеотрезка не превышает заданного значения погрешности, то координата середины отрезка и есть корень.Рекурсивное утверждение: корень расположен меисду серединой отрезка и тем концом, значение функции в котором по знаку не совпадает созначением функции в середине отрезка (рис. 5.12).Program ex;Var a,b,eps,x:real;1725. Модульное программированиеСRoot Л(а.Ь г,е) JРис. 5.12. Рекурсивный алгоритм определениякорней уравненияProcedure root(a,b,eps:real;var r:real);Varf,x:real;Begin x:=(a+b)/2;f:=x*X'l;ifabs(f)<=eps then r:=xelseif (a *a'l) y> 0 then root(x, b, eps, r)else root(a,x,eps,r)End;Begin ReadLnfa, b, eps);root(a,b,eps,x);WriteLn('Корень x^ \x:9:7);EndЕсли для данной программы задать отрезок, не содержащий корня, топроизойдет «зацикливание», что вызовет аварийное завершение программыпо переполнению стека.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
