Описание класса Poly

Класс Poly нужен для представления и работы с многочленами. Многочлен представляется в виде списков коэффициентов. Индекс коэффициента соответствует степени одночлена, которому он соответствует.

Коэффициенты многочлена могут быть одного из следующих типов: int, float, Fraction. Допускаются многочлены с коэффициентами смешанных типов.

Конструктор

Конструктор __init__ может принимать следующие аргументы:

1. Один аргумент типа int, float, Fraction. В этом случае создается многочлен степени 0 с одним коэффициентом.
2. Один аргумент типа список или кортеж коэффициентов (от младшего к старшему) многочлена типа int, float, Fraction. Конструктор должен создавать копию указанного списка (кортежа).
3. Строка, содержащая коэффициенты многочлена (от младшего к старшему) через пробел. При вводе объекта типа Fraction используется запись вида “Fraction(‘a/b’)” или “Fraction(a,b)”, без пробелов внутри. Пример: “0 1 Fraction(‘1/2’)” задает многочлен (1/2)x2 + x.
4. Многочлен (объект класса Poly). Конструктор должен создавать копию списка коэффициентов.
5. Без аргументов (Poly()). В таком случае создается многочлен степени 0 с единственным коэффициентом 0.

Метод __str__

Выводит представление многочлена.

1. Одночлены в многочлене записываются от старшего к младшему с переменной x через знаки «+» и «-».
2. Одночлены, коэффициент при которых равен 0, пропускаются.
3. Между коэффициентом и переменной знаков нет, например: 2x.
4. Степень многочлена записывается в верхнем регистре, соответствующими символами Unicode (см. таблицу ниже), например, x10.
5. Если коэффициент отрицательный, то вместо знака «+» перед слагаемым пишется «-».
6. Пробелы ставятся только вокруг знаков «+» и «-», но если коэффициент перед старшим членом отрицательный, то между знаком и модулем коэффициента пробела нет.
7. Свободный  член записывается без x0, вместо x1 записывается x.
8. Коэффициент типа Fraction записывается в скобках через «/», знак не в скобках, например: - (3/2)x5. Если коэффициент имеет тип Fraction, но является целым числом, то он выводится как int, то есть без скобок.
9. Коэффициенты, равные по модулю 1, не пишутся, например: - x2. Исключением является свободный член, он пишется и в том случае, когда равен 1.
10. Если коэффициент имеет тип float, то округляется до 3 знаков после запятой, например: - 0.333x.
11. Если все коэффициенты многочлена равны 0, то он выводится в виде строки из одного символа “0”.

Таблица символов степеней:

Сложение объектов класса Poly

Необходимо реализовать все методы сложения и вычитания многочленов, сложение и вычитание многочленов и чисел.

1. Сложение двух объектов класса Poly. Возвращает объект класса Poly.
2. Сложение Poly и числа типа int, float или Fraction. Возвращает объект класса Poly.

Должны быть определены операторы “+” для операндов типа Poly, int, float, Fraction, при этом хотя бы один операнд имеет тип Poly.

Должен быть определен оператор “+=” для левого операнда типа Poly, правого операнда типа Poly, int, float, Fraction.

Вычитание объектов класса Poly

Необходимо реализовать все методы вычитания многочленов, умножение многочленов и чисел.

Должны быть определены операторы “-” для операндов типа Poly, int, float, Fraction, при этом хотя бы один операнд имеет тип Poly.

Должен быть определен оператор “-=” для левого операнда типа Poly, правого операнда типа Poly, int, float, Fraction.

Умножение объектов класса Poly

Необходимо реализовать все методы умножения многочленов, умножение многочленов и чисел.

1. Умножение двух объектов класса Poly. Возвращает объект класса Poly.
2. Умножение Poly и числа типа int, float или Fraction. Возвращает объект класса Poly.

Должны быть определены операторы “*” для операндов типа Poly, int, float, Fraction, при этом хотя бы один операнд имеет тип Poly.

Должен быть определен оператор “*=” для левого операнда типа Poly, правого операнда типа Poly, int, float, Fraction.

Деление объектов класса Poly

Необходимо реализовать деление многочленов с остатком. Операция деления многочленов с остатком работает только для многочленов с коэффициентами типа int и Fraction (оба многочлена, и делимое, и делитель должны иметь целочисленные или рациональные коэффициенты). Действительные числа в качестве коэффициентов многочленов пока не рассматриваются.

Пусть даны два многочлена A и B. При делении многочлена A на многочлен B получается два многочлена Q (частное) и R (остаток) такие, что A = Q * B + R, при этом deg(R) < deg(B). Для нахождения частного и остатка используется алгоритм деления “в столбик”.

Необходимо реализовать:

метод __divmod__(self, other) - возвращает кортеж из двух элементов: частного и остатка. Для вызова используется divmod(a, b).

метод __rdivmod__(self, other)

Должны быть определены операторы “//” и “%” для операндов типа Poly, int, float, Fraction, при этом хотя бы один операнд имеет тип Poly.

Должен быть определен операторы “//=”  и “%=” для левого операнда типа Poly, правого операнда типа Poly, int, float, Fraction.

Возведение в степень

Необходимо реализовать алгоритм быстрого возведения многочлена в степень. Показатель степени - целое неотрицательное число.

Должен быть определены операторы “**” для левого операнда типа Poly, правого операнда типа int (при этом неотрицательное).

Должен быть определен оператор “**=” для левого операнда типа Poly, правого операнда типа int.

Вычисление значение многочлена в точке

Необходимо реализовать функцию вычисления значения выражения в точке x. Если P - объект класса Poly, x - объект типа int, float, Fraction, то вычисление многочлена в точке x производится при помощи перегруженной операции P | x.

Для перегрузки операции P | x нужно определить метод __or__ класса Poly. Левый операнд имеет тип Poly, правый операнд: тип int, float, Fraction.

Значение многочлена в точке должно вычисляться по схеме Горнера.

Определение длины многочлена и доступ к коэффициентам

Необходимо реализовать функцию определение длины многочлена len(P) и возможности чтения и изменения коэффициентов по индексу P[i].

Для определения длины объекта необходимо определить метод __len__(self). Данный метод должен возвращать длину списка коэффициентов, т.е. степень многочлена + 1.

Для возможности чтения значения коэффициента многочлена P[i] необходимо определить метод P.__getitem__(self, i). Если значение i некорректно, необходимо генерировать исключение IndexError при помощи инструкции raise IndexError(). Исключение IndexError необходимо генерировать и в случае, когда i < 0.

Для возможности присваивания коэффициенту многочлена нового значения val необходимо определить метод P.__setitem__(self, i, val). При этом если i >= len(P) необходимо “расширить” список коэффициентов до нужного значения, при i < 0 необходимо генерировать исключение IndexError.

Композиция многочленов

Необходимо реализовать операцию композиции многочленов: если P и Q - объекты класса Poly, то P(Q) должно возвращать объект класса Poly, являющийся композицией многочленов.

Для этого необходимо перегрузить определить метод __call__(self, x). Если P - объект класса Poly, то при использовании объекта P, как вызова функции P(x) будет вызван метод P.__call__(x).

Метод P.__call__(x) должен возвращать значение многочлена в точке x, если x является объектом классов int, float, Fraction, если x является объектом класса Poly, то метод __call__ должен возвращать композицию многочленов.