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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Помогу http://www.cyberforum.ru/cpp-beginners/thread722948.html
Всем привет!!! Язык программирования C++; Знания: немного STL; ООП; теория. Обращайтесь в ЛС!!!
C++ Проигрывание видео mp4, avi Доброго. Проблема собственно с проигрыванием видеофайлов. Пытался использовать DirectShow - он воспроизводит авишники но в каком то своем окне и нигде не нашел как это лечить. Пытался понять... http://www.cyberforum.ru/cpp-beginners/thread722905.html
C++ Какая-то неопределенность при наследовании
Всем привет! Прошу помощи. Суть: //A.h class A { A(); virtual ~A();
Дерево и длина строки C++
Есть пример дерева , где вычисляется наименьший его элемент. Помогите переписать код , чтобы найти самую короткую строку в дереве, элементы которого хранят какую-то строку. #include<iostream>...
C++ Алгоритм шифрования WAKE http://www.cyberforum.ru/cpp-beginners/thread722827.html
Пытаюсь реализовать алгоритм шифрования WAKE, нашел сайт, где функции вроде бы описаны, но не могу разобраться, как их применять, так же есть исходник, где видимо пытались реализовать алгоритм, но он...
C++ Сформировать произвольную матрицу Дано натуральное число N. Сформировать произвольную матрицу размерностью NxN. Найти минимальный из элементов, расположенных под главной диагональю, и максимальный из элементов, расположенных над... подробнее

Показать сообщение отдельно
Tedorius
7 / 7 / 0
Регистрация: 12.06.2012
Сообщений: 59

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

07.12.2012, 17:20. Просмотров 1291. Ответов 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 просмотров)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru