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

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

Войти
Регистрация
Восстановить пароль
 
gosser92
0 / 0 / 0
Регистрация: 16.04.2012
Сообщений: 20
#1

Генерация программы - C++

05.01.2013, 14:27. Просмотров 500. Ответов 14
Метки нет (Все метки)

Есть рабочая программа.Требуется в помощь в компиляции её в Visual Studio 2005 Происходит выход из программы без просмотра результатов.Заранее благодарю.

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
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
// Гиперкуб.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
 
using namespace std;
 
vector< vector<bool> > graph;
string last_error;
 
// проверить валидный ли символ (валидные - '0' и '1', всё остальное - невалидное)
bool is_invalid_char(char ch)
{
    return (ch!='0' && ch!='1');
}
 
// читать файл
bool read_file(const char *file_name)
{
    ifstream fs;
 
    // открыть файл с именем file_name
    fs.open(file_name);
 
    // если открыть не удаётся - выход
    if (!fs.is_open()) {
        return false;
    }
 
    string buf;
    int size = 0;
 
    // пока не конец файла
    while (!fs.eof())
    {
        // прочитать строку
        getline(fs, buf);
        // удалить из неё всё кроме валидных символов
        buf.erase(remove_if(buf.begin(), buf.end(), is_invalid_char), buf.end());
 
        // если пусто - выход
        if (!buf.size()) {
            continue;
        }
 
        // длины всех строк должны быть одинаковы.
        // если хоть одна строка в файле имеет другую длину - значит файл неправильный
        if (!size) {
            size = buf.size();
        } else if (size != buf.size()) {
            return false;
        }
 
        // заполняем массив (vector) по правилу - если в строке '1', пишем в массив true, иначе false
        // т.е. из строки "1100" получаем массив (true, true, false, false)
        vector<bool> line;
 
        for (string::iterator it = buf.begin(); it != buf.end(); it++) {
            line.push_back(*it == '1');
        }
 
        // записываем только что прочитанный и заполненный массив в матрицу смежности
        graph.push_back(line);
    }
 
    // закрыть файл
    fs.close();
    return true;
}
 
// считаем кол-во едениц в двоичном представлении числа
// например, в числе 12 (двоичное представление: 1100) - 2 еделицы
int ones_count(int n)
{
    int res = 0;
    unsigned un = (unsigned)n;
 
    while (un)
    {
        res += (un & 1);
        un >>= 1;
    }
 
    return res;
}
 
// считаем расстояние хэмминга
int calc_dist(int a, int b)
{
    return ones_count(a ^ b);
}
 
// проверка графа на правильность
bool graph_check()
{
    int s = graph.size();
 
    for (int r = 0; r < s; r++)
    {
        // 1. вершина не должна быть связана сама с собой
        if (graph[r][r]) {
            return false;
        }
 
        for (int c = 0; c < s; c++)
        {
            if (r!=c && graph[r][c])
            {
                // 2. если вершина A связана с вершиной B, то и B должно быть связано с A
                if (!graph[c][r]) {
                    return false;
                }
 
                // 3. вершины связанные в какой-либо вершиной не должны быть связаны между собой
                for (int k = 0; k < s; k++) {
                    if (k!=c && graph[r][k]) {
                        if (graph[k][c] || graph[c][k]) {
                            return false;
                        }
                    }
                }
            }
        }
    }
 
    return true;
}
 
// вычисление логарифма по модулю 2 (работает только для чисел вида 2^n)
int quick_log2(int n)
{
    int res = 0;
    unsigned un = (unsigned)n >> 1;
 
    while (un)
    {
        res++;
        un >>= 1;
    }
 
    return res;
}
 
/*
void debug_vector(vector<int> v)
{
    cout << v.size() << ": ";
 
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
    {
        if (it != v.begin()) {
            cout << ", ";
        }
 
        cout << *it;
    }
 
    cout << endl;
}
*/
 
// рассчитывает новую метку по двум старым если:
// колво_едениц(базовая_метка) + 2 == колво_едениц(вторая_метка)
void calc_labels_2(int base, int second, vector<int> &res)
{
    unsigned d = base ^ second;
    unsigned b = 1;
 
    while (b && b<d)
    {
        if (d & b) {
            res.push_back(base | b);
        }
 
        b <<= 1;
    }
}
 
// рассчитывает новую метку по двум старым
// результат будет в переменной res
void calc_labels(int la, int lb, vector<int> &res)
{
    res.clear();
 
    int oa = ones_count(la);
    int ob = ones_count(lb);
 
    if (oa == ob) {
        // если кол-во едениц совпадает, то новая метка получается битовым "или" от старых
        res.push_back(la | lb);
    } else if (oa == ob+2) {
        // колво_едениц(la) == колво_едениц(lb) + 2
        calc_labels_2(la, lb, res);
    } else if (oa+2 == ob) {
        // колво_едениц(la) + 2 == колво_едениц(lb)
        calc_labels_2(lb, la, res);
    }
 
    // если рассчитать метку не удалось, результат будет пустым
}
 
int hypercube_n = 0;
 
// главная функция - проверяет является ли граф гиперкубом
bool is_hypercube()
{
    // число будет в виде 2^n тогда и только тогда, если кол-во едениц в его двоичном представлении == 1
    if (ones_count(graph.size()) != 1)
    {
        last_error.assign("graph size != 2^n");
        return false;
    }
 
    // если граф не проходит определённые проверки - выход из функции
    if (!graph_check())
    {
        last_error.assign("invalid graph");
        return false;
    }
 
    int s = graph.size();
    int n = quick_log2(s);      // считаем размерность гиперкуба
    vector<int> labels(s, -1);  // массив для меток, сразу заполняем его числом (-1) (минус один означает что на данной вершине ещё нет метки)
 
    // расставляем начальные метки - для первой вершины метка будет 0
    labels[0] = 0;
    int curr = 1;
 
    // для вершин связанных с первой - 2^n (т.е. 1, 2, 4, ...)
    for (int i = 0; i < s; i++)
    {
        if (graph[0][i])
        {
            labels[i] = curr;
            curr <<= 1;
        }
    }
 
    bool loop;
    vector<int> verts;
    vector<int> new_labels;
    vector<int> tmp_labels;
    vector<int> curr_labels;
 
    // цикл расстановки остальных меток
    do
    {
        // флаг повторения цикла
        loop = false;
 
        // проходим циклом по всем вершинам
        for (int ind = 0; ind < s; ind++)
        {
            // если метка уже стоит - пропускаем
            if (labels[ind] >= 0) {
                continue;
            }
 
            // очищаем список связанных вершин
            verts.clear();
            // очщаем список возможных новых меток для вершины
            new_labels.clear();
 
            // проходим по всем вершинам, связанным с текущей
            for (int i = 0; i < s; i++) {
                // и если на вершине уже есть метка, добавляем её в списов связанных вершин
                if (graph[ind][i] && labels[i]>=0) {
                    verts.push_back(i);
                }
            }
 
            // делаем полный перебор всех найденных связанных вершин
            for (int i = 0; i < verts.size() - 1; i++)
            {
                for (int j = i + 1; j < verts.size(); j++)
                {
                    // на данном этапе есть 2 вершины, которые всязаны с рассматривоемой
                    int la = labels[verts[i]];  // метка первой связанной вершины
                    int lb = labels[verts[j]];  // метка второй связанной вершины
 
                    // рассчитываем возможные новые метки для рассматриваемой вершины
                    calc_labels(la, lb, tmp_labels);
                    // очищаем список возможных меток, которые точно подходят
                    curr_labels.clear();
 
                    // проходим по возможным новым меткам для рассматриваемой вершины
                    for (vector<int>::iterator it = tmp_labels.begin(); it != tmp_labels.end(); it++)
                    {
                        int l = *it;    // l = рассматриваемая метка
 
                        // если:
                        // 1. метка уже используется (find(labels.begin(), labels.end(), l) != labels.end())
                        // 2. расстояние хэмминга от рассматриваемой метки до метки первой связанной вершины != 1 (calc_dist(l, la) != 1)
                        // 3. расстояние хэмминга от рассматриваемой метки до метки второй связанной вершины != 1 (calc_dist(l, lb) != 1)
                        // то пропустить эту метку (она не подходит)
                        if (find(labels.begin(), labels.end(), l) != labels.end()
                            || calc_dist(l, la) != 1
                            || calc_dist(l, lb) != 1)
                        {
                            continue;
                        }
 
                        // если список возможных меток не пустой (это может быть тогда, когда найденных связанных вершин более двух
                        if (new_labels.size()) {
                            // проверяем есть ли рассматриваемая метка с списке.
                            // если её нет - она не подходит
                            if (find(new_labels.begin(), new_labels.end(), l) == new_labels.end()) {
                                continue;
                            }
                        }
 
                        // если метка прошла все испытания - добавляем её в список
                        curr_labels.push_back(l);
                    }
 
                    // если список меток пустой (т.е. ни одна из новых меток не прошла все проверки) - то это не гиперкуб
                    if (curr_labels.empty()) {
                        last_error.assign("not hypercube");
                        return false;
                    }
 
                    // копируем массив curr_labels в new_labels
                    new_labels.assign(curr_labels.begin(), curr_labels.end());
                }
            }
 
            // just for case (проверка на всякий случай)
            if (new_labels.empty()) {
                last_error.assign("not hypercube (sanity check)");
                return false;
            }
 
            // проставляем рассматривоемой вершине метку (если их более одной - первую из списка)
            labels[ind] = new_labels.front();
            // если была проставлена хоть одна новая метка - повторить цикл
            loop = true;
        }
    } while (loop);
 
    // сохраняем размерность гиперкуба в глобальной переменной (чтоб потом её вывести, если потребуется)
    hypercube_n = n;
 
    // find(labels.begin(), labels.end(), -1) == labels.end() - поиск непроставленных меток.
    // false - если есть хоть одна непроставленная метка, true - всё в порядке, все метки проставлены
    return (find(labels.begin(), labels.end(), -1) == labels.end());
}
 
int main(int argc, const char **argv)
{
    // если имя файла было передано параметром, берём его. иначе будем читать файл input.txt
    const char *file_name = (argc > 1 ? argv[1] : "input.txt");
 
    // читаем файл
    if (!read_file(file_name)) {
        // если не удалось - выводим ошибку
        cout << "no" << endl;
        cout << "Error occurred while reading " << file_name << endl;
        return 0;
    }
 
    // проверяем является ли граф гиперкубом
    if (is_hypercube()) {
        // да (выводим "yes" и на следующей строке размерность гиперкуба)
        cout << "yes" << endl;
        cout << hypercube_n << endl;
    } else {
        // нет (выводим "no" и на следующей строке причину, по которой граф не прошёл проверку)
        cout << "no" << endl;
        cout << last_error << endl;
    }
 
    return 0;
}
0
Вложения
Тип файла: zip Гиперкуб.zip (43.8 Кб, 2 просмотров)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.01.2013, 14:27
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Генерация программы (C++):

Генерация случайного числа при запуске программы - C++
Доброго всем времени суток. В данный момент потихоньку осваиваю C++ и столкнулся с такой вещью, что при использовании srand( (time(0) )...

Генерация - C++
#include &quot;iostream&quot; #include &quot;ctime&quot; #include &quot;cstdlib&quot; using namespace std; int main(){ srand(time(NULL)); setlocale(LC_ALL,...

Генерация ПСП - C++
Пожалуста, помогите. Задача состоит в том чтобы написать на С++ генератор псевдослучайных последовательностей по формуле: Y=F*Y, где F...

Генерация чисел - C++
Нужно программа для генерации тризначных чисел и таких, что бы в этих числах них не было парных цифр. ТИпу, если число &quot;ХХХ&quot;, то &quot;Х&quot; не...

Генерация лабиринта - C++
Разработать приложение, генерирующее лабиринт размером m x n клеток. Дополнительные условия: а) Вход и выход – произвольные клетки...

Генерация матриц - C++
Программа, которая генерирует три матрицы и записывает их в файл (генерацию и запись оформить в виде функций).

14
Issues
430 / 365 / 37
Регистрация: 06.08.2012
Сообщений: 961
05.01.2013, 14:50 #2
перед return 0;
C++
1
system("PAUSE");
0
Croessmah
Эксперт CЭксперт С++
13407 / 7557 / 853
Регистрация: 27.09.2012
Сообщений: 18,590
Записей в блоге: 3
Завершенные тесты: 1
05.01.2013, 14:52 #3
Можно запустить без отладчика ctrl+F5
Можно "тормознуть" консоль:
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
int main(int argc, const char **argv)
{
    // если имя файла было передано параметром, берём его. иначе будем читать файл input.txt
    const char *file_name = (argc > 1 ? argv[1] : "input.txt");
 
    // читаем файл
    if (!read_file(file_name)) {
        // если не удалось - выводим ошибку
        cout << "no" << endl;
        cout << "Error occurred while reading " << file_name << endl;
        return 0;
    }
 
    // проверяем является ли граф гиперкубом
    if (is_hypercube()) {
        // да (выводим "yes" и на следующей строке размерность гиперкуба)
        cout << "yes" << endl;
        cout << hypercube_n << endl;
    } else {
        // нет (выводим "no" и на следующей строке причину, по которой граф не прошёл проверку)
        cout << "no" << endl;
        cout << last_error << endl;
    }
    std::cin.get();//Задержим консоль!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
    //system("pause");//И так можно в Windows
    return 0;
}
0
Issues
430 / 365 / 37
Регистрация: 06.08.2012
Сообщений: 961
05.01.2013, 14:53 #4
Цитата Сообщение от gosser92 Посмотреть сообщение
#include "stdafx.h"
думаю нужно:
C++
1
#include <stdafx.h>
0
Croessmah
Эксперт CЭксперт С++
13407 / 7557 / 853
Регистрация: 27.09.2012
Сообщений: 18,590
Записей в блоге: 3
Завершенные тесты: 1
05.01.2013, 14:57 #5
Цитата Сообщение от SeregaC++ Посмотреть сообщение
думаю нужно
stdafx.h лежит в папке с проектом.
0
gosser92
0 / 0 / 0
Регистрация: 16.04.2012
Сообщений: 20
05.01.2013, 14:58  [ТС] #6
Пробовал ,не помогает,сразу вылетает.
0
Issues
05.01.2013, 14:58
  #7

