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

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

01. Конструктор и 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))

02. Конструктор — 2

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

  • Без аргументов (Poly()). В таком случае создается многочлен степени 0 с единственным коэффициентом 0.
  • Один аргумент типа int, float. В этом случае создается многочлен степени 0 с одним коэффициентом;
  • Один аргумент — итерируемый объект, возвращающий элементы типа int, float (например, список, кортеж, range, map и т.п. ). При этом нулевые старшие коэффициенты обрезаются. Проверить, что объект является итерируемым, можно при помощи hasattr(объект, '__iter__');

ВВОД:
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))

03. Конструктор — 3

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

  • Один аргумент типа int, float. В этом случае создается многочлен степени 0 с одним коэффициентом;
  • Строка, содержащая коэффициенты многочлена типа int, float (от младшего к старшему) через пробел;
  • Многочлен (объект класса Poly). Конструктор должен создавать копию списка коэффициентов.
  • Один аргумент — итерируемый объект, возвращающий элементы типа int, float (например, список, кортеж, range, map и т.п. ). Проверить, что объект является итерируемым, можно при помощи hasattr(объект, '__iter__');
  • Без аргументов (Poly()). В таком случае создается многочлен степени 0 с единственным коэффициентом 0.

ВВОД:
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

04. __str__

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

  • Одночлены в многочлене записываются от старшего к младшему с переменной x через знаки «+» и «-».
  • Одночлены, коэффициент при которых равен 0, пропускаются.
  • Между коэффициентом и переменной знаков нет, например: 2x.
  • Степень многочлена записывается в верхнем регистре, соответствующими символами Unicode (см. таблицу ниже), например, x¹⁰.
  • Если коэффициент отрицательный, то вместо знака «+» перед слагаемым пишется «-».
  • Пробелы ставятся только вокруг знаков «+» и «-», но если коэффициент перед старшим членом отрицательный, то между знаком и модулем коэффициента пробела нет.
  • Свободный член записывается без x⁰, вместо x¹ записывается x.
  • Коэффициенты, равные по модулю 1, не пишутся, например: - x². Исключением является свободный член, он пишется и в том случае, когда равен 1.
  • Если коэффициент имеет тип float, то округляется до 3 знаков после запятой, например: - 0.333x.
  • Если все коэффициенты многочлена равны 0, то он выводится в виде строки из одного символа “0”.

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

Символ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='')
Единственное ограничение: у вашего многочлена не должно быть ведущих нулей (кроме последнего), иначе метод будет работать неправильно.

05. Равенство, неравенство, __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

06. Сложение многочленов

Реализуйте методы для сложения многочленов друг с другом, а также с числами типа 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

07. Вычитание многочленов

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

ВВОД:
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

08. Умножение многочленов

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

ВВОД:
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

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

Реализуйте методы для быстрого возведения в степень. Показатель степени - целое неотрицательное число. Должен быть определены операторы “**” для левого операнда типа 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

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

Реализуйте функцию вычисления значения выражения в точке 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

11. Итератор по коэффициентам

Реализуйте метод-генератор __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

12. Добавление поддержки класса 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

13. Деление многочленов с остатком: 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)

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

Необходимо реализовать:
метод __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)

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

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

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

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

17. Рациональные корни многочлена

Реализуйте метод 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]

18. Алгоритм Евклида

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

ВВОД:
print(pgcd((X + 1)**10, (X + 1) * (X + 2)**2))
ВЫВОД
x + 1