Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/7: Рейтинг темы: голосов - 7, средняя оценка - 5.00
Tedorius
7 / 7 / 2
Регистрация: 12.06.2012
Сообщений: 59
1

Вывести все возможные комбинации цепочек в матрице смежности

07.12.2012, 17:20. Просмотров 1356. Ответов 10
Метки нет (Все метки)

Есть матрица смежности вида:
AB0
BCD
DD0
CKN
NE0
KB0
Т.е. если в конце строки 0, то из одного узла есть связь только к одному узлу, иначе - к двум.
Задача: вывести все возможные комбинации цепочек.
Результат:
ABDD
ABCKB
ABCNE
Возможно есть очень простой алгоритм решения этой задачи, но вот как я думаю надо делать:
Кроме матрицы смежности, надо создать дополнительную матрицу(для удобства) куда будут записываться те узлы, у которых есть два выхода и создать рекурсивную функцию для нахождения всех цепочек. Цепочки можно записывать в еще одну матрицу.
Код реализации нахождения цепочки выкладывать не буду, ибо он не правильный...выложу оболочку:
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
#include "stdafx.h"
#include <iostream> 
#include <fstream>
#include <time.h> 
#include <iomanip>
#include <string>
 
using namespace std;
 
int main()
{
    char arr[1000][4];
    char arrPred[1000][4];
    char temp[10];
    char temparr[1000][1000];
    int i=1,j=0,n,m,l=0;
    int k=0,p=0;
    
    system("cls");
    setlocale(LC_ALL,"Rus") ;
    fstream file("data.txt") ;  
    //////////////////////////////
    cout<<"Матрица смежности: \n";
    while(!file.eof())
    {
        
        j++;
        file >> arr[i][j] ; 
 
        if(file.eof())
        {
            break;
        }
        cout << setw(4)<< arr[i][j];
 
        if(j%3==0)
        {           
            j=0;
            i++;    
            cout<<"\n";
        }
                
    }
    ////////////////////////////
    n=i;
    m=3;
    i=0;
    int a=0;
    int b=2;
    temparr[0][0]=arr[1][1];
    temparr[0][1]=arr[1][2];
    temp[0]=temparr[0][1];
    //////////////////////////////////////////////////////
    
    /////////////////////////////////////
    for(int i=1;i<n;i++)// нахождение предикатных узлов
    {
        
        if(arr[i][m]!='0')
        {
            for(int z=0;z<m;z++)
            {
            arrPred[k][z]=arr[i][z+1];
            }
            k++;    
        }
    }
    /////////////////////////////////////
    for(int i=1;i<n;i++)//нахождение цепочек
    {//реализация
                //Примерный алгоритм:
        //если в конце строки 0 то присвоить в матрицу ответов 1 и 2 элемент первой строки матрицы смежности
        //присвоить temp 2й элемент первой строки
        //////1-если temp=первому элементу одной из следующих строк и в этой строке в конце 0
        //присвоить второй элемент строки в матрицу ответов
        //присвоить temp=второй элемент строки
        //////2-если равен и в конце не 0 //рекурсивная функция
        //проверить не является ли 2 и 3 элемент строки предикатным узлом(по дополнительну массиву предикатных узлов)
        //если является то проверить не являются ли в свою очередь выходящие из этого узла элементы предикатными//рекурсия
        //как-то запомнить все цепочки
        //и вывести
        //////3- если не равен - конец цепочки
        }
        ///////////////////////////////////////////////////////
    cout <<"\n\n\n"<< endl ; 
    //////////////////////////////
    system ("pause");
    return 0;
}
Также прикрепляю файл с данными(матрицей смежности).
0
Вложения
Тип файла: txt data.txt (40 байт, 11 просмотров)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.12.2012, 17:20
Ответы с готовыми решениями:

Нужно вывести все возможные возрастающие 6-ти значные комбинации
Задачка: Нужно вывести все возможные возрастающие 6-ти значные комбинации из...

Вывести все возможные комбинации трех натуральных чисел x, y и z до 36 с определенными условиями
Всем привет, ребят, нужно написать программу вывода на экран всех возможных...

Массивы. Вычислить по формуле и вывести на экран все возможные комбинации сумм чисел
Доброго всем времени суток.Я делаю только первые шаги в программировании.Начал...

Все возможные комбинации 5 чисел
В общем задача такая: Нужно, чтобы программа выдавала все возможные комбнации...

Все возможные комбинации из 10 цифр по n
есть 10 цифр, нужно написать программу, где вводишь n-кол-во чисел в...

10
Tedorius
7 / 7 / 2
Регистрация: 12.06.2012
Сообщений: 59
07.12.2012, 23:14  [ТС] 2
Неужели никто не может помочь?

Добавлено через 4 часа 42 минуты
Актуально
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
07.12.2012, 23:48 3
Поиск в глубину, не? А наличие повторной строки проверять при помощи добавления map.
0
Tedorius
7 / 7 / 2
Регистрация: 12.06.2012
Сообщений: 59
08.12.2012, 00:07  [ТС] 4
Это не поиск в глубину, т.к. у меня не дерево и связи могут быть с абсолютно любым узлом.
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
08.12.2012, 00:08 5
А почему поиск в глубину и сразу - на дереве? его можно прикрутить много к чему, и не только к деревьям.
0
Tedorius
7 / 7 / 2
Регистрация: 12.06.2012
Сообщений: 59
08.12.2012, 00:09  [ТС] 6
В этом и заключается проблема. Мне надо остановить цепочку если узел уже описывался.

Добавлено через 31 секунду
Ну помогите с реализацией тогда =)
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
08.12.2012, 00:12 7
А какие ограничения на количество вершин?
0
Tedorius
7 / 7 / 2
Регистрация: 12.06.2012
Сообщений: 59
08.12.2012, 00:15  [ТС] 8
Вы имеете в виду количество выходов из вершины? тогда два. Если имеете в виду общее количество вершин, то сколько угодно.
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
08.12.2012, 00:15 9
Сколько угодно? Многовато.
0
Tedorius
7 / 7 / 2
Регистрация: 12.06.2012
Сообщений: 59
08.12.2012, 00:17  [ТС] 10
Ну скажем 20. Разве это имеет значение? Мы же просто задаем в матрице смежности связи и проходим по ней.
0
Dani
1393 / 637 / 134
Регистрация: 11.08.2011
Сообщений: 2,299
Записей в блоге: 2
Завершенные тесты: 1
08.12.2012, 00:19 11
Tedorius, 20? Это меняет дело.
Как можно сделать (версия для маленьких значений): на первое место в исходной строке ставим всевозможные вершины, на второе - не посещенного ранее соседа первой вершины и т.д.
0
08.12.2012, 00:19
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.12.2012, 00:19

Все возможные комбинации из 4 цифр
Доброго времени суток! Прошу помочь с такой задачей: Пользователь вводит...

Все возможные комбинации длины k из 0 и 1
Как бы это реализовать? Подкиньте идей или может есть готовая у кого-то. Ввод...

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


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru