Реализация класса Fraction рациональных чисел

В этом листке мы реализуем класс рациональных чисел подобно тому, что уже есть в стандартной библиотеке питона. Только мы реализуем не все его возможности, а достаточную для разумной работы часть. Тем самым мы научимся перегружать часть возможных операторов. А после этого прикрутим к нашим рациональным числам новые фичи.

Итак, рациональное число. Очевидно, что внутри нужно хранить целые числа — числитель и знаменатель. Это будут внутренние атрибуты. Чтобы перегрузить стандартные операторы, нужно определить внутри класса «волшебные» (magic) функции (вернее, методы). Они все имеют вид __ZZZZ__, то есть окружены двойными подчёркиваниями. Все встроенные в питон методы с таким именем — «волшебные», они используются при арифметических операциях, сравнениях, приведении типов, итерации и т.д. Ничего не мешает создать атрибут или метод с подобным именем, только он уже не будет «волшебным». Поэтому использовать такие имена не принято.

Вычитание: __sub__, __rsub__ и __isub__, в чём разница?

Оказывается, для переопределения вычитания есть целых три магических метода: __sub__, __rsub__ и __isub__. Работает это следующим образом.

Для удобства введём обозначение: fr, fr1, fr2 — это будут рациональные числа, экземпляры нашего нового класса Fraction. Переменные m, n и т.п. — это строго целые числа. Пусть у нас есть такой код:

class Fraction:
    ...
    def __sub__(self, other):
        ...
    def __rsub__(self, other):
        ...

fr1 = Fraction(1, 3)
fr2 = Fraction(3, 4)
n = 5
fr3 = fr1 - fr2  # На самом деле fr3 = Fraction.__sub__(fr1, fr2)
fr4 = fr1 - n    # На самом деле fr4 = Fraction.__sub__(fr1, n)
fr5 = n - fr2    # На самом деле fr5 = Fraction.__rsub__(fr2, n)

Строка fr1 - fr2 на самом деле превращается в сначала в fr1.__sub__(fr2), а затем — в Fraction.__sub__(fr1, fr2).
Строка fr1 - n сначала превращается в fr1.__sub__(n), а затем — в Fraction.__sub__(fr1, n). Здесь вроде бы никаких отличий, только вторым параметром в метод __sub__ придёт целое цисло, а не рациональное.
А вот с n - fr2 более хитрая магия. Подобно прошлому разу это превращается в n.__sub__(fr2). Тип переменной n — это int, поэтому дальше это превращается в int.__sub__(fr1, n). Но тот метод __sub__, что реализован для целых чисел, ничего не знает про наши новые рациональные. Он не знает, где там числитель и знаменатель, и даже не знает, что эта штука вообще по смыслу число. Поэтому вместо разности возвращается специальная константа NotImplemented. В этом случае питон понимает, что левый операнд (целое число) не умеет вычитать из себя правый операнд (рациональное). Тогда он обращается ко второму операнду: «Эй, вычти себя из целого, он говорит, что сам не умеет». В результате происходит вызов fr2.__rsub__(n), который в свою очередь превращается в Fraction.__rsub__(fr2, n).

То есть если целые числа не умеют вычитать из себя наши новые рациональные (а они, конечно же не умеют, откуда им?), то мы сами должны научить наши новые рациональные числа вычитать себя из целых (и из любых других типов, если нам это надо). И это самое «научить» реализуется в магических __rZZZ__ методах.

А с __isub__ всё гораздо проще. Этот метод вызывается, когда мы пишем fr1 -= n. Если этот метод в классе не реализован, то код fr1 -= n интерпретируется просто как fr1 = fr1 - n, то есть используя «обычный» __sub__.

Список операторов, которые мы перегрузим в этом листке

Полный список волшенбных методов можно найти в документации (их довольно много на все случаи жизни): http://docs.python .org/py3k/reference/datamodel.html.

Далее идут только те методы, которые нам в этом листке понадобятся. Для удобства введём обозначение: fr — это рациональные числа, экземпляры нашего нового класса Fraction. Переменные n — это строго целые числа.

Большой и сложный пример для вдумчивого исследования

Очень рекомендуется пройти эту программу по шагам в режиме отладки, чтобы увидеть, как и что происходит.

def obj_printer(obj, show_value=True):
    return '<{} object at {} with value {}>'.format(obj.__class__.__name__, hex(id(obj)), repr(obj) if type(obj) != DummyNumbers else obj.value if show_value else '?')

class DummyNumbers():
    """Класс для демонстрации возможностей классов
    """
    print("Эта строка будет выведена раньше всех: здесь Python начал читать, как устроен этот класс")
    def __init__(self, some_value=0):
        print("Запущен конструктор. Переданы парамеры: self={} и some_value={}".format(obj_printer(self, False), obj_printer(some_value)))
        self.value = some_value

    def __repr__(self):
        print("Запущен медот __repr__. Передан self={}".format(obj_printer(self)))
        return 'DummyNumbers({})'.format(self.value)

    def __str__(self):
        print("Запущен медот __str__. Передан self={}".format(obj_printer(self)))
        return 'Дурацкое число: {}'.format(self.value)

    def __sub__(self, other):
        print("Запущен метод __sub__ с параметрами self={}, other={}. "
              "Здесь self гарантированно является экземпляром DummyNumbers, "
              "а other может быть любым объектом.".format(obj_printer(self), obj_printer(other)))
        print("Хотят self - other")
        if type(other) in (int, float):
            return DummyNumbers(self.value - other)
        elif isinstance(other, DummyNumbers):
            return DummyNumbers(self.value - other.value)
        else:
            print("Мы сами не знаем, как вычесть такой объект")
            return NotImplemented

    def __rsub__(self, other):
        print("Запущен метод __rsub__ с параметрами self={}, other={}. "
              "Здесь self гарантированно является экземпляром DummyNumbers, "
              "а other может быть любым объектом. При этом мы из other вычитаем self".format(obj_printer(self), obj_printer(other)))
        print("Хотят other - self, но класс other не знает, как вычесть self")
        if type(other) in (int, float):
            return DummyNumbers(other - self.value)
        else:
            print("Мы сами не знаем, как можно вычитать из такого объекта")
            return NotImplemented

    def __isub__(self, other):
        print("Запущен метод __isub__ с параметрами self={}, other={}. "
              "Здесь self гарантированно является экземпляром DummyNumbers, "
              "а other может быть любым объектом.".format(obj_printer(self), obj_printer(other)))
        print("Хотят из self вычесть other и положить в self")
        if type(other) in (int, float):
            self.value -= other
            return self
        elif isinstance(other, DummyNumbers):
            self.value -= other.value
            return self
        else:
            print("Мы сами не знаем, как из себя вычесть такой объект")
            return NotImplemented

print('\n' * 2, 'a = DummyNumbers()')
a = DummyNumbers()

print('\n' * 2, 'b = DummyNumbers(3)')
b = DummyNumbers(0)

print('\n' * 2, 'c = DummyNumbers(3)')
c = DummyNumbers(3.3)

print('\n' * 2, 'd = a - b')
d = a - b

print('\n' * 2, 'e = b - 5')
e = b - 5

print('\n' * 2, 'f = 3.3 - c')
f = 3.3 - c

print('\n' * 2, 'c -= b')
c -= b

print('\n' * 2, 'd -= 1.79')
d -= 1.79

print('\n' * 2, 'q = 7, q -= b')
q = 7
q -= b

print('\n' * 2, 'print(a, b, c, d, e, f)')
print(a, b, c, d, e, f)

print('\n' * 2, "g = 'a' - a")
try:
    g = 'a' - a
except TypeError as e:
    print(e)

print('\n' * 2, "g = a - 'b'")
try:
    g = a - 'b'
except TypeError as e:
    print(e)

print('\n' * 2, "a -= 'q'")
try:
    a -= 'q'
except TypeError as e:
    print(e)

print('\n' * 2, "q = 'q', q -= a")
try:
    q = 'q'
    q -= a
except TypeError as e:
    print(e)

Ввод-вывод и тестирование

Во всех задачах на доработку методов класса тестирование производится следующим образом: вашей программе на вход передаётся тест, состоящий из последовательность питоновских команд, который нужно исполнить при помощи функции exec. Сделать это удобнее всего одним из двух способов:

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

import sys
exec(sys.stdin.read())

или

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

exec(open('input.txt').read())

В первом случае ввод производится с клавиатуры (не забудьте про Ctrl+D для завершения ввода), но плохо работает отладка (debug). Во втором случае ввод производится из файла.

В задачах A-F каждая следующая задача содержит тесты всех предыдущих.

Используем реализацию рациональных чисел для решения задач

В следующих задачах используйте вашу реализацию рациональных чисел.

Цепные дроби

Определение: цепная (или непрерывная) дробь (continued fraction)— это конечное или бесконечное выражение вида: $$[a_0;a_1,a_2,\dots]=a_0+\dfrac{1}{a_1+\dfrac{1}{a_2+\dfrac{1}{a_3+\dots}}}$$ где $a_0$ — целое число, остальные $a_i$ — натуральные числа, причём если дробь конечная, то последнее значение отлично от единицы. Число представляется конечной цепной дробью тогда и только тогда, когда оно рационально.

Декоратор @staticmethod для методов, которым не нужен экземпляр класса

Сейчас мы добавим нашим дробям возможность превращения в цепную или периодическую десятичную дробь и обратно. Начнём с конструирования рационального числа из цепной дроби.

Добавим метод from_continued в класс Fraction, который по массиву или кортежу целых чисел — элементов цепной дроби — будет создавать дробь. Работать это должно так:

class Fraction:
    ...
    def from_continued(terms):
        ...
        return Fraction(p, q)

x = Fraction.from_continued([1, 1, 2])  # 5/3
y = Fraction.from_continued([0, 2, 4, 8, 16])  # 532/1193

Обратите внимание, здесь внутри метода from_continued нам не нужен self — экземпляр класса. При вызове как в примере выше он и не будет передан. Но этот метод можно вызвать и так:

>>> x = Fraction(1, 2)
>>> y = x.from_continued([1, 1, 2])
TypeError: from_continued() takes 1 positional argument but 2 were given

Нужно дать знать питону, что экземпляр класса нам никогда не потребуется. Для этого перед определением метода нужно добавить декоратор @staticmethod. Вот так:

class Fraction:
    ...
    @staticmethod
    def from_continued(terms):
        ...
        return Fraction(p, q)

class Fraction:
    ...
    @classmethod
    def from_continued(cls, terms):
        ...
        return cls(p, q)