От вас требуется реализовать класс Poly, используемый для представления многочленов и операций над ними. Реализация класса Poly должна работать с классом Fraction, поэтому в сдаваемом файле также должна быть реализация класса Fraction, полностью проходящая тестирование по предыдущему листку.
Полное описание класса Poly создается в Google docs в результате коллективного обсуждения.
Программа должна содержать реализацию класса Fraction, реализацию класса
Poly. После этого программа должна считывать данные со стандартного ввода
или из файла input.txt и исполнять считанные данные, как python-код, при помощи
функции exec. Пример:
exec(sys.stdin.read())
или
exec(open('input.txt').read())
Входные данные для программы содержат некоторый python-код, выводящий результат на стандартный вывод. Вывод вашей программы должен побайтово совпадать с выводом эталонной реализации.
Задание сдается на проверку в тестирующую систему в контест 295 как задача Poly.
По мере добавления функциональности в класс Poly новые задачи не создаются,
а в задачу Poly добавляются новые тесты. Каждый тест в задаче Poly
тестирует ту или иную часть выполнения спецификации класса Poly, а именно:
Тест 01: конструктор __init__
Тест 02: метод __str__
Тест 03: сложение многочленов и чисел.
Тест 04: вычитание многочленов и чисел.
Тест 05: умножение многочленов и чисел.
Тест 06: быстрое возведение многочлена в степень.
Тест 07: вычисление значения многочлена в точке.
Тест 08: деление многочленов с остатком.
Целью каждого теста является проверка полноты соответствия указанной части спецификации класса
Poly поставленной задаче. Тесты содержат подтесты, покрывающие, по возможности, все аспекты спецификации.
Программа проверяется на всех тестах. За каждый пройденный тест начисляется 1 балл, то есть количество набранных баллов
равно количеству пройденных тестов. Оценивается только последнее сданное решение. Не последние сданные решения могут
переводиться в статус Ignored.
Время от времени тесты могут модифицироваться, а именно:
Могут добавляться новые тесты, по мере добавления в спецификацию Poly новых методов.
Могут добавляться новые подтесты, для обеспечения полноты покрытия спецификации тестами.
Могут исправляться существующие тесты при обнаружении в них ошибок.
После изменения системы тестов проводится перетестирование решений всех школьников (возможно, только последних из сданных ими решений) на новой системе тестов. Это означает, что баллы могут понижаться (например, если были добавлены новые подтесты, на которых программа работает неверно).
Fraction + PolyДля этого необходимо, чтобы метод __add__ для
класса Fraction возвращал специальную константу
NotImplemented, тогда будет вызван метод
__radd__ для класса Poly.
Подробности смотрите ниже.
Методы
__iadd__ (оператор +=),
__isub__ (оператор -=),
__imul__ (оператор *=),
__ipow__ (оператор **=),
__ifloordiv__ (оператор //=),
__imod__ (оператор %=)
должны модифицировать значение левого операнда (к которому они применяются),
а не просто возвращать значение.
Вам нужно реализовать вычисление значения многочлена по схеме Горнера, тогда ответы будут совпадать.
Скорее всего это происходит из-за того, что функция divmod использует
другие функции работы с многочленами: вычитание, умножение и т.д. Из-за многократного
вызова других функций время работы многократно растет. Реализуйте функцию divmod так,
чтобы она работала только со списками коэффициентов на “низком” уровне, не вызывая
реализованные методы выполнения действий над многочленами.
__add__ и __radd__?При реализации операции сложения многие столкнулись с проблемой:
как реализовать операцию вида Fraction + Poly? Ведь в этом
случае будет вызываться метод __add__ для класса Fraction,
а не метод __radd__ для класса Poly.
Чтобы решить эту проблему, нужно понять, в каком порядке вызываются эти методы.
Пусть у нас есть два объекта A и B. Они могут
быть объектами как стандартных классов, так и классов, созданных пользователем.
Пусть в коде программы используется операция A + B. Что при этом происходит?
Сначала делается попытка вызова A.__add__(B). Если этот метод не определен
или этот метод вернет константу NotImplemented, то делается попытка вызова
B.__radd__(A). То есть константа NotImplemented как раз нужна
для того, чтобы сообщить о том, что объект A не может реализовать операцию
+ для объекта B.
В нашем случае класс Fraction является более фундаментальным классом,
нежели Poly. Класс Fraction вообще ничего не должен знать
о существовании класса Poly. При попытке сложения Fraction
и Poly класс Fraction должен сообщать, что он не умеет реализовывать
такое действие, т.к. для него класс Poly неизвестен.
Таким образом, класс Fraction должен содержать реализацию операций сложения
для стандартных типов: int, float и самого класса Fraction.
Во всех остальных случаях вызов метода __add__ должен возвращать NotImplemented.
Итак, правильная реализация метода __add__ для класса __fraction__ следующая:
class Fraction:
def __add__(self, other):
if type(other) == int:
# Возвращаем результат сложения Fraction + int
return ...
elif type(other) == float:
# Возвращаем результат сложения Fraction + float
return ...
elif type(other) == Fraction:
# Возвращаем результат сложения Fraction + Fraction
return ...
else:
# Возвращаем сообщение о том, что сложение для данного типа не реализовано
return NotImplemented
Для анализа производительности программы и поиска “тонких” мест в реализации можно использовать профайлер.
Самый простой способ запустить профайлер: запуск из командной строки
$ python3 -m Cprofile program.py
После завершения работы профайлер выведет на стандартный вывод статистику о числе вызовов функций и времени их исполнения. Для удобства вывод лучше перенаправить в файл.