Практика 8

Введение в абстракцию данных

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

В книге SICP интерфейсом между двумя частями системы служит набор процедур, называемых селекторами и конструкторами, реализующих абстрактные данные в терминах конкретного представления. Мы тоже начнем с такого подхода.

Задания в классе

Есть простые задания, средние и сложные. За каждое из них можно получить разное количество баллов. Можно не тратить время на простое задание и делать сложное, чтобы получить много баллов и шанс на автомат.

Если вы умеете, делайте всё на классах. Переопределяйте магические методы, чтобы переопределить операторы(суммы, сравнение и прочее). Выбрасывайте исключения, если надо(деление на 0). В IDEA можете нажать “generate” -> “override methods” и она покажет вам список всех магических методов, которые вам надо будет переопределить.

Как делать классы можно прочитать тут или в официальной документации. Вам, возможно, будет интересно как переопределить операторы в Python, тогда вам сюда.

Рациональные числа. Easy.

Требуется создать абстракцию рациональных чисел с возможностью: создавать, складывать, вычитать, умножать, делить, сравнивать, печатать и превращать их в float number. Результаты должны быть всегда с наименьшим знаменателем (алгоритм Евклида в помощь). Целую часть выделять не надо.

Итого, нужен тип данных, который реализует следующие правила:

$\frac{n_1}{d_1} + \frac{n_2}{d_2} = \frac{n_1 d_2 + n_2 d_1}{d_1 d_2}$ $\frac{n_1}{d_1} - \frac{n_2}{d_2} = \frac{n_1 d_2 - n_2 d_1}{d_1 d_2}$ $\frac{n_1}{d_1} * \frac{n_2}{d_2} = \frac{n_1 n_2}{d_1 d_2}$ $\frac{n_1}{d_1} / \frac{n_2}{d_2} = \frac{n_1 d_2}{d_1 n_2}$ ${\frac{n_1}{d_1} = \frac{n_2}{d_2}} \Longleftrightarrow {n_1 d_2 = n_2 d_1}$

Hints

Вам скорее всего понадобится создать функцию make_rat(n1, d1), которая вернёт нечто. Например, словарь методов, какой-то объект или еще что-то. В качестве базового типа предлагается использовать tuple. Если вы умеете, можете сделать всё на основе классов.

Тесты

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

import unittest

class Fraction:
    pass

class TestFraction(unittest.TestCase):

    def testEg(self):
        self.assertTrue(Fraction(1, 2) == Fraction(-3, -6))
        self.assertTrue(Fraction(9, 15) == Fraction(6, 10))
        self.assertTrue(Fraction(1, 3) == Fraction(1, 3))

    def testLt(self):
        self.assertTrue(Fraction(1, 2) < Fraction(2, 3))
        self.assertTrue(Fraction(-1, 2) < Fraction(1, 2))
        self.assertTrue(Fraction(0, 2) < Fraction(2, 3))

    def testGt(self):
        self.assertTrue(Fraction(2, 3) > Fraction(1, 3))

    def testGe(self):
        self.assertTrue(Fraction(2, 3) >= Fraction(1, 3))
        self.assertTrue(Fraction(2, 3) >= Fraction(4, 6))

    def testLe(self):
        self.assertTrue(Fraction(1, 2) <= Fraction(2, 3))
        self.assertTrue(Fraction(2, 3) <= Fraction(2, 3))

    def testFloat(self):
        self.assertEqual(float(Fraction(1, 2)),0.5)
        self.assertEqual(float(Fraction(-1, 5)), -0.2)
        self.assertEqual(float(Fraction(10, 2)), 5)
        self.assertEqual(float(Fraction(3, -8)), -0.375)

    def testADD(self):
        self.assertEqual(Fraction(1, 2) + Fraction(1, 3), Fraction(5, 6))
        self.assertEqual(Fraction(1, 2) + Fraction(1, 6), Fraction(2, 3))
        self.assertEqual(Fraction(1, 2) + Fraction(1, -3), Fraction(1, 6))

    def testSUB(self):
        self.assertEqual(Fraction(1, 2) - Fraction(1, 3), Fraction(1, 6))
        self.assertEqual(Fraction(1, 6) + Fraction(1, 2), Fraction(-1, 3))

    def testSUB(self):
        self.assertEqual(Fraction(1, 2) - Fraction(1, 3), Fraction(1, 6))
        self.assertEqual(Fraction(1, 6) - Fraction(1, 2), Fraction(-1, 3))
        self.assertEqual(Fraction(1, 3) - Fraction(1, 3), Fraction(0, 3))

    def testMUL(self):
        self.assertEqual(Fraction(1, 2) * Fraction(1, 3), Fraction(1, 6))
        self.assertEqual(Fraction(1, 2) * Fraction(2, 1), Fraction(1, 1))
        self.assertEqual(Fraction(1, 2) * Fraction(-1, 2), Fraction(-1, 4))
        self.assertEqual(Fraction(-1, 2) * Fraction(1, -2), Fraction(1, 4))

    def testDIV(self):
        self.assertEqual(Fraction(1, 2) / Fraction(1, 2), Fraction(1, 1))
        self.assertEqual(Fraction(1, 2) / Fraction(1, 3), Fraction(3, 2))

    def testZiro(self):
        try:
            Fraction(2, 0)
            self.assertTrue(False)
        except(ArithmeticError):
            pass

if __name__ == '__main__':
    unittest.main()

Интервальная арифметика. Moderate.

Идея появилась из проблем инженеров. У них принято характеристики физических объектов описывать в рамках некоторых интервалов. Например, сопротивление резистора бывает 6.8 Ом с погрешностью 10%, что значит сопротивление лежит в интервале [6.12;7.48] Ом.

Необходимо разработать абстрактную структуру данных, на которой возможны все арифметические операции: сложение, вычитание, умножение, деление. И дополнительные функции: создание, сравнение(проверка равенства), форматирование в красивой форме, вычисление радиуса погрешности (в примере это 0.68).

Например: резистор R1=[6.8;10%]Ом подключен параллельно к резистору R2=[4.7;5%]Ом, тогда сопротивление их комбинации будет R3=[2.58;2.97]Ом.

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

def buildIntervalWithPercentage(center, percent):
    pass


def buildIntervalWithLowerUpper(lower, upper):
    pass


def buildIntervalWithRadius(center, radius):
    pass

Тесты

Придумайте сами исчерпывающий набор тестов python unittest.

Hints

Базовая структура данных скорее всего будет tuple.

Можете вдохновляться этой библиотекой interval-arithmetic

Гуглить книгу КОНЕЧНОМЕРНЫЙ ИНТЕРВАЛЬНЫЙ АНАЛИЗ С. П. Шарый.

Статья в вики на английском Interval_arithmetic.

Вопросы

Хитрый вопрос: что будет, если интервал пересекает 0?

Очень хитрый вопрос: проверьте, действительно ли вы получите одинаковый результат для следующей формулы:

$\frac{R_1 R_2}{R_1 + R_2} = \frac{1}{1/R_1 + 1/R_2}$

Ультрахитрый вопрос: а можете сделать, чтобы получилось равенство?

Домашнее задание

Сделать как можно больше заданий.

За помощью можете обратиться к книге “Структура и интерпретация компьютерных программ” и главе 2.