Программирование операций с дробями

Операции  с дробями

1. Умножение. Для умножения двух дробей надо:

1) Умножить числитель одной  дроби на числитель другой.

2) Умножить знаменатель одной  дроби на знаменатель другой.

 

2. Сложение. Для сложения двух дробей надо:

1) Если знаменатели дробей равны,  то сложить числители, а знаменатель  оставить тем же.

2) Если знаменатели не равны,  то приводим их к общему  знаменателю, домножая каждую из них на знаменатель другой.

3) Складываем дроби по п.1.

 

3.Сравнение на равенство. 

1) Если знаменатели дробей равны,  то проверить на равенство  числители.

2) Если знаменатели не равны, то приводим их к общему знаменателю, домножая каждую из них на знаменатель другой.

3) Сравниваем дроби по п.1.

 

4.Сокращение дробей.

1)Находим наибольший общий делитель(НОД) числителя и знаменателя.

2)Делим числитель на НОД.

3)Делим знаменатель на НОД.

 

 

 

 

ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И

ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ

                                          Спецификация подпрограмм

1. int GetSimpleChain(vector<vector<rational> > &matr,  vector<int>  &W, list<vector<int> > &lst,  int i)

2) Находит в графе matr все простые цепи, начинающиеся вершиной i. Цепи хранятся в линейном списке lst.

3) Входные параметры – matr, I.

4) Выходные параметры – W, lst.

 

1) int GetSimpleChain(vector<vector<rational> > &matr,  vector<int>  &W, list<vector<int> > &lst,  int i)

    2) Находит в графе matr все простые циклы, начинающиеся вершиной i. Циклы     хранятся в линейном списке lst.

    3) Входные параметры – matr, i.

    4) Выходные параметры – W, lst.

 

 

1) int FindMaxAmplification(list<vector<int> > lst, vector<vector<rational> > &matr)

2) Находит среди всех простых цепей цепь с наибольшим усилением.

3) Входные параметры – matr, lst.

4) Выходные параметры – нет.

 

 

 

 

 

 

 

 

 

ВЫЧИСЛИТЕЛЬНЫЙ ЭКСПЕРИМЕНТ

Количество вершин	Время выполнения, мс
	Поиск постой цепи с максимальным усилением	Поиск простого цикла с максимальным усилением
5	223	157
10	614	542
15	2245	1804

 

Как видно  из таблицы, время выполнения алгоритма  поиска с возвращением сильно растет по мере увеличения количества вершин.

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЛИТЕРАТУРА

 

1 Рязанов Ю.Д. Дискретная математика: учебное пособие. Белгород, БГТУ, 2010.

2. Свами М., Тхуласираман К. - Графы, сети и алгоритмы. М., Мир, 1984.

3. Липский В. Комбинаторика для программистов. М., Наука, 1989.

4. Новиков Ф.А. Дискретная математика для программистов.СПб., Питер,2003.

5.  Шапорев С.Д. Дискретная математика. СПб., БХВ-Петербург, 2007.

6. Харари Ф. Теория графов. М., Мир, 1973.

7.  http://ru.wikipedia.org

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение

Текст программы

#include <iostream>

#include <vector>

#include <list>

using namespace std;

 

class rational {

public:

int numenator, denominator;

 rational(int numenator1 = 0, int denominator1 = 1)

{

     numenator = numenator1;

     denominator = denominator1;

};

void normalize(void);

rational& operator+=(const rational& Right);

rational& operator*=(const rational& Right);

rational operator+(const rational& Right);

rational operator*(const rational& Right);

bool operator==(const rational& Right);

bool operator<(const rational& Right);

bool operator>(const rational& Right);

bool operator<=(const rational& Right);

bool operator>=(const rational& Right);

bool operator!=(const rational& Right);

};

 

 

 int gcd(int a, int b)

{

    while( 1 )

    {

        a = a % b;

if( a == 0 )

return b;

b = b % a;

 

        if( b == 0 )

return a;

    }

}

 

ostream& operator<<(ostream& str, rational& a) {

    return (str << a.numenator << "/" << a.denominator, str);

}

 

 void rational::normalize(void)

{

    int d = gcd(denominator, numenator);

    denominator /= d;

    numenator /= d;

}

 

rational& rational::operator*=(const rational& Right)

{

     this->numenator *= Right.numenator;

     this->denominator *= Right.denominator;

     normalize();

     return *this;

}

 

 rational rational::operator*(const rational& Right)

{

    rational n = *this;

    n *= Right;

    return n;

}

 

rational& rational::operator+=(const rational& Right)

{

  if (this->denominator == Right.denominator)

   {

       this->numenator += Right.numenator;

       normalize();

   }

  else

   {

      this->numenator = this->numenator * Right.denominator + Right.numenator * this->denominator;

      this->denominator = this->denominator * Right.denominator;

      normalize();

   }

  return *this;

}

 

rational rational::operator+(const rational& Right)

{

    rational n = *this;

    n += Right;

    return n;

}

 

bool rational::operator==(const rational& Right)

{

    rational n = *this;

    if (Right.denominator == n.denominator)

      if (Right.numenator == n.numenator) return 1;

      else return 0;

    else

    {

        int d = gcd(Right.denominator, n.denominator);

        int p = d * Right.numenator;

        int q = d * n.numenator;

        if (p == d) return 1;

        else return 0;

    }

}

 

bool rational::operator<(const rational& Right)

{

    rational n = *this;

    if (Right.denominator == n.denominator)

      if (n.numenator < Right.numenator) return 1;

      else return 0;

    else

     {

         int d = gcd(Right.denominator, n.denominator);

         int p = d * Right.numenator;

         int q = d * n.numenator;

         if (q < p) return 1;

         else return 0;

     }

}

 

bool rational::operator>(const rational& Right)

{

    rational n = *this;

    if (Right.denominator == n.denominator)

      if (n.numenator > Right.numenator) return 1;

      else return 0;

    else

     {

         int d = gcd(Right.denominator, n.denominator);

         int p = d * Right.numenator;

         int q = d * n.numenator;

         if (q > p) return 1;

         else return 0;

     }

}

 

bool rational::operator<=(const rational& Right)

{

    rational n = *this;

    if (Right.denominator == n.denominator)

      if (n.numenator <= Right.numenator) return 1;

      else return 0;

    else

     {

         int d = gcd(Right.denominator, n.denominator);

         int p = d * Right.numenator;

         int q = d * n.numenator;

         if (q <= p) return 1;

         else return 0;

     }

}

 

bool rational::operator>=(const rational& Right)

{

    rational n = *this;

    if (Right.denominator == n.denominator)

      if (n.numenator >= Right.numenator) return 1;

      else return 0;

    else

     {

         int d = gcd(Right.denominator, n.denominator);

         int p = d * Right.numenator;

         int q = d * n.numenator;

         if (q >= p) return 1;

         else return 0;

     }

}

 

bool rational::operator!=(const rational& Right)

{

    rational n = *this;

    if (Right.denominator == n.numenator)

     if (n.numenator != Right.numenator) return 1;

     else return 0;

    else

     {

        int d = gcd(Right.denominator, n.denominator);

         int p = d * Right.numenator;

         int q = d * n.numenator;

         if (q != p) return 1;

         else return 0;

     }

}

 

void Read_matr(vector<vector<rational> > &matr)

{

  int i,j,n;

  n=matr.size();

  for (i=0; i < n; i++)

   for (j=0; j < n; j++)

      cin >> matr[i][j].numenator >> matr[i][j].denominator;

 

}

 

 

int find_elem(int x, vector<int> &mass)

{

    unsigned int i = 0;

    while ((i < mass.size()) && (x != mass[i]))

     i++;

    if (x == mass[i]) return 1;

    else return 0;

}

 

int find_adjeacency(vector<vector<rational> > &matr, int x, vector<int> &mass)

{

    unsigned int t = x;

    while(((t < matr.size()) && (matr[x][t] == 0)) || (find_elem(t,mass)))

     t++;

    if ( t < 0) return 1;

    else return 0;

}

 

int GetSimpleChain(vector<vector<rational> > &matr, vector<int> &W, list<vector<int> > &lst, int i)

{

     unsigned int n = matr.size();

     for(int x = 0; x < n; x++)

      {

          if ((matr[i-1][x] != 0) && (!find_elem(x,W)))

              {

                W.resize(W.size()+1);

                W[i] = x;

          if (find_adjeacency(matr,x,W))

           {

               GetSimpleChain(matr, W, lst, i++);

           }

          else

            {

              lst.push_back(W);

              return 1;

            }

              }

     }

}

 

 int GetSimpleCycle(vector<vector<rational> > &matr, vector<int> &W, list<vector<int> > &lst, int i)

{

     cout << W[0];

     unsigned int n = matr.size();

     for(int x = 0; x < n; x++)

      {

          if ((matr[i-1][x] != 0) && ((!find_elem(x,W) || (x == W[0]))))

              {

                W.resize(i);

                W[i] = x;

          if (W[0] == x)

           {

              lst.push_back(W);

               return 1;

           }

          else GetSimpleCycle(matr, W, lst, i++);

              }

     }

}

 int FindMaxAmplification(list<vector<int> > lst, vector<vector<rational> > &matr)

 {

     list<vector<int> > lst_2;

     list<vector<int> > :: iterator iq, id;

     vector<int> :: iterator iw, is;

     rational Amplif = 0;

     rational  MaxAmplif = 0;

      for (iq = lst.begin(); iq != lst.end(); iq++)

     {

      for (iw = (*iq).begin(); iw != (*iq).end(); iw++)

        Amplif += matr[*iw][*iw+1];

      if (MaxAmplif < Amplif)

       {

           lst_2.clear();

           MaxAmplif = Amplif;

           lst_2.push_back(*iq);

       }

     }

     id = lst_2.begin();

     for (is = (*id).begin(); is!= (*id).end(); is++)

       cout << *is;

     cout << endl;

     return 0;

}

int main()

{

    list<vector<rational> > lst;

    vector<vector<rational> > graph;

    vector<rational>  chain, cycle;

    unsigned  int p;

    unsigned int j,i;

    cout << "Vvedite razmer matritci smezhnosty:\n";

    cin >> p;

    graph.resize(p);

    for ( j = 0; j < p; j++)

     graph[j].resize(p);

    cout << "Vvedite matritcy smezhnosti \n";

    Read_matr(graph);

    char ch;

    std::cout <<"press 1 if you want find simple chain or press 2 if you want find simple cycle  or press 3 to exit \n ";

    std::cin >> ch;

    switch (ch)

     {

         case '1':

           cout << "Enter i /n";

           cin >> i;

           chain.resize(1);

           chain[0] = i;

           i++;

           DWORD dwTicks = ::GetTickCount();

           GetSimpleChain(graph, cycle, lst, i);

           cout << "Simple chain with maximum amplification is \n";

           FindMaxAmplification(lst, graph);

           dwTicks = ::GetTickCount() - dwTicks;

           cout << "algorithm execution time is " << dwTicks;

           break;

         case '2':

           cout << "Enter i \n";

           cin >> i;

           cycle.resize(1);

           cycle[0] = i;

           i++;

           DWORD fwTicks = ::GetTickCount();

           GetSimpleCycle(graph, cycle, lst, i);

           cout << "Simple cycle with maximum amplification is \n";

           FindMaxAmplification(lst, graph);

           fwTicks = ::GetTickCount() - fwTicks;

           cout << "algorithm execution time is " << fwTicks;

           break;

         case '3':

           return 0;

     }

return 0;

}