Н. Вирт - Программирование на языке Модула-2 (1160777), страница 12
Текст из файла (страница 12)
В приведенном примере рекурсия завершается, когда число объектов,которые нужно переставить, становится равным единице.Число возможных перестановок легко вывести из рекурсивного определения алгоритма.Мы выразим это число как функцию np(n). Пусть задано п элементов, тогда существует nвариантов выбора элемента а[n], и при каждом Фиксированном а[n] мы получаем np(n—1)перестановок. Следовательно, общее число np(n) n*np(n—1). Очевидно, что np(1) = 1.
Вычислениевеличины np можно теперь выразить как вызов рекурсивной процедуры.PROCEDURE np(n: CARDINAL): CARDINAL;BEGINIF n <= 1 THEN RETURN 1ELSE RETURN n*np(n-1)ENDEND npВ функции np мы узнаем Факториал, который вычисляется какnp = 1 *2*3*... *nЭта Формула наводит на мысль об алгоритме, использующем вместо рекурсии повторение:PROCEDURE np(n: CARDINAL): CARDINAL;VAR p: CARDINAL;BEGIN p := 1;WHILE n > 1 DOp := n*p; n := n-1END;RETURN pEND npЭтот вариант вычислит результат более эффективно, чем рекурсивная версия. Причина втом, что каждый вызов требует некоторых дополнительных "административных" операций, навыполнение которых тоже расходуется время.
Команды, обеспечивающие повторение, тратятменьше времени. И хотя эта разница не может быть слишком уж существенной, рекомендуется всеже использовать циклические конструкции вместо рекурсивных всегда, когда это можно сделатьбез особых усилий. В принципе, это возможно всегда, однако циклическая версия в состояниинастолько усложнить алгоритм и затуманить его смысл, что минусов окажется намного больше,57чем плюсов. Например, циклическая форма процедуры перестановки намного сложнее изапутаннее приведенной рекурсивной. Для иллюстрации полезности рекурсии дадим двадополнительных примера.
Приводимые далее алгоритмы обычно возникают в задачах, решение вкоторых легко находится и объясняется с применением рекурсии.Первый пример принадлежит классу алгоритмов, работающих с данными, структуракоторых тоже определяется рекурсивно. Характерной задачей такого рода являетсяпреобразование простых выражений в соответствующую постфиксную форму или польскуюинверсную запись (Полиз), т.е. в Форму, при которой знак операции следует за операндами.Выражение в данном случав будет определяться в виде РБНФ так:Выражение - Слагаемое {("+"|"-") Слагаемое}.Слагаемое - Множитель {("*"|"/") Множитель}.Множитель - Буква | "(" Выражение ")" | "[" Выражение "]".Обозначая слагаемые как Т0,Т1, а множители - как F0,F1, запишем правилапреобразования:Т0 + Т1—>Т0 Т1 +Т0 - Т1—>Т0 Т1 -F0 * F1—>F0 F1 *F0 / F1—>F0 F1 /(Е)—>Е[Е]—>ЕСледующая далее программа Полиз вводит выражения с терминала и проверяет входнуюинформацию на синтаксическую правильность.
В случае правильного ввода информация внеизменном виде повторяется на выходе, если же ввод неверен, то такой выдачи информации непроисходит. Процедура вывода Write импортируется не из стандартного модуля Terminal, а измодуля TextWindows (текстовые окна), управляющего размещением на экране так называемыхокон и выдачей на них текста. Мы можем считать, что одно окно используется для повторенияпринятой входной информации, а второе - для выдачи преобразованных выражений, т.е. основнойвыходной информации.Наша программа в точности отражает структуру синтаксиса плодных выражений.Поскольку синтаксис рекурсивен, рекурсивна и сама программа.
Такое точное отражение - лучшаягарантия правильности программы. Заметим также, что, аналогично, итерация в синтаксисе,выражаемая Фигурными скобками, ведет к итерации в программе, выражаемой оператором сусловием повторения. В этой программе ни одна из процедур не вызывает себя непосредственно.Здесь рекурсия имеет непрямой характер и возникает, благодаря обращению в процедуреВыражение к Слагаемое, которая в свою очередь обращается к Множитель, а уже Множительобращается к Выражение. Очевидно, что непрямая рекурсия менее наглядна и заметна, чемпрямая.Этот пример иллюстрирует также применение локальных процедур.
Примечателен тотФакт, что процедура Множитель описана локальной для процедуры Слагаемое, а та в своюочередь локальна в процедуре Выражение. Это сделано в соответствии с тем правилом, чтообъекты следует описывать преимущественно локальными в той области, где они используются.Это правило иногда может оказаться не только желательным, но и необходимым, какиллюстрируется переменными ОпСлож (локальная в Слагаемое) и ОпУмнож (локальная вМножитель). Если бы эти переменные были описаны как глобальные, то программа не смогла быработать. Для объяснения этого мы должны вспомнить то правило, что локальные переменныесуществуют (и под них выделяется память) лишь в тот промежуток времени, когда процедура58активна. Непосредственным следствием этого в случае рекурсивного вызова является созданиенового экземпляра локальной переменной.
Таким образом, существует столько экземпляровпеременной, сколько уровней рекурсии, из чего, в частности, заключаем, что программист должензаботиться о том, чтобы глубина рекурсии не оказалась чересчур большой.MODULE Полиз;FROM Terminal IMPORT Read:FROM TextWindows IMPORTWindow,OpenTextWindow,Write,WriteLn,CloseTextWindow;CONST EOL = 36C;VAR ch: CHAR; w0,wl: Window;PROCEDURE Выражение;VAR ОпСлож: CHAR;PROCEDURE Слагаемое;VAR ОпУмнож: CHAR;PROCEDURE Множитель;BEGINIF ch = "(" THENWrite(w0,ch); Read(ch); Выражение;WHILE ch # ")" DO Read(ch) ENDELSIF ch = "[" THENWrite(w0,ch); Read(ch); Выражение;WHILE ch # "Г DO Read(ch) ENDELSEWHILE (ch < "a") OR (ch > "z") DO Read(ch) END;Write(wl,ch)END;Write(w0,ch); Read(ch)END Множитель;59BEGIN (*Слагаемое*) Множитель;WHILE (ch = "*") OR (ch = "/") DOWrite(w0,ch); ОпУмнож := ch; Read(ch); Множитель;Write(wl,ОпУмнож)ENDEND Слагаемое;BEGIN (*Выражение*) Слагаемое;WHILE (ch = "+") OR (ch = "-") DOWrite(w0,ch); ОпСлож := ch; Read(ch);Слагаемое; Write(w1,ОпСлож)ENDEND Выражение;BEGIN OpenTextWindow(w0,50,50,300,400,"ввод");(*Открыть текстовое окно*)OpenTextWindow(w1,400,100,300,400,"вывод");Write(w0,">"); Read(ch);WHILE ch >= EOL DOВыражение;WriteLn(w0); WriteLn(w1);Write(w0,">"); Read(ch)END;CloseTextWindow(w1); CloseTextWindow(w0)END Полиз.Образец данных, обрабатываемых и генерируемых программой, приведен ниже.>a+bab+>a*b+cab*c+>a+b*cabc*+>a*(b/[c-d])abcd-/*Следующий пример программы демонстрирует рекурсию в применении к классу задачпоиска решения методом проб и ошибок.
В этом методе используется последовательное60построение частичных "решений" и проверка их допустимости. Каждое новое частичное решениеполучается дополнением некоторого другого. Если полученное частичное решениенеудовлетвооительно, то происходит возврат к частичному решению, из которого оно былополучено, и попытка дополнить его другим способом. Поэтому такой подход называется ещепоиском с возвратами.
Выбор решения задачи осуществляется среди множества частичныхрешений. Для записи таких алгоритмов очень удобно применение рекурсии. Наш конкретныйпример предназначен для поиска всех возможных размещений 8 Ферзей на шахматной доске так,чтобы ни один из них не находился под ударом остальных, т.е. на каждой вертикали, горизонталии диагонали должно находиться не более одного Ферзя. Метод состоит в помещении на j-ювертикаль (начиная с j = 8) еще одного Ферзя; при этом предполагается, что все вертикали справауже содержат правильно размещенные Фигуры.
Если на вертикали j нет допустимого места, тонужно пересмотреть размещение Ферзя на (j+1)-й вертикали. Информация, необходимая длязаключения о том, доступна ли данная клетка, содержится в трех глобальных переменных типамассив: Гориз, Диагон1, Диагон2 так, что Гopиз[i]&Диaгoн1[i+j]&Диaгoн2[N+i-j] = "клетка нагоризонтали 1 и вертикали J свободна"Программа использует набор процедур, импортируемых из модуля, называемогоLineDrawing (вычерчивание прямых), чтобы представить выходные данные в легковоспринимаемой графической Форме.. В частности, вызов процедурыarea(c,x,y,w,h) (* область(...) *)закрасит прямоугольник с координатами левого нижнего угла х и у, шириной w и высотойh, "цветом" с.
Очевидно, что эта процедура может быть использована как для прочерчиваниялиний между полями шахматной доски, так и для закрашивания отдельных клеток. Рекурсиявозникает непосредственно в процедуре НоваяВертикаль. Вспомогательные процедурыПоставитьФерзя и УдалитьФерзя могли бы быть, в принципе, описаны локальными внутрипроцедуры НоваяВертикаль. Однако, поскольку существует только одна доска (представленнаяпеременными ГОРИЗ, Диагон1, Диагон2), эти процедуры соответственно считаютсяприписанными глобальным данным, а следовательно, не должны быть локальными в (каждййактивации) НоваяВертикаль.MODULE Ферзи;FROM LineDrawing IMPORT width,height,area,clear;CONST N = 8; (* число вертикалей и горизонталей *)L = 512; (* размер доски *)М = L DIV N; (* размер полей *)VAR x0,y0: CARDINAL; (* начальные координаты на доске *)ГОРИЗ: ARRAY [1..N] OF BOOLEAN;(* Гopиз[i] = "на i-й горизонтали нет Ферзей" *)Диагон1: ARRAY [2..2*N] OF BOOLEAN;(* Диaгoн1[i] = "на i-й нисходящей диагонали нет Ферзей *)Диагон2: ARRAY [1..2*N-1] OF BOOLEAN;(* Диaгoн2[i] - "на i-й восходящей диагонали нет Ферзей *)61PROCEDURE НарисоватьДоску;VAR i,j,x,y: CARDINAL;BEGIN clear(l):FOR i := 1 TO N DO Гopиз[i] :- TRUE END;FOR i := 2 TO 2*N DO Диaгoнl[i] := TRUE END;FOR i := 1 TO 2*N-1 DO Диaгoн2[i] := TRUE END;x0 := (Width-L) DIV 2; x := x0;y0 := (height-L) DIV 2; у := y0;area(3,x0,y0,L,L);FOR i := 0 TO N DOarea(0,x0,y,L,2); у := у + M;area(0,x,y0,2,L); х : = х + М;ENDEND НарисоватьДоску;PROCEDURE Пауза;VAR n: CARDINAL;BEGIN n := 50000:REPEAT n := n-1 UNTIL n = 0END пауза;PROCEDURE ПоставитьФерзя(1,J: CARD INAL):BEGINГopиз[i] := FALSE;Диaгoнl[i+j] := FALSE; Диaгoн2[N+i-j] := FALSE;area(0,x0+2+(j-i )*M,y0+2+( i-j)*M,M-2,M-2)END ПоставитьФерзя;PROCEDURE УбратьФерзя i, j: CARDINAL);BEGINГopиз[i] := TRUE;Диaгoн'l[i+j] := TRUE; Диaгoн2[N+i-j] := TRUE:62area(3,x0+2+(j-1 )*M,y0+2+(i-1)*М,М-2,м-2)END УбратьФерзя;PROCEDURE НоваяВертикаль(j: CARDINAL);VAR i: CARDINAL;BEGIN i := N;REPEATIF Гориз[il&Диагон1[i+j]&Диагон2[N+i-j] THENПоставитьФерзя(i,j);IF j > 1 THEN НоваяВертикаль(j-1)ELSE ПаузаEND;УбратьФерзя(i,j)END;i := i-1UNTIL i = 0END НоваяВертикаль;BEGIN НарисоватьДоску; НоваяВертикаль(N); clear(3) END Ферзи.Вывод программы ферзи.63Часть З15.
ОПИСАНИЯ ТИПОВКаждое описание переменной задает тип этой переменной как ее неизменное свойство.Типом может быть один из стандартных, примитивных типов либо же тип может быть описан всамой программе. Описания типов имеют Форму$ОписаниеТипа = Идентификатор "=" Тип.Им предшествует ключевое слово TYPE. Типы делятся на неструктурированные иструктурированные. По существу каждый тип определяет множество значений, которые можетпринимать переменная данного типа. Значение неструктурированного типа -неделимый объект, вто время как величина структурированного типа имеет компоненты (элементы). Например, типCARDINAL -неструктурированный: его значение неделимо. Не имеет смысла ссылаться, скажем,к третьему биту значения 13; тот Факт, что число может "иметь третий бит" или вторую цифру характеристика его (внутреннего) представления, которое намеренно оставлено скрытым.В последующих разделах мы опишем способы описания неструктурированных иструктурированных типов.
Кроме стандартных типов, с которыми мы встречались до сих пор, какнеструктурированные типы описываются перечислимый тип и тип диапазона. Из всехструктурированных типов мы до сих пор имели дело только с массивами. Кроме этого существуетеще тип запись и тип множество. Возможность введения структур, которые динамическиизменяются во время исполнения программы, основана на понятии указателей. Эта возможностьбудет обсуждаться в отдельном разделе.$$$Тип = ПростойТип|ТипМассив|ТипЗапись|ТипМножество|ТипУказатель|ТипПроцедура.ПростойТип = КвалИдент|Перечисление|ТипДиапазон.Прежде чем приступить к рассмотрению различных способов гадания типов, сделаем однообщее замечание. Если тип Т описан так:TYPE T = НекоторыйТипа переменная t:VAR t: Tто эти два описания можно слить в одно:VAR t: НекоторыйТиподнако в этом случае тип переменной t не будет иметь явного имени.Понятие типа играет важную роль в программировании, поскольку типы делят всемножество переменных в программе на непересекающиеся классы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
