Формулировка задания.Требуется разработать программу-калькулятор дробей: fc(fraction calculator), который обеспечивает выполнение арифметических операций (сложение, вычитание, умножение и деление) для рациональных дробей, заданных в символическом формате. Программа fc должна быть ориентированна на использование следующего формата дробей: a/b, где a и b наборы цифр, отображающие числитель и знаменатель дроби.
  Исходными данными программы fc являются последовательности символов, представляющие вычисляемые арифметические выражения, где дробные операнды связывает символ операции(+, -, *, /). Дробные операнды и символ операции должны передаватся программе fc, через параметры командной строки её вызова. В командной строке операнды и символ операции разделяются с помощью прробелов.
  Результатом работы программы fc должно быть дробное число, которое представляет итог вычисления входного выражения и отображается в потоке стандартного вывода (stdout). Для некоторых операций и операндов должен быть предусмотрен вывод соответствующих информационных сообщений в поток протокола стандартной диагеостики (stderr).
  Программа fc должна быть составленна в системе програмирования C++ на основе разработки специального класса, в котором перегружены специальные арифметические операциинад дробными числами.

  В некоторых алгоритмах обработки численных данныхболее полезным является точное выражение результата в виде дроби (например, 1/3), чем приближенное представление с плавающей точкой (0,33333...). Использование дробей позволяет получить нецелочисленный ответ задачи в наглядной форме и исключить ошибку округления, свойственные обработке чисел с плавающей точкой в ограниченной разрядной сетке.
  Как известно, дробное число образует отношение 2-х целых чисел, которое записывается следующем образом: a/b, где a и b - наборы цифр, представляющие числитель и знаменатель дроби. Относительно числителя и знаменателя дроби приняты следующие договоренности:
   - знаменатель дроби долженбыть натуральным числом (b>0);
   - целое число можно представить дробью с единичным знаменателем (a/1);
   - знак дроби определяется знаком числителя;
   - если числитель и знаменатель дроби умножить на одно и тоже натуральное число (N), то получиться дробь   равная данной (a/b=(N*a)/(N*b));
   - если числитель и знаменатель дроби и меют общий делитель, то при делении их на него происходит сокращение дроби и образуется дробь равная данной
     ((D*a)/(D*b)=a/b);
   - если числитель и знаменатель взаимно-просты числа, т. е. не имеют общих делителей, то дробь называется несократимой;
   - любая дробь можен быть представлена к несократимой, если её числитель сократить на их наибольший общий делитель (Hog) - наибольшее натуральное  число, на которое ониоба делются без остатка;
   - две любые дроби a/b и c/b считаются равными, если (a*d)=(b*c);
   - две не сократимые дроби считаются равными, если равны их числители и знаменатели (a=c и b=d).
  Вычислительная обработка дробных чисел основана на использовании 4-х арифметических операций: сложение, вычитание, умножение и деление. Для выполнения этих операций символическое представление дроби выражается парой целых чисел, соответствующих её числителю и знаменателю. Пусть U/U' и V/V' обозначают дроби-операнды, а W/W'-дроби, результат операции. Тогда числитель и знаменатель результирующей дроби для 4-х арифметических оперций выражают следующие соотношения:

 1. Умножение: (W/W')={(U/U')*(V/V')}
    W=(U/d1)*(V/d2) и W'=(U'/d2)*(V'/d1),
    где d2=Hog(U,V') и d2=Hog(U'/V).
 2. Деление: (W/W')={(U/U')/(V/V')}
    W=(U/d2)*(V'/d1)sign(V) W'=|(U'/d2)*(V/d1)|,
    где d1=Hog(U,V) и d2=Hog(U',V').
 3. Сложение: (W/W')={(U/U')+(V/V')}
    а. Если Hog(U'/V')=1,то
       W=(U*V')+(U'*V) и W'=(U'*V')
    б. Если Hog(U'/V')>1,то
       W=t/d2 и W'=(U'/d1)*(V'/d2),
       где d1=Hog(U',V'), t=U*(V'/d2)+V*(U'/d1) и d2=Hog(t,d1).
 4. Вычитание: (W/W')={(U/U')-(V/V')}
    Выполняется аналогично сложению, если везде заменить знак плюс на знак     минус.
  В приведенных соотношениях Hog(m,n) обозначает наибольший общий делитель чисел |m| и |n|. Для эффективного выполнения Hog применяется алгоритм Евклида - самый старый нетривиальный алгоритм, дошедший до наших днейю. В современной редакции псевдо-код алгоритма Евклида выглядит следующим образом:

     IF m<0 THEN
        m <- |m|;  /* перейти к абсолютной величине числа m */
     IF n<0 THEN
        n <- |n|;  /* перейти к абсолютной величине числа n */
     WHILE n<>0 { /* цикл уменьшения n */
      r <- m mod n; /* остаток деления m на n */
      m <- n;
      n <- r;
      }
     RETURN m.

  В классическом варианте алгоритм Евклида используется для поиска наибольшего общего делителя пары не отрицательных целых чисел, при условии, что Hog(0,0) принимается равным 0. Для расширения области применения на поле произвольных чисвел в предлагаемой версии алгоритма Евклида предусмотрен переход к абсолютным величинам рассматриваемых чисел. На каждом шаге основного цикла алгоритма Евклида происходит последовательное уменьшение обоих чисел, но при этом значение их наибольшего общего делителя остается неизменным, т. к.:

  Hog(m,n)=Hog(n,m-r*n).

  Цикл уменьшения обоих чисел продолжается, пока на очередной итерации меньшее из чиселне станет равным 0. В этом случае большее из чисел принемается за наибольший общий делитель исходной пары, т. к.:
       Hog(m,0)=0.
  Например, Hog(259,111) выполняется за 3 шага:

  Hog(259,111)=Hog(111,37)=Hog(3,0)=3.

  Сложность алгоритма Евклида пропорциональна логарифму от максимального по абсолютной величине числа из рассматриваемой пары чисел. ффективность алгоритма Евклида определяет эффективность выполнения арифметических операций над дрробями по соотношениям, определенным выше.
  На первый взгляд кажется, что арифметические операции над дробями можно реализовать более эффективно, вычисляя наибольший общий делитель в каждой операции только один раз вместо двух. Например, при умножении {(U/U')*(V/V')}, числитель и знаменатель ответа можно получить по внешне более простым формулам:

  W=(U*V)/d и W'=(U/U')/d,

где d=Hog(U*V,U'*V').
  При сложении 2-х дробей {(U/U')+(V/V')} можно представить результат в виде следующей дроби:

  (U*V'+V*U')/(U'*V'),

а затем привести результирующую дробь к не сократимому виду, используя

Hog(U*V'+V*U',U'*V').

  Однако, в обоих случаях придется оперировать с относительно большими числами на каждой итерации алгоритма Евклида. Каждая итерация будет выполнятся медленее, чем кодна вней рассматриваются меньшие числа, которые характерны для операций обработки дробей с 2-мя вычислителями наибольшего общего делителя. Таким образом, по быстродействию оба подхода по-крайней мере равнозначны, но в первом исключена возможность переполнения разрядной сетки, что является решающим преимуществом, когда числители и знаменатели дробей являются большими числами.

  При разроботки программы калькулятора дробей целесообразно сосредоточить описание дробных структур данных и операций их обработки в отдельном классе Fraction. Класс Fraction должен содержать частные (private) компаненты данные и общедоступные (public) компанентные методы обработки приватных данных. Это позволит оперировать данными класса Fraction только в компанентных методах и исключит возможность непосредственного обращения к ним из любой внешней функции программы. Исходя из этого декларация логической структуры класса Fraction должна иметь следующий формат:

  class Fraction {
    private: /* спецификация компанентных данных */
    public:  /* объявление прототипов компанентных методов */
 };

  Вприватную часть класса Fraction следует включить спецификацию целочисленных компанентных данных, которые обозначают числитель и знаменатель дроби, как показано в следующем фрагменте класса Fraction:

 class Fraction {
    private:
     int nominator; /* числитель */
     int denominator; /* знаменатель */
    public:
  ................................
};

  В общедоступную часть деклорации класса Fracton нужно включить объявления прототипов компонентных методов, которые реализуют арифметическую оброботку  дробей и отображение результатов обработки. Кроме того, в общедоступной части следует объявить конструктор класса.
  Желаемую арифметическую обработку дробных чисел удобно реализовать с  помощью компонентных оператор-функций, которые обеспечат перегрузку арифметических операций (+,-,*,/) в выражениях с объектами класса Fraction. Наличие оператор-функций позволит конструировать арифметические выражения для объектов класса Fraction в наглядной форме как для объектов простых типов. При наличии соответствующих оператор-функций будет правильно вычислятся, например, следующее выражение прграммы:

   r=f1@f2;

где r,f1 и f2 объекты класса Fraction, а @ - знак операции.
  По формату определения и декларации оператор-функции идентична обычной функции с предопределееным именем operator@, где @ обозначает знак перегружаемой операции, и специальным соглашением по аргументам. Для декларации 4-х трабуемых оператор-функций в классе Fraction может быть рекомендован следующий идентичный формат:

   Fraction operator@( Fraction& );

который отличается только символом перегружаемой операции @ (+,-,*,/). Используя эти декларации, компилятор языка C++ будет рассматривать приведенное  выше выражение как следующий вызов соответствующей компанентной оператор-функции:

   r=f1 operator@(f2);

  Как видно из приведённой спецификации вызова, аргумент компанентноу оператор-функции используется для передачи по ссылке 2-го операнда операции. Перыый операнд операции неявно передается через скрытый аргумент, присущий любой компанентной функции и доступный по указателю this. Результат вычислений в теле оператор-функции возвращается в основную программу для присвоения объекту класса Fraction. Следует отметить, что передача аргумента по ссылке в данном случае выбрана из экономических соображений. Для оператор-функции допустима передача аргумента по значению. Однако, в этом случае происходит создание промежуточной копии объекта передачи в стеке оператор-функции.
  Кроме компанентных оператор-функций в состав компанентных методов класса Fraction целесообразно включить 3 обычные компанентные функции:

  int euclid(int,int);
  int sign(int);
  void ptint(void);

декларировав их в общедоступной части класса Fraction, указанным образом.
  Компанентный метод euclid должен вычислять наибольший общий делитель своих аргументов, используя алгоритм Евклида. Вычисленное значение должно передаваться через код возврат метода. Этод метод предназначается для реализации алгоритмов арифметических операций с дробями в компанентных оператор-функциях класса Fraction.
  Компанентный метод sign используется для определения знаков своего аргумента, возвращая (-1), если значение аргумента меньше 0 или +1, если аргумент имеет неотрицательное значение. Этот метод следует использовать для реализации алгоритма деления дробных чисел в соответствующей компанентной оператор-функции класса Fraction.
  Компанентный метод print должен отображать в стандартном потоке вывода числитель и знаменатель объекта класса Fraction, от имени которого он выздван. Этод метод следует применяыть в программе калькыулятора дробей дляы отображения результата операций с дробями.
  Для инициализации компанентных данных при создании объектов класса Fraction в ней необходимо предусмотреть конструктор с аргументом типа указателя на строку символов (char*). Поэтому декларация в общественной части объявления класса Fraction должен иметь следующий формат:

   Fracion(char*);

  Через аргумент в этот конструктор должно передаваться представление дроби в виде строки символов, где числитель и знаменатель вфражаются выборами цифр, которые разделяются символом '/'. Конструктор должен преобразовывать символьное представление числителяы и знаменателя в целочисленное значение компанент-данныхкласса Fraction, используя библиотечную функцию atoi системы програмирования C++.
  Рассмотренные общедоступные компаненты класса Fraction можно использовать в основной функции main( int argc,char** argv) программы калькулятора дробей fc. Вычисляемое арифметическое выражение должно передаваться в функцию main через параметры командной строки вызова программы fc, так что 1-й (argv[1]) и 3-й
(argv[3]) параметры соответствуют дробным операндам, а 2-й
 
 

  В теле функции main следует задать 3 объекта класса Fraction для хранения операндов и результата операции. Объекты операнды должны быть инициализированы строками соответствующих параметров командной стоки. Объект результата можно инициализировать произвольной дробью, представленной в символическом формате, например, "0/1".
  Знак операции, передаваемый в функцию main через 2-й параметр командной строки, удобно рассматривать в операторе switch системы прграммирования C++ для выбора одного из 4-х вариантов вычисляемых дробных выражений. После вычисления выбранного выражения с помощью соответствующе компонентной оператор- функции класса Fraction ответ нужно сохранить в зарезирвированном объекте-результате. Вызов компонентной функции print класса Fraction от имени объекта  результата, позволит отобразить полученную дробь в потоке стандартного вывода.

  1. Расширить класс Fraction перегрузкой операции присваивания (=), в которой должно быть реализовано копирование числителя и знаменателя, а также приведение результирующей дроби к несократимому виду, если это необходимо.
  2. Расширить класс Fraction перегрузкой операции проверки равенства 2-х  дробей (==).
  3. Модифицировать класс Fraction, так чтобы перегрузку операций над объектами обеспечивали дружественные оператор-функции. При этом необходимо учесть, что прототипы дружественных функций должны быть объявлены в декларации класса с модификатором friend и в них по ссылке должны передаваться оба операнда, т.к. скрытый указатель this на объект класса в них недоступен.
  4. Усовершенствовать представление результата операций с дробями, так чтобы в случае, когда числитель больше знаменателя, выделялась целая часть числа.
  5. Разработать средства контроля достоверности результов операций с дробными числами. Например, сложение дробей должно проверяться вычитанием, а умножение - делением.
  6. Переориентировать программу-калькулятор для интерактивного ввода вычисляемых арифметических выражений с дробями из потока стандартног ввода.
  7. Реализовать операцию сложения и вычитания с помощью приведения дробей к общему знаменателю. Для вычисления наименьшего общего кратного (Hok) знаменателей дробей, которое необходимо в этом случае, рекомендуется использовать следующее соотношение:

            U'/V'=Hog(U'/V')+Hok(U'/V').

  1. Д. Кнут
     Искусство программирования для ЭВМ, т.2 Получисленные алгоритмы - М.,
     Мир, 1977 г.
  2. П. Лукас
     С++ под рукой - Киев, НИПФ "ДиаСофт", 1993 г.