В этой статье я не буду разбирать какой-либо алгоритм или решение олимпиадной задачи, а будет обычное написание класса. Но я считаю, что стоит это сделать, чтобы в следующих статьях я мог ссылаться на него, а не реализовывать каждый раз.
Более того, всем рекомендую иметь и пополнять свою библиотеку классов и алгоритмов, которые вы сможете применять в онлайн соревнованиях.
Писать буду класс рациональных чисел (простыми словами: дроби). Это бывает полезно, когда не хочется связываться с вещественными числами (а я рекомендую всегда, где это возможно, их избегать, потому что в них накапливаются ошибки округлений, возникают сложности со сравнением и, как следствие, сортировкой и хранением в set'е и т.д.). Например в задачах на геометрию все операции можно делать в рациональных числах до момента вывода ответа или вычисления квадратного корня (а эту операцию часто удаётся оставить напоследок).
Для дроби будем хранить числитель (numerator) и знаменатель (denominator), причём знаменатель не должен быть меньше нуля, а сама дробь должна быть несократимая.
Оформим класс в виде шаблона, чтобы можно было подстраивать его под ограничения задачи и компилятора тестирующей системы (например, если установлена старая версия, которая не поддерживает тип __int128).
Метод reduce занимается сокращением дроби. Для этого с помощью алгоритма Евклида ищется наибольший общий делитель числителя и знаменателя, которые затем делятся на него.
Важно не забыть, что числитель может быть отрицательным, поэтому для нахождения наибольшего общего делителя необходимо передавать модуль от этого числа.
Добавим get'еры, но они нужны лишь для отладки, когда хочется точнее посмотреть, что происходит. И иногда бывают задачи, в которых оперируют дробями и надо выводить в виде дроби.
Замечу, что set'еры я не пишу, потому что бесконтрольное изменение компонентов дроби может нарушить соглашения о том, что знаменатель больше 0 и дробь несократимая. Да, можно было бы в них сделать проверку и коррекцию, но на практике лучше сразу создать рациональное число через конструктор.
Добавим операторы присваивания стандартного типа и другой дроби.
Переопределим операторы арифметических операций и унарный минус.
Стоит отметить, что эти операции можно было бы реализовать аккуратнее. Чтобы уменьшить вероятность переполнения типа, в операции сложения надо находить наименьшее общее кратное и ставить его в качестве знаменателя, а в умножении и делении перекрёстно сокращать дроби перед умножением.
Переопределяем операции сравнения, чтобы к переменным нашего класса были применимы алгоритмы из стандартной библиотеки.
И, напоследок, две полезные функции. Первая нужна для вывода ответа, а вторая просто для сокращения кода и вычислений (но лучше, конечно, отдельно иметь шаблонную функцию возведения в квадрат).
На этом всё. Ничего сложного здесь нет, а скоро появится разбор задачи, где я буду использовать этот класс по полной программе.
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.