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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ В текстовом файле t записаны буквы латинского алфавита и цифры. Занести в текстовый файл h из текстового файла t только латинские буквы. http://www.cyberforum.ru/cpp-beginners/thread753271.html
В текстовом файле t записаны буквы латинского алфавита и цифры. Занести в текстовый файл h из текстового файла t только латинские буквы.
C++ Задачи С++ Помогите с задачами. Сказали реализовать на С++, но я даже не знаю как это сделать. Читала в книгах, но там примера кода не было, только описывается что это такое. Если кто может помогите. 1. Вставка нового элемента в односвязный список в -ую позицию. 2. Вставка нового элемента в связный список перед первым элементом, содержащим заданное значение. 3. Удаление -го элемента из односвязного... http://www.cyberforum.ru/cpp-beginners/thread753259.html
C++ Посчитать m последних разрядов числа n
Всем привет! В свободное от работы время занимаюсь программированием - подтягиваю свой уровень до того, который был когда-то раньше, во время обучения в ВУЗе. Для начала решил озаботиться азами, для этого использую С++ Builder 6 и сборник лабораторных работ для каких-то первокурсников (супруга преподаватель). Задачки решаются, но возникает вопрос, насколько они кустарно сделаны. Мне было бы...
Подскажите алгоритм заполнения матрицы по спирали C++
нужно сделать так чтобы получалась вот такая матрица 2х2 1 2 4 3 3х3
C++ Повторный вызов процедуры http://www.cyberforum.ru/cpp-beginners/thread753206.html
Всем очень добрый день! А подскажите,пожалуйста,в Си++ процедура может вызываться несколько раз в различных местах кода,как в Паскале?
C++ Найти в тексте все слова, буквы в которых упорядочены по алфавиту. Помогите пожалуйста с программкой на С++, сама не справляюсь. "В данном тексте найти все слова, буквы в которых упорядочены по алфавиту." В программу вводится текст, и она выводит все слова, где буквы идут по алфавиту. подробнее

Показать сообщение отдельно
gosser92
0 / 0 / 0
Регистрация: 16.04.2012
Сообщений: 20
05.01.2013, 14:27     Генерация программы
Есть рабочая программа.Требуется в помощь в компиляции её в 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;
}
Вложения
Тип файла: zip Гиперкуб.zip (43.8 Кб, 2 просмотров)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 18:44. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru