Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.55/11: Рейтинг темы: голосов - 11, средняя оценка - 4.55
0 / 0 / 2
Регистрация: 17.12.2013
Сообщений: 11

Найти вероятность существования пути в графе между заданными точками

24.03.2014, 19:12. Показов 2037. Ответов 1
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Запутался в рекурсии. Смысл задачи: найти вероятность существования пути в графе между заданными точками. Смысл функции gen() на данном этапе: генерирование всех возможных матриц смежности и проверка есть путь или нет с помощью функции poisk().
Алгоритм: из матрицы смежности графа последовательно берем ребро и рекурсивно строим матрицы с существованием ребра и несуществованием ребра.
Все функции работают правильно кроме функции gen() - она выводит повторяющиеся матрицы, что в принципе по алгоритму быть не должно.
Кому не лень посмотрите код и покидайте идеи - у меня они кончились) Заранее благодарю

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
#include <iostream>
#include <vector>
#include <fstream>
#define M 4
#define P 0.1
 
using namespace std;
int graph[M][M]={
    {0,1,1,1},
    {1,0,0,0},
    {1,0,0,1},
    {1,0,1,0}
};
bool matrix[M][M]={0};
 
int count_paths(){
    int elements=0;
    for(int i=0;i<M;i++)
        for(int j=0;j<M;j++)
            if(graph[i][j])
                elements++;
    return elements/2;
}
 
vector<int>get_nodes(int node, int g[M][M]){
    vector<int> nodes;
    int j=0;
    for(int i=node;j<M;j++)
    {
        if(g[i][j])
            nodes.push_back(j);
    }
    return nodes;
}
 
float result=0;
void res(int path_size,int etc){
    result+=pow(P,path_size)*pow((1-P),etc);    
}
 
bool is_element(vector<int> nodes,int element){
    for(vector<int>::iterator it=nodes.begin(); it != nodes.end(); ++it)
    {
        if(*it==element)
            return true;
    }
    return false;
}
 
vector<int> used;
bool poisk(int from, int to, int g[M][M]){//, vector<int>&path){
    if(from==to)
    {
        used.erase(used.begin(),used.end());
        return 1;
    }
    else{
        vector<int> nodes=get_nodes(from,g);//все смежные вершины нужной вершины
        used.push_back(from);
        for(vector<int>::iterator it=nodes.begin(); it != nodes.end(); ++it)
        {
            if(is_element(nodes,*it) && !is_element(used,*it))
            {
                if(poisk(*it,to,g))//,path))
                    return 1;
            }
        }
    }
    return 0;
}
 
void clear(){
    for(int i=0;i<M;i++)
        for(int j=0;j<M;j++)
            matrix[i][j]=0;
}
ofstream ofs ("test.txt", std::ofstream::out);
void show(int g[M][M]){
    for(int i = 0 ; i < M; i++){
        for(int j = 0;j < M; j++)
            cout<<g[i][j];
        cout<<endl;
    }
    cout<<endl;
}
int cp=0;
 
void gen(int X, int Y, int from, int to, int g[M][M]){
    for(int i = X ; i < M; i++)
        for(int j = Y;j < M; j++){
            if(g[i][j] == 1 && j>i)//мы идем по ребрам графа
            {
                g[i][j] = 0;
                if(poisk(from,to,g))
                    cp++;
                else{}
                show(g);
                if(j+1<M && i<M)
                    gen(i,j+1,from,to,g);//считаем если ребра нет
                else if(i+1<M && j>=M){
                    gen(i+1,0,from,to,g);//считаем если ребра нет
                }
 
                g[i][j] = 1;
                if(j+1<M && i<M)
                    gen(i,j+1,from,to,g);//считаем если ребро есть
                else if(i+1<M && j>=M){
                    gen(i+1,0,from,to,g);//считаем если ребро есть
                }
 
            }
        }
}
 
int main(){
    int copy[M][M];
    for(int i=0;i<M;i++)
        for(int j=0;j<M;j++)
            copy[i][j] = graph[i][j];
    gen(0,0,0,3,copy);
    ofs.close();
    return 0;
}
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
24.03.2014, 19:12
Ответы с готовыми решениями:

Найти кратчайшие пути между двумя заданными точками графа
Добрый вечер. Кто сможет написать программу для задачи, буду очень признателен 4) Найти кратчайшие пути из точки D1 в точку D8 Вот...

Найти кратчайшие расстояния между заданными точками в графе
Найти кратчайшие расстояния между заданными точками в графе в соответствии с вариантом. Для всех вариантов использовать алгоритм...

Найти расстояние между заданными точками
Даны точки (х1, у1), (х2, у2). Найти расстояние между ними

1
0 / 0 / 2
Регистрация: 17.12.2013
Сообщений: 11
25.03.2014, 19:41  [ТС]
Если кому-то было интересно, я нашел ответ:
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
void gen(int X, int Y, int from, int to, int g[M][M]){
    bool f1 = true;
    for(int i = X ; i < M; i++){
        for(int j = Y;j < M; j++){
            if(g[i][j] == 1 && j>i && f1)//мы идем по ребрам графа
            {
                f1=false;
                g[i][j] = 0;
                if(poisk(from,to,g)){//главный подсчет
                    probab_way += probabulity(g);
                    cp++;
                }
                bool flag1 = true, flag2 = true;
                if(j+1<M && i<M){
                    flag1=false;
                    gen(i,j+1,from,to,g);//считаем если ребра нет
                }
                else if(i+1<M  && flag1){
                    gen(i+1,0,from,to,g);//считаем если ребра нет
                }
                g[i][j] = 1;
                if(j+1<M && i<M){
                    gen(i,j+1,from,to,g);//считаем если ребро есть
                    flag2 = false;
                }
                else if(i+1<M && flag2){
                    gen(i+1,0,from,to,g);//считаем если ребро есть
                }
            }
        }
    }
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
25.03.2014, 19:41
Помогаю со студенческими работами здесь

Найти расстояние между двумя точками с заданными координатами
Найти расстояние между двумя точками с заданными координатами (х1,у1),(х2,у2).

Найти расстояние между двумя точками с заданными координатами
Найти расстояние между двумя точками с заданными координатами (x1, y1) и (x2, y2).

Найти расстояние между двумя точками с заданными координатами
9. Найти расстояние между двумя точками с заданными координатами (x1, y1) и (x2, y2).

Найти расстояние между двумя точками с заданными координатами
Решите плиииз легенькую задачку) Очень надо Найти расстояние между двумя точками с заданными координатами (x1, y1) и (x2, y2).

Найти с процедурой расстояние между точками заданными в динамической массиве
У меня задание узнать периметр и расстояние между точками фигуры, которые определит пользователь. Проблема в том что я не знаю как это...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru