Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 33
Текст из файла (страница 33)
Получив очереднулз перестановку, вызвать параметрическую процедуру (), которая мо»лет, например, выводить полученную перестановку. Указание. Рассиатрявайге задачу получения всех перестановок элементов аь ..., а», как состоящую пз ш подзадач, строящих все перестановки аь , аи, за которыми следует а„ь и так, что в 1-й подзадаче сначала мсиюогся постами два элемента аг и а,, 3.3. Определите рекурсивную схему для рнс. 3,!1, который представляет собой наложение четырех кривых 1Рь йг», («з, йгь Эта структура сход- Рпс. 3.1!. (Р-кривые порядка 1 — 4. иа с крпаызш Серпвнского (3.21) и (3.22). На пскове рекурсянной схемы получите рекурсивную программу, которая чертит этп кривые 3.4. Лишь 12 из 92 р«шенлй, вычисляемых программой восьми ферзей существенпо разлачны.
Остальные можно получить с помощью осевой пли центральной симметрвй. Придумайте программу, которая находят 12 основных решений. Заметил!, что, например, поиск в вертикали 1 можно ограничить позицнямн 1 — 4. 3.3. Изме!пзте программу устойчивых браков так, чтобы она находила оп. тимальное решение (для мужчин и для женщин). Следовательно, она станет программой, работающей по принципу «ветвлеиня с ограничением» подобно программе 3.7 188 3.
Рекрнсивпыа алеоригмы 3.6. Некотораи гкелезггодорнгггия компания обслуживает л стагщнй Вг, 5„. Опа предполагает улуч пить информационное обслужнва:шс клиентов с помощью информацнон,гых терминалов, управляемых вычислительной машиной. Клггенг набирает название своей станции отправления Вг и станции назначения Ви, и ему должна выдаваться схема расписаний поездов с минимальным общим времеяем поездки.
Разработайте программу для нычцслеиня нужной информации. Пусгь распнсание (представляющее собой ваш банк данных) нзобрагкено соответствуюнгей структурой данных, содержащей время отправления (=- прнбьпня) всех имегогцггхся поездов Разумеется, ее все стаяцни связаны непрерывными линиями (см.
тишке упр, ! Я). ЗЛ. Функции Аккермзна А определена для всех неотряцатсльных целых аргументов т н п следующим образом: А(Оен) = и + 1 А(иг,0) = А(т — 1,1) (т > О) А(т, п) = А(т — 1,А(т,п — 1)) (т,п > О) Разработайте про~рамму, которая вычисляет А(т, и) без использования рекурсии. В качестве образца используйте программу 2.11 — нерекурснвную версию быстрой сортнровнн Определите множество правил для общего случая преобразования рекурсивной программы в нтеративн>ю.
йитйрд?урд 31. МсА|1Т)Е О, О., %!).БОР( 1.. В. Тне 9(аЫе Магпайе РгоЫещ. — Сотт. АСМ, 14, й(о. 7, 19? |, 486 — 492. 3.2, МсИТ!Е О, О., %11.$ОР( 1.. В. 3(аЫе й1агг(апе Азз!ипщеп! 1ог |.'пеона| Беби — В?Т, 1О, 1970, 295 — 309, З.З. Брезе Р|П|пй Сцгуез, ог Ночг |о г(газ(с Т|гпе оп а (г!о!(ег, — Бо()жиге — Ргасйге ипг( Ехремепсе, 1, Хо. 4, 1971, 403--440. 3.4. 1РН!ТН Н. Ргойгат Оече|оргпеп1 Ьу Згери)зе Кейпепген|.— Сотиг. АСМ, 14, Хо.
4, 1971, 221 — 227. ДИНАМИЧЕСКИЕ ИНФОРМАЦИОННЫЕ СТРУКТУРЫ 4.1. РВКХРсивные типы данных В гл. 1 мы определили фундаментальные сзруктуры данных; массив, запись и множество. Эти структуры называются фундаментальными, так как, во-первых, онн представляют собой строительные блоки, из которых формируются более сложные структуры, и, во.вторых, онн чаше встречаются на практике. Пель описания типа данных и последующего определения некоторых переменных как относящихся к этому типу состоит в том, чтобы зафиксировать раз и навсегда размер значений, которые могут присваиваться этим переменным, и соответственно размер выделяемой для ннх памяти.
Поэтому описанные таким образом переменные называются стнтическпжа. Однако многие задачи треб;ют более сложных информационных структур. Для таких задач характерно, что используемые в них структуры пзменяются во время выполнения. Поэтому они называются динпжпческиии структурамп. Разумеется, на каком-то уровне детализации компоненты этих структур являются статическими, т. е, относятся к одному из фундаментальных типов данных. Эта глава посвящена конструированию н анализу динамических информационных структур, а также работе с ними. Примечательно, что существуют некоторые близкие аналоги между методами структурирования алгоритмов и методами структурирования данным Как и при любых аналогиях, остаются некоторые различия (иначе мы имели бы дело с идентичностью), тем не менее сравнение методов структурирования программ и данных полезно для их понимания, Элементарным, неструктурированным оператором является присваивание.
Соответствующий ему тип даных--скалярный, неструктурированный. Оба они являются атомарными ст)зоительиыми блоками для сос генных операто)зов и типов данных. Простейшие структуры, пол)чаемые с помощью перечисления, нлн следовании,— это сосгзвной оператор и запись. Оба состоят из конечного (обычно небольшого) количества явно перечисляемых компонент, которые могут различаться. Если все коыпоиенты одинаковы, их не нужно выписывать отдельно: для того чтобы описать повторения, число которых известно и конечно, мы пользуемся 4.
Данампческие информационные структуры Тип данных, значениями которого являются подобны! выражения, легко могкно описать с помо'цью известного уже средства — рекурсии '1. Фуре ехргегл)отт =- тесвгв ор) орегпгог) орту!, оЫ2: гент, евй; Фуре Терт =-- >есвгв Кг Фйев (ы: айаг) е)зе (аЬехг ехаогеа)ои) (4.1) ') Оппсанпо типа !стт в (4 1) не принадлежат языку Пасналь: в нем не пспользустся конструкцня и...
1)теп... с!зе для выраження варианта в заплсн. йолсе правпльной с точки зртпня Паскаля была бы формулк- оператором цикла с параметром (Фог) и массивом. Выбор из двух или более вариантов выражается условным или выбирающим оператором п соответственно записью с вариантами. И наконец, повторение неизвестное (потенциально бесконечное) количество раз выра>кается оператором цикла с пред- условием (туЫ1е) или с постусловнем (гереа1). Соответств>!ошая структура данных — последовательность (файл) — простейший вид структуры, допускающей построение типов с бесконечным кардинальным числом. Возникает вопрос: а существует ли структура данных, которая подобным же образом соответствует оператору процедуры) Разумеется, наиболее интересная и новая по сравнению с другими операторами особенность процедур — зто волмо>кность рекурсии. Значения типа данных, который можно назвать рекурсивным, должны содержать одну илп более компонент того же типа, что и все значение, по аналогии с процедурой, содержащей один илп более вызовов самой себя.
Как и в процедурах, в таких определениях типов рекурсия может быть прямой плц косвенной. Простои пример объекта, тпп которого можно определить рекурсивно, — арифа!ет>п!еское выражт ние, встречаю! >ееся в языках программирования. Рекурсия отражает возможность вложенности, т. е.
использования заключенных в скобки подвыражений в качестве операндов в выражении. ))'так, пусть выражение здесь определяется нефор.!плыло следующим образом: выражение состоит пз тсрма, за ктпорын следует знак спсрацнп, за которым следует терм. !Этн два тсрма являются операплзмн соответствую!пай операции ) Терл — зто :шбо гсрсмспная, представленная ндснтнфнка>ором, либо вырюкснпс, закмочспное в скоб и е.1. Рекарсиепые талы дппчых Итак, каждая переменная типа 1епп,состоит из двух кол!по, нент: воля признака 1 и, если ! истинно, поля Ы, иначе— Рнс 4.1. Расположенне в пвмятн рекурсивных запнсегь поля виЬех. Теперь рассмотрим в качестве примеров следующие четыре выражения: 1. х+у 2.
х — (у*а) 3. (х + у) е (г — тн) (4. 2) 4. (х)(у + г)) е м Эти выражения можно представить, как показано на рис. (4.1), на котором наглядно видна их вложенная, рекур- ранка: Фуре 1егга = гесогд саве И Воогеап о1 Вчге; (И; а)та] (аые: (знбек; е тргеазуоп) епй Однако «зацпклнванвез в опнсаннях типов: темп определяется через ехргезноп, а схргезщоп через !егпт — обычно также зап!зещастся. Такнм обт разом, подобного рода рекурсивные оппсанпя таков в Паскале не прнменяазтся.
Для построения дннамнческнх структур в псм используется аппарат дннамнческого размещения персменаых и ссылок, опнсанный ннже.— Прим. нерее. Е. динамические инсрормонионнскс стркктчрм сивная структура. Эти схемы определяют также размещение этих выражений в памяти.
Другой пример рекурсинной информационной структуры— генеалогическое дерево. Пусть генеалогическое дерево со- стоит из имени человека и двух генеалогических деревьев его ро- т та дителей. Такое определение неизбежно приводит к бесконечной структуре. Реальные генеалогические деревья конечны, потому что на каком-то уровне сведения о предках отсутствуют, Если мы вновь используем рекурсивную структуру, как показано в (4.3), то этот факт мы можем учестаи Фуререй = гесага И йпокп т)аев (пате: а1/а; ,байер, тоггсег: рей) (4.3) (Заметим, что каждая переменная типа рей (от рей(агес — «геяеалогнческое дерево». — Перев.) содержит по крайней мере одну компоненту — поле признака Гепагоп («известен»). Если егО зпа- чение истинно, то имеются еще Рис. 4.2.
Структура геиеалогитри поля; иначе больше нет полей.) Отдельное значение, обозначенное (рекурсивиым) конструктором записи х = (Т,Тей,(Т,Ггей,(Т, Айат,(Г),(Г)),Г)), (Т,э(агу,(Г),(Т,Еэа,(Г),(Г))) изображено на рнс. 4.2, причем, глядя ца рисунок, можно также сделать выводы о возможном расположении данных в памяти. (Так как рассматривается только одно определение типа, мы пропускаем идентификатор типа рей перед каждым конструктором.) Здесь очевидна важная роль вариантов: это единственное средство, Позволяющее сделать рекурсивную структуру конечной, поэтому в рекурсивном определении всегда участвуют 4.л.
Сг»!лки или указатели 193 варианты. В этом особенно наглядно прослеживается аналогия между структурами программ и данных. Каждая рекурсивная процед!'ра также должна обязатст!Ы10 содержать условпьпй оператор, чтобы ее выполнение могло когда-нибудь закончиться. Ясно, что окончание выполнения для процедуры со1гтветствует конечности кардинального числа для типа данных. АХ. ССЫЛКИ ИЛИ УКАЗАТЕЛИ Характерная особенность рекурсивных структур, которая отличает нх от основных структур (масс!!вон, записей, множеств), — их способность изменять размер.
Поэтому для рекурсивио определенных структур невозможно установить фиксированный размер памяти, и поэтому транслятор не может приписать компонентам такой переменной определенные адреса. Для решения этой проблемы чаще всего применяется метод динамического раепределенин пал!нти, т.
е, выделения памяти для отдельных компонент в тот момент, когда они появляются во время выполнения программы, а не во время трансляции, В этом случае транслятор выделяет фиксированный объем памяти для хранения адреса динамически размещаемой компоненты, а не самой компоненты. Например, генеалогическое дерево, изображенное на рпс. 4.2, можно представить в виде отдельных, вполне возможно, ие расположенных рядом в памяти записей — по одной для каждого человека. Эти записи связываются с помощью адресов, находящихся в соответствующих полях )а(йег («оте11») и то1пег («л!ать»). Графически это лучше всего нзобразнть стрелками (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