Не по теме:

Croessmah, извиняюсь тогда, я не скачивал проэкт.

0
Croessmah
05.01.2013, 14:59
  #8

Не по теме:

Цитата Сообщение от SeregaC++ Посмотреть сообщение
Croessmah, извиняюсь тогда, я не скачивал проэкт.
Студия кладет этот фаил в папку с проектом.

0
Issues
05.01.2013, 15:01
  #9

Не по теме:

Цитата Сообщение от Croessmah Посмотреть сообщение
Студия кладет этот фаил в папку с проектом.
у меня VS2012 ругается на #include "stdafx.h"

0
Croessmah
05.01.2013, 15:03
  #10

Не по теме:

Цитата Сообщение от SeregaC++ Посмотреть сообщение
у меня VS2012 ругается на #include "stdafx.h"
Если ставите галочку "пустой проект", то этот фаил отсутствует вовсе. Да и не нужен он тут.

1
Issues
430 / 365 / 37
Регистрация: 06.08.2012
Сообщений: 961
05.01.2013, 15:05 #11
Цитата Сообщение от gosser92 Посмотреть сообщение
Пробовал ,не помогает,сразу вылетает.
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
int main(int argc, const char **argv)
{
    // если имя файла было передано параметром, берём его. иначе будем читать файл input.txt
    const char *file_name = (argc > 1 ? argv[1] : "input.txt");
 
    // читаем файл
    if (!read_file(file_name)) {
        // если не удалось - выводим ошибку
        cout << "no" << endl;
        cout << "Error occurred while reading " << file_name << endl;
        system("PAUSE");
        return 0;
    }
 
    // проверяем является ли граф гиперкубом
    if (is_hypercube()) {
        // да (выводим "yes" и на следующей строке размерность гиперкуба)
        cout << "yes" << endl;
        cout << hypercube_n << endl;
    } else {
        // нет (выводим "no" и на следующей строке причину, по которой граф не прошёл проверку)
        cout << "no" << endl;
        cout << last_error << endl;
    }
 
    system("PAUSE");
    return 0;
}
0
gosser92
0 / 0 / 0
Регистрация: 16.04.2012
Сообщений: 20
05.01.2013, 15:07  [ТС] #12
Возможно ошибка с чтением файла input.txt Создаём его в корне программы,записываем одним из вариантов из папки test.Но всё равно не работает.
0
Croessmah
Эксперт CЭксперт С++
13407 / 7557 / 853
Регистрация: 27.09.2012
Сообщений: 18,590
Записей в блоге: 3
Завершенные тесты: 1
05.01.2013, 15:10 #13
Цитата Сообщение от gosser92 Посмотреть сообщение
Возможно ошибка с чтением файла input.txt Создаём его в корне программы,записываем одним из вариантов из папки test.Но всё равно не работает.
Название: Безымянный.jpg
Просмотров: 28

Размер: 2.7 Кб
только я проект не скачивал. Это просто результат работы кода.
0
Issues
430 / 365 / 37
Регистрация: 06.08.2012
Сообщений: 961
05.01.2013, 15:11 #14
gosser92, попробуйте включить его в проэкт. (input.txt)
0
gosser92
0 / 0 / 0
Регистрация: 16.04.2012
Сообщений: 20
05.01.2013, 15:22  [ТС] #15
Он лежит в корне с программой.В него занесены данный с теста,которые должны выдавать результат,не являющийся ошибкой(при запуске ctr+F5)Всё рано происходит вылет,а при ( ctr+F5) в консоле выводится ошибка,что не верно.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.01.2013, 15:22
Привет! Вот еще темы с ответами:

Генерация чисел - C++
Доброго времени суток, не могли бы вы подсказать как выбрать рандомно число из двух чисел 2 и 4 и в диапозоне от 1 до 4 благодарю

Процедурная генерация - C++
Доброго времени суток, форумчане. Как сделать переходы между комнатами? Читал о применении алгоритмов поиска пути, в частности А*....

генерация строк - C++
подскажите плиз как сгенерировать строки????????? void karta(){ char...

Генерация чисел - C++
Помогите написать программу, а мучусь уже два часа. :) Нужно сгенерировать 30 трёхзначных чисел, и что бы в цифры этих чисел не были...


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

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

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