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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 5.00
asotel
2 / 2 / 0
Регистрация: 11.11.2010
Сообщений: 58
#1

таблица знакомств - C++

20.11.2010, 03:34. Просмотров 1243. Ответов 9
Метки нет (Все метки)

помогите написать программу

Имеется N человек и прямоугольная таблица знакомств А[1:N,1:N], в которой элемент A[i,j] равен 1, если человек i знаком с человеком j, и, соответственно, наоборот, А[i,j]=А[j,i]. Выяснить, можно ли разбить людей на 2 группы так, чтобы в каждой группе были только незнакомые люди.
Информация о знакомствах задается вводом, в первой строке которого находится число N<250, а в следующих N строках - таблица знакомств А (без пробелов)
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.11.2010, 03:34
Здравствуйте! Я подобрал для вас темы с ответами на вопрос таблица знакомств (C++):

Программа знакомств - C++
Здрям! Надо консольную программу написать. 3 строки: мужчины, женщины, подробный поиск. При выборе первой строки показывает всех...

Таблица лексем и таблица идентификаторов - C++
Помогите пожалуйста найти ошибку в коде. Прога строит ТИ и ТЛ. К таблице идентификаторов претензий нет, а вот в таблице лексем возникают...

Таблица в C++ - C++
Здравствуйте. Как выравнять ячейки в таблице без помощи пробелов? С пробелами получилось где-то так... #include &lt;stdio.h&gt; #include...

Таблица умножения - C++
Использовать двойной цикл for. В программе вводятся шестнадцатеричные числа m и n, после чего на экран выводится таблица умножения в...

Таблица истинности - C++
Всем привет. Задание следующее: Напечатать таблицу истинности для логической функции (картинка). Помогите - объясните задание,...

Таблица истинности - C++
Доброго времени суток. Хотел поинтересоваться, пытался ли кто нибудь реализовать таблицу истинности? Последнее время стал задумываться о...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
20.11.2010, 08:49 #2
Вариант:
Для решения этой задачи потребуется int mas[N] - будем его использовать в качестве очереди, и int mas1[N] - для установки номера группы (всего групп две: 1 и 2). Изначально всем элементам mas1[i] делаем значения 0.
Заносим в очередь номер 0 (первого человека). mas1[0]=1.
Затем цикл while()
- берем из очереди очередной номер человека. Проходим по таблице знакомств в соответствующей строке. Если A[i][j]==1, то смотрим на mas1[j]. Если mas1[j]==0, то делаем mas1[j]=2 (если mas1[i]=1) или mas1[j]=1 (если mas1[i]=2) и заносим j в очередь. Если mas1[i]==2 и mas1[j]==2 или mas1[i]==1 и mas1[j]==1, то выходим из цикла (в этом случаем разбить на 2 группы нельзя).
Если очередь закончилась и мы досрочно не вышли из цикла, то разбить на 2 группы можно.

Добавлено через 6 минут
У меня алгоритм не совсем полный (если будут существовать две или более изолированные группы), то мы таким алгоритмом просмотрим только одну изолированную группу. Нужно добавить рассмотренный алгоритм для всех изолированных групп. Но это не так и сложно.
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
20.11.2010, 11:16 #3
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
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
//////////////////////////////////////////////////////////////////////////////////////
//Имеется N человек и прямоугольная таблица знакомств А[1:N,1:N], 
//в которой элемент A[i,j] равен 1, если человек i знаком с человеком j, 
//и, соответственно, наоборот, А[i,j]=А[j,i]. 
//Выяснить, можно ли разбить людей на 2 группы так, чтобы в каждой группе 
//были только незнакомые люди.
//////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
//////////////////////////////////////////////////////////////////////////////////////
enum T_color
{
    NO_COLOR = 0,
    WHITE,
    BLACK    
};
//////////////////////////////////////////////////////////////////////////////////////
typedef std::string                   T_vertice;
typedef std::set<T_vertice>           T_vertices_set;
typedef std::vector<T_vertice>        T_vertices;
typedef T_vertices_set                T_edge;
typedef std::set<T_edge>              T_edges;
typedef std::map<T_vertice, bool>     T_row;
typedef std::map<T_vertice, T_row>    T_matr;
typedef std::map<T_vertice, int>      T_vertice_time;
typedef std::map<T_vertice, T_color>  T_vert_color;
//////////////////////////////////////////////////////////////////////////////////////
void  print_matr(T_matr&  matr, const T_vertices&  vertices)
{
    
    for(T_vertices::const_iterator  vertice_row_it = vertices.begin();
        vertice_row_it != vertices.end(); ++vertice_row_it)
    {
        for(T_vertices::const_iterator  vertice_col_it = vertices.begin();
            vertice_col_it != vertices.end(); ++vertice_col_it)
        {
            std::cout << '\t'
                      << matr[*vertice_row_it][*vertice_col_it];
                      
        } 
        std::cout << std::endl
                  << std::endl
                  << std::endl;
    }  
}
//////////////////////////////////////////////////////////////////////////////////////
T_vertices  get_vertices(const T_edges&  edges)
{
    T_vertices_set  vertices_set;
    for(T_edges::const_iterator  edge_it = edges.begin(); edge_it != edges.end();
        ++ edge_it)
    {
        vertices_set.insert(*edge_it->begin());
        vertices_set.insert(*edge_it->rbegin());
    }
    return T_vertices(vertices_set.begin(), vertices_set.end()); 
}
//////////////////////////////////////////////////////////////////////////////////////
T_matr  get_adjacency_matr(const T_edges&    edges)
{   
    T_matr  adjacency_matr;
    for(T_edges::const_iterator  edge_it = edges.begin(); edge_it != edges.end();
        ++ edge_it)
    {
        T_vertice  v1 = *edge_it->begin();
        T_vertice  v2 = *edge_it->rbegin();
        
        adjacency_matr[v1][v2] = adjacency_matr[v2][v1] = true;        
    }
    return  adjacency_matr;
}
//////////////////////////////////////////////////////////////////////////////////////
bool  successfully_depth_first_black_white_colouring
    (
        T_vertice         vertice_U,
        T_color           color_prev,
        const T_vertices  vertices,                  
        T_matr&           adjacency_matr,
        T_vert_color&     vert_color,
        T_vertices&       vertices_white,
        T_vertices&       vertices_black
    )
{
    if(color_prev == WHITE)
    {
        vert_color[vertice_U] = BLACK;
        vertices_black.push_back(vertice_U);
    }
    else
    {
        vert_color[vertice_U] = WHITE;
        vertices_white.push_back(vertice_U);   
    }
    
    for(T_vertices::const_iterator  vertice_it_V = vertices.begin();
        vertice_it_V != vertices.end(); ++vertice_it_V)
    {
        if(adjacency_matr[vertice_U][*vertice_it_V])
        {
            if(vert_color[*vertice_it_V] == NO_COLOR)
            {
                if(
                      !successfully_depth_first_black_white_colouring
                         (
                             *vertice_it_V,
                             vert_color[vertice_U],
                             vertices,
                             adjacency_matr,
                             vert_color,
                             vertices_white,
                             vertices_black
                         )
                  )
                {
                    return false;
                }
            }
            else if(vert_color[vertice_U] == vert_color[*vertice_it_V])
            {
                return  false;
            }
        }
    }
    return  true;
}
//////////////////////////////////////////////////////////////////////////////////////
void  print_2_vertice_groups
    (
        const T_vertices  vertices,                  
        T_matr&           adjacency_matr
    )
{
    T_vertices  vertices_white;
    T_vertices  vertices_black;
    bool res_bool = true;
    
    T_vert_color  vert_color;
    for(T_vertices::const_iterator  vertice_it = vertices.begin();
        vertice_it != vertices.end(); ++vertice_it)
    {
        if(
              vert_color[*vertice_it] == NO_COLOR
              && !successfully_depth_first_black_white_colouring
                      (
                          *vertice_it,
                          BLACK,
                          vertices,
                          adjacency_matr,
                          vert_color,
                          vertices_white,
                          vertices_black
                      )
          )
        {
            res_bool = false;
            break;
        }
    }
    
    if(res_bool)
    {
        std::cout << "Граф является двудольным. Группы вершин:"
                  << std::endl
                  << "группа A:"
                  << std::endl
                  << "\t";
 
        std::copy(vertices_white.begin(), vertices_white.end(),
                  std::ostream_iterator<T_vertice>(std::cout, " "));
 
        std::cout << std::endl
                  << "группа B:"
                  << std::endl
                  << "\t";
 
        std::copy(vertices_black.begin(), vertices_black.end(),
                  std::ostream_iterator<T_vertice>(std::cout, " "));
    }
    else
    {
        std::cout << "Граф НЕ является двудольным.";
    }
    std::cout << std::endl;
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));   
    
    int n = 0;
    do
    {
        std::cout << "Введите количество ребер неориентированного графа > 0: ";
        std::cin >> n;
    }while(n <= 0);
 
 
    std::cout << "Введите ребра неориентированного графа "
                 "(вершины в ребре не должны совпадать):";
    T_edges  edges;
    
    do
    {
        std::cout << std::endl
                  << "ребро #"
                  << edges.size() + 1
                  << ":"
                  << std::endl
                  << "\t-> ";
        T_vertice  v1;
        std::cin >> v1;
        T_edge  edge_cur;
        edge_cur.insert(v1);
        
        T_vertice  v2;
        std::cout << "\t-> ";
        std::cin >> v2;        
        edge_cur.insert(v2);        
        if(edge_cur.size() == 2)
        {
            edges.insert(edge_cur);
        }        
    }while(static_cast<int>(edges.size()) < n);
 
    T_vertices  vertices = get_vertices(edges);
 
    T_matr  adjacency_matr = get_adjacency_matr(edges);
    std::cout << "Матрица смежности графа:"
              << std::endl;
 
    print_matr(adjacency_matr, vertices);
 
    print_2_vertice_groups(vertices, adjacency_matr);
}
0
asotel
2 / 2 / 0
Регистрация: 11.11.2010
Сообщений: 58
20.11.2010, 14:42  [ТС] #4
Спасибо Огромное)))
0
asotel
2 / 2 / 0
Регистрация: 11.11.2010
Сообщений: 58
23.11.2010, 04:15  [ТС] #5
исправте ошибки плиз

