Основы программирования (947332), страница 30

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

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

Для исключения подобных ситуаций необходимо восновной программе проверить приведенное выше условие наличия корнейна отрезке.При объявлении косвенно рекурсивных подпрограмм возникает пробле­ма: их описания принципиально не удается расположить так, чтобы избежатьобращения к еще не описанным ресурсам, как того требуют правила объяв­ления ресурсов Borland Pascal. В этом случае используют специальную ди­рективу forward, которая позволяет выполнять предописание: сначала запи173Часть 1.

Основы алгоритмизации и процедурное программированиеРис. 5.13. Пример взаимнорекурсивных подпрограммсывают заголовки подпрограмм с пара­метрами, за которыми вместо тела под­программы следует forward; затем опи­сывают тела этих подпрограмм (причемпараметры второй раз можно уже неописывать).Например, описание процедур А иВ, которые рекурсивно вызывают другдруга (рис. 5.13), можно выполнить сле­дующим образом:procedure В(j:byte); forward;procedure A (j: byte);begin ... B(i); ... end;procedure B;begin ... A(j); ... end;Пример 5.14. Разработать программу проверки чередования букв ицифр в заданной строке (первый символ ~ обязательно буква).Базисные утверэюдения:• строка допустима, если она пустая;• строка не допустима, если в ней обнаружен недопустимый символ.Рекурсивное утверэюдение: если текущий символ строки допустим, тодопустимость строки определяется оставшейся частью строки.Для написания данной программы используем взаимно рекурсивныеподпрограммы.

Первая будет проверять, является ли текущий символ бук­вой, и если является, будет удалять этот символ и вызывать вторую. Вторая будет проверять, является ли текущий символ цифрой, и если является, будетудалять эту цифру и вызывать первую. Выход из рекурсии - по достиженииконца строки. Параметры: строка передается по ссылке, а номер символа по значению.Program ex;Var s.string;Function f_char(var st: string; i: word): boolean; forward;Function f_value(var st: string; i:word): boolean;Beginif i>length(st) thenf_value:=trueelse iffstfij in f'0\. *9'J)thenf_value:=f_char(st,i-^l)elsef_yalue:=false;End;1745.

Модульное программированиеFunction f_char;Beginif i>length(st) then f_char:=trueelseif Mi] in ['A \. 'Z\ 'a'.. *z']) thenf_Shar: =f_value(st, /+1)elsefjohar:=false;End;BeginWriteLnCВведите строку: *);Readln(s);iff_char(s, 1) thenWriteLnCCmpoKa корректна *)else WriteLnCCmpoKa не корректна *);EndВо всех рассмотренных выше случаях рекурсивные подпрограммы име­ли структуру, представленную на рис. 5.14, которая характеризуется тем, чтокаждая рекурсивная подпрограмма вызывает саму себя один раз.

Такая орга­низация рекурсии названа линейной.Операторы, которые на схеме помечены как «операторы после вызова»,выполняются после возврата управления из рекурсивно вызванной подпро­граммы. Если попытаться изобразитьпоследовательность действий при ли­fИмя Лнейной рекурсии, то она будет выгля­V (-0 Jдеть, как это показано на рис. 5.15.данетВыходТаким образом, сначала в каждойактивации выполняются операторы,расположенные до рекурсивного вызо­БазиснаяОператорыветвьва, затем (при достижении условия вы­"до вызова"хода) ~ нерекурсивная часть очеред­Имяной активации, а затем ~ операторы,(...)записанные после рекурсивного вызо­—\—ва.

На этом построены многие рекур­Операторысивные алгоритмы."послеПример 5.15. Разработать про­вызова"грамму, которая выводит из заданноготмассива, завершающегося нулем, сна­( Return jчала положительные значения, а за­тем - отрицательные в любом поряд­ке. Между положительными и отрица­Рис. 5.14. Структурательными элементами массива вывес­подпрофаммы с линейнойти три звездочки.рекурсией175Часть J. Основы алгоритмизации и процедурное программированиеОсновная программаПервая активацияВторая активацияОператоры"до вызова"Третья активация - базисОператоры"после вызова"Рис. 5.15.

Рекурсивное погружение и рекурсивный выходпри линейной рекурсииНерекурсивная программа для решения данной задачи должна содер­жать, по крайней мере, два цикла, не считая циклов ввода и вывода. Рекур­сивный вариант может использовать рекурсивный возврат для вывода остав­шихся элементов.Построим решение следующим образом: в области до вызова запро­граммируем печать положительных чисел, в области после вызова - печатьотрицательных чисел, а нерекурсивная часть будет содержать вывод звездо­чек.Program ex;Type mas =array[I..

JOJ of real;Var x:mas;i: integer;Procedure print(var x:mas;i: integer);Beginifx[i]=Othen WriteLnf'***')elsebeginifx[i]>0 then WriteLnfi,': xfij);print(Xyi+l);{рекурсивный вызов}ifx[i]<0 then WriteLn(i,' ^ xfiJ);endEnd;Begini:=0;repeat i:=i+l; Read(x[i]) until x[ij=0;ReadLn;print(xj);End.\165, МодульноепрограммированиеПримечание. Обратите внимание, что значение i вкаждой активации свое, и оно не меняется во времявыполнения подпрограммы: одно и то же как до рекурсив­ного вызова, так и после него.л л л1 2 li121321 2323311 32Кроме линейной достаточно часто встреча­ется рекурсия, получившая название древовид­ной.

При древовидной рекурсии подпрограмма в 123 132 213 231 312 321течение одной активации вызывает саму себяРис. 5.16. Деревоболее одного раза. Полученная в данном случаеформированияпоследовательность вызовов имеет форму дере­перестановоква, с чем и связано название данного вида орга­при т=3низации процесса вычислений.Пример 5.16. Разработать программу, которая формирует все переста­новки без повторений некоторого массива значений. Например, если заданмассив, содержащий символы ABC, то необходимо сформировать следую­щие комбинации: ABC, АСВ, ВАС, ВСА, CAB, СВА.Будем исходить из того, что в комбинации на первое место можно поста­вить любой из имеющихся m символов. На второе место в каждом вариантеможно поставить любое из оставшихся т-1 значений. На третье место - лю­бое из П1-2 значений и т.д.

На послед­Perest Лнее т-е место -- единственное остав­(п,т,г,р)Jшееся значение. На следующем т+1-мшаге перестановку можно выводить.На рис. 5.16 представлено дерево фор­мирования вариантов перестановокr^^:=l,m-n+lV-|для т=3.Таким образом, каждая активацияВыводp[n]:=iподпрограммы уровня п должна вызы­p[m]вать саму себя n-m+1 раз, каждый разПолучениепередавая следующей активации мас­rlсив еще не расставленных значений г1.Окончательный алгоритм подпрограм­Perest(n+l,m,rl,p)|мы формирования перестановок пред­ставлен на рис. 5.17.1 1I I 1 1(Program ex;Typemas=array[L,5] of char;Const a:mas= 'ABCDE VVar pole:mas;(ReturnjРис. 5.17. Схема алгоритмаподпрофаммы формированияперестановок177Часть I. Основы алгоритмизации и процедурное программированиеprocedure Perest(n,m:integer; Const г:mas; Var pole:mas);Var rl:mas;kjJ: integer;Beginifn>m thenbeginfor i:=l to m do Write (pole fij);WriteC '):endelsefor i:-l to m-n+l dobeginpole[n]:^r[i];k:=l;forji^l to m-n^l doifjoi thenbeginrl[k]:-r[j];k:=k+];end;Perest(n-^l,m,rl,pole);end;End;BeginPeres t(l, 5, a.pole);EndОпределим размер фрейма активации.Параметры:V, = 2*2 + 4 + 4;локальные переменные: V2 = m + 3*2;служебная информация: V3 « 12.ОткудаV = V, + V2 + Уз = 12 + m + 6 + 12 « 30 + т .Максимальное количество одновременно существующих активацийравно т + 1 .

Соответственно максимальный объем используемой памяти сте­ка^тах = (30 + п^)(п1 + 1) = т 2 4- 31т + 30.Так, для т = 5Vj^^^^ ="210 (байт).Примечание. Интересно, что при развертывании древовидной рекурсии в каждый мо­мент времени в стеке хранятся фреймы активации одной ветви дерева, и, следовательно, су­щественного увеличения объема хранимой информации не происходит.1785. Модульное программированиеЗадания для самопроверкиЗадание 1. Разработайте рекурсивную подпрофамму, формирующую последо­вательность строк:АВВСССDDDDЕЕЕЕЕFFFFFF и т.

д. Всего 26 строк. Разработайте тестирующую профамму.Задание 2. Разработайте рекурсивную подпрограмму вычисления биномиаль­ных коэффициентов:Г О, если m>n>0;C{m,n} = ^ U ^сли (т=0 и п>0) или (m=n=0);I C{m-l,n-l} + C{m,n-1} в остальных случаях.Задание 3. Разработайте рекурсивную подпрофамму быстрой сортировки эле­ментов массива (сортировка Хоора [3, 6]).

Быстрая сортировка выполняется следую­щим образом. Выбирают любой, например, первый элемент массива, и затем элемен­ты переставляют так, чтобы слева располагались элементы меньше выбранного, асправа - больше. Для этого массив просматривают с двух сторон и меняют местамиэлементы, стоящие не в своей части массива. Тем самым выбранный элемент оказы­вается на своем месте. После этого описанный алгоритм применяют к левой и пра­вой частям подмассива и т.

д., пока очередной подмассив не окажется состоящим изодного элемента. Корректная реализация данного метода обеспечивает вычислитель­ную сложность Оср(п Iog2 п).Задание 4. Разработайте рекурсивную подпрограмму «Ханойская башня».Имеется три колышка. На первом нанизаны m пронумерованных колец. Необходиморасположить кольца в том же порядке на любом из оставшихся колышков.

При этомкольца можно переносить только по одному, причем не разрешается класть кольцо сбольшим номером на кольцо с меньшим номером.5.8. Практикум. Полный и ограниченный перебор.Реализация ограниченного перебора с использованием рекурсииСуществует класс задач, в которых из некоторого количества вариантовнеобходимо выбрать наиболее подходящий (оптимальный).

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

Список файлов книги