Напишите процедуру, которая формирует все п\ перестановок и эле-3.2 центов аи а„ in situ, т. е. без использования другого массива. Получив очередную перестановку, вызвать параметрическую процедуру Q, которая может, например, выводить полученную перестановку.

Указание. Рассматривайте задачу получения всех перестановок элементов й1, т как состоящую из т подзадач, строящих все перестановки йь ..., йт-ь за которыми следует am, и так, что в t-fi подзадаче сначала меняются местами два элемента й,- и йщ.

-а-ч-Ояределите рекурсивную схему для рис. 3.11, который представляет собой наложение четырех кривых Wi, W, Ws, Wf. Эта структура сход-

Рис. 3.11. И^-кривые порядка 1-4.

на с кривыми Серпинского (3.21) и (3.22). На основе рекурсивной схемы получите рекурсивную программу, которая чертит эти кривые.

3-4. Лишь 12 из 92 решений, вычисляемых программой восьми ферзей существенно различны. Остальные можно получить с помощью осевой или центральной симметрии. Придумайте программу, которая находит 12 основных решений. Заметим, что, например, поиск в вертикали 1 можно ограничить позициями 1-4.

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

Нием подобно программе 3.7.

3.6. Некоторая железнодоржная компания обслуживает п станций S .... S . Она предполагает улучшить информационное обслужива-,-клиентов с помощыо информационных терминалов, управляемых числительной машиной. Клиент набирает название своей станции правления Sa и станции назначения So, и ему должна выдавать схема расписаний поездов с минимальным общим временем поезда

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

3.7. Функция Аккермана А определена для всех неотрицательных целых аргументов m и п следующим образом:

Л(0,л) = га + 1

Л(т,0) = А(т - 1,1) (ш > 0)

Л(ш, п) = Л(ш - 1,Л(т,/г - 1)) (т,га > 0)

-Разрабо1айге iipoipaMMy, которая вычисляет Л(т, га) без использова.

ния рекурсии.

В качестве образца используйте программу 2.11-нерекурсивную версию быстрой сортировки. Определите множество правил для общего случая преобразования рекурсивной программы в итеративную.

литература

3.1. McVITIE D. G., WILSON L. В. The Stable Marriage Problem. - Comm. ACM, 14, No. 7, 1971, 486-492.

3.2. McVITIE D. G., WILSON L. B. Stable Marriage Assignment for Unequal Sets. - BIT, 10, 1970, 295-309.

3.3. Spase Filling Cv.rves, or How to Waste Time on a Plotter. - So; -re - Practice anc. experience, 1, No. 4, 1971, 403-440.

3.4. WIRTH H. Program Development by Stepwise Refinement.--Comm. ACM, 14, No. 4, 1971, 221-227.

ИЧЕСКИЕ ИНФОРМАЦИОННЫЕ руКТУРЫ

РЕКУРСИВНЫЕ типы данных--

В гл. 1 мы определили фундаментальные структуры дан-рь1х: массив, запись и множество. Эти структуры называются фундаментальными, так как, во-первых, они представляют собой строительные блоки, из которых формируются более сложные структуры, и, во-вторых, они чаще встречаются на практике. Цель описания типа данных и последующего определения некоторых переменных как относящихся к этому типу состоит в том, чтобы зафиксировать раз и навсегда размер значений, которые могут присваиваться этим переменным, и соответственно размер выделяемой для них памяти. Поэтому описанные таким образом переменные называются статическими. Однако многие задачи требуют более сложных информационных структур. Для таких задач характерно, что используемые в них структуры изменяются во время выполнения. Поэтому они называются динамическими структурами. Разумеется, на каком-то уровне детализации компоненты этих структур являются статическими, т. е. относятся к одному из фундаментальных типов данных. Эта глава посвящена конструированию и анализу динамических информационных структур, а также работе с ними.

Примечательно, что существуют некоторые близкие аналоги между методами структурирования алгоритмов и методами структурирования данных. Как и при любых аналогиях, остаются некоторые различия (иначе мы имели бы дело с идентичностью), тем не менее сравнение методов структурирования программ и данных полезно для их понимания.

Элементарным, неструктурированным оператором яв- яется присваивание. Соответствующий ему тип даных - ска- ярный, неструктурированный. Оба они являются атомарными строительными блоками для составных операторов типов данных. Простейшие структуры, получаемые с по-ощью перечисления, или следования, - это составной оператор и запись. Оба состоят из конечного (обычно небольшого) количества явно перечисляемых компонент, которые могут различаться. Если все компоненты одинаковы, их не УЖно выписывать отдельно: для того чтобы описать повторения, число которых известно и конечно, мы пользуемся