Д. Кнут - Искусство программирования том 1 (1119450), страница 77
Текст из файла (страница 77)
упр. 15). Вызов: 1МР А 00. Состояние до вызова: г11 = Р, г12 = Ц. Состояние после вызова: Многочлен (Ц) заменяется суммой: многочлен(Ц) + многочлен (Р); г11 и г12 остаются неизменными; все другие регистры имеют неопределенное содержимое. Рис. 10. Сложение многочленов. В приведенном ниже коде Р = г?1, Ц = г12, Ц1 = г13 и Ц2 = г1б для принятых в алгоритме А обозначений. 1 1+ т" 1-~- нг 1+р 1+Р х х Р +Ч Ч »( Ч гн+ 1 гн 01 01МК 00 АВС 00 АОО 01 1Н Об Об ОН 07 ЯМ1 00 2Н 09 10 11 10 10 11 ЗН 10 БЧ2 1б ЕЦО 4:б ЕЦО 0:3 ЯТЮ ЗР ЕМТЗ 0,2 102 1,3(ЫМК) 001 1,1(11МК) 10А 1,1 СИРА 1,2(АВС) ЗЕ ЗР 16 5Р ЕМТЗ Огй 1.02 1,3(11МК) ЗМР 2В ЗАМ 10А 0,1 А00 0,2 Определение поля 1.1ИК.
Определение поля АВС. Вход в подпрограмму. ~г.у .у г г. Ц +- 1.1ИК(Ц1). Р +- 1.1ИК(Р). гА(0:3) » — АВС(Р). ~гг. ~ы» гнув Если равно, перейти к шагу АЗ. Если больше, перейти к шагу Аб. Если меньше, установить Ц1 » — Ц. Ц +- ПИК(Ц1). Повторить. АЗ. Сложение коз н центов. СОЕК(Р) Ч- СОЕР(Ц) -+ СОЕР(Ц). Если не равно нулю, совершить переход. А4. У алениен левого члена. Ц2 +- Ц. э Ц +- ЫМЕ(Ц). АЕАП. т Ц2. 11ИК(Ц1) < — Ц.
Перейти с продвижением указателя Р. А6. Вставка левою члена. Ц2 т АУАП.. АВС(02) +- АВС(Р). гА +- СОЕР(Р). СОЕР(Ц2) +- гА. 11МК(Ц2) +- Ц. 11МЕ(Ц1) +- Ц2. Ц1 е- Ц2. Перейти с продвижением указателя Р. Обратите внимание, что в алгоритме А предусмотрен только однократный проход каждого списка, причем для их обработки не пришлось выполнять несколько циклов. Используя закон Кирхгофа, без особого труда найдем, что количество комацд и время выполнения зависят от следующих четырех величин: т' — количество подобных членов, которые взаимно сокращаются; т" — количество подобных членов, которые нельзя сократить; р' — количество членов в многочлене (Р), для которых нет подобных членов в многочлене(Ц); д' — количество членов в многочлене (Ц), для которых нет подобных членов в многочлене (Р).
Анализ программы А с помощью обозначений т = т' + т", р = т + р', Ц = т+ Ц', х = 1+ т+ р'+ е позволяет получить следующую оценку времени ее выполнения на компьютере М1Х: (27т' + 18гп" + 27р' + 8д' + 13)и. Минимальное количество узлов в пуле, которые необходимы для выполнения алгоритма, равно 2+ р+ д, а максимальное — равно 2+р+Ц+р'. УПРАЖНЕНИЯ 1. ]81] В начале этого раздела было предложено представлять пустой циклический список с помощью указателя РТЕ = Л.
Однако согласно идеологии создания циклических списков для обозначения пустого списка более последовательно было бы использовать значение РТЕ = 1.0С(РТЕ). Упрощает ли такое условие выполнение операций (а) — (с), которые описаны а начале этого раздела? 2. [80] Нарисуйте схемы состояний "до" и "после", которые демонстрируют результат выполнения операции конкатенации (3) при условии, что РТЕ1 и РТАМ не равны Л. 17 18 19 86 81 88 88 81 85 86 БН 87 88 88 86 81 БИ3 88 88 81 85 86 БТА 0,2 ЛАМЕ 1В ЕМТб 0,2 ЕО2 1,2(ЫМКУ )Л)Х АУАП. БТХ 1,6(1.1ИК) БТ6 АУА11.
БТ2 1,3(ЫМК) ЛМР ОВ 106 АУАП ЛВЕ ОУЕЕРЬОМ ЬОХ 1>6(ЫМК) БТХ АУА11. БТА 1,6 1Л)А О, 1 БТА 0,6 БТ2 1,6(1.1МК) БТ6 1,3(ЫМК) ЕИТЗ 0,6 ЛМР ОВ т т' т т' т' т Ф т т' Р Р Р Р Р Р Р Р Р Р р' 3. [20] Каким будет результат выполнения операции (3), если оба указателя РТйг и РТЕг направлены на узлы одного и тяго хсе пиклического списка? 4. [20] Сформулируйте операции вставки и удаления, которые в результате позволят использовать список (4) как стеМ: 5. [21] Создайте алгоритм, который обращает циклический список, т.
е. направления всех стрелок на схеме (1). О. [13] Нарисуйте схему представления следующих многочленов в виде списков: (а) хг — 3; (Ь) О. Т. [10] В чем заключается преимущество расположения членов многочлена в порядке убывания значений поля АВС? 8. [10] В чем заключается преимущество следования указателя Ц1 за указателем Ц в алгоритме А? 9. [23] Будет ли алгоритм А функционировать правильно, если Р = Ц (т. е. оба указателя указывают иа один и тот же многочлен)? В каком случае алгоритм М будет работать правильно: если Р = Н, если Р = Ц или если И = Ц? ь 10. [20] При создании алгоритмов в данном разделе предполагалось, что в многочленах используются три переменные х, у и г, а их степени по отдельности никогда не превышают 6- 1 (где 6 — размер байта в компьютере НХХ).
Вместо этого предположим, что осуществляется сложение и умножение многочленов от одной переменной, х, степень которой может достигать значения 6 — 1. Какие изменения следует внести в алгоритмы А и М? г 11. [24] (Назначение этого упражнения и многих следующих заключается в создании пакета подпрограмм арифметики многочленов для совместной работы с программой А.) Поскольку алгоритмы А и М изменяют многочлен (Ц), иногда полезно иметь подпрограмму, которая делала бы копию исходного многочлена. Наггишите программу для компьютера Н11 со следующими заданными спецификациями.
Вызов: Л1Р СОРТ. Состояние до вызова: г11 ж Р. Состояние после вызова: г12 указывает иа вновь созданный многочлен, равный многочлену (Р); г11 остается неизменным; другие регистры не определены. 12. [21] Сравните время выполнения программы из упр. 11 и время выполнения алгоритма А, если многочлен(Ц) = О. 13. [20] Напишите подпрограмму для компьютера ИТХ со следующими спецификациями. Вызов; 1НР ЕЕАБЕ. Состояние до вызова: г11 = Р. Состояние после вызова: Многочлен (Р) добавляется в список АЧА11; значения других регистров не определены.
[Замечание. Эта подпрограмма может быть использована вместе с подпрограммой из упр. 11 в последовательности "1.91 Ц; ЛИР ЕВАБЕ; 191 Р; ЛИР СОРТ; БТ2 Ц", чтобы получить "многочлен (Ц) +- многочлен (Р)".] 14. [22] Создайте подпрограмму для компьютера И11 со следующими спецификациями. Вызов: )НР ЕЕЕО. Состояние до вызова: Не обусловлено. Состояние после вызова: г12 указывает на вновь созданный многочлен, равный О; значения других регистров не определены. 15.
[24] Создайте подпрограмму для компьютера НТХ для выполнения алгоритма М со следующими спецификациями. Вызов: Л(Р ИЯ.Т. Состояние до вызова: г11 = Р, г12 = Ц, г14 = И. Состояние после вызова: Многочлен(Ц) +- многочлен(Ц) + многочлен(М) х многочлен(Р); значения регистров г11, г!2, г14 остаются неизменными; значения других регистров не определены. [Замечание. Используйте программу А как подпрограмму, изменив значения 5И1, 5И2 и 5ИЗ.] 16. [Мэу] Оцените время выполнения подпрограммы из упр. 15 на основе наиболее важных параметров. ь 17.
[Як] В чем заключается преимущество представления многочлена в виде циклического списка (описанного э этом разделе) по сравнению с представлением э виде прямого линейного связанного списка, который завершается Л (и описанного в предыдущем разделе)? ь 18. [55] Придумайте способ нредстаэления циклических списков внутри компьютера таким образом, чтобы проход списка был эффективным в обоих направлениях, причем чтобы в каждом узле использовалось только одно поле связи. [Указание.
Если есть два ухазателя на два последовательных узла гн г и ян то должна существовать возможность доступа к узлам хьы и х,-г.] 2.2.5. Дважды связанные списки Для гибкой работы со связанными списками в каждый узел можно включить даже две связи, которые будут указывать на два соседних элемента: агент (1) Здесь КЕРТ и Я16НТ обозначают переменные связи, которые указывают на левый и правый концы списка.
Каждый узел списка включает две связи, например (.(.1ИК и ЭТИК. Как показано в упр. 1, при таком представлении со списком можно выполнять те же операции, что и с деком общего типа. Однако операции с деком почти всегда гораздо легче выполняются, если в нем присутствует узел с функциями заголовка списка, который рассмотрен в предыдущем разделе. При наличии заголовка списка типичная схема дважды связанного списка выглядит так, как показано ниже: Заголовок списка (2) Поля Н11ИК и ЬЫИК заголовка списка используются вместо указателей ьЕг 1 и Я16НТ в схеме (1).
Правый и левый концы абсолютно симметричны, поэтому заголовок списка может с таким же успехом располагаться с правой стороны списка на схеме (2). Если список пуст, оба поля связи заголовка списка указывают на сам заголовок. Представление списка в виде (2), очевидно, удовлетворяет условию Н~1ИК((.ЫИК(Х)) = ЕЕ1ИК(КЕ1ИК(Х)) = Х, где Х вЂ” адрес любого узла в списке (включая его заголовок).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
