Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.80
Tedorius
7 / 7 / 0
Регистрация: 12.06.2012
Сообщений: 59
#1

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

07.12.2012, 17:20. Просмотров 1332. Ответов 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
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Вывести все возможные комбинации цепочек в матрице смежности (C++):

Нужно вывести все возможные возрастающие 6-ти значные комбинации - C++
Задачка: Нужно вывести все возможные возрастающие 6-ти значные комбинации из промежутка чисел &lt;0,100&gt; Подкиньте пару идей.

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

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

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

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

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

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

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

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

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

Найти все возможные комбинации по номеру карты - C++
Все привет!!! Выручайте с этим кодом уже вожусь почти неделю и не могу с ним нечего сделать #include &quot;stdafx.h&quot; #include &lt;iostream&gt; ...

Найти все возможные комбинации четырех букв - C++
Есть задача с 4 буквами.A,B,C,D нужно найти все возможные комбинации этих букв. Комбинации если я не путаю не чего считаются так...

Написать программу, выводящую все возможные трехзначные комбинации с числами от 0 до 9 - C++
Нужно написать программу выводящую все возможный трехзначные комбинации с числами от 0 до 9. Вот как это сделать? Буду рад даже совету.


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

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

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