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

Найти Булеан множества типа {a,b,c} - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 41, средняя оценка - 4.61
Elfenlide
23 / 23 / 1
Регистрация: 15.04.2012
Сообщений: 183
25.10.2012, 14:54     Найти Булеан множества типа {a,b,c} #1
Доброго времени суток, помогите написать метод нахождения булеана множества.
Булеан множества - множество все возможных подножеств искомого множества.
Пример: A={a,b,c};
Булеан А = {{}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c} };
Рекурсия обязательно!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,651
27.10.2012, 17:28     Найти Булеан множества типа {a,b,c} #2
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
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cctype>
#include <functional>
#include <iostream>
#include <set>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string         T_str;
typedef T_str::size_type    T_pos;
/////////////////////////////////////////////////////////////////////////////////////////
class  T_elem;
/////////////////////////////////////////////////////////////////////////////////////////
typedef T_elem*             T_elem_p;
/////////////////////////////////////////////////////////////////////////////////////////
struct T_elem_p_compare
{
    bool  operator()
        (
            const T_elem_p&     L_elem_p,
            const T_elem_p&     R_elem_p
        )                                       const;
};
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::set<T_elem_p, T_elem_p_compare>  T_stand_elem_p_set;
/////////////////////////////////////////////////////////////////////////////////////////
class  T_my_elem_p_set
{
    //-----------------------------------------------------------------------------------
    static const char   BEGIN_SYMB  =   '{';
    static const char   END_SYMB    =   '}';
    static const char   COMMA_SYMB  =   ',';
    //-----------------------------------------------------------------------------------
    T_stand_elem_p_set    stand_elem_p_set_;
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    T_my_elem_p_set
        (
            const T_str&    s,
            T_pos&          pos
        )
    {
        bool    bool_res    =   successfully_read_begin_symb(s, pos);
 
        if( bool_res )
        {
            while   (
                            successfully_add_elem           (s, pos)
                        &&  successfully_read_comma_symb    (s, pos)
                    );
 
            bool_res    =   successfully_read_end_symb(s, pos);
        }
        if( !bool_res )
        {
            throw   std::invalid_argument("Bad string.");
        }
    }
    //-----------------------------------------------------------------------------------
    T_my_elem_p_set(const T_my_elem_p_set&  my_elem_p_set);
    //-----------------------------------------------------------------------------------
    T_my_elem_p_set( const T_stand_elem_p_set&  stand_elem_p_set = T_stand_elem_p_set() );
    //-----------------------------------------------------------------------------------
    ~T_my_elem_p_set();
    //-----------------------------------------------------------------------------------
    T_my_elem_p_set&  operator=(const T_my_elem_p_set&  my_elem_p_set)
    {
        stand_elem_p_set_   =   my_elem_p_set.get_stand_elem_p_set_copy();
        return  *this;
    }
    //-----------------------------------------------------------------------------------
    bool  empty()                                       const
    {
        return  stand_elem_p_set_.empty();
    }
    //-----------------------------------------------------------------------------------
    void  print()                                       const;
    //-----------------------------------------------------------------------------------
    const T_stand_elem_p_set&  get_stand_elem_p_set()   const
    {
        return  stand_elem_p_set_;
    }    
    //-----------------------------------------------------------------------------------
    T_stand_elem_p_set  get_stand_elem_p_set_copy()     const;
    //-----------------------------------------------------------------------------------
    T_my_elem_p_set  powerset()                         const;
    //-----------------------------------------------------------------------------------
    void  insert( const T_elem&  elem );
    //-----------------------------------------------------------------------------------
private:
    //-----------------------------------------------------------------------------------
    static bool  successfully_read_begin_symb
        ( 
            const T_str&    s,
            T_pos&          pos
        )
    {
        return  successfully_read_symb
                    (
                        BEGIN_SYMB,
                        s,
                        pos
                    );
    }
    //-----------------------------------------------------------------------------------
    bool  successfully_add_elem
        ( 
            const T_str&    s,
            T_pos&          pos
        );
    //-----------------------------------------------------------------------------------
    static bool  successfully_read_comma_symb
        ( 
            const T_str&    s,
            T_pos&          pos
        )
    {
        return  successfully_read_symb
                    (
                        COMMA_SYMB,
                        s,
                        pos
                    );
    }
    //-----------------------------------------------------------------------------------
    static bool  successfully_read_end_symb
        ( 
            const T_str&    s,
            T_pos&          pos
        )
    {
        return  successfully_read_symb
                    (
                        END_SYMB,
                        s,
                        pos
                    );
    }
    //-----------------------------------------------------------------------------------
    static bool  successfully_read_symb
        (
            char            symb,
            const T_str&    s,
            T_pos&          pos
        )
    {
        bool    bool_res    =       pos_is_correct(s, pos)
                                &&  s[pos]  ==  symb;
 
        if( bool_res )
        {
            ++pos;
        }
 
        return  bool_res;
    }
    //-----------------------------------------------------------------------------------
    static bool  pos_is_correct 
        (
            const T_str&    s,
            T_pos&          pos
        )
    {
        return  pos < s.size();
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
class  T_elem
{
    friend struct       T_elem_compare;
    //-----------------------------------------------------------------------------------
    bool                is_symb_;
    char                symb_;
    T_my_elem_p_set*    set_p_;
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    T_elem
        ( 
            const T_str&    s,
            T_pos&          pos,
            bool            is_symb
        )
        :
        is_symb_( is_symb )
    {
        if( is_symb_ )
        {
            symb_   =   s[pos];
            set_p_  =   0;
            ++pos;
        }
        else
        {
            symb_   =   0;
            set_p_  =   new T_my_elem_p_set(s, pos);
        }
    }
    //-----------------------------------------------------------------------------------    
    T_elem( const T_my_elem_p_set&  my_elem_p_set )
        :
        is_symb_    ( false ),
        symb_       ( 0     ),
        set_p_      (
                        new     T_my_elem_p_set( my_elem_p_set )
                    )
    {}
    //-----------------------------------------------------------------------------------
    T_elem(const T_elem&  elem)
        :
        is_symb_    ( elem.is_symb_     ),
        symb_       ( elem.symb_        ),
        set_p_      ( 
                        elem.set_p_
                            ?   new     T_my_elem_p_set( *elem.set_p_ )
                            :   elem.set_p_
                    )
    {}
    //-----------------------------------------------------------------------------------
    ~T_elem()
    {
        if( !is_symb_ )
        {
            delete  set_p_;
        }
    }
    //-----------------------------------------------------------------------------------
    void  print()           const
    {
        if( is_symb_ )
        {
            std::cout   <<  symb_
                        <<  ' ';
        }
        else
        {
            set_p_->print();
        }
    }
    //-----------------------------------------------------------------------------------
    void  insert( const T_elem&  elem )
    {
        if( !is_symb_ )
        {
            set_p_->insert( elem );
        }
    }
    //-----------------------------------------------------------------------------------
private:
    //-----------------------------------------------------------------------------------
    T_elem&  operator=( const T_elem&  elem );
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
struct  T_elem_compare
{
    bool  operator() 
        (
            const T_elem&  L,
            const T_elem&  R
        )                           const
    {
        //Если один множество, а другой символ.
        if  ( 
                    L.is_symb_
                !=  R.is_symb_
            )
        {
            return  L.is_symb_;
        }
 
        //Если оба символы.
        if( L.is_symb_ )
        {
            return  L.symb_   <   R.symb_;
        }
        
        //Если оба множества.
        return  std::lexicographical_compare
                    (
                        L.set_p_->get_stand_elem_p_set().begin  (),
                        L.set_p_->get_stand_elem_p_set().end    (),
                        R.set_p_->get_stand_elem_p_set().begin  (),
                        R.set_p_->get_stand_elem_p_set().end    (),
                        T_elem_p_compare                        ()
                    );
    }
};
/////////////////////////////////////////////////////////////////////////////////////////
bool  T_elem_p_compare::operator()
    (
        const T_elem_p&     L_elem_p,
        const T_elem_p&     R_elem_p
    )                                   const
{
    T_elem_compare  elem_compare;
    return  elem_compare
                (
                    *L_elem_p,
                    *R_elem_p
                );
}
/////////////////////////////////////////////////////////////////////////////////////////
//Реализация функций класса T_my_elem_p_set, содержащих тип T_elem.
//---------------------------------------------------------------------------------------
T_my_elem_p_set::T_my_elem_p_set(const T_my_elem_p_set&  my_elem_p_set)
    :
    stand_elem_p_set_
        (
            my_elem_p_set.get_stand_elem_p_set_copy()
        )
{}
//---------------------------------------------------------------------------------------
T_my_elem_p_set::T_my_elem_p_set( const T_stand_elem_p_set&  stand_elem_p_set )
    :
    stand_elem_p_set_   ( stand_elem_p_set )
{
    stand_elem_p_set_   =   get_stand_elem_p_set_copy();
}
//---------------------------------------------------------------------------------------
T_my_elem_p_set::~T_my_elem_p_set()
{
    for (
            T_stand_elem_p_set::const_iterator
            elem_p_it     =   stand_elem_p_set_.begin   ();
            elem_p_it     !=  stand_elem_p_set_.end     ();
            ++elem_p_it
        )
    {
        delete  *elem_p_it;
    }
}
//---------------------------------------------------------------------------------------
void  T_my_elem_p_set::print()  const
{
    std::cout   <<  BEGIN_SYMB;
 
    std::for_each
        (
            stand_elem_p_set_.begin     (),
            stand_elem_p_set_.end       (),
            std::mem_fun                ( &T_elem::print )
        );
 
    std::cout   <<  END_SYMB; 
}
//---------------------------------------------------------------------------------------
bool  T_my_elem_p_set::successfully_add_elem
    ( 
        const T_str&    s,
        T_pos&          pos
    )
{
    bool    bool_res    =   pos_is_correct( s, pos );
    if( bool_res )
    {
        bool    elem_is_symb    =   isalpha( s[pos] ) != 0;
        bool    elem_is_set     =   s[pos]  == BEGIN_SYMB;
 
        bool    bool_res    =       elem_is_symb
                                ||  elem_is_set;
 
        if( bool_res )
        {
            stand_elem_p_set_.insert
                (
                    new     T_elem
                                (
                                    s, 
                                    pos,
                                    elem_is_symb
                                )
                );
        }
    }
    return  bool_res;
}
//---------------------------------------------------------------------------------------
T_stand_elem_p_set  T_my_elem_p_set::get_stand_elem_p_set_copy()    const
{
    T_stand_elem_p_set  res_set;
    for (
            T_stand_elem_p_set::const_iterator  
            elem_p_it     =   stand_elem_p_set_.begin   ();
            elem_p_it     !=  stand_elem_p_set_.end     ();
            ++elem_p_it            
        )
    {
        res_set.insert
            (
                new     T_elem( **elem_p_it )
            );
    }
    return  res_set;
}
//---------------------------------------------------------------------------------------
T_my_elem_p_set  T_my_elem_p_set::powerset()                        const
{
    T_my_elem_p_set  res_powerset;
 
    if  ( 
            empty()
        )
    {
        res_powerset.insert
            (
                T_elem
                    (
                        T_my_elem_p_set()
                    )
            );
    }
    else
    {
        T_stand_elem_p_set  prev_stand_set              =   get_stand_elem_p_set_copy();
        //Удаляем из prev_stand_set первый элемент.
        T_stand_elem_p_set::value_type  begin_elem_p    =   *prev_stand_set.begin();
        prev_stand_set.erase( begin_elem_p );
 
        res_powerset                                    =   T_my_elem_p_set( prev_stand_set ).powerset();
        T_stand_elem_p_set  prev_powerset_stand_set     =   res_powerset.get_stand_elem_p_set_copy();
        //Добавляем к res_powerset элементы-множества из prev_powerset_stand_set, в каждый из которых 
        //добавлен элемент *begin_elem_p.
        for (
                T_stand_elem_p_set::const_iterator  
                elem_p_it     =   prev_powerset_stand_set.begin     ();
                elem_p_it     !=  prev_powerset_stand_set.end       ();
                ++elem_p_it
            )
        {
            T_elem_p  cur_elem_p    =   *elem_p_it;
            cur_elem_p->insert      ( *begin_elem_p     );
            res_powerset.insert     ( *cur_elem_p       );
        }        
    }//else
    return  res_powerset;
}
//---------------------------------------------------------------------------------------
void  T_my_elem_p_set::insert( const T_elem&  elem )
{
    stand_elem_p_set_.insert
        ( 
            new T_elem( elem )
        );
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
 
    for(;;)
    {
        std::cout   <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  "Введите строку:"
                    <<  std::endl;
 
        T_str   s;
        T_pos   pos     =   0;
        getline(std::cin, s);
 
        try
        {
            T_my_elem_p_set     set( s, pos );
 
            if  (
                    pos != s.size() 
                )
            {
                throw   std::invalid_argument( "Bad string." );
            }
 
            std::cout   <<  "Создано множество:"
                        <<  std::endl;
 
            set.print();
 
            std::cout   <<  std::endl
                        <<  "Булеан данного множества имеет вид:"
                        <<  std::endl;
 
            set.powerset().print();
        }
        catch(std::invalid_argument&  e)
        {
            std::cout   <<  e.what()
                        <<  std::endl;
        }
    }
}
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
27.10.2012, 18:20     Найти Булеан множества типа {a,b,c} #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
#include<iostream>
 
void Print(char *a, int n, int i)
{
   if (n)
   {
       if (n & 1)
          std::cout << a[i] << " ";
       Print(a, n >> 1, i + 1);
   }
}
 
int main()
{
   int r, i, size;
   char a[] = {'a', 'b', 'c'};
   size = sizeof(a) / sizeof (*a);
   r = 1 << size;
   for (i = 0; i < r; i++)
   {
      Print(a, i, 0);
      std::cout << "\n";
   }
   return 0;
}
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,651
27.10.2012, 21:37     Найти Булеан множества типа {a,b,c} #4
Цитата Сообщение от Thinker Посмотреть сообщение
зачем усложнять, если все просто))
Действительно, вот так попроще будет (ошибку исправил, вкравшуюся в предыдущую версию).
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
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cctype>
#include <functional>
#include <iostream>
#include <set>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string         T_str;
typedef T_str::size_type    T_pos;
/////////////////////////////////////////////////////////////////////////////////////////
class  T_elem;
/////////////////////////////////////////////////////////////////////////////////////////
typedef T_elem*             T_elem_p;
/////////////////////////////////////////////////////////////////////////////////////////
struct T_elem_p_compare
{
    bool  operator()
        (
            const T_elem_p&     L_elem_p,
            const T_elem_p&     R_elem_p
        )                                       const;
};
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::set<T_elem_p, T_elem_p_compare>  T_stand_elem_p_set;
/////////////////////////////////////////////////////////////////////////////////////////
class  T_my_elem_p_set
{
    //-----------------------------------------------------------------------------------
    static const char   BEGIN_SYMB  =   '{';
    static const char   END_SYMB    =   '}';
    static const char   COMMA_SYMB  =   ',';
    //-----------------------------------------------------------------------------------
    T_stand_elem_p_set    stand_elem_p_set_;
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    T_my_elem_p_set
        (
            const T_str&    s,
            T_pos&          pos
        )
    {
        bool    bool_res    =   successfully_read_begin_symb(s, pos);
 
        if( bool_res )
        {
            while   (
                            successfully_add_elem           (s, pos)
                        &&  successfully_read_comma_symb    (s, pos)
                    );
 
            bool_res    =   successfully_read_end_symb(s, pos);
        }
        if( !bool_res )
        {
            throw   std::invalid_argument("Bad string.");
        }
    }
    //-----------------------------------------------------------------------------------
    T_my_elem_p_set(const T_my_elem_p_set&  my_elem_p_set);
    //-----------------------------------------------------------------------------------
    T_my_elem_p_set( const T_stand_elem_p_set&  stand_elem_p_set = T_stand_elem_p_set() );
    //-----------------------------------------------------------------------------------
    ~T_my_elem_p_set();
    //-----------------------------------------------------------------------------------
    T_my_elem_p_set&  operator=(const T_my_elem_p_set&  my_elem_p_set)
    {
        stand_elem_p_set_   =   my_elem_p_set.get_stand_elem_p_set_copy();
        return  *this;
    }
    //-----------------------------------------------------------------------------------
    bool  empty()                                       const
    {
        return  stand_elem_p_set_.empty();
    }
    //-----------------------------------------------------------------------------------
    void  print()                                       const;
    //-----------------------------------------------------------------------------------
    const T_stand_elem_p_set&  get_stand_elem_p_set()   const
    {
        return  stand_elem_p_set_;
    }    
    //-----------------------------------------------------------------------------------
    T_stand_elem_p_set  get_stand_elem_p_set_copy()     const;
    //-----------------------------------------------------------------------------------
    T_my_elem_p_set  powerset()                         const;
    //-----------------------------------------------------------------------------------
    void  insert( const T_elem&  elem );
    //-----------------------------------------------------------------------------------
private:
    //-----------------------------------------------------------------------------------
    static bool  successfully_read_begin_symb
        ( 
            const T_str&    s,
            T_pos&          pos
        )
    {
        return  successfully_read_symb
                    (
                        BEGIN_SYMB,
                        s,
                        pos
                    );
    }
    //-----------------------------------------------------------------------------------
    bool  successfully_add_elem
        ( 
            const T_str&    s,
            T_pos&          pos
        );
    //-----------------------------------------------------------------------------------
    static bool  successfully_read_comma_symb
        ( 
            const T_str&    s,
            T_pos&          pos
        )
    {
        return  successfully_read_symb
                    (
                        COMMA_SYMB,
                        s,
                        pos
                    );
    }
    //-----------------------------------------------------------------------------------
    static bool  successfully_read_end_symb
        ( 
            const T_str&    s,
            T_pos&          pos
        )
    {
        return  successfully_read_symb
                    (
                        END_SYMB,
                        s,
                        pos
                    );
    }
    //-----------------------------------------------------------------------------------
    static bool  successfully_read_symb
        (
            char            symb,
            const T_str&    s,
            T_pos&          pos
        )
    {
        bool    bool_res    =       pos_is_correct(s, pos)
                                &&  s[pos]  ==  symb;
 
        if( bool_res )
        {
            ++pos;
        }
 
        return  bool_res;
    }
    //-----------------------------------------------------------------------------------
    static bool  pos_is_correct 
        (
            const T_str&    s,
            T_pos&          pos
        )
    {
        return  pos < s.size();
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
class  T_elem
{
    friend struct       T_elem_compare;
    //-----------------------------------------------------------------------------------
    bool                is_symb_;
    char                symb_;
    T_my_elem_p_set*    set_p_;
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    T_elem
        ( 
            const T_str&    s,
            T_pos&          pos,
            bool            is_symb
        )
        :
        is_symb_( is_symb )
    {
        if( is_symb_ )
        {
            symb_   =   s[pos];
            set_p_  =   0;
            ++pos;
        }
        else
        {
            symb_   =   0;
            set_p_  =   new T_my_elem_p_set(s, pos);
        }
    }
    //-----------------------------------------------------------------------------------    
    T_elem( const T_my_elem_p_set&  my_elem_p_set )
        :
        is_symb_    ( false ),
        symb_       ( 0     ),
        set_p_      (
                        new     T_my_elem_p_set( my_elem_p_set )
                    )
    {}
    //-----------------------------------------------------------------------------------
    T_elem(const T_elem&  elem)
        :
        is_symb_    ( elem.is_symb_     ),
        symb_       ( elem.symb_        ),
        set_p_      ( 
                        elem.set_p_
                            ?   new     T_my_elem_p_set( *elem.set_p_ )
                            :   elem.set_p_
                    )
    {}
    //-----------------------------------------------------------------------------------
    ~T_elem()
    {
        if( !is_symb_ )
        {
            delete  set_p_;
        }
    }
    //-----------------------------------------------------------------------------------
    void  print()           const
    {
        if( is_symb_ )
        {
            std::cout   <<  symb_
                        <<  ' ';
        }
        else
        {
            set_p_->print();
        }
    }
    //-----------------------------------------------------------------------------------
    void  insert( const T_elem&  elem )
    {
        if( !is_symb_ )
        {
            set_p_->insert( elem );
        }
    }
    //-----------------------------------------------------------------------------------
private:
    //-----------------------------------------------------------------------------------
    T_elem&  operator=( const T_elem&  elem );
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
struct  T_elem_compare
{
    bool  operator() 
        (
            const T_elem&  L,
            const T_elem&  R
        )                           const
    {
        //Если один множество, а другой символ.
        if  ( 
                    L.is_symb_
                !=  R.is_symb_
            )
        {
            return  L.is_symb_;
        }
 
        //Если оба символы.
        if( L.is_symb_ )
        {
            return  L.symb_   <   R.symb_;
        }
        
        //Если оба множества.
        return  std::lexicographical_compare
                    (
                        L.set_p_->get_stand_elem_p_set().begin  (),
                        L.set_p_->get_stand_elem_p_set().end    (),
                        R.set_p_->get_stand_elem_p_set().begin  (),
                        R.set_p_->get_stand_elem_p_set().end    (),
                        T_elem_p_compare                        ()
                    );
    }
};
/////////////////////////////////////////////////////////////////////////////////////////
bool  T_elem_p_compare::operator()
    (
        const T_elem_p&     L_elem_p,
        const T_elem_p&     R_elem_p
    )                                   const
{
    T_elem_compare  elem_compare;
    return  elem_compare
                (
                    *L_elem_p,
                    *R_elem_p
                );
}
/////////////////////////////////////////////////////////////////////////////////////////
//Реализация функций класса T_my_elem_p_set, содержащих тип T_elem.
//---------------------------------------------------------------------------------------
T_my_elem_p_set::T_my_elem_p_set(const T_my_elem_p_set&  my_elem_p_set)
    :
    stand_elem_p_set_
        (
            my_elem_p_set.get_stand_elem_p_set_copy()
        )
{}
//---------------------------------------------------------------------------------------
T_my_elem_p_set::T_my_elem_p_set( const T_stand_elem_p_set&  stand_elem_p_set )
    :
    stand_elem_p_set_   ( stand_elem_p_set )
{
    stand_elem_p_set_   =   get_stand_elem_p_set_copy();
}
//---------------------------------------------------------------------------------------
T_my_elem_p_set::~T_my_elem_p_set()
{
    for (
            T_stand_elem_p_set::const_iterator
            elem_p_it     =   stand_elem_p_set_.begin   ();
            elem_p_it     !=  stand_elem_p_set_.end     ();
            ++elem_p_it
        )
    {
        delete  *elem_p_it;
    }
}
//---------------------------------------------------------------------------------------
void  T_my_elem_p_set::print()  const
{
    std::cout   <<  BEGIN_SYMB;
 
    std::for_each
        (
            stand_elem_p_set_.begin     (),
            stand_elem_p_set_.end       (),
            std::mem_fun                ( &T_elem::print )
        );
 
    std::cout   <<  END_SYMB; 
}
//---------------------------------------------------------------------------------------
bool  T_my_elem_p_set::successfully_add_elem
    ( 
        const T_str&    s,
        T_pos&          pos
    )
{
    bool    bool_res    =   pos_is_correct( s, pos );
    if( bool_res )
    {
        bool    elem_is_symb    =   isalpha( s[pos] ) != 0;
        bool    elem_is_set     =   s[pos]  == BEGIN_SYMB;
 
        bool_res                =       elem_is_symb
                                    ||  elem_is_set;
 
        if( bool_res )
        {
            stand_elem_p_set_.insert
                (
                    new     T_elem
                                (
                                    s, 
                                    pos,
                                    elem_is_symb
                                )
                );
        }
    }
    return  bool_res;
}
//---------------------------------------------------------------------------------------
T_stand_elem_p_set  T_my_elem_p_set::get_stand_elem_p_set_copy()    const
{
    T_stand_elem_p_set  res_set;
    for (
            T_stand_elem_p_set::const_iterator  
            elem_p_it     =   stand_elem_p_set_.begin   ();
            elem_p_it     !=  stand_elem_p_set_.end     ();
            ++elem_p_it            
        )
    {
        res_set.insert
            (
                new     T_elem( **elem_p_it )
            );
    }
    return  res_set;
}
//---------------------------------------------------------------------------------------
T_my_elem_p_set  T_my_elem_p_set::powerset()                        const
{
    T_my_elem_p_set  res_powerset;
 
    if  ( 
            empty()
        )
    {
        res_powerset.insert
            (
                T_elem
                    (
                        T_my_elem_p_set()
                    )
            );
    }
    else
    {
        T_stand_elem_p_set  prev_stand_set              =   get_stand_elem_p_set_copy();
        //Удаляем из prev_stand_set первый элемент.
        T_stand_elem_p_set::value_type  begin_elem_p    =   *prev_stand_set.begin();
        prev_stand_set.erase( begin_elem_p );
 
        res_powerset                                    =   T_my_elem_p_set( prev_stand_set ).powerset();
        T_stand_elem_p_set  prev_powerset_stand_set     =   res_powerset.get_stand_elem_p_set_copy();
        //Добавляем к res_powerset элементы-множества из prev_powerset_stand_set, в каждый из которых 
        //добавлен элемент *begin_elem_p.
        for (
                T_stand_elem_p_set::const_iterator  
                elem_p_it     =   prev_powerset_stand_set.begin     ();
                elem_p_it     !=  prev_powerset_stand_set.end       ();
                ++elem_p_it
            )
        {
            T_elem_p  cur_elem_p    =   *elem_p_it;
            cur_elem_p->insert      ( *begin_elem_p     );
            res_powerset.insert     ( *cur_elem_p       );
        }        
    }//else
    return  res_powerset;
}
//---------------------------------------------------------------------------------------
void  T_my_elem_p_set::insert( const T_elem&  elem )
{
    stand_elem_p_set_.insert
        ( 
            new T_elem( elem )
        );
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
 
    for(;;)
    {
        std::cout   <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  "Введите строку:"
                    <<  std::endl;
 
        T_str   s;
        T_pos   pos     =   0;
        getline(std::cin, s);
 
        try
        {
            T_my_elem_p_set     set( s, pos );
 
            if  (
                    pos != s.size() 
                )
            {
                throw   std::invalid_argument( "Bad string." );
            }
 
            std::cout   <<  "Создано множество:"
                        <<  std::endl;
 
            set.print();
 
            std::cout   <<  std::endl
                        <<  "Булеан данного множества имеет вид:"
                        <<  std::endl;
 
            set.powerset().print();
        }
        catch(std::invalid_argument&  e)
        {
            std::cout   <<  e.what()
                        <<  std::endl;
        }
    }
}
Artist
 Аватар для Artist
0 / 0 / 0
Регистрация: 13.06.2014
Сообщений: 3
13.01.2015, 17:31     Найти Булеан множества типа {a,b,c} #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
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
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <string>
 
using namespace std;
using namespace System;
 
vector <wstring> input(int noe, vector <wstring> vectorx) // Ввод множества
{
    wstring e;
    int k = 1;
 
    for (int i = 0; i < noe; i++)
    {
        Console::Write("Введите {0} элемент множества: ", (i + 1));
        wcin >> e;
        if (i == 0) vectorx.push_back(e);
        else
        {
            for (int j = 0; j < i; j++)
            {
                if (vectorx[j] == e)
                {
                    Console::Write("Множество не может содержать одинаковые элементы!\n");
                    i = (i - 1);
                    j = 0;
                    k = 1;
                    break;
                }
                else 
                {
                    if (k == i)
                    {
                        vectorx.push_back(e);
                        k = 1;
                    }
                    else k++;
                }
            }
        }
    }
    return vectorx;
}
 
void output(vector <wstring> vectorx) // Вывод
{
    int i;
    for (i = 0; i < vectorx.size(); i++)
    {
        if (i == (vectorx.size() - 1))
            wcout << vectorx[i];
        else wcout << vectorx[i] << ", ";
    }
    cout << "} \n";
};
 
void bn(int noe, vector <wstring> vectorx)
{
    int nos = pow(2, noe); // Количество подмножеств
    
    for (int i = 0; i < nos; i++) // Перебор битовых масок
    {
        Console::Write("Подмножество {0}: {1}", i + 1, "{");
        for (int j = 0; j < noe; j++) // Перебор битов в маске
            if (i & (1 << j)) // Если j-й бит установлен
                wcout << vectorx[j] << " "; // То выводим j-й элемент множества
        cout << "}\n";
    }
}
 
void main()
{
    vector <wstring> many;
    int noe;
    string num;
 
    Console::Write("Введите количество элементов множества: ");
    cin >> noe;
    many = input(noe, many);
    
    Console::Write("\nИсходное множество: {0}", "{");
    output(many);
 
    Console::Write("\nБулеан: \n\n");
    bn(noe, many);
 
    cout << "\n";
    system("pause");
}
Yandex
Объявления
13.01.2015, 17:31     Найти Булеан множества типа {a,b,c}
Ответ Создать тему
Опции темы

Текущее время: 05:53. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru