Арифметика многочленов

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

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

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

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

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

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

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

Таким образом, с учетом вышеизложенного, рекомендуется следующая структура хранения полиномов. Полиномы упорядочиваются по убыванию степеней мономов. Для определения старшинства мономов вводится следующее правило. Во-первых, фиксируется старшинство переменных. Будем считать, что x - самая старшая переменная, затем следует y, затем z. Для каждого монома определим его "свернутую степень" (индекс). Для монома x^A y^B z^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 рассматриваются как равные нулю при

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать