Д. Кнут - Искусство программирования том 1 (1119450), страница 99
Текст из файла (страница 99)
Полиномы в разделе 2.2.4 содержали не более трех переменных, в то время как при работе с большим количеством переменных удобнее использовать не линейный список, а древовидную структуру. Полипом либо представляет собой константу, либо имеет вид дух", э<1<в где х — переменная, и > О, О = ее < е~ < . < е„, де,...,д„— полиномы по другим переменным, символьные имена которых в алфавитном порядке располагаются до переменной х, а полиномы дм..., д„отличны от нуля.
Это рекурсивное определение полипомов подходит для представления деревьев, как показано иа рис. 28. Узлы имеют по шесть полей, которые в случае использования компьютера И1Х можно разместить в трех словах: (17) Здесь ЕЕРТ, 81СНТ, ОР и 000М вЂ” связи, ЕХР†цел число, которое указывает степень, а Су — либо константа (коэффициент), либо символьное имя переменной. Для корневого узла ОР = А, ЕХР = О, 1.ЕРТ = 81СНТ = * (связан с самим собой). $ Я с 4 й о Я 3 Ф Б Ы О3 х о и а Е я М И + ФЪ Ф + о Н И о о л о й О о Е о Е ! м .). В, м + й + о Г о Р Ю о о Е о х Л м о Б Д 4 Г "б ~б й л о И М а Ф о д Ф Й а о 6 о Я 4 а о д О О О" 3и ж о в 2 д Ф Л О Й~ Ф Л а. о о М Ю (Ч (> О, ~~ В следующем алгоритме показано, как в таком дереве со связями ло четырем направлениям можно организовать операции обхода, вставки и удаления.
А потому он заслуживает особого внимания. Алгоритм А (Сложение полииомов). Этот алгоритм складывает полипом (Р) с полиномом (Ц) при условии, что Р и Ц являются указательными переменными, которые указывают на корни различных полиномиальных деревьев, подобных показанным иа рис. 28. По завершении работы этого алгоритма полипом (Р) останется в исходном неизменном виде, а лелином (Ц) будет содержать искомую сумму. А1.
[Проверка типа лолинома.] Если РОМИ(Р) = Л (т. е...если Р указывает на константу), то ни разу не устанавливать или устанавливать Ц + — РОМИ(Ц) до тех пор, пока не выполнится условие РОММ(ц) = Л, н перейти к шагу АЗ. Если РОМИ(Р) ф Л, то при РОМИ(Ц) = Л или СЧ(Ц) < СЧ(Р) перейти к шагу А2. В противном случае, если СЧ(Ц) = СЧ(Р), установить Р с — РОМИ(Р), Ц +- РОМИ(Ц) и повторить этот шаг.
Если СЧ(Ц) > СЧ(Р), установить Ц < — РОМИ(Ц) и повторить этот шаг. (На шаге А1 будут найдены два подобных члена в складываемых полиномах или указано на необходимость вставки новой переменной в текущем месте полинома (Ц).) А2. [Вставка по направлению вниз.] Установить К ~ АЧАП., Я +- РОММ(Ц). Если Я ф Л, установить ОР(Я) < — К, Я е- К1СНТ(Я) и, если ЕХР(Я) ф О, повторять зту операцию до тех пор, пока не получится ЕХР(Я) = О. Установить ОРОМ) < — Ц, РОМИОК) + — РОМИ(Ц), 1.ЕРТ(К) +- К, К1СНТ(К) с — К, СЧОК) + — СЧ(Ц) и ЕХР(К) +- О, Наконец, установить СЧ(Ц) < — СЧ(Р) и РОМИ(Ц) < — К, а затем вернуться к шагу А1. (" Фиктивный" нулевой полипом вставляется сразу под узлом ИООЕ(Ц), чтобы составить пару с полиномом, найденным внутри дерева Р.
Обработка связей на этом шаге выполняется очень просто и может быть легко выведена с помощью схемы "до и после", как показано в разделе 2.2.3.) АЗ..[Пара найдена.) (Здесь Р и Ц указывают на соответствующие члены данных полнномов, поэтому можно приступать к сложению.) Установить СЧ(Ц) +- СЧ(Ц) + СЧ(Р). Если сумма равна нулю и если ЕХРОЦ) ф О, перейти к шагу А8. Если ЕХР(Ц) = О, перейти к шагу А7. А4.
[Продвижение влево.] (После успешного сложения одного члена перейдем к следующему члену, который нужно сложить.) Установить Р е- 1.ЕРТ(Р). Если ЕХР(Р) = О, перейти к шагу Аб. В противном случае ни разу не устанавливать или устанавливать Ц е — АЛЕЕТ(Ц) до тех пор, пока не выполнится условие ЕХР(Ц) ( ЕХР(Р). Затем, если ЕХР(Ц) = ЕХР(Р), вернуться к шагу А1.
Аб. [Вставка справа.] Установить К ~ АЧА11. Установить ОР(К) <- ОР(Ц), РОМИ(К) +- Л, СЧ(К) +- О, 1ЕРТ(К) е- Ц, КТСНт(К) +- КТСНТ(Ц), АЛЕЕТ(К1СНТ(К)) +- К, К1СНТ(Ц) +- К, ЕХР(К) +- ЕХР(Р) и Ц < — К. Вернуться к шагу А1. (Необходимо вставить новый член в текущей строке справа от узла МООЕ(Ц) в соответствии со степенями текущего члена полинома (Р). Как и на шаге А2, эту операцию легче понять, если составить схему "до и после".) Аб. [Возвращение вверх,] (Обход строки полинома (Р) полностью завершен,) Установить Р (- ОР(Р).
АТ. [Перевод Ц иа соответствующий уровень.] Если 0Р(Р) = Л, перейти к |лагу А11. В противном случае ни разу не устанавливать или устанавливать Ц | — ЦР(Ц) до тех пор, пока не вылолнится условие СЧ(0Р(Ц)) = СЧ(0Р(Р)). Вернуться к шагу А4. А8. [Удаление нулевого члена.] Установить Н +- Ц, Ц | — Н1ОНТ(й), Я | — ~,ЕРТ(Н), АЛЕЕТ(Ц) |- Я, 816НТ(Я) |- Ц н АЧА1Е ~= Н. [Удаление выполнено, поэтому удаляется строка лолинома (Ц).) Если теперь ЕХР(ЕЕРТ(Р)) = О и Ц = Я, перейти к шагу А9; в противном случае вернуться к шагу А4. А9. [Удаление полинома-константы.] [Аннулирование членов вызвало сокращение лолинома до константы, поэтому строка полннома (Ц) удаляется.) Установить Н+- Ц, Ц +- 0Р(Ц), ООЫИ(Ц) +- РОЫИ(Н), СЧ(Ц) | — СЧ(Н) и АЧА11.
Ф= Н. Установить Я | — ООЫИ(Ц). Если Я ф Л, установить 0Р(Я) +- Ц, Я +- Н16НТ(Я) и, если ЕХР(Я) ф О, повторять эту операцию до тех лор, пока не получится ЕХР(Я) = О. А10. [Обнаружение нуля?] Если ООЫИ(Ц) = Л, СЧ(Ц) = О и ЕХР(Ц) ф О, установить Р | — 0Р(Р) и перейти к шагу А8, в противном случае перейти к шагу Аб. А11. [Прекращение выполнения алгоритма.] Ни разу не устанавливать или устанавливать Ц |- 0Р(Ц) до тех пор, пока не получится 0Р(Ц) = Л (с. переводом указателя Ц на корень этого дерева).
1 Даиньш алгоритм выполняется гораздо быстрее, чем алгоритм 2.2.4А, если полипом (Р) имеет мало членов, а полипом (Ц) — много, так как в процессе сложения совершать обход всего полинома (Ц) необязательно. Читателю будет очень полезно вручную выполнить алгоритм А, складывая полипом хр — х — хрх — х + Зхх с 2 з, з полнномом, показанным на рнс. 28. (Этот случай це предназначен для демонстрации эффективности данного алгоритма, ио позволяет ознакомиться со всеми его шагами и представить все сложные ситуации, которые следует обработать.) Дальнейшее обсуждение алгоритма А приводится в упр. 12 и 13. Показанное на рнс. 28 представление для полиномов от произвольного количества переменных не является "наилучшим".
Например, в главе 8 будет рассмотрен другой формат представления полнномов, а также некоторые арифметические алгоритмы па основе вспомо|ятельного стека, которые ло сравнению с алгоритмом А обладают существенными преимуществами в отношении концептуальной простоты. Алгоритм А интересен для нас в основном тем, как в нем организована обработка деревьев с большим количеством связей. УПРАЖНЕНИЯ 1. [Щ Можно ли восстановить связи ШИК, зная только поля ьТАС, 1ИГО и НТАО узлов в последовательном порядке уровней, подоб|юм (8)? (Иначе говоря, не являются ли поля ьь1ик избыточными в представлении (8) и поля кь1ик — в представлении (3)?) 2.
[Ий] (Зада |а Беркса, Уоррена н Райта, А(асб. Со|ар. 8 (1954), 53 — 57.) Пустьдеревья (2) хранятся в памяти в прямом порядке с указанием степеней ОЕОКЕК 2 О 1 О 3 1 О 1 О О 1ИРО 4 В С К В Е Н Р' У С [Ср. с (9), где онн приведены н обратном порядке.] Создайте алгоритм, аналогичный алгоритму Г, для опенки локально определенной функции узлов, выполнив обход этого представления справа палево. ° 3. [24] Измените алгоритм 2 3 2[], используя идею алгоритма р промежуточные производные размещались в стеке, а их адреса не записываются таким необычным способом, который применяется на шаге ]33 (см упр 232-21) Управление стеком может осуществляться на основе поля Н1.1ИК в корне каждой производной 4.
[1В] Деревья (2) содержат 10 узлов, пять из которых являютсяконцевыми Представление этих деревьев в виде нормальных бинарных деревьев включает 10 полей ЕХХМК и 10 полей НЕ1МК (по одному для каждого узла) Для представления этих деревьев в виде (10), где ШМК и 1МР0 совместно используют одно и то же пространство внутри узла, требуется 5 полей ШМК и 15 полей Н1.1ИК В каждом случае имеется по 10 пслей 1МРС Для леса с и узлами, гн из которых являются концевыми, сравните общее количество полей 511ИК и НИИК, которые необходимы для каясцого из этих двух методов представления дерева 5. [15] Трижды связанное дерево, аналогичное показанному на рис 26, содержит в каждом узле поля РАНЕИТ, ЕСН110 и НЕ1МК, причем при отсутствии узла, на который могли бы указать поля РАНЕМТ, ЕСН110 и Н11ИК, в них применяются связи Л Стоит ли расширять это представление до прошитого дерева, применяя связи-нити вместо пустых связей ЕСН110 и Ы.1МК, как показано в разделе 2 3 1т 6.
[21] Предположим, что узлы ориентированного леса имеют по три поля связи РАНЕМТ, ЬСНП.0 и М.1МК, но талька одна связь РАНЕИТ используется для обозначения древовидной структуры Поле ЕСИПОВ каждого узла равно Л, а поля Ы.1МК расположены в линейном списке, который просто связывает узлы вместе в некотором порядке Переменная связи Р1НЯТ указывает иа первый узел, а в последнем узле Ы.1ИК = Л Создайте алгоритм обхода этих узлов и заполнения полей 100110 и Ы.1ИК в соответствии со значениями связей РАНЕИТ, чтобы в результате можно было получить представление трижды связанного дерева, подобное показанному на рис 26 Кроме того, установите для Г1ННТ значение которое будет указывать на корень первого дерева в этом представлении 7. [15] Какие классы содержались бы в (12), если бы в (11) отсутствовало отношение 9 ги Зт 8. [15) Алгоритм Е задает древовидную структуру, которая представляет заданные пары эквивалентных элементов, но в этом разделе явно не указывается, как можно использовать результат выполнения алгоритма Е Создайте алгоритм, который может установигь справедливость выражения "1 = /с" при условии, что 1 < 1 < и, 1 < А < и и алгоритм Е задает таблицу РАНЕИТ для некоторого набора пар эквивалентных элементов 9.
[20] Предложите таблицу наподобие (15) и схему вида (16), которые изображали оы деревья, полученные после обработки алгоритмом Е всех пар эквивалентных элеменгов в (11) в направлении слева направо 10. [ВВ] Для обработки п пар эквивалентных элементов с помощью алгоритма Е в худшем случае потребуется выполнить около пг шагов Покажите, как можно было бы модифицировать этот алгоритм, чтобы повысить эффективность его работы в данном случае ь 11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
