1611678431-0e68e83522cb9d960ac896aa5d90854d (826635), страница 14

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

Это правило доступности поколений (экземпляров) локальныхпеременных относится не только к процедуре ОБРАЩЕНИЕ, но и к любойрекурсивной подпрограмме, причем распространяется на все ее параметрызначения. Например, пусть имеетсяprocedure ФАКТ (N:Integer):Integer;begin if N1 then ФАКТ := NФАКТ(N-1) else ФАКТ :=1 end end ФАКТ;тогда при обращении ФАКТ(5) сначала заводится пять переменных с именем N,в которых последовательно запоминаются значения 5,4,3,2,1, а затемосуществляется вычисление результата по следующей формуле5(4(3(2(1)))).Аналогично циклам рекурсивные подпрограммы могут описывать процессывычисления, которые никогда не завершаются.

Например, процедураprocedure БесконечнаяПечать;begin Write(' '); БесконечнаяПечать end БесконечнаяПечать;печатает последовательность звездочек неограниченной длины. Посколькурекурсивные подпрограммы являются более мощной алгоритмическойконструкцией, чем цикл, нет и не может быть никакого общего метода, которыйбы позволял проверить завершимость произвольной программы сподпрограммами. Прием, который можно рекомендовать для достижениягарантированной завершимости рекурсивной подпрограммы, мы ужерассматривали в п. 4.1.2, посвященном анализу свойств циклов.

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

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

Вариант функции, рекурсивно вычисляющей факториал числа N.functicon Factorial(N: Byte): Longint;beginif N in [0..1]then Factorial := 1else Factorial := N * Factorial(N - 1)end;30. Метод структурной индукции, анализ функции факториала,91 Маккарти и АккерманаСтруктурная индукция — метод доказательства, который используется в математической логике(например, в доказательстве теоремы Лося об ультрапроизведениях, информатике, теорииграфов, и некоторых других областях математики.

Это — обобщение математической индукции.Структурная рекурсия — метод рекурсии, имеющий те же самые отношения к структурнойиндукции как обычные рекурсии к обычной математической индукции.6.1.9 Метод структурной индукцииОбычно рекурсивная подпрограмма предполагает разложение класса всех задач,решаемых данной подпрограммой, на совокупность подзадач таким образом,что любые две подзадачи либо не пересекаются, либо одна из них являетсяподзадачей другой. При этом описание подпрограммы строится по следующейсхеме: сначала в ней определяется споcоб решения тривиальных случаев(наипростейших подзадач), каждый из которых может быть разрешеннепосредственно (без рекурсивного вызова), а затем -- способ вычислениярезультата для общего случая, причем используется сведение к решению однойили нескольких более простых подзадач (через рекурсивные обращения к тойже подпрограмме).Таким образом, вполне естественным представляется следующий методдоказательства свойств рекурсивных подпрограмм, получившийназвание структурной индукции (индукции "по структуре" данных) исостоящий из следующих двух этапов:1) базис -- доказательство справедливости свойства подпрограммы для всехнаипростейших случаев (подзадач);2) индуктивный переход -- доказательство справедливости свойстваподпрограммы для любого нетривиального случая в предположении, чтосвойство справедливо для всех случаев (подзадач), более простых, чем данный.Проиллюстрируем применение метода для доказательства того, что рекурсивнаяфункция ФАКТ(N) вычисляет факториал N! заданного неотрицательного целогочисла N.Базис тривиален: при N = 1 имеем ФАКТ(N) = 1 = 1!.Для доказательства индуктивного перехода рассмотрим такое целое N, чтоN1 и ФАКТ(М) = М! для всех М, 1определением получаемФАКТ (N)=NMN.

Тогда в соответствии сФАКТ(N-1)= N (N-1)!)=N!,что завершает доказательство правильности функции ФАКТ.Рассмотрим функцию, известную как функция Аккермана:procedure A (N:integer; M:integer):integer;begin (* {N0, M0} *)if N = 0 then A := M+1 elsif M = 0 then A := A(N-1,1) else A := A(N-1, A(N,M1)) endend A.Для нее, в частности, имеем А(1,2) = А(0,А(1,1)) = А(0,А(0,А(1,0))) =А(0,А(0,А(0,1))) = А(0,А(0,2)) = А(0,3) = 4.Методом структурной индукции покажем, что А(N,M) заканчивается для любойпары неотрицательных целых чисел N и M.Будем рассматривать подзадачи, каждая из которых определяется некоторойпарой неотрицательных чисел K и R и представляет собой вычисление функцииA для всех таких пар (X,Y), что либо XK, либо X = K и YТаким образом, A(K,R) является подзадачей A(N,M), если KRR.N, либо K = N иM, и наипростейший случай-- это A(0,0).Ясно, что вычисление A(0,0) заканчивается.Пусть N и M не равны нулю одновременно, и пусть A(X,Y) заканчивается длявсех таких X и Y, что либо XN, либо X = N и YM.

Рассмотрим A(N,M).Если N = 0, то очевидно, что A(N,M) закончится. Если N0 и M=0, то A(N,M)= A(N-1,1) и по гипотезе индукции вычисление A(N-1,1) закончится, аследовательно, закончится и вычисление A(N,M). Пусть N0иM0, тогдаA(N,M) = A(N-1, A(N,M-1)) и, дважды применяя индуктивное предположение,сначала получаем завершимость A(N,M-1), а затем завершимость A(N-1,K), гдеK = A(N,M-1).В качестве последнего примера рассмотрим следующую функцию, известнуюкак функция 91 Маккарти:procedure F (N:integer):integer;begin if N100 then F := N-10 else F := F(F(N+11)) end end F;и докажем, что F(N) = 91 для всех N100.Базис (при N=100) очевиден: F(100)=F(F(111))=F(101)=91.Пусть N100 и для любого такого M, что 100MN, выполняется F(M) =91.

Для нахождения значения F(N) отдельно рассмотрим два случая: 89100 и N89. При 89NN100 имеем F(N)=F(F(N+11))=F((N+11)-10) =F(N+1)= (по индуктивному предположению)= 91. Пусть N89, тогдаF(N)=F(F(N+11)) = (по индуктивному предположению)= F(91)= (поиндуктивному предположению)= 91.Завершая рассмотрение метода структурной индукции, отметим, что онприменим и для доказательства свойств нерекурсивных (итеративных)программ. При этом в некоторых случаях для доказательства правильностиитеративных программ, фактически реализующих рекурсивный процессобработки входных данных, метод структурной индукции может оказатьсяболее удобным, чем метод промежуточных утверждений, являющийся такжеметодом доказательства по индукции, но не по структуре данных, а по числупопаданий (в цикле) в некоторую точку программы.31.

Пошаговая разработка программ без и с использованием процедур и функций,особенности восходящего и нисходящего подходовЛекции: фото 27; книга: п. 4.1.5, 6.1.6Разработка программы представляет собой задачу на построение. Поэтому, как обычно втаких случаях (вспомним, например, геометрические задачи на построение из школьной математики),необходим этап анализа задачи. На этом этапе, задавая вопросы: что дано? и что требуется? нужноустановить классы наборов входных и выходных данных будущего алгоритма, выделить основныенеобходимые отношения между входными и выходными наборами данных и компонентами этихнаборов, выделить подцели, которые нужно достичь для решения задачи, и, как следствие этого,выработать подход к построению алгоритма.Результатом этого этапа должна быть внешняя спецификация программы, т.е.

строгая, точнаяи понятная формулировка в общем виде того, что должна делать программа, чтобы переработатьвходные данные в выходные.Когда внешняя спецификация программы такова, что программисту не удается сразупредставить детальный вид программы, с самого начала ее создания можно и нужно придерживатьсянекоторой дисциплины, позволяющей разбить процесс программирования на ряд последовательныхшагов, выделить необходимые подцели каждого шага разработки и проследить взаимосвязь междуними. Эта дисциплина получила название метода пошаговой разработки. Механизм подпрограммявляется хорошим инструментом для поддержки пошаговой разработки программы.Нисходящий подход к разработке программных систем.// сначала main, потом функцииВ соответствии с этим методом создание программы начинается сверху, т.е.

с разработкисамого главного, генерального алгоритма. Так как на верхнем уровне обычно еще не ясны деталиреализации той или иной части программы, то эти части следует заменить временными заглушками .Прогон незаконченной программы (перед заменой заглушек реально работающимипроцедурами) дает определенную уверенность перед разработкой и реализацией алгоритмовнижнего уровня. Если реализуемый в заглушке алгоритм достаточно сложен, его вновь структурируют,выделяя главный алгоритм и применяя новые заглушки и т.д. (Заглушка - заменяющая компонента,которая временно используется в программе с тем, чтобы можно было продолжать ее разработку, т. е.компилирование или тестирование, до того времени, когда эта компонента будет сделана внадлежащем виде.)На практике “чистую” нисходящую разработку осуществить невозможно.

На одной из болеепоздних стадий часто обнаруживается, что некоторый выбор, сделанный ранее, был неадекватным иэто приводит к необходимости итеративной разработки.Проблемы нисходящего подхода: высокая цена ошибки; дублирование решений (одинаковые задачи приходится решать заново; привосходящем подходе можно было бы написать подпрограмму); проблема проверки решений.Восходящий подход к разработке программ.// сначала функции, потом mainВ этом случае осуществляется последовательное построение программы из уже имеющихсяэлементов, начиная с примитивов, предоставляемых выбранным языком программирования. Этотпроцесс заканчивается получением требуемой готовой программы. На каждом этапе из имеющихсяэлементов строятся более мощные элементы.

Характеристики

Список файлов ответов (шпаргалок)