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

Найти максимальное по числу вершин подмножество - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ создать класс BufStr http://www.cyberforum.ru/cpp-beginners/thread776100.html
помогите создать класс пожалуйста.Разработать класс , содержащий указатель на строку, а также функции ввода этой строки из внешнего массива, файла или объекта такого же класса, функцию, возвращающую указатель на копию строки, функцию записи строки в файл. Разработать программу тестирования объекта данного класса. Добавлено через 22 минуты интерфейс а дальше вот как не понимаю((( class BufStr...
C++ Генератор случайных чисел Как написать генератор случайных (пусть и псевдо) чисел, выдающий на выходе целые случайные числа от 1 до 10 и в кол-ве 10-и и без повторов. Тоесть надо на выходе получить 10 случайных чисел без повторов от 1-го до 10-и http://www.cyberforum.ru/cpp-beginners/thread776087.html
C++ Непонятно условие. Основы С++ (Найти все слова, в которых доля букв a, b максимальна)
Добрый день. Задали решить пару задач из задачника Абрамова. Только условия вообще не могу понять! Помогите, пожалуйста, чем-нибудь!! Заранее благодарен!! Тема: Программирование задач по обработке последовательности символов. Задача 808в Дан текст. Группы символов, разделенные пробелами (одним или несколькими) и не содержащие пробелов внутри себя, будем называть, как прежде (см. задачу...
Непонятно условие. Основы С++ (найти в S1,…,Sn все слова, из которых могло бы получиться a1,…,a10 в результате одной ошибки) C++
Добрый день. Задали решить пару задач из задачника Абрамова. Только условия вообще не могу понять! Помогите, пожалуйста, чем-нибудь!! Заранее благодарен!! Тема: Программирование задач по обработке последовательности символов. Задача 366 (3) Даны символы a1,…,a10, натуральное число n , символы S1,…,Sn . Как и в предидущей задаче, будем рассматривать слова, входящие в последовательность...
C++ Однотипный вызов функции http://www.cyberforum.ru/cpp-beginners/thread776039.html
У меня много функций. Мне нужно в начале каждой из этих функций делать вызов еще одной, можно ли это как нибудь автоматически сделать? Вот пример void a() { fun(); } void b() {
C++ Алгоритм на языке псевдокода (Преобразовать одномерный массив) Было задание в борланде - Преобразовать одномерный массив, состоящий из 10(любых) вещественных элементов, таким образом, чтобы сначала располагались все положительные элементы, а потом - все отрицательные ( элементы, равные 0, считать положительными). код готовой проги #include <iostream.h> #define N 10 int main(){ int i, j; float a, t; подробнее

Показать сообщение отдельно
ChuckNorris
2 / 2 / 0
Регистрация: 25.10.2012
Сообщений: 42
03.06.2013, 16:55     Найти максимальное по числу вершин подмножество
Цитата Сообщение от kitiket22 Посмотреть сообщение
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
#include "stdafx.h"
#include <iostream>
#include <conio.h>
using namespace std;
struct Bow
{
    int vertex1, vertex2;
};
int** AdjMatrix(Bow *Bows, int BowNumber, int VertexNumber)
{
    int **AdjMatr = new int*[VertexNumber];     
 
    for(int i = 0; i < VertexNumber; i++)
        AdjMatr[i] = new int[VertexNumber];     
    for( int i = 0; i <  VertexNumber; i++)
        for( int j = 0; j < VertexNumber; j++)
            AdjMatr[i][j] = 0;                  
    for( int i = 0; i < BowNumber; i++)         
    {
        AdjMatr[ Bows[i].vertex1 - 1][Bows[i].vertex2 - 1] = 1;         AdjMatr[ Bows[i].vertex2 - 1][Bows[i].vertex1 - 1] = 1; 
    }
                                                
return AdjMatr;
};
 
Bow* FindunAdj(Bow *Bows, int BowNumber, int VertexNumber, int *count)
{
    int maxnumb = VertexNumber*( VertexNumber - 1 )/2;  
    *count = 0;                                         
    Bow *temp =  new Bow[maxnumb];                      
 
    int** AdjMatr = AdjMatrix(Bows, BowNumber, VertexNumber);   
 
    for ( int i = 0; i < VertexNumber; i++)
        for( int j = i + 1; j < VertexNumber; j++)
            if ( AdjMatr[i][j] != 1 )   
            {
                temp[*count].vertex1 = i + 1;
                temp[*count].vertex2 = j + 1;
                (*count)++;
            }
    Bow* UnAdj =  (Bow*) realloc (temp, *count * sizeof(Bow));  
    return UnAdj;
};
 
int _tmain(int argc, _TCHAR* argv[])
{
    int BowNumber, VertexNumber; 
    Bow *Bows;  
 
    printf("Vvedite kol-vo vershin.\n");
    scanf("%d", &VertexNumber);         
    printf("Vvedite kol-vo dug.\n");
    scanf("%d", &BowNumber);                
    Bows = new Bow[BowNumber];              
    printf("Vvedite dugi\n");
    for ( int j = 0; j < BowNumber; j++)    
    {
        do
        {
            printf( "Duga %d\n", j + 1);
            printf("Vvedite nachalnuu i konechnuu vershinu\n");
            scanf("%d %d", &Bows[j].vertex1, &Bows[j].vertex2); //      }
        while ( !( ( Bows[j].vertex1 <= VertexNumber )  && ( Bows[j].vertex2 <= VertexNumber )  && ( Bows[j].vertex1 > 0 )  && ( Bows[j].vertex2 > 0 ) ) );
    }
    
    printf("V grafe %d vershin i %d dug\n", VertexNumber, BowNumber);
    for ( int j = 0; j < BowNumber; j++ )   // 
    {
        printf("Duga %d { %d, %d }\n", j + 1, Bows[j].vertex1, Bows[j].vertex2);
    }
    int count;                                  Bow *UnAdj = FindunAdj(Bows, BowNumber, VertexNumber, &count);  for( int i = 0; i < count; i++)
        printf("Para 1 { %d, %d }\n", UnAdj[i].vertex1, UnAdj[i].vertex2); 
    delete[](UnAdj);
    getch();
    return 0;
}
Добавлено через 6 часов 23 минуты
С описанием
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
// lab1.cpp: определяет точку входа для консольного приложения.
//
 
#include "stdafx.h"
#include <iostream>
#include <conio.h>
using namespace std;
// структура Bow состоит из двух целых чисел vertex1 и vertex2
struct Bow
{
    int vertex1, vertex2;
};
//Создание матрици смежности. Входные параметры: дин.массив дуг, кол-во дуг, и вол-во вешин
//Возвращает дин. двумерный массив (матрицу) определяющий граф, т.к. граф - динамический, то и 
//матрица динамическая и возвращается указатель на неё.
int** AdjMatrix(Bow *Bows, int BowNumber, int VertexNumber)
{
    int **AdjMatr = new int*[VertexNumber];     //Выделение памяти для строк
    for(int i = 0; i < VertexNumber; i++)
        AdjMatr[i] = new int[VertexNumber];     //Выделение памяти столбцов
    for( int i = 0; i <  VertexNumber; i++)
        for( int j = 0; j < VertexNumber; j++)
            AdjMatr[i][j] = 0;                  //Изначально она заполняется нулями
    for( int i = 0; i < BowNumber; i++)         //Создается матрица смежности. Если есть дуга от а до b, то в [a,b] ставится еденица
    {
        AdjMatr[ Bows[i].vertex1 - 1][Bows[i].vertex2 - 1] = 1; // Заполнение матрицы.
        AdjMatr[ Bows[i].vertex2 - 1][Bows[i].vertex1 - 1] = 1; //Вычитается единица из-за особенностей работы С++ с матрицами,
    }                                           // итерация идет с 0 по BowNumber - 1 элемент
    return AdjMatr;
};
//Изначально не известно сколько всего искомых пар елементов, поэтому берется максимально возможное значение
//Во входных параметрах подается указатель на интовое число, в него запишется кол-во найденых пар элементов
// а, так как обращение идет по адресу, то значение не потеряется после выполнения функции
//Когда все пары найдены, происходит перевыделение памяти и часть освобождается
Bow* FindunAdj(Bow *Bows, int BowNumber, int VertexNumber, int *count)
{
    int maxnumb = VertexNumber*( VertexNumber - 1 )/2;  // Для нахождения нужных вершин нужно обработать только половину матрицы
    *count = 0;                                         // Так, как матрица симметрицна относительно диагонали
    Bow *temp =  new Bow[maxnumb];                      // Так как изначально неизвестно сколько искомых вешин, выделяется память на максимально их число
    int** AdjMatr = AdjMatrix(Bows, BowNumber, VertexNumber);   //Это число является треугольным и вычисляется по формуле n*(n + 1)/2;
    for ( int i = 0; i < VertexNumber; i++)
        for( int j = i + 1; j < VertexNumber; j++)
            if ( AdjMatr[i][j] != 1 )   //если не смежно не равно 1
            {
                temp[*count].vertex1 = i + 1;
                temp[*count].vertex2 = j + 1;
                (*count)++;
            }
    Bow* UnAdj =  (Bow*) realloc (temp, *count * sizeof(Bow));  //Вперевыделяестя память с освобождение лишней памяти
    return UnAdj;
};
 
int _tmain(int argc, _TCHAR* argv[])
{
    int BowNumber, VertexNumber; // Содержит кол-во дуг и вершин для каждого графа ( Bow - дуга, Vertex - вершина )
    Bow *Bows;  // Заранее не известно какого размера граф, поэтому память выделяется динамически в дин. массив структуры Bow (структура Bow описана выше)
                                    // Ввод начальных данных
    printf("Vvedite kol-vo vershin.\n");
    scanf("%d", &VertexNumber);         // Кол-во вершин
    printf("Vvedite kol-vo dug.\n");
    scanf("%d", &BowNumber);                // Кол-во дуг
    Bows = new Bow[BowNumber];              // Выделение памяти под массив дуг
    printf("Vvedite dugi\n");
    for ( int j = 0; j < BowNumber; j++)    // Ввод
    {
        do
        {
            printf( "Duga %d\n", j + 1);
            printf("Vvedite nachalnuu i konechnuu vershinu\n");
            scanf("%d %d", &Bows[j].vertex1, &Bows[j].vertex2); // Вводятся 2 числа начала и конца дуги
        }//Защита от дурака: проверяется введены ли такие значения, которые пренадлежат множеству вешин. Множество вершин {1, ..., VertexNumber }
        while ( !( ( Bows[j].vertex1 <= VertexNumber )  && ( Bows[j].vertex2 <= VertexNumber )  && ( Bows[j].vertex1 > 0 )  && ( Bows[j].vertex2 > 0 ) ) );
    }
    // Вывод всех введённых данных
    printf("V grafe %d vershin i %d dug\n", VertexNumber, BowNumber);
    for ( int j = 0; j < BowNumber; j++ )   // Zapusk cikla
    {
        printf("Duga %d { %d, %d }\n", j + 1, Bows[j].vertex1, Bows[j].vertex2);
    }
    int count;                              // Создается счетчик найденых пар, его адрес передается в функции FindAdj и все изменения в ней произошедшис с count сохранятся
    Bow *UnAdj = FindunAdj(Bows, BowNumber, VertexNumber, &count); //Выполнение функции поиска нужных вершин
    for( int i = 0; i < count; i++)
        printf("Para 1 { %d, %d }\n", UnAdj[i].vertex1, UnAdj[i].vertex2); // Вывод найденых пар
    delete[](UnAdj);
    getch();
    return 0;
}

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