Форум программистов, компьютерный форум CyberForum.ru

Дискретная математика - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Двумерный массив. http://www.cyberforum.ru/cpp-beginners/thread181904.html
Дан массив int mass={{0},{0},{0}} И с помощью функции надо изменить одно из чисел, как это реализовать? int XO_pozi(int mass,int pozi) { for(int i=0;i<3;i++)
C++ Класс, реализующий стек Помогите девушке, только учусь программировать и чет пока не очень=( плиииииииииииииииииииииииииз кого не затруднит...... Задание 5. • Реализовать заданную динамическую структуру данных, с которой можно работать через перегруженные операции. • Для демонстрации работы программы необходимо реализовать меню, позволяющее вызывать операции реализованной структуры данных. На экране должна... http://www.cyberforum.ru/cpp-beginners/thread181900.html
C++ Вычислить значения функции
Составьте программу и модули с функциями для выполнения следующих заданий. 1. Вычислить значения функции y = f(x) и ее производной для последовательных значений аргумента x, которые отличаются на величину h, и напечатать таблицу значений аргумента, функции и производной. 2. Определить наименьшее fmin и наибольшее fmax табличные значения функции и соответствующие значения аргумента. ...
C++ Как преобразовать string в double и обратно?
нашел функцию atof но не хочет запускаться. сам начеркал функцию для перевода в double но обратно чет даже идей нет.
C++ Максимально длинная последовательность http://www.cyberforum.ru/cpp-beginners/thread181885.html
дан масив чисел до 1 000 000 чисел нужно выбрать максимально длинную последовательность возрастающих чисел и вывести её на экран момню, была похожая задачка, но не могу найти помогите, очень нужно
C++ Отыскание корня уравнения f(x)=0 на интервале (A,B) с точностью Е (метод хорд) Вот такая задача: Отыскание корня уравнения f(x)=0 на интервале (A,B) с точностью Е (решение с помощью метода хорд). Уравнение такое: x^4-x^3-2.5 A=1; B=2; E=10; Пожалуйста, прошу помощи. Добавлено через 23 часа 33 минуты не понимаю совсем как работают эти фунции... подробнее

Показать сообщение отдельно
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
26.10.2010, 17:23     Дискретная математика
Есть три программы по дискретной математике. Выложу сюда. Может кому-то пригодиться. До конца семестра думаю будет еще 1-2 по оптимизационным алгоритмам.
Проги под консоль, универсальности нет, но работает верно.
Все сделано только через матрицу смежности.

Ориентированные, неориентированные графы. Выводит связанные вершины по матрице смежности
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//Graph.h
#ifndef _GRAPH_H_
#define _GRAPH_H_
 
#include <vector>
 
class Graph
{
public:
   Graph(){}
   virtual ~Graph(){}
   void SetSize(int size_);
   const int GetSize() const {return size;} 
   virtual void Input()=0;
   void Output();
   void Resize();
protected:
   std::vector<std::vector<int> > VecGraph;
   int size;
};
 
class OrGraph:public Graph
{
public:
   OrGraph(){}
   ~OrGraph(){}
   void Input();
};
 
class UnOrGraph:public Graph
{
public:
   UnOrGraph(){}
   ~UnOrGraph(){}
   void Input();
};
 
#endif
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
//Graph.cpp
#include "Graph.h"
 
#include <iostream>
#include <algorithm>
#include <iterator>
 
//Functions for abstract Graph
void Graph::SetSize(int size_)
{
   size=size_;
   Resize();
}
 
void Graph::Output()
{
   for(int i=0; i<size; ++i)
   {
      std::copy(VecGraph[i].begin(), VecGraph[i].end(), std::ostream_iterator<int>(std::cout, " "));
      std::cout<<std::endl;
   }
   for(int i=0; i<size; ++i)
   {
      for(int j=0; j<size; ++j)
      {
         if(VecGraph[i][j]==1)
            std::cout<<i+1<<" node is connected with "<< j+1 <<" node.\n";
      }
   }
}
 
void Graph::Resize()
{
   VecGraph.resize(size);
   for(int i=0; i<size; ++i)
      VecGraph[i].resize(size);
}
 
//Functions for UnOrGraph
void UnOrGraph::Input()
{  
   for(int i=0; i<size; ++i)
   {
      for(int j=0; j<size; ++j)
      {
         if(i>j)
            continue;
         std::cout<<"Enter 1 for connect "<< i+1 <<" node with "<< j+1 <<" node: ";
         std::cin>>VecGraph[i][j];
         if(i!=j)
            VecGraph[j][i]=VecGraph[i][j];
      }
   }
}
 
//Functions for OrGraph
void OrGraph::Input()
{
   for(int i=0; i<size; ++i)
   {
      for(int j=0; j<size; ++j)
      {
         std::cout<<"Enter 1 for connect "<< i+1 <<" node with "<< j+1 <<" node: ";
         std::cin>>VecGraph[i][j];
      }
   }
}
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//Main.cpp
#include <iostream>
#include <stdexcept>
 
#include "Graph.h"
 
int main()
{
   try
   {
      int size=0;
      int state=0;
   
      Graph*pOb;
 
      std::cout<<"Enter numb of nodes: ";
      std::cin>>size;
 
      if(size<0)
         throw "Numb of nodes can`t be less then zero. End of program\n";
      else if(size==0)
      {
         std::cout<<"It is empty graph\n";
         return 0;
      }
 
      std::cout<<"Enter 1 for unor graph and 2 for or graph: ";
      std::cin>>state;
 
      if((state!=1)&&(state!=2))
      {
         throw "You can only input 1 for unor graph or two for or graph. End of program\n";
      }
 
      if(state==2)
         pOb=new OrGraph;
      else if(state==1)
         pOb=new UnOrGraph;
   
      pOb->SetSize(size);
      pOb->Input();
      pOb->Output();
   }
   
   catch(char*str)
   {
      std::cerr<<str;
      return EXIT_FAILURE;
   }
 
   system("pause");
   return 0;
}


Добавлено через 3 минуты
Алгоритм Уоршалла
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//Matrix_adj.h
#ifndef _MATRIX_ADJ_H_
#define _MATRIX_ADJ_H_
 
#include <vector>
 
class AdjMatr
{
public:
   AdjMatr()
   {
      VecAdj.resize(0);
      VecPath.resize(0);
   }
   ~AdjMatr(){}
   void input();
   void output(const std::vector<std::vector<int> >& Vec);
   void resize(size_t size);
   void find_path();
   void copy_matr();
   size_t set_size();
private:
   std::vector<std::vector<int> > VecAdj;
   std::vector<std::vector<int> > VecPath;
};
 
#endif /*ifndef Matrix_adj*/
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
//Matrix_adj.cpp
#include "Matrix_adj.h"
 
#include <iostream>
#include <algorithm>
#include <iterator>
 
void AdjMatr::resize(size_t size)
{
   VecAdj.resize(size);
   for(size_t i=0; i<size; ++i)
      VecAdj[i].resize(size);
}
 
void AdjMatr::copy_matr()
{
   VecPath.resize(VecAdj.size());
   for(size_t i=0; i!=VecAdj.size(); i++)
   {
      VecPath[i].resize(VecAdj[i].size());
      std::copy(VecAdj[i].begin(), VecAdj[i].end(), VecPath[i].begin());
   }
}
 
void AdjMatr::input()
{
   size_t size=set_size();
   resize(size);
   for(size_t i=0; i<size; ++i)
   {
      for(size_t j=0; j<size; ++j)
      {
         if(i==j)
         {
            VecAdj[i][j]=0;
            continue;
         }
         std::cout<<"Enter 1 for connect "<< i+1 <<" node with "<< j+1 <<" node and 0 for not\n";
         std::cin>>VecAdj[i][j];
      }
   }
   std::cout<<"Initial adj matrix\n";
   output(VecAdj);
}
 
size_t AdjMatr::set_size()
{
   size_t size;
   std::cout<<"Enter size: ";
   std::cin>>size;
   return size;
}
 
void AdjMatr::output(const std::vector<std::vector<int> >& Vec)
{
   for(size_t i=0; i<Vec.size(); ++i)
   {
      std::copy(Vec[i].begin(), Vec[i].end(), std::ostream_iterator<int>(std::cout, " "));
      std::cout<<std::endl;
   }
}
 
void AdjMatr::find_path()
{
   copy_matr();
   std::cout<<"Initial path matrix\n";
   output(VecPath);
   for(size_t k=0; k<VecPath.size(); ++k)
   {
      for(size_t i=0; i<VecPath.size(); ++i)
      {
         if(VecPath[i][k]==1)
         {
            for(size_t j=0; j<VecPath.size(); ++j)
            {
               VecPath[i][j]=(VecPath[i][j]||VecPath[k][j]);
            }
         }
      }
   }
   std::cout<<"Path matrix\n";
   output(VecPath);
}
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
//Main.cpp
#include "Matrix_adj.h"
 
#include <iostream>
 
int main()
{
   AdjMatr Ob;
   Ob.input();
   Ob.find_path();
   system("pause");
   return 0;
}


Добавлено через 5 минут
Код прюфера. Кодирование/декодирование дерева. Много комментов.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//Prufer.h
#ifndef _PRUFER_H_//Страж включения
#define _PRUFER_H_//
 
#include <vector>//Для использования std::vector
#include <iostream>//Для использования потоков ввода/вывода/ошибки
 
class AbstractMatr//Класс-контейнер матрица
{
public:
    AbstractMatr() {}//Конструктор без параметров
    AbstractMatr(size_t n, size_t m);//Конструктор с параметрами размеров
    AbstractMatr(const AbstractMatr&Ob):Matrix(Ob.Matrix) {}//Конструктор копирования. Копируем один вектор в другой
    virtual ~AbstractMatr() {}//Виртуальный деструктор
    void SetSize(size_t n, size_t m);//Функция установки размера
    inline const size_t GetRow() const {return Matrix.size();}//Получение кол-ва строк в векторе
    inline const size_t GetCol() const {return Matrix[0].size();}//Получение кол-ва столбцов в векторе
    void swap(AbstractMatr&);//Меняем местами значения двух объектов.
protected:
    std::vector<std::vector<int> > Matrix;//Вектор векторов типа int. Исходная матрица смежности
};
 
class Prufer:public AbstractMatr//Открытое наследование
{
public:
    Prufer():AbstractMatr() {}//Конструктор без параметров, вызывающий конструктор AbstractMatr()
    Prufer(size_t n, size_t m):AbstractMatr(n, m) {}//Конструктор с параметрами размера, вызывающий констр. AbstractMatr
    Prufer(const AbstractMatr& Ob):AbstractMatr(Ob) {}//Конструктор копирования, вызывающий констр. AbstractMatr
    friend std::ostream& operator <<(std::ostream&, const Prufer&);//Перегрузка оператора вывода в поток
    friend std::istream& operator >>(std::istream&, Prufer&);//Перегрузка оператора ввода в поток
    void Code();//Функция кодирования
    void Decode();//Функция декодирования
    int Degree(int row);//Функция вычисления степени вершины
    int Adjacent(int row);//Функция получения единственной смежной вершины с данной
    bool IsMin(int elem);//Функция проверки на минимальный элемент
    void DeleteEdge(int row, int col);//Функция удаления ребра
    bool IsInPruf(int elem);//Функция проверки на присутствие в коде Прюфера
    bool IsMinNode(int elem, int row);//Функция проверки на минимальный элемент. Для Decode
private:
    std::vector<int> Pruf;//Вектор типа int. Код Прюфера
    std::vector<int> Nodes;//Вектор типа int. Вершины
    std::vector<std::pair<int, int> > Edges;//Вектор типа пары двух интовых значений. Ребра
    std::vector<int> Degrees;//Вектор типа int. Степени
};
 
#endif//
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
//Prufer.cpp
#include <vector>
#include <algorithm>//Использование стандартных алгоритмов
#include <iostream>
#include <functional>//Использование функторов
#include <stdexcept>//Использование стандартных классов исключений
 
#include "Prufer.h"
 
AbstractMatr::AbstractMatr(size_t n, size_t m)
{
    Matrix.resize(n);//Установка размера исходной матрицы
    for(int i=0; i!=GetRow(); ++i)
    {
        Matrix[i].resize(m);//Установка размера строки исходной матрицы
    }
}
 
void AbstractMatr::SetSize(size_t n, size_t m)
{
    if(GetRow()!=0&&GetCol()!=0)//Если столбцы/строки не равны нулю
        Matrix.clear();//Чистим вектор
    Matrix.resize(n);
    for(int i=0; i!=GetRow(); ++i)
    {
        Matrix[i].resize(m);
    }
}
 
void AbstractMatr::swap(AbstractMatr& Ob)
{
    Matrix.swap(Ob.Matrix);//Меняем местами значения вектора
}
 
void Prufer::Code()
{
    for(int i=0; i!=GetRow(); ++i)
        Nodes.push_back(i+1);//Записываем в вершины элемент i+1
    for(int i=0; i!=GetRow(); ++i)
        Degrees.push_back(Degree(Nodes[i]-1));//Записываем в степени степень i элемента вектора Nodes - 1
    for(int t=0; t!=GetRow()-2; ++t)//От 0 до N-2
    {
        //Проверка на то, что наличие листьев
        if(std::count_if(Degrees.begin(), Degrees.end(), std::bind2nd(std::equal_to<int>(), 1))==0)
        {
            std::cout<<"On "<< t+1 <<" step\n";//Пишем на каком шаге
            //Кидаем исключение, которое будет обработано в main(). Используем стандартный класс
            //std::invalid_argument
            throw std::invalid_argument("Can`t code this graph (tree). There are no nodes with degree 1\n");
        }
        for(int i=0; i!=Nodes.size(); ++i)//От 0 до размера вектора вершин
        {
            if(Degrees[i]==1)//Если i-ая вершина - лист
            {
                if(IsMin(Nodes[i]))//Если i-ая вершина минимальна
                {
                    int Adj=Adjacent(Nodes[i]-1);//Возвращаем смежную с i-1 вершиной вершину
                    Pruf.push_back(Adj+1);//Добавляем в вектор кода Прюфера, смежную вершину+1
                    DeleteEdge(Nodes[i]-1, Adj);//Удаляем ребро Nodes[i]-1, Adj
                    //Удаляем из вектора вершин i-тую вершину
                    Nodes.erase(std::remove(Nodes.begin(), Nodes.end(), Nodes[i]), Nodes.end());
                    Degrees.clear();//Очищаем вектор степеней
                    for(int i=0; i!=Nodes.size(); ++i)
                    {
                        Degrees.push_back(Degree(Nodes[i]-1));//Заполняем вектор степеней
                    }
                    break;//Брякаем цикл
                }
            }
        }
    }
    Edges.push_back(std::make_pair<int, int>(Nodes[0], Nodes[1]));//Записываем ребро Nodes[0]->Nodes[1] в вектор ребер
    std::cout<<"Prufer`s code\n";//Вывод в консоль строки
    std::copy(Pruf.begin(), Pruf.end(), std::ostream_iterator<int>(std::cout, " "));//Вывод в консоль вектора
    std::cout<<std::endl;//Перевод каретки+очистка буфера
}
 
void Prufer::Decode()
{
    std::pair<int, int> Temp;//Создаем временный элемент типа пары двух интовых значений
    Temp=Edges.front();//Записываем первый элемент из вектора ребер во временный элемент
    Edges.clear();//Чистим вектор ребер
    Nodes.clear();//Чистим вектор вершин
    for(int i=0; i!=Matrix.size(); ++i)
        Nodes.push_back(i+1);//Записываем i+1 вершину (дабы начиналось с 1)
    for(int t=0; t!=GetRow()-2; ++t)//До N-2
    {
        for(int i=0; i!=Nodes.size(); ++i)
        {
            if(!IsInPruf(Nodes[i]))//Если не i-тая вершина не выходит в код прюфера
            {
                if(IsMinNode(Nodes[i], i))//И если она минимальная среди вершин
                {
                    //Делаем пару интовых значений. Первый элемент вектора Прюфера и i-тую вершину.
                    //Записываем ее в вектор ребер
                    Edges.push_back(std::make_pair<int, int>(Pruf[0], Nodes[i]));
                    //Удаляем i-тую вершину
                    Nodes.erase(std::remove(Nodes.begin(), Nodes.end(), Nodes[i]), Nodes.end());
                    Pruf.erase(std::find(Pruf.begin(), Pruf.end(), Pruf[0]));//Удаляем первый элемент из в. Прюфера
                    break;//Брякаем
                }
            }
        }
    }
    Edges.push_back(Temp);//Записываем в конец вектора значение, записанное во временной переменной
    std::cout<<"Decode from Prufers`s code\nDefault tree\n";//Вывод строки
    //Цикл по итератору. От начала вектора ребер, до конца.
    for(std::vector<std::pair<int, int> >::const_iterator Iter=Edges.begin(); Iter!=Edges.end(); ++Iter)
    {
        std::cout<<"<"<<Iter->first<<','<<Iter->second<<'>'<<'\n';//Выводим в консоль <вершина из прюфера, вершина из nodes>
    }
}
 
int Prufer::Degree(int row)
{
    int cnt=0;//Счетчик
    for(int j=0; j!=GetCol(); ++j)//До кол-ва столбцов
    {
        if(Matrix[row][j]==1)//Если j-ый элемент строки row равен 1
            cnt++;//Плюсуем счетчик
    }
    return cnt;
}
 
int Prufer::Adjacent(int row)
{
    int i;
    for(i=0; i!=GetCol(); ++i)
        if(Matrix[row][i]==1)//Если i-ый элемент строки row равен 1
            break;//Брякаем
    return i;//Вернули i
}
 
bool Prufer::IsMin(int elem)
{
    int min=elem;//min=elem
    for(int i=0; i!=Degrees.size(); ++i)
    {
        if(Degrees[i]==1)//Если i-ая степень=1 
        {
            if(Nodes[i]<min)//Если i-ая вершина меньше минимума
                min=Nodes[i];//Минимум становится равен i-ой вершине
        }
    }
    return (min==elem);//Если min==elem возвращаем true, иначе false
}
 
void Prufer::DeleteEdge(int row, int col)
{
    Matrix[row][col]=0;//col-тый элемент в row-той строке равен 0
    Matrix[col][row]=0;//наоборот
}
 
std::ostream& operator <<(std::ostream& os, const Prufer& Ob)
{
    for(int i=0; i!=Ob.GetRow(); ++i)
    {
        //Вывод на экран. Стандартный алгоритм copy
        std::copy(Ob.Matrix[i].begin(), Ob.Matrix[i].end(), std::ostream_iterator<int>(os, " "));
        os<<'\n';
    }
    return os;
}
 
std::istream& operator >>(std::istream& is, Prufer& Ob)
{
    for(int i=0; i!=Ob.GetRow(); ++i)
    {
        for(int j=0; j!=Ob.GetCol(); ++j)
        {
            if(i>=j)//Если i>=j переходим к след итерации
                continue;
            std::cout<<"Enter 1 for connect "<< i+1 <<" and "<< j+1 <<" nodes, and 0 for not\n";
            is>>Ob.Matrix[i][j];
            if(i!=j)//Если i!=j
                Ob.Matrix[j][i]=Ob.Matrix[i][j];//
        }
    }
    return is;
}
 
bool Prufer::IsInPruf(int elem)
{
    for(int i=0; i!=Pruf.size(); ++i)
    {
        if(elem==Pruf[i])//Если элемент = Pruf[i]
        {
            return true;//Вернули true. То есть элемент присутствует в Прюфере
        }
    }
    return false;//Вернули false. Элемента нет. Все гуд
}
 
bool Prufer::IsMinNode(int elem, int row)
{
    int min=elem;//Минимум = элемент
    for(int i=row; i!=Nodes.size(); ++i)//От номера элемента в массиве до конца
    {
        if(Nodes[i]<min)
            min=Nodes[i];
    }
    return (min==elem);
}
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//Main.cpp
#include <iostream>
 
#include "Prufer.h"
 
int main()
{
    Prufer Ob;//Создали объект
    int N;
    std::cout<<"Enter N: ";
    std::cin>>N;//Ввели размер
    Ob.SetSize(N, N);//Установили размер для квадратной матрицы
    std::cout<<"Enter matrix\n";
    std::cin>>Ob;//Ввели матрицу
    std::cout<<"Initial matrix\n";
    std::cout<<Ob;//Вывели матрицу
    try//Блок try, catch
    {
        Ob.Code();//Вызвали кодирование. Если в функции кинулось исключение - перешли в блок catch
        Ob.Decode();//Если нет - декодируем дерево
    }
    catch(const std::invalid_argument& e)//Ловим исключение типа const std::invalid_argument&
    {
        std::cout<<e.what()<<'\n';//what - функция класса invalid_argument.
    }
    system("pause");//Для release версии
    return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 00:52. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru