Форум программистов, компьютерный форум 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
В астрале
Эксперт С++
7969 / 4731 / 320
Регистрация: 24.06.2010
Сообщений: 10,539
Завершенные тесты: 3
12.11.2010, 23:49  [ТС]     Дискретная математика
Алгоритм Флойда-Уоршала. Поиск матрицы кратчайших путей. Матрица вершин через которые проходят кратчайшие пути. Поиск кратчайшего пути между двумя вершинами.
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
//Floyd.h
#ifndef _FLOYD_H_
#define _FLOYD_H_
 
#include <vector>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <stack>
 
typedef std::vector<std::vector<int> > VM;
typedef std::stack<int> ST;
 
class MatrixAdj
{
public:
    MatrixAdj()
    {
    }
 
    virtual ~MatrixAdj()
    {
    }
 
    void SetSize(const size_t n)
    {
        Matr.resize(n);
        for(size_t i=0; i<n; ++i)
            Matr[i].resize(n);
    }
 
    void Fill()
    {
        for(size_t i=0; i<Matr.size(); ++i)
        {
            for(size_t j=0; j<Matr.size(); ++j)
            {
                if(i==j)
                    Matr[i][j]=0;
                else if(i>j)
                {
                    Matr[i][j]=Matr[j][i];
                }
                else
                {
                    std::cout<<"Enter weight of V"<< i <<",V"<< j <<" edge\n"
                        <<"0 for not connect them\n";
                    std::cin>>Matr[i][j];
                    if(Matr[i][j]==0)
                        Matr[i][j]=100;
                }
            }
        }
    }
protected:
    VM Matr;
};
 
class Floyd:public MatrixAdj
{
public:
    Floyd():MatrixAdj()
    {
    }
 
    ~Floyd()
    {
    }
 
    void Initialise()
    {
        MatrPath.resize(Matr.size());
        for(size_t i=0; i<Matr.size(); ++i)
            MatrPath[i].resize(Matr.size());
        for(size_t i=0; i<MatrPath.size(); ++i)
        {
            for(size_t j=0; j<MatrPath.size(); ++j)
            {
                if(Matr[i][j]==100)
                    MatrPath[i][j]=100;
                else
                    MatrPath[i][j]=j;
            }
        }
        Copy();
    }
    
    void FindPathMatr()
    {
        for(size_t k=0; k<Matr.size(); ++k)
        {
            for(size_t i=0; i<Matr.size(); ++i)
            {
                for(size_t j=0; j<Matr.size(); ++j)
                {
                    int b=MatrSPath[i][k]+MatrSPath[k][j];
                    if(b<MatrSPath[i][j])
                    {
                        MatrSPath[i][j]=b;
                        MatrPath[i][j]=k;
                    }
                }
            }
        }
    }
 
    void FindPath(size_t first, size_t second)
    {
        if(first>=MatrPath.size() || second>=MatrPath.size())
            throw std::invalid_argument("One of nodes for searching is more than Matr size");
        ST Goals;
        Path.push(first);
        Goals.push(second);
        while(!Goals.empty())
        {
            int u=Path.top();
            int v=Goals.top();
            int s=MatrPath[u][v];
            if(v==s)
            {
                Path.push(v);
                Goals.pop();
            }
            else
                Goals.push(s);
        }
    }
 
    void PrintWMatr(std::ostream& os) const
    {
        PrintMatr(Matr, os);
    }
 
    void PrintSPMatr(std::ostream& os) const
    {
        PrintMatr(MatrSPath, os);
    }
 
    void PrintPMatr(std::ostream& os) const
    {
        PrintMatr(MatrPath, os);
    }
 
    void PrintSt(std::ostream& os)
    {
        while(!Path.empty())
        {
            os<<Path.top()<<' ';
            Path.pop();
        }
        os<<'\n';
    }
private:
    VM MatrPath;
    VM MatrSPath;
    ST Path;
    
    void PrintMatr(const VM& Vec, std::ostream& os) const
    {
        for(size_t i=0; i<Vec.size(); ++i)
        {
            for(size_t j=0; j<Vec.size(); ++j)
            {
                os<<std::setw(3)<<Vec[i][j]<<' ';
            }
            os<<'\n';
        }
    }
 
    void Copy()
    {
        MatrSPath.resize(Matr.size());
        for(size_t i=0; i<Matr.size(); ++i)
            MatrSPath[i].resize(Matr.size());
        for(size_t i=0; i<Matr.size(); ++i)
            std::copy(Matr[i].begin(), Matr[i].end(), MatrSPath[i].begin());
    }
};
 
std::ostream& operator <<(std::ostream& os, const Floyd& Ob)
{
    os<<"Weight matrix\n";
    Ob.PrintWMatr(os);
    os<<"Shortest paths matrix\n";
    Ob.PrintSPMatr(os);
    os<<"Shortest path nodes matrix\n";
    Ob.PrintPMatr(os);
    return os;
}
 
#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
//Floyd.cpp
#include "Floyd.h"
 
int main()
{
    try
    {
        int n;
        std::cout<<"Enter numb of nodes: ";
        std::cin>>n;
        Floyd Ob;
        Ob.SetSize(n);
        Ob.Fill();
        Ob.Initialise();
        Ob.FindPathMatr();
        std::cout<<Ob;
        size_t first, second;
        std::cout<<"Enter first and second nodes for search path between them\n";
        std::cin>>first>>second;
        Ob.FindPath(first, second);
        std::cout<<"Shortest path between " << first <<" and "<< second <<" nodes is\n";
        Ob.PrintSt(std::cout);
    }
    catch(std::exception& e)
    {
        std::cerr<<e.what()<<'\n';
        return 1;
    }
    return 0;
}
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru