Класс Poly многочленов

В этом листке мы будем реализовывать класс многочленов Poly, используемый для представления многочленов и операций над ними. Как и в прошлом листке, при сдаче в тестирующую программу необходимо добавить после описания класса строку exec(open('input.txt').read()).

A: Конструктор и repr

Создайте новый класс Poly с единственным атрибутом: _coeff — списком коэффициентов многочлена.
Конструктор __init__ на данном этапе может принимать только список чисел типов int или float.

Метод __repr__ должен возвращать строку, из которой можно создать в точности такой-же многочлен. При этом нулевые старшие коэффициенты должны быть обрезаны (кроме многочлена нулевого многочлена).

Добавьте также константу X — многочлен Poly([0, 1]).

print(repr(Poly([1, 2, 3]))) print(repr(Poly([1, 2.34, 4.56, 7]))) print(repr(X))
Poly([1, 2, 3]) Poly([1, 2.34, 4.56, 7]) Poly([0, 1])
IDE

B: Конструктор — 2

Доработайте конструктор __init__ так, чтобы он мог принимать следующие типы аргументов:

print(repr(Poly())) print(repr(Poly(1))) print(repr(Poly(1.23))) print(repr(Poly((1, 2.34, 4.56, 7, 0)))) print(repr(Poly([1, 2.34, 4.56, 7, 0, 0, 0]))) print(repr(Poly(range(10)))) print(repr(Poly(map(lambda x: x ** 4, range(5))))) print(repr(Poly(map(int, '1 2 3'.split()))))
Poly([0]) Poly([1]) Poly([1.23]) Poly([1, 2.34, 4.56, 7]) Poly([1, 2.34, 4.56, 7]) Poly([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]) Poly([0, 1, 16, 81, 256]) Poly([1, 2, 3])
IDE

C: Конструктор — 3

Доработайте конструктор __init__ так, чтобы он мог принимать следующие типы аргументов:

print(repr(Poly('1'))) print(repr(Poly('1 2 3'))) print(repr(Poly('1 2.34 5.67 0'))) A = Poly('1 2.34 5.67 0') B = Poly(A) print(A is B) print(A._coeff is B._coeff) print(A._coeff == B._coeff)
Poly([1]) Poly([1, 2, 3]) Poly([1, 2.34, 5.67]) False False True
IDE

D: __str__

Реализуйте метод __str__, который будет выводить удобное для человека представление многочлена:

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

СимволUnicode-код, в десятичной системе
x⁰8304
185
178
179
x⁴-x⁹8308-8313
print(Poly(range(11))) print(Poly([1.2345, 0.0001, -1])) print(Poly([1, 0, 1, 0, -1, 0, 1]))
10x¹⁰ + 9x⁹ + 8x⁸ + 7x⁷ + 6x⁶ + 5x⁵ + 4x⁴ + 3x³ + 2x² + x
-x² + 0.0x + 1.234
x⁶ - x⁴ + x² + 1
Подсказка
Да, мне кажется, что я уже достаточно думал над этой задачей
Чес-слово! :)

Нужно реализовать функцию, которая по степени и коэффициенту выведет строковое представление монома данной степени. Для хранения юникод-символов можно использовать словарь {'0': chr(8304), ...}. Далее создать список строковых представлений мономов. У старшего коэффициента поправить знак (убрать + и побел перед минусом). После чего склеить вместе.

Я не могу решить эту задачу
Я вообще не понимаю этого и не хочу задавать вопросы
Но я попробую к ней вернуться, честно!

Просто игнорируйте её и решайте дальше, начиная с 5-й задачи. В качестве __str__ следующий код:

    def __str__(e):
        return (lambda f, g, i, j, l: (lambda k: '0' if f(k) == 1 and k[0] == 0 else (lambda b: ((lambda a: ((l if a.startswith(' + ') else '-') + a[3:]))(b(f(k) - 1, k[-1])) + l.join(b(h, k[h]) for h in range(f(k) - 2, -1, -1))))(((lambda a, b: (l if b == 0 else (' + ' if b.real >= 0 else ' - ') + (l if g(b) == 1 and a > 0 else i(j(g(b), 3)) if type(b) == float else i(g(b))) + (l if a == 0 else 'x' if a == 1 else 'x' + l.join({'0': chr(8304), '1': chr(185), '2': chr(178), '3': chr(179), '4': chr(8308), '5': chr(8309), '6': chr(8310), '7': chr(8311), '8': chr(8312), '9': chr(8313)}[s] for s in i(a))))))))(e._coeff))(f=len, g=abs, i=str, j=round, l='')

Единственное ограничение: у вашего многочлена не должно быть ведущих нулей (кроме последнего), иначе метод будет работать неправильно.

IDE

E: Равенство, неравенство, __neg__, __pos__, __bool__

Реализуйте методы __eq__, __ne__, __neg__, __pos__ и __bool__. Метод __neg__ должен возвращать новый многочлен, равный минус текущему. Метод __pos__ должен возвращать self. Метод __bool__ должен возвращать False только для многочлена, равного нулю.

A = Poly(range(5)) B = Poly([0, 1, 2, 3, 4]) C = Poly(range(4)) print(+A) print(-A) print((+A) is A) print(-A is A) print(A == B) print(A == C) print(A != B) print(A != C) print(Poly(3) == 3)
4x⁴ + 3x³ + 2x² + x -4x⁴ - 3x³ - 2x² - x True False True False False True True
IDE

F: Сложение многочленов

Реализуйте методы для сложения многочленов друг с другом, а также с числами типа int и float. Кроме __add__ и __radd__ необходимо также реализовать метод __iadd__, который используется в выражениях (A += 2). Метод __iadd__ должен модифицировать собственный набор коэффициентов и возвращать self. В классе комплексных чисел мы не стали реализовывать этот метод, так как комплексные числа неизменяемы, при операции A += 2 в A попадает уже новое комплексное число.

Совет

Постарайтесь уменьшить дублирование кода. Например, можно реализовать метод __iadd__, а в методах __add__ и __radd__ его вызывать (используя += или прямо .__iadd__()). При ловком исполнении __add__, __radd__, __isub__, __sub__, __rsub__, __mul__, __rmul__ делаются используя эту идею за одну строчку (без маразма, лямбда функций и т.п.).

A = Poly(range(5)) B = Poly([1.23, 2.34, 0, -5]) C = Poly([0, 0, 0, 0, 0, 0, 2]) print(A + B) print(A + C) print(B + C) print(A + (-A)) print(A + B + C) print(3 + A) print(A + 3) print(2.1 + B) print(B + 2.1) A += 1 B += 1.23 D = C C += B + A print(C) print(D) print(C is D)
4x⁴ - 2x³ + 2x² + 3.34x + 1.23 2x⁶ + 4x⁴ + 3x³ + 2x² + x 2x⁶ - 5x³ + 2.34x + 1.23 0 2x⁶ + 4x⁴ - 2x³ + 2x² + 3.34x + 1.23 4x⁴ + 3x³ + 2x² + x + 3 4x⁴ + 3x³ + 2x² + x + 3 -5x³ + 2.34x + 3.33 -5x³ + 2.34x + 3.33 2x⁶ + 4x⁴ - 2x³ + 2x² + 3.34x + 3.46 2x⁶ + 4x⁴ - 2x³ + 2x² + 3.34x + 3.46 True
IDE

G: Вычитание многочленов

Реализуйте методы для вычитания многочленов и чисел.

A = Poly(range(5)) B = Poly([1.23, 2.34, 0, -5]) C = Poly([0, 0, 0, 0, 0, 0, 2]) print(A - B) print(A - C) print(B - C) print(A - (+A)) print(A - B + C) print(3 - A) print(A - 3) print(2.1 - B) print(B - 2.1) A -= 1 B -= 1.23 D = C C -= B - A print(C) print(D) print(C is D)
4x⁴ + 8x³ + 2x² - 1.34x - 1.23 -2x⁶ + 4x⁴ + 3x³ + 2x² + x -2x⁶ - 5x³ + 2.34x + 1.23 0 2x⁶ + 4x⁴ + 8x³ + 2x² - 1.34x - 1.23 -4x⁴ - 3x³ - 2x² - x + 3 4x⁴ + 3x³ + 2x² + x - 3 5x³ - 2.34x + 0.87 -5x³ + 2.34x - 0.87 2x⁶ + 4x⁴ + 8x³ + 2x² - 1.34x - 1.0 2x⁶ + 4x⁴ + 8x³ + 2x² - 1.34x - 1.0 True
IDE

H: Умножение многочленов

Реализуйте методы для умножения многочленов и чисел.

A = Poly(range(5)) B = Poly([1.23, 2.34, 0, -5]) C = Poly([0, 0, 0, 0, 0, 0, 2]) print(A * B) print(A * C) print(B * C) print(A * (+A)) print(A * B * C) print(3 * A) print(A * 3) print(2.1 * B) print(B * 2.1) A *= 1 B *= 1.23 D = C C *= B * A print(C) print(D) print(C is D) print( 7 * X*X*X*X*X*X*X*X*X*X - 3 * X*X*X*X*X + (X - 3) * (2 - X * 5 * X) )
-20x⁷ - 15x⁶ - 0.64x⁵ + 6.94x⁴ + 8.37x³ + 4.8x² + 1.23x 8x¹⁰ + 6x⁹ + 4x⁸ + 2x⁷ -10x⁹ + 4.68x⁷ + 2.46x⁶ 16x⁸ + 24x⁷ + 25x⁶ + 20x⁵ + 10x⁴ + 4x³ + x² -40x¹³ - 30x¹² - 1.28x¹¹ + 13.88x¹⁰ + 16.74x⁹ + 9.6x⁸ + 2.46x⁷ 12x⁴ + 9x³ + 6x² + 3x 12x⁴ + 9x³ + 6x² + 3x -10.5x³ + 4.914x + 2.583 -10.5x³ + 4.914x + 2.583 -49.2x¹³ - 36.9x¹² - 1.574x¹¹ + 17.072x¹⁰ + 20.59x⁹ + 11.808x⁸ + 3.026x⁷ -49.2x¹³ - 36.9x¹² - 1.574x¹¹ + 17.072x¹⁰ + 20.59x⁹ + 11.808x⁸ + 3.026x⁷ True 7x¹⁰ - 3x⁵ - 5x³ + 15x² + 2x - 6
IDE

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

Реализуйте методы для быстрого возведения в степень. Показатель степени - целое неотрицательное число. Должен быть определены операторы “**” для левого операнда типа Poly, правого операнда типа int (при этом неотрицательное). Должен быть определен оператор “**=” для левого операнда типа Poly, правого операнда типа int.

A = Poly([1, 1]) B = Poly([2]) C = Poly([1, 0, 0, 0, 0, 0, 0, 0, 2.34, 0, 0, 0, -2]) print(A ** 0) print(A ** 1) print(A ** 2) print(A ** 10) print(B ** 100) print(C ** 3) D = C C **= 3 print(C) print(D) print(C is D) print( 7 * X**10 - 3 * X**5 + (X - 3) * (2 - 5 * X**2) )
1 x + 1 x² + 2x + 1 x¹⁰ + 10x⁹ + 45x⁸ + 120x⁷ + 210x⁶ + 252x⁵ + 210x⁴ + 120x³ + 45x² + 10x + 1 1267650600228229401496703205376 -8x³⁶ + 28.08x³² - 32.854x²⁸ + 24.813x²⁴ - 28.08x²⁰ + 16.427x¹⁶ - 6.0x¹² + 7.02x⁸ + 1 -8x³⁶ + 28.08x³² - 32.854x²⁸ + 24.813x²⁴ - 28.08x²⁰ + 16.427x¹⁶ - 6.0x¹² + 7.02x⁸ + 1 -8x³⁶ + 28.08x³² - 32.854x²⁸ + 24.813x²⁴ - 28.08x²⁰ + 16.427x¹⁶ - 6.0x¹² + 7.02x⁸ + 1 True 7x¹⁰ - 3x⁵ - 5x³ + 15x² + 2x - 6
IDE

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

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

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

A = Poly(range(5)) B = Poly([1, 1]) ** 10 print(A | 1) print(A | -1.0) print(B | 0) print(B | 1) print(B | -1)
10 2.0 1 1024 0
IDE

K: Итератор по коэффициентам

Реализуйте метод-генератор __iter__, по очереди выдающий все коэффициенты, начиная с нулевого.

A = Poly(range(10)) print([x ** 2 for x in A]) print(*A)
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81] 0 1 2 3 4 5 6 7 8 9
IDE

L: Добавление поддержки класса Fraction

Добавьте во все методы поддержку класса Fraction.
В методе __str__ выводите дроби со знаменателем, не равным 1 в скобках (3/4). Дроби, со знаменателем, равным 1 выводите как целое.

A = Poly((1, 1.2, Fraction(5, -2), 0, Fraction('-1.2'))) B = A ** 2 - 2 * A print(A) print(B)
-(6/5)x⁴ - (5/2)x² + 1.2x + 1 (36/25)x⁸ + 6x⁶ - 2.88x⁵ + 6.25x⁴ - 6.0x³ + 1.44x² - 1
IDE

