1 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

     1.1 Выбор структуры хранения полинома

     При выполнении работы можно использовать следующее понимание полинома. Полином  состоит из мономов. Каждый моном  характеризуется коэффициентом Coef и степенями переменных A, B, C: Coef*x^Ay^Bz^C. Величину степеней переменных можно ограничить значением 9. При таком предположении максимально возможное количество мономов в полиноме - 1000. Полином разрежен, если по сравнению с максимально возможным количеством мономов он имеет относительно небольшое количество отличных от нуля коэффициентов. Например, у полинома P(x,y,z) отличных от нуля коэффициентов всего 4.

     При манипуляции разреженными полиномами эффективной структурой хранения являются списки. При этом каждое звено списка хранит моном с отличным от нуля коэффициентом.

     Структура хранения полиномов должна обеспечивать эффективное выполнение операций. Если мономы в списке упорядочить по степеням переменных, то можно предложить эффективный  алгоритм сложения полиномов, основанный на идее алгоритма слияния двух упорядоченных массивов.

     В результате операций (например, сложения) может быть получен полином, у  которого нет отличных от нуля коэффициентов. Структура хранения такого нулевого полинома не должна отличаться от структуры  хранения прочих полиномов.

     Для эффективного использования оперативной памяти реализуем операцию сложения таким образом, чтобы результат операции был получен на месте одного из слагаемых. При этом неизбежны вставки и удаления звеньев в списке. Для унификации вставок и удалений звеньев в начало, середину и конец списка рекомендуется использовать кольцевые списки.

     Таким образом, с учетом вышеизложенного, рекомендуется следующая структура  хранения полиномов. Полиномы упорядочиваются  по убыванию степеней мономов. Для определения  старшинства мономов вводится следующее правило. Во-первых, фиксируется старшинство переменных. Будем считать, что x - самая старшая переменная, затем следует y, затем z. Для каждого монома определим его "свернутую степень" (индекс). Для монома x^Ay^Bz^C. индекс равен A*10²+B*10¹+C*10⁰ (по условию задачи A, B и C не выше 9). Старшим считается моном с большей свернутой степенью. Например, x³y старше xy⁷z⁶, так как 310 больше 176.

     Полином представляется кольцевым списком. Каждое звено списка соответствует  моному с ненулевым коэффициентом. Звено состоит из трех полей и включает поле для хранения коэффициента, поле для хранения свернутой степени и поле для хранения указателя на звено следующего по порядку монома. Следующим после последнего звена является

     

     Структура хранения нулевого полинома

     

     

     

     Примеры структур хранения полиномов 

     первое  звено списка. Первым звеном списка является так называемое "головное " звено (голова списка), поле свернутой степени которого равно -1. Нулевой полином представляется только головой списка.

     Структуры хранения полиномов P(x,y,z), Q(x,y,z) и их суммы показаны на рисунке.

     1.2 Полиноминальная арифметика

     Арифметические  операции естественным образом применимы не только к числам, но и к различным математическим величинам. В этом разделе речь пойдет о полиномах, что представляет шаг вперед по сравнению с числами. Формально говоря, полином над S представляет собой выражение вида

      (1)

     где коэффициенты U1, ..., Un, U0 — элементы некоторой алгебраической системы S, а переменная х может рассматриваться как формальный символ без определенного значения. Будем полагать, что алгебраическая система S представляет собой коммутативное кольцо с единицей. Это означает, что S допускает операции сложения, вычитания и умножения, удовлетворяющие обычным свойствам: сложение и умножение являются ассоциативными и коммутативными бинарными операциями, определенными на S, причем умножение дистрибутивно по отношению к сложению. Существует также единичный элемент по сложению 0 и единичный элемент по умножению 1, такие, что а + 0 = а и а • 1 = а для всех а из S. Вычитание является обратной по отношению к сложению операцией, но о возможности деления как об операции, обратной по отношению к умножению, ничего не предполагается.

     Полином рассматривается как идентичный полиному (1), хотя формально он отличается от него.

     Мы  говорим, что (1) является полиномом степени n со старшим коэффициентом Un, если Un <> 0; в этом случае запишем

     deg(u)=n, L(u)=Un

     Кроме того, по определению

     deg(0) = -оо,

     L(0) = 0,

     где 0 означает нулевой полином, т.е. полином, все коэффициенты которого равны нулю. Мы говорим также, что U(х) — нормированный полином, если его старший коэффициент L(u) равен 1.

     Арифметика  полиномов состоит, в первую очередь, из сложения, вычитания и умножения; иногда к этим операциям добавляются  другие, например, деление, возведение в степень, разложение на множители  и поиск наибольшего общего делителя. Сложение, вычитание и умножение определяются естественным образом, как если бы переменная х была элементом S: мы складываем или вычитаем полиномы посредством сложения или вычитания коэффициентов при одинаковых степенях х. Умножение выполняется согласно правилу

     

     Где

     

     В последней формуле Ui и Vj рассматриваются как равные нулю при i > г и j > s соответственно.

     Алгебраическая  система S обычно представляет собой  множество целых или рациональных чисел. Она может быть и множеством полиномов (с другими, отличными  от х переменными); тогда (1) — полином от нескольких переменных. В частности, алгебраическая система S может состоять из целых чисел 0, 1, ..., m — 1 со сложением, вычитанием и умножением, выполняемыми по модулю m, этот важный случай называется полиномиальной арифметикой по модулю m. Особенно важна полиномиальная арифметика по модулю 2, когда каждый коэффициент равен 0 или 1.

     Имеется сходство между полиномиальной арифметикой и арифметикой многократной точности, где основание счисления Ь заменено на х. Основное отличие состоит в том, что коэффициент U_k при х^k в полиномиальной арифметике, вообще говоря, никак не связан с соседними коэффициентами Uk±i, так что понятие "перенос" из одного места в другое в полиномиальной арифметике отсутствует. В действительности полиномиальная арифметика по модулю Ь, по существу, идентична арифметике с многократной точностью по основанию Ь за исключением отсутствия переносов. Например, сравним умножение (1101)2 на (1011)2 в двоичной системе счисления с аналогичным умножением х³ + х² + 1 на х³ + х + 1 по модулю 2.

     Двоичные  числа

     1101 х 1011

     1101

          1101

        1101

        10001111

     Полиномы  по модулю 2

     1101 х 1011

     1101

          1101

        1101

         1111111

     Произведение  этих полиномов по модулю 2 получено путем отказа от всех переносов и  составляет х⁶ + х⁵ + х⁴ х³ + х² + х + 1. Если умножать полиномы так же, как целые числа, без получения остатков по модулю 2, результат будет равен х⁶ + х⁵ + х⁴ + Зх³ + х² + х + 1; переносы в данном случае также не используются, однако коэффициенты в произведении могут оказаться произвольно большими.

     Необходимо отметить некоторые аспекты, отличающие практическое использование полиномиальной арифметики от арифметики многократной точности. Очень часто при работе с полиномами наблюдается тенденция к появлению большого количества нулевых коэффициентов и полиномов огромных степеней, а потому желательно использовать специальные формы представления полиномов. Кроме того, арифметика полиномов от нескольких переменных приводит к программам, которые легче всего понять в рамках рекурсии. Хотя методы сложения, вычитания и умножения полиномов сравнительно просты и понятны, несколько важных аспектов полиномиальной арифметики достойны специального рассмотрения. В следующих разделах будут обсуждаться деление полиномов и связанные с ним методы, такие как поиск наибольшего общего делителя и разложение на множители. Мы рассмотрим также проблему эффективного вычисления полиномов, т.е. задачу поиска значения u(х) при данном х принадлежащем S с использованием минимально возможного числа операций. Частный случай вычисления хⁿ при больших n достаточно важен и разбирается отдельно в разделе.

     4.6.1. Деление полиномов

     Разделить один полином на другой можно так  же, как одно целое число с многократной точностью на другое, при выполнении арифметических операций с полиномами над полем. Поле S представляет собой коммутативное кольцо с единицей, в котором точное деление возможно так же, как и операции сложения, вычитания и умножения.. Как обычно, это означает, что для любых U,V принадлежащих S и V<>0 в S всегда имеется элемент w, такой, что u = vw. Наиболее важными полями коэффициентов, появляющимися в приложениях, являются

     a)  рациональные числа;

     b)  действительные или комплексные числа;

     c)  целые по модулю р, где р  — простое число;

     d)  рациональные функции над полем, т. е. частное двух полиномов, коэффициенты которых находятся в этом поле, а знаменатель нормирован.

     Особо важный случай представляет собой поле целых по модулю 2, в котором элементы могут принимать значения 0 и 1. Полиномы над этим полем (т. е. полиномы по модулю 2) имеют много общего с целыми числами в двоичной записи; рациональные функции над данным полем поразительно схожи с рациональными числами, числители и знаменатели которых представлены в двоичной записи.

     Если  даны два полинома, u{х) и v(x), над полем и v(x) <> 0, можно разделить u(х) на v(х) и получить полином-частное q(x) и полином-остаток г(х), удовлетворяющие условиям

     

     Легко увидеть, что существует не более  одной пары полиномов (q(x),r(x)), удовлетворяющих  этим соотношениям; в самом деле, если условиям при одних и тех же полиномах u(х) и v(x) удовлетворяют две пары — (q1(x),r1(x)) и (q2(x),r2(x)),— то q1(x)v{x) + r1(x) = q2(x)v(x) + r2(x), т. е. (q1(x) -q2(x))v{x) = r2(х) – r1(х). Теперь, если q1(x) - q2(x) <> 0, имеем deg((g1 - q2) • v) - deg(q1 - q2) + deg(u) >= deg(v) > deg(r2 — r1), т.е. получаем противоречие (так как из равенства (q1(x) - q2(x))v(x) = r2(х) — r1(х) следует deg((g1 — q2) * v) = deg(r1 — r2)). Значит, q1(x) - q2(x) = О и r1(х) = r2(х).

     Чтобы определить q(x) и r(х), можно использовать алгоритм для деления чисел с многократной точностью, только без переносов.

     Области единственного разложения на множители. Если мы ограничимся рассмотрением  полиномов над полем, то не охватим полиномы над множеством целых чисел и полиномы от нескольких переменных. Поэтому будем рассматривать более общую ситуацию, когда алгебраическая система коэффициентов S представляет собой область единственного разложения на множители и не обязана быть полем. Это означает, что S — коммутативное кольцо с единицей и что

     i) uv <> 0, если u и v — ненулевые элементы S;

     ii) каждый ненулевой элемент u, принадлежащий S, либо обратим, либо имеет "единственное" представление в виде произведения простых р1, .. , Pt

     u = p1...pt, t>l (2)

     Обратимый элемент в данном случае представляет собой элемент, который имеет  обратную величину, а именно—элемент и, такой, что uv = 1 для некоторого v принадлежащих S. Простой элемент — это не являющийся обратимым элемент р, такой, что уравнение р = qr истинно только тогда, когда либо q, либо r представляет собой обратимый элемент. Представление (2) единственно в том смысле, что если р1.. .pt = q1 . . qs, где все р и q просты, то s = t и имеется перестановка пх .  пt множества {1,..., t}, такая, что р1 = a1qп1, pt = atqпi для некоторых обратимых а1, ..., at. Другими словами, разложение на простые множители единственно с точностью до порядка множителей и до умножения на обратимые.