Класс 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 |
x¹ | 185 |
x² | 178 |
x³ | 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