Д. Кнут - Искусство программирования том 1 (1119450), страница 75
Текст из файла (страница 75)
ь 23. [87] Если алгоритм топологической сортировки не может продолжить работу из-за обнаружения замкнутой петли во входном потоке (см. шаг Т8), вряд ли стоит останавливать его работу только для вывода сообщения "Возникла петля". Лучше распечатать одну из петель с отображением части входного потока, который привел к ошибке. Расширьте алгоритм Т так, чтобы в нем была предусмотрена дополнительная возможность распечатки петли в случае необходимости. [Указание.
В этом разделе приводится доказательство существования петли, если И ) 0 на шаге Т8, на основании которого можно создать данный алгоритм.] 24. [кэ'] Реализуйте расширения алгоритма т из упр. 23 в коде программы т. 25. [47] Напишите максимально эффективный алгоритм для выполнения топологической сортировки для очень больших множеств Я, которые содержат гораздо больше узлов, чем может поместиться в памяти компьютера. Предположим, что операции ввода, вывода н временного хранения данных выполняются с помощью накопителя на магнитной ленте. [Указание.
При обычной сортировке входных данных предполагается, что все отношения узла располагаются рядом. Что в таком случае можно было бы предпринять? В частности, необходимо предусмотреть самый неблагоприятный случай, когда задано сильно переме. шанное линейное упорядочение. В упр. 24, во введении к главе 5, описывается вариант решения этой задачи с помощью 0((о8 п)э итераций.] 26. [хр] (Распределение памяти длл подпрограмм.) Допустим, что на магнитной ленте хранится основная библиотека подпрограмм в перемещаемом виде, который широко использовался в компьютерах 60-х годов.
Процедуре загрузки нужно определить величину перемещения для каждой применяемой подпрограммы, чтобы для загрузки каждой необходимой программы потребовалось выполнить только один проход по всем данным. Проблема заключается в том, что для работы одних подпрограмм необходимо загрузить в память другие подпрограммы. При этом редко используемые подпрограммы (которые эбычно располагаются в конце ленты) могут вызывать часто используемые подпрограммы (которые обычно располагаются в начале ленты), и потому нужно знать обо всех необходимых подпрограммах до выполнения прохода по всем данным на ленте. Один из способов решения этой проблемы заключается в хранении "каталога ленты" в памяти.
Процедура загрузкй обладает правом доступа к двум таблицам. а) Каталог ленты. Эта таблица состоит из узлов переменной длины слелующего вида: или Здесь БРАСŠ— количество слов памяти, необходимых для двиной подпрограммы; 1.1ИХ— ссылка на элемент каталога для подпрограммы, которая находится сразу за данной подпрограммой; ЯОВ1, ЯОВ2,, ЯОВп (и > 0) — связи с элементами каталога для других подпрограмм, которыенсобходимыдляработыданнойподпрограммы; В = Одлявсехслов, за исключением последнего, В " — 1 для последнего слова в узле. Адрес элемента каталога для первой подпрограммы на магнитной ленте с библиотекой подпрограмм задается переменной связи Р1ЕЯТ. Ь) Список подпрограмм, непосредственно указанных загружаемой программой.
Он хранится в последовательных позициях Х(1], Х(2], ..., Х(М], где И > 0 — переменная, которая известна процелуре загрузки. Каждый элемент этого списка является связью с элементом каталога для соответствующей подпрограммы. Процелуре загрузки также известно количество перемещений (И1.ОС), которые необходимо выполнить для загрузки первой подпрограммы. В качестве небольшого примера рассмотрим следующую конфигурацию. Каталог ленты Необходимые подпрограммы Х(1] = 1003 Х(2] = 1010 М=2 РХЕЯТ = 1002 МАСС = 2400 Каталог ленты в данном случае показывает,что в указанном порядке на ленте хранятся подпрограммы 1002, 1010, 1006, 1000, 1005, 1003 и 1007. Подпрограмма 1007 занимает 200 позиций, и при ее работе предполагается использовать подпрограммы 1005, 1002 и 1006, и т.
д. Для загрузки этой подпрограммы потребуются подпрограммы 1003 и 1010, которые будут размещены в ячейках по адресам > 2400. В свою очередь, для этих подпрограмм потребуется загрузить также подпрограммы 1000, 1006 и 1002. Блок распределения памяти подпрограммы должен изменить таблицу Х так, чтобы каждый элемент Х П], Х [2],... принял следующую форму: О ВАЯЕ ЯОВ В 1000: 0 1001: -1 1002: -1 1003: 0 1004: -1 1005;, -1 1006: -1 1007: 0 1008: 0 1009: — 1 1010: -1 ЯРАСЕ 11ИК 20 1005 1002 0 30 1010 200 1007 1000 1006 100 1003 60 1000 200 0 1005 1002 1006 0 20 1006 (за исключением последнего элемента, который описывается ниже), где ЯЯ — загружаемая подпрограмма и ВАЯŠ— величина перемещения. Данные элементы должны быть расположены в том же порядке, в котором они располагаются на ленте.
Ниже показано одно нз возможных решений задачи из приведенного выше примера. ВАЯЕ ЯВВ ВАЯЕ ЯВВ Х (1]: 2400 1002 Х (4]: 2510 1000 Х (2]: 2430 1010 Х (5]: 2530 1003 Х(3]: 2450 1006 Х(6]: 2730 0 Последний элемент содержит значение адреса первой неиспользуемой ячейки памяти, (Очевидно, что это не единственный способ работы с библиотекой подпрограмм. Соответствующая ему организация библиотеки в значительной степени зависит от типа используемого компьютера и выполняемых приложений. При работе с мощными современными компьютерами для организации библиотеки подпрограмм потребуется совершенно другой подход.
Тем не менее рассмотренный выше метод является прекрасным примером использования интересных приемов работы с последовательными и связанными данными,) Назначение этого упражнения состоит в создании алгоритма решения поставленной задачи. Созданный для этого блок распределения памяти может при подготовке решения преобразовывать каталог ленты произвольным образом, так как каталог ленты может считываться снова и снова блоком распределения памяти при следующем распределении, причем каталог ленты не будет востребован никакими другими частями процедуры загрузки. 27.
[25] Напишите программу для компьютера ВХХ, реализующую алгоритм из упр. 26. 28. [40[ Приведенная ниже конструкция демонстрирует способ "решения" достаточно общей задачи — игры для двух лиц, например шахматы, ним или другие более простые игры. Рассмотрим конечное множество узлов, каждый из которых представляет собой возможное состояние игры. Существует несколько шагов (или ни одного), которые позволяют преобразовать каждое состояние в некоторое другое. Назовем состояние х предшественником состояния у (а у †наследник состояния х), если существует такой шаг, который переводит состояние х в состояние у.
Состояния без наследников называются проигрышем или вмигрмшехс Игрок, делающий ход с переходом в состояние х, является соперником игрока, который делает ход с переходом от состояния х к состояниям-наследникам. Имея такую конфигурацию состояний, полный набор выигрышных состояний (в которых может выиграть игрок, делающий следующий ход) и полный набор проигрышных состояний (в которых обязательно проигрывает игрок, делающий следующий ход) можно вычислить, повторяя следующую операцию до тех пор, пока не будет достигнуто неизменное состояние.
Обозначим состояние "проигрышным", если все состояния-наследники являются "выигрышными", и обозначим состояние "выигрышным", если хотя бы одно состояние-наследник является "проигрышным". После бесконечного повторения этой операции некоторые состояния могут быть никак не обозначены. Это значит, что игрок, делающий следующий ход из такого состояния, не может выиграть, но его нельзя победить.
Такая процедура вычисления полного набора выигрышных и проигрышных состояний может быть сформулирована для компьютера в виде алгоритма, подобного алгоритму Т. Для этого можно сохранять для каждого состояния количество его состояний-наследников, которые не отмечены как "выигрышные", а также список всех его предшественников. Назначение этого упражнения состоит в создании конкретного алгоритма, который лишь приблизительно описан выше, и в его применении для некоторых интересных игр, не содержащих слишком большого количества возможных состояний [подобных "военной игре": Е. 1 исав, Н4сгеасюлв МасАешасСсСиев 3 (Рапэ, 1893), 105 — 116; Е. Н.
Вег1е1сашр, 1. Н. Сопжау, апсс Н. К. Сйу, И'слп!л8 Срауэ 2 (Асабесо!с Ргеээ, 1982), СЬарсег 21]. ° 29. [И] (а) Предложите алгоритм "удаления" всего списка (1) с размещением всех его узлов в стеке АЧА11., если известно только значение РТК8Т. При этом алгоритм должен иметь оптимизированную скорость выполнения. (Ь) Решите задачу из и. (а) для списка (12) при условии, что известны значения Р и К. 30. [17] Предположим, что очереди выглядит тах, как (12), но с пустой очередью, представленной значением Г = Л и нсопределенньсм значением К. Как в таком случае следует изменить операции вставки и удаления, представленные правилами (14) и (17)? 2.2.4. Циклические списки Немного изменив способ связывания, можно ввести новый метод, альтернативный предложенному в предыдущем разделе.
Циклически связанный список (ссгси)аг19 )спйесС йэС) (или короче — циклический список) — это связанный список., в котором последний узел связан с первым узлом, а не с Л. Поэтому всегда существует возможность доступа к любому элементу списка, начиная с произвольно выбранного элемента. К тому же повышается степень симметрии структуры списка, и при работе со списком можно не заботиться о том, где находится последний или первый узел. Типичная схема циклического списка выглядит так: гтв .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
