Методы программирования. Громов Ю.Ю - 26 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

26
A1. [Начальная установка.] P ← LINK(P), Q
1
← Q, Q ← LINK(Q).
(Теперь P и Q указывают на старшие члены многочленов. Переменная Q
1
в алгоритме почти везде будет «на один шаг отставать» от Q, т.е. будет
выполняться равенство Q = LINK(Q
1
).)
A2. [Сравнение ABC(P) и ABC(Q).] Если ABC(P) < ABC(Q), то Q
1
← Q,
Q ← LINK(Q) и выполнить этот шаг сначала. Если ABC(P) = ABC(Q), то
перейти к шагу A3. Если ABC(P) > ABC(Q), то перейти к шагу A5.
A3. [Сложение коэффициентов.] (Найдены два члена с равными сте-
пенями.) Если ABC(P) < 0, то конец алгоритма; в противном случае
COEF(Q) ← COEF(Q) + COEF(P). Теперь если COEF(Q) = 0, то перейти
к шагу A4; в противном случае Q
1
← Q, P ← LINK(P), Q ← LINK(Q) и
вернуться к шагу A2.
A4. [Исключение нулевого члена.] Q
2
← Q, LINK(Q
1
) ← Q ← LINK(Q)
и AVAIL ⇐ Q
2
. (Нулевой член, образовавшийся на шаге A3, исключён из
многочлена Q.) P ← LINK(P) и вернуться к шагу A2.
A5. [Включение нового члена.] (Многочлен P содержит член, кото-
рый не представлен в многочлене Q и поэтому мы включаем его в много-
член Q.) Q
2
⇐ AVAIL, COEF(Q
2
) ← COEF(P), ABC(Q
2
) ← ABC(P),
LINK(Q
2
) ← Q, LINK(Q
1
) ← Q
2
, Q
1
← Q
2
, P ← LINK(P) и вернуться к
шагу A2. ■
В рассмотренном алгоритме значением отношения:
• ABC(P) < ABC(Q) следует считать значение логического выраже-
ния A(P) + B(P) + C(P) < A(Q) + B(Q) + C(Q) или A(P) + B(P) + C(P) =
= A(Q) + B(Q) + C(Q) и (A(P) < A(Q) или A(P) = A(Q) и B(P) < B(Q));
• ABC(P) = ABC(Q) – значение логического выражения A(P) = A(Q)
и B(P) = B(Q) и C(P) = C(Q);
• ABC(P) > ABC(Q) – значение истина, если ложны первое и вто-
рое логические выражения, а значение ложь в противном случае.
Время выполнения реализующей данный алгоритм программы для
гипотетической вычислительной машины MIX составляет (29m’ + 18m” +
+ 29p’ + 8q’ + 13) u, где m’ – количество подобных и взаимно уничто-
жающихся членов; m” – количество подобных, но взаимно не уничто-
жающихся членов; p’ – количество членов в многочлене P, которым нет
подобных в многочлене Q; q’ – количество членов в многочлене Q, кото-
рым нет подобных в многочлене P; u – время выполнения машиной одно-
го такта. Во время выполнения алгоритма в пуле памяти необходимо
иметь не менее чем (2 + p + q) и самое большое (2 + p + q+ p’) узлов.
Списки с двумя связями позволяют достичь ещё большей гибкости в
работе с линейными списками. При этом каждый элемент списка имеет
две связи LLINK и RLINK, которые указывают на элементы, находящиеся
по обе стороны от данного узла:

Страницы