M: Деление многочленов с остатком: divmod

Реализуйте деление многочленов с остатком.
Пусть даны два многочлена A и B. При делении многочлена A на многочлен B получается два многочлена Q (частное) и R (остаток) такие, что A = Q * B + R, при этом deg(R) < deg(B). Для нахождения частного и остатка используется алгоритм деления “в столбик”.
Необходимо реализовать метод __divmod__(self, other) - возвращает кортеж из двух элементов: частного и остатка. Для вызова используется divmod(a, b).
Если в процессе деления возникает деление целого числа на целое, то результат деления должен иметь тип Fraction.

A = Poly([1, 1]) ** 5 B = Poly([1, 1]) C = Poly([1, -1, 1]) print('({}) = ({}) * ({}) + ({})'.format(A, B, *divmod(A, B))) print('({}) = ({}) * ({}) + ({})'.format(A, C, *divmod(A, C))) print('({}) = ({}) * ({}) + ({})'.format(B, A, *divmod(B, A))) print('({}) = ({}) * ({}) + ({})'.format(B, 2, *divmod(B, 2)))
(x⁵ + 5x⁴ + 10x³ + 10x² + 5x + 1) = (x + 1) * (x⁴ + 4x³ + 6x² + 4x + 1) + (0) (x⁵ + 5x⁴ + 10x³ + 10x² + 5x + 1) = (x² - x + 1) * (x³ + 6x² + 15x + 19) + (9x - 18) (x + 1) = (x⁵ + 5x⁴ + 10x³ + 10x² + 5x + 1) * (0) + (x + 1) (x + 1) = (2) * ((1/2)x + (1/2)) + (0)
IDE

N: Деление многочленов с остатком: всё остальное

Необходимо реализовать:
метод __divmod__(self, other) - возвращает кортеж из двух элементов: частного и остатка. Для вызова используется divmod(a, b).
метод __rdivmod__(self, other) - вызывается при делении числа на многочлен.
Должны быть определены операторы “//” и “%” для операндов типа Poly, int, float, Fraction при этом хотя бы один операнд имеет тип Poly. Должен быть определен операторы “//=” и “%=” для левого операнда типа Poly, правого операнда типа Poly, int, float, Fraction.

A = Poly([1, 1]) ** 5 B = Poly([1, 1]) C = Poly([1, -1, 1]) print(A // B) print(B // A) print(A % C) print(C % A) A //= B print(A) A %= C print(A) print('({}) = ({}) * ({}) + ({})'.format(2, A, *divmod(2, A)))
x⁴ + 4x³ + 6x² + 4x + 1 0 9x - 18 x² - x + 1 x⁴ + 4x³ + 6x² + 4x + 1 9x - 9 (2) = (9x - 9) * (0) + (2)
IDE

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

Необходимо реализовать функцию определение длины многочлена 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.

A = Poly([1, 1]) ** 20 print(len(A)) print(A[0], A[1], A[2], A[10]) print(A[100])
21 1 20 190 184756 0
IDE

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

Необходимо реализовать операцию композиции многочленов: если 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__ должен возвращать композицию многочленов.

A = Poly([1, 1]) B = A(A) print(B) print((A**2)(A**2)) print((A**10)(1))
x + 2 x⁴ + 4x³ + 8x² + 8x + 4 1024
IDE

Q: Рациональные корни многочлена

Реализуйте метод rational_roots, возвращающий упорядоченный по возрастанию список всех рациональных корней ненулевого многочлена. Если какой-либо коэффициент имеет тип, отличный от int, Fraction, то необходимо взвести ошибку TypeError().

print(((X - 1) * (X - Fraction(3, 7)) * (X ** 2 + 2 * X + 2)).rational_roots()) print(Poly((Fraction(9, 49), Fraction(-60, 49), Fraction(142, 49), Fraction(-20, 7), 1)).rational_roots())
[Fraction(3, 7), 1] [Fraction(3, 7), Fraction(3, 7), 1, 1]
IDE

R: Алгоритм Евклида

Реализуйте функцию pgcd(a, b), возвращающую НОД двух многочленов. Старший коэффициент НОДа должен быть равен 1. Если какой-либо коэффициент имеет тип, отличный от int, Fraction, то необходимо взвести ошибку TypeError().

print(pgcd((X + 1)**10, (X + 1) * (X + 2)**2))
x + 1
IDE