вот код :

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
#include <iostream.h>
void main()
{
    int a[250][250];  //ГІГ*áëèöГ*
    int mas[250];  //ëþäè î÷åðåäü
    int m[250][250]=0;  // yjvth uhegs õç
    int i,j;
    m[0][0]=1;
    while(m[i][j])
        if (a[i][j]==1)
        { 
            if (m[j]==0)
            {
                m[j]=2;
            }
            if ((m[j]==1)||(m[i]==1))
            {
                if (m[i]==2)
                {
                mas[i]=j;
                }
                if (((m[i]==2)&&(m[j]==2))||((m[i]==1)&&(m[j]=1)))
                {
                    break;
                }
                cout<<"EROR"<<endl;
                
                return(0);
        }}
                cout<<"YES"<<endl;
}

вот ошибки:

c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(6) : error C2440: 'initializing' : cannot convert from 'const int' to 'int [250][250]'
There are no conversions to array types, although there are conversions to references or pointers to arrays
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(14) : error C2440: '=' : cannot convert from 'const int' to 'int [250]'
There are no conversions to array types, although there are conversions to references or pointers to arrays
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(16) : error C2446: '==' : no conversion from 'const int' to 'int *'
Conversion from integral type to pointer type requires reinterpret_cast, C-style cast or function-style cast
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(16) : error C2040: '==' : 'int [250]' differs in levels of indirection from 'const int'
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(16) : error C2446: '==' : no conversion from 'const int' to 'int *'
Conversion from integral type to pointer type requires reinterpret_cast, C-style cast or function-style cast
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(16) : error C2040: '==' : 'int [250]' differs in levels of indirection from 'const int'
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(18) : error C2446: '==' : no conversion from 'const int' to 'int *'
Conversion from integral type to pointer type requires reinterpret_cast, C-style cast or function-style cast
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(18) : error C2040: '==' : 'int [250]' differs in levels of indirection from 'const int'
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(22) : error C2446: '==' : no conversion from 'const int' to 'int *'
Conversion from integral type to pointer type requires reinterpret_cast, C-style cast or function-style cast
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(22) : error C2040: '==' : 'int [250]' differs in levels of indirection from 'const int'
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(22) : error C2446: '==' : no conversion from 'const int' to 'int *'
Conversion from integral type to pointer type requires reinterpret_cast, C-style cast or function-style cast
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(22) : error C2040: '==' : 'int [250]' differs in levels of indirection from 'const int'
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(22) : error C2446: '==' : no conversion from 'const int' to 'int *'
Conversion from integral type to pointer type requires reinterpret_cast, C-style cast or function-style cast
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(22) : error C2040: '==' : 'int [250]' differs in levels of indirection from 'const int'
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(22) : error C2440: '=' : cannot convert from 'const int' to 'int [250]'
There are no conversions to array types, although there are conversions to references or pointers to arrays
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(28) : error C2562: 'main' : 'void' function returning a value
c:\documents and settings\andrey\ðàáî÷èé ñòîë\4laba\2n\42\2.cpp(2) : see declaration of 'main'
Error executing cl.exe.

- 16 error(s), 0 warning(s)
0
Nameless One
Эксперт С++
5773 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
23.11.2010, 07:36 #6
Цитата Сообщение от asotel Посмотреть сообщение
исправте ошибки плиз
А ты сообщения компилатора читать умеешь? А чем отличается указатель от обычной переменной, знаешь? Про возвращаемые значения функций читал?
0
asotel
2 / 2 / 0
Регистрация: 11.11.2010
Сообщений: 58
24.11.2010, 00:01  [ТС] #7
я не всмысле ошибки помпилятора, а ошибки в моем коде, во втором сообшении мне написали алгоритм
0
silent_1991
Эксперт С++
4964 / 3040 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
24.11.2010, 05:39 #8
asotel, а вы думаете, компилятор вам от балды 27 строчек ошибок нагенерил? Нет, компилятор генерирует осмысленные сообщения, которые зависят от ошибок в коде, а не в компиляторе. И сообщения компилятора нужны затем, чтобы помочь программисту исправить ошибки в коде самостоятельно, а не бежать сразу на форму, не вникнув в суть ошибок.
0
taras atavin
24.11.2010, 06:20
  #9

Не по теме:

Цитата Сообщение от asotel Посмотреть сообщение
так, чтобы в каждой группе были только незнакомые люди.
?Надеюсь, A[i][i]=1? Кстати, на сях нет понятия многомерного массива. Это на паскале многомерный массив есть синоним массива массивов, а на сях вместо синонимичности ограничились заменой всех многомерных массивов массивами массивов.

0
asotel
2 / 2 / 0
Регистрация: 11.11.2010
Сообщений: 58
24.11.2010, 22:41  [ТС] #10
Цитата Сообщение от silent_1991 Посмотреть сообщение
asotel, а вы думаете, компилятор вам от балды 27 строчек ошибок нагенерил? Нет, компилятор генерирует осмысленные сообщения, которые зависят от ошибок в коде, а не в компиляторе. И сообщения компилятора нужны затем, чтобы помочь программисту исправить ошибки в коде самостоятельно, а не бежать сразу на форму, не вникнув в суть ошибок.


пишу еще раз ошибки помпилятора я просто так выложил, мне нужно чтоб ктото сверил алгоритм из второго сообшения с моим кодом
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.11.2010, 22:41
Привет! Вот еще темы с ответами:

Структуры, Таблица - C++
Это таблица, не смог ее показать в подобающем виде, простите. Помогите составить программу по структурам на С++ или Pascal Abc. Заранее...

Таблица Истенности - C++
Собрался писать прогу на С++, но не знаю как лучше сделать! Задание такое: дана формула (заносится с клавиатуры любая формула) и надо...

Хеш-таблица - C++
В спортивных соревнованиях участвуют n команд. В файле SPORT содержатся прогнозы результатов соревнований. Каждый прогноз включает номер...

Турнирная таблица - C++
Люди добрые умоляю помогите пожалуйста ((( Срочно нужно составить программу, курсовик после завтра. Знаю писали такую тему, но там...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
24.11.2010, 22:41
Ответ Создать тему
Опции темы

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