AOP_Tom1 (1021736), страница 79
Текст из файла (страница 79)
АЗ. [Сложение коэффициентов.) (Найдены члены с одинаковыми степенями.) Если АВС(Р) < О, выполнение алгоритма прекращается. В противном случае установить СОЕР(Ц) +- СОЕР(Ц) + СОЕР(Р), Теперь, если СОЕР(Ц) = О, перейти к шагу А4; в противном случае установить Р +- ЫМК(Р), Ц1 +- Ц, Ц е- 1.1ИК(Ц) и перейти к шагу А2.
(Любопытно, что последние операции идентичны шагу А1.) А4. [Удаление нулевого члена.) Установить Ц2 е- Ц, ЫМК(Ц1) < — Ц +- ЫМК(Ц) и АЧА11 с.= Ц2. (Порожденный на шаге АЗ нулевой член удален из многочлена (Ц) .) Установить Р +- ЫИК(Р) и вернуться к шагу А2. АЗ.
[Вставка нового члена.] (Многочлен (Р) содержит член, который отсутствует в многочлене (Ц), поэтому его необходимо вставить в многочлен (Ц).) Установить Ц2 с= АЧАП., СОЕР(Ц2) е — СОЕР(Р), АВС(Ц2) е — АВС(Р), 11МК(Ц2) +- Ц, ЫМК(Ц1) +- Ц2, Ц1+- Ц2, Р+ — ЫИК(Р) и вернуться к шагу А2. ) Одна нз наиболее замечательных особенностей алгоритма А заключается в способе следования указателя Ц1 за указателем Ц в списке.
Этот способ типичен для алгоритмов обработки списков, и мы не раз еще встретим алгоритмы с такой же особенностью. Может ли читатель объяснить, почему данная идея использовалась в алгоритме А? Читателю с небольшим опытом работы со связанными списками будет очень полезно внимательно изучить алгоритм А, например в качестве упражнения попробовать сложить многочлены х + у+ х и х — 2у — г. г Зная алгоритм А, можно удивительно просто создать следующий алгоритм для операции умножения. Алгоритм М (Умножение многочленов). Этот алгоритм аналогичен алгоритму А и заменяет многочлен (Ц) суммой многочлен (Ц) + многочлен (И) х многочлен (Р). М1.
[Следующий множитель.] Установить И е — 1.1ИК(И). Если АВС(И) < О, то выполнение алгоритма прекращается. М2. [Цикл умиожения.] Выполнить алгоритм А, но всякий раз, когда появляется обозначение "АВС(Р)", заменить его командой "если АВС(Р) < О, то -1; в противном случае АВС(Р)+АВС(И)"; когда появляется обозначение "СОЕР(Р)", заменить его командой" "СОЕР(Р) х СОЕР(И)". Затем перейти к шагу М1. $ Программирование алгоритма А на языке компьютера И1Х вновь демонстрирует легкость, с которой компьютер может манипулировать связанными списками. В приведенном ниже коде предполагается, что ори возникновении переполнения (ОЧЕНР10М) вызывается подпрограмма, которая либо завершает выполнение программы (из-за нехватки памяти), либо находит свободное пространство и выходит на г8 — 2.
Программа А (Слоэгсение многочленов). Эта подпрограмма (рнс. 10) создана так, чтобы ее можно было использовать вместе с подпрограммой умножения (см. упр. 15). Вызов: 1ИР А 00. Состояние до вызова: гП = Р, г12 = Ц. Состояние после вызова: Многочлен (Ц) заменяется суммой: многочлен (Ц) + многочлен (Р); гП и г12 остаются неизменными; все другие регистры имеют неопределенное содержимое. Рис. 10. Сложение многочленов. В приведенном ниже коде Р ЕК гП, Ц = г12г Ц1 = г13 и Ц2 = г16 для принятых в алгоритме А обозначений. 1 1+ ага 1+ пг'~ 1Ч-Р 1+И Р'+ Ч' г) Ч Ч пг -ь 1 01 1.1МК 08 АВС 08 А00 01 1Н ОБ Об ОН 07 ЯМ1 08 2Н ОУ 10 11 18 18 11 ЗН 18 ЯМ2 1б ЕЦО 4:Ь ЕЦО 0:3 ЯТЗ ЗР ЕМТЗ 0,2 102 1,3(1.1МК) 1.01 1,1(1.1МК) 10А 1,1 СИРА 1,2(АВС) ЛЕ ЗР 10 ЯР ЕМТЗ 0,2 1.02 1,3(1.1МК) ЗИР 2В )АМ ЫА 0,1 АОО 0,2 Определение поля 1.1ИК.
Определение поля АВС. Вход в подпрограмму. гг~е ьгк г, Ц +- 11ИК(01). Р +- 1.1МК(Р). гА(0:3) +- АВС(Р). ггг. г~гг шгэг, Если равно, перейти к шагу АЗ. Если больше, перейти к шагу А5. Если меньше, установить 01 +- Ц. Ц ь- 11ИК(Ц1). Повторить. АЗ. Сложение коз и нентов.
СОЕР(Р) + СОЕР(Ц) -+ СОЕР(Ц). Если не равно нулю, совершить переход. А4. У аление и левого члена. Ц2 ь- Ц. Ц <- ЫИК(Ц) ЫИК021) +- Ц. Перейти с продвижением указателя Р. А5. Вставка нового члена. Ц2 ~ АЧАТ) АВС(Ц2) <- АВС(Р). гА +- СОВР(Р). СОЕР(Ц2) +- гА. ЫИК(Ц2) +- Ц. ЫИХ(Ц1) +- Ц2. 01+- 02, Перейти с продвижением указателя Р. Обратите внимание, что в алгоритме А предусмотрен только однократный проход каждою списка, причем для их обработки не пришлось выполнять несколько циклов. Используя закон Кнрхгофа, без особого труда найдем, что количество команд н время выполнения зависят от следующих четырех величин: т' — количество подобных членов, которые взаимно сокращаются; гл" — количество подобных членов, которые нельзя сократить; )1 — количество членов в многочлене (Р), для которых нет подобных членов в многочлене(Ц); д' — количество членов в многочлене (Ц), для которых нет подобных членов в многочлене (Р).
Анализ программы А с помощью обозначений т = т' + т", р = т + р', д = т + д', х = 1 + т + р' ч- д' позволяет получить следующую оценку времени ее выполнения на компьютере М1Х: (27т'+ 18т" + 27р'+ 8о' + 13)и. Минимальное количество узлов в пуле, которые необходимы для выполнения алгоритма, равно 2+ р + д, а максимальное — равно 2+р+д+р. УПРАЖНЕНИЯ 1. [21] В начале этого раздела было предложено представлять пустой циклический список с помощью указателя РТЕ = Л. Однако согласно идеологии создания циклических списков для обозначении пустого списка более последовательно было бы использовать значение РТЕ = 1.ОС(РТЕ).
Упрощает ли такое условие выполнение операций (а) — (с), которые описаны в начале этого раздела? 2. [20[ Нарисуйте схемы состояний "до" и "после", которые демонстрируют результат выполнения операции конкатенации (3) при условии, что РТВ~ и РТЕэ не равны Л. 17 1В 19 2О 21 22 22 2А 25 Еб ЯН 27 2В 29 бб 21 ЯИЗ 22 Уу .14 бб уб ЯТА 0,2 ЗАМЕ 1В ЕМТ6 0,2 ЕР2 1,2(ЫМКУ 1.0Х АЧАУЛ. ЯТХ 1,60 1МК) ЯТ6 АЧА1 ЯТ2 1„3(1,1МК) ЗМР ОВ 106 АЧА1) З62 ОЧЕВРЬОИ ЕВХ 1,6(ЫМК) БТХ АЧШ БТА 1,6 ЕРА 0,1 ЯТА 0,6 ЯТ2 1,6(ЫМК) БТ6 1,3(1.|МК) ЕМТЗ 0,6 ЗМР ОВ т т' т' т' т' т' т' т' Р Р' Р Р Р Р Р Р Р Р Р 3. [20] Каким будет результат выполнения операции (3), если оба указателя РТЕг и РТЯэ направлены на узлы одного а тяго хсг циклического списка? 4.
[ЯО] Сформулируйте операции вставки и удаления, которые в результате позволят использовать список (4) как стгьЬ ° б. [31] Создайте алгоритм, который обращает циклический список, т. е. направления всех стрелок на схеме (1). б. [10] Нарисуйте схему представления следующих многочленов в виде списков: (а) хг — 3; (Ь) О. Т. [10] В чем заключается преимущество расположения членов многочлена в порядке убывания значений поля АВС? Я. [10] В чем заключается преимущество следования указателя Ц1 за указателем О в алгоритме А? ° 9. [Еу] Будет ли алгоритм А функционировать правильно, если Р = О (т.
е. оба указателя указывают на один н тот же многочлен)? В каком случае алгоритм М будет работать правильно: если Р = Н, если Р = Ц или если И = Ц? ° 10. [ЯО] При создании алгоритмов в данном разделе предполагалось, что в многачленах используются три переменные х, р и г, а их степени по отдельности никогда не превышают Ь вЂ” 1 (где 6 — размер байта в компьютере И1Х).
Вместо этого предположим. что осуществляется сложение и умножение многочленов от одной переменной, х, степень которой может достигать значения Ь вЂ” 1. Какие изменения следует внести в алгоритмы А и М? 11. [Ед] (Назначение этого упражнения и многих следующих заключается в создании пакета подпрограмм арифметики многочленов для совместной работы с программой А.) Поскольку алгоритмы А и М изменяют многочлен (О), иногда полезно иметь подпрограмму, которая делала бы копию исходного многочлена. Напишите программу для компьютера НТХ со следующими заданными спецификациями. Вызов; Л(Р СОРТ.
Состояние до вызова: г11 = Р. Состояние после вызова: Н2 указывает на вновь созданный многочлен, равный многочлену (Р); г11 остается неизменным; другие регистры не определены. 12. [Я)] Сравните время выполнения программы из упр, 11 и время выполнения алгоритма А, если многочлен(О) = О. 13. [ЯО] Напишите подпрограмму для компьютера Н1Х со следующими спецификациями. Вызов: УИР ЕЕАЯЕ, Состояние до вызова: г11 = Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
