Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
KyKi
4 / 4 / 1
Регистрация: 12.09.2013
Сообщений: 134
#1

Дискретная математика. Класс-Группа:множество+бинарная операция - C++

23.09.2014, 19:28. Просмотров 723. Ответов 3
Метки нет (Все метки)

Здравствуйте, помогите пожалуйста. Начали изучать дискретку и как-то тяжело в начале это понять. Помогите пожалуйста разобраться в задании. Вроде и с программированием нормально, но тут не понимаю абсолютно. Буду очень благодарна за любые подсказки.

Задание:
Создать класс группу, которая содержит определенное множество, на котором введено бинарную алгебраическую операцию (определены в задании 3 контрольной работы 1), и имеет конструктор, деструктор, функции доступа, метод-операцию над элементами множества, единичный (нейтральный) элемент, обратный элемент для каждого элемента множества. Реализовать операцию над элементами и вывести результаты выполнения операции на экран.
Замечание. Если множество с операцией не является группой, добавить в множество элементы, для которых нарушается какое -то свойство, чтобы она стала группой.

Задание из контрольной:
Определите, образует ли группу множество невырожденных матриц порядка n с действительными элементами относительно умножения.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.09.2014, 19:28
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Дискретная математика. Класс-Группа:множество+бинарная операция (C++):

Нужна помощь по Дискретке. Класс-группа: множество + бинарная операция
Здравствуйте. В этом году в академии начали преподавать дискретную математику....

Бинарная(побитовая) операция
Мне нужно написать функцию которая проверяет значение есть парным или нет...

Дискретная математика
Есть три программы по дискретной математике. Выложу сюда. Может кому-то...

дискретная математика
Применение дискретной математики в системах автоматизаций???

Дискретная математика
Кароч парни не знаю как обьяснить......кароч есть число обозначим n,и есть k...

Дискретная математика
Здравствуйте! Помогите с зачетным задание! Вот оно: Дано несколько вершин,...

3
OstapBender
584 / 523 / 75
Регистрация: 22.03.2011
Сообщений: 1,585
24.09.2014, 16:44 #2
Ну в общих чертах я так понял:

делаем класс "группа", в нем:
1) элементы множества - в твоем случае это матрицы порядка n (можно оформить в виде массива матриц например)
2) операции - бинарная: умножение (реализуй метод умножения матриц) и унарная: взятие обратного элемента (нахождение обратной матрицы)
3) нейтральный элемент - матрица Е (при умножении А*Е = А)

"Определите, образует ли группу множество невырожденных матриц порядка n с действительными элементами относительно умножения." - см. вики

общие комментарии:
в конструктор можно передавать массив матриц (элементы множества) и их размерность n
матрицы лучше сделать отдельным классом
матрицу Е можно хранить как статическую константу
можно воспользоваться сторонней библиотекой для матриц
0
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
28.09.2014, 09:05 #3
delete

Добавлено через 7 минут
Первая часть:
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
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <set>
#include <utility>
#include <string>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string     T_str;
/////////////////////////////////////////////////////////////////////////////////////////
template
    <
        typename    T_elem,
        typename    T_less,
        typename    T_bin_op,
        typename    T_inverse_elem,
        typename    T_print_elem
    >
class   T_group
{
    //-----------------------------------------------------------------------------------
    static  const   int     MAX_GROUP_SIZE  =   10;
    //-----------------------------------------------------------------------------------
    typedef std::set    < T_elem,                       T_less  >   T_elements;
    typedef std::map    < T_elem,           T_elem,     T_less  >   T_inverse_element_of;
    typedef std::pair   < T_elem,           T_elem              >   T_elements_pair;
    typedef std::map    < T_elements_pair,  T_elem              >   T_product_of_elements;
    //-----------------------------------------------------------------------------------
    T_elements                  elements_;
    T_inverse_element_of        inverse_element_of_;
    T_product_of_elements       product_of_elements_;
    T_elem                  *   identity_element_ptr_;
    bool                        generation_is_stopped_;
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    T_group( T_elements     const   &   elements )
        :
        elements_               ( elements  ),
        identity_element_ptr_   ()
    {
        generate_elements();
    }
    //-----------------------------------------------------------------------------------
    ~T_group()
    {
        delete  identity_element_ptr_;
    }
    //-----------------------------------------------------------------------------------
    int     size()                                                                  const
    {
        return  elements_.size();
    }
    //-----------------------------------------------------------------------------------
    void    print()                                                                 const
    {
        T_print_elem    print_elem;
 
        if( generation_is_stopped_ )
        {
            std::cout   <<  "Генерация элементов группы приостановлена."
                        <<  std::endl;
        }//if
 
        std::cout   <<  "Группа состоит из "
                    <<  size()
                    <<  " элементов"
                    <<  std::endl
                    <<  std::endl
                    <<  "Нейтральный элемент: "
                    <<  std::endl;
 
        if  (
                get_identity_element_ptr()
            )
        {
            print_elem
                (
                    *get_identity_element_ptr()
                );
        }
        else
        {
            std::cout   <<  "не сформирован"
                        <<  std::endl;
        }//else
 
        std::cout   <<  std::endl
                    <<  std::endl
                    <<  "Элемент"
                    <<  "\t\t\t"
                    <<  "Обратный элемент"
                    <<  std::endl;
 
        std::for_each
            (
                inverse_element_of_.begin   (),
                inverse_element_of_.end     (),
 
                [=]                         ( T_inverse_element_of::value_type  const   &  elem_and_this_inv_elem )
                {
                    print_elem( elem_and_this_inv_elem.first    );
                    std::cout   <<  '\t';
                    print_elem( elem_and_this_inv_elem.second   );
                    std::cout   <<  std::endl;
                }
            );
 
        std::cout   <<  std::endl
                    <<  "Произведения элементов"
                    <<  std::endl;
 
        std::for_each
            (
                product_of_elements_.begin  (),
                product_of_elements_.end    (),
 
                [=]                         ( T_product_of_elements::value_type  elements_pair_and_their_product )
                {
                    print_elem( elements_pair_and_their_product     .first.first    );
                    std::cout   <<  "\t* ";
                    print_elem( elements_pair_and_their_product     .first.second   );
                    std::cout   <<  "\t= ";
                    print_elem( elements_pair_and_their_product     .second         );
                    std::cout   <<  std::endl;
                }
            );
    }
    //-----------------------------------------------------------------------------------
    T_elem  const   &   mult
        (
            T_elem  const   &   L,
            T_elem  const   &   R
        )
    {
        T_bin_op    bin_op;
        auto    elem_pair   =   std::make_pair( L, R );
        auto    it          =   product_of_elements_.find( elem_pair );
 
        return  it  ==  product_of_elements_.end()
                    ?   product_of_elements_[ elem_pair ]   =   bin_op( L, R )
                    :   product_of_elements_[ elem_pair ];
    }
    //-----------------------------------------------------------------------------------
    T_elem  *   get_identity_element_ptr()                                      const
    {
        return  identity_element_ptr_;
    }
    //-----------------------------------------------------------------------------------
    T_elem  const   &   get_inverse_element( T_elem    const   &   elem    )
    {
        T_inverse_elem  inverse_elem;
        auto    it      =   inverse_element_of_.find( elem );
 
        if  (
                it  ==  inverse_element_of_.end()
            )
        {
            inverse_element_of_[ elem ]   =   inverse_elem( elem );
 
            if  (
                        inverse_element_of_[ elem ]     ==  elem
                    &&  !identity_element_ptr_
                )
            {
                identity_element_ptr_    =   new     T_elem (
                                                                inverse_element_of_[ elem ]
                                                            );
            }//if
        }//if
 
        return  inverse_element_of_[ elem ];
    }
    //-----------------------------------------------------------------------------------
    T_elem  left_division
        (
            T_elem  const   &   L,
            T_elem  const   &   R
        )
    {
        return  mult    (
                            get_inverse_element( R ),
                            L
                        );
    }
    //-----------------------------------------------------------------------------------
    T_elem  right_division
        (
            T_elem  const   &   L,
            T_elem  const   &   R
        )
    {
        return  mult    (
                            L,
                            get_inverse_element( R )
                        );
    }
    //-----------------------------------------------------------------------------------
private:
    //-----------------------------------------------------------------------------------
    //Из математики известно, что множество с определенной на нем ассоциативной операцией
    //является группой только в том случае, если на этом множестве выполняется левое и правое 
    //деление для любых двух его элементов.
    //В данной процедуре выполняется левое и правое деление для элементов стартового множества,
    //пока не будут получены все элементы группы, или пока процесс не будет приостановлен 
    //из-за превышения заданного предельного количества элементов группы.
    void    generate_elements()
    {
        int     old_elements_size   =   0;
        generation_is_stopped_      =   false;
 
        do
        {
            old_elements_size   =   elements_.size();
 
            for (
                    auto
                    L_elem_it     =   elements_.begin     ();
                    L_elem_it     !=  elements_.end       ();
                    ++L_elem_it
                )
            {
                for (
                        auto
                        R_elem_it     =   elements_.begin     ();
                        R_elem_it     !=  elements_.end       ();
                        ++R_elem_it
                    )
                {
                    elements_.insert
                        (
                            left_division   ( *L_elem_it,   *R_elem_it )
                        );
 
                    elements_.insert
                        (
                            right_division  ( *L_elem_it,   *R_elem_it )
                        );
 
                    if  (
                            elements_.size()    >   MAX_GROUP_SIZE
                        )
                    {
                        generation_is_stopped_  =   true;
                        break;
                    }
                }//for
            }//for
        }while  (
                    elements_.size()    !=  old_elements_size
                );
    }
    //-----------------------------------------------------------------------------------
};
1
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
28.09.2014, 09:06 #4
Вторая часть:
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
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::vector < double    >   T_row;
typedef std::vector < T_row     >   T_matr;
typedef std::set    < T_matr    >   T_matr_set;
/////////////////////////////////////////////////////////////////////////////////////////
struct  T_matr_mult
{
    //-----------------------------------------------------------------------------------
    T_matr  operator()
        (
            T_matr  const   &   L,
            T_matr  const   &   R
        )
    {
        int     matr_dim    =   L.size();
        auto    transp_R    =   get_transp_matr( R );
        auto    res_matr    =   L;
 
        for( int  i = 0; i < matr_dim; ++i )
        {
            for( int  j = 0; j < matr_dim; ++j )
            {
                res_matr[i][j]  =   std::inner_product
                                        (
                                            L[i]        .begin  (),
                                            L[i]        .end    (),
                                            transp_R[j] .begin  (),
                                            0
                                        );
            }//for
        }//for
 
        return  res_matr;
    }
    //-----------------------------------------------------------------------------------
    T_matr  get_transp_matr( T_matr  const   &   matr )
    {
        T_matr  res_matr    =   matr;
        int     matr_dim    =   res_matr.size();
 
        for( int  i = 0; i < matr_dim; ++i )
        {
            for( int  j = i + 1; j < matr_dim; ++j )
            {
                std::swap
                    (
                        res_matr[i][j],
                        res_matr[j][i]
                    );
            }//for
        }//for
 
        return  res_matr;
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
struct  T_get_invertible_matr
{
    //-----------------------------------------------------------------------------------
    T_matr  operator()  ( T_matr  matr )                                            const
    {
        int     matr_dim    =   matr.size();
 
        auto    res_matr    =   T_matr
                                    (
                                        matr_dim,
                                        T_row( matr_dim )
                                    );
 
        for( int  i = 0; i < matr_dim; ++i )
        {
            res_matr[i][i]  =   1;
        }//for
 
        for( int  j = 0; j < matr_dim; ++j )
        {
            int     max_abs_elem_row_ind    =   j;
 
            for( int  i = j + 1; i < matr_dim; ++i )
            {
                if  (
                        abs( matr[i][j] )   >   abs( matr[ max_abs_elem_row_ind ][j] )
                    )
                {
                    max_abs_elem_row_ind    =   i;
                }//if
            }//for
 
            std::swap
                (
                    matr[j],
                    matr[ max_abs_elem_row_ind ]
                );
 
            std::swap
                (
                    res_matr[j],
                    res_matr[ max_abs_elem_row_ind ]
                );
 
            double  factor  =   matr[j][j];
 
            for( int  jj = 0; jj < matr_dim; ++jj )
            {
                matr        [j][jj]     /=  factor;
                res_matr    [j][jj]     /=  factor;
            }//for
 
            for( int  i = 0; i < matr_dim; ++i )
            {
                if  (
                            i           ==  j
                        ||  matr[i][j]  ==  0
                    )
                {
                    continue;
                }//if
 
                factor  =   matr[i][j];
 
                for( int  jj = 0; jj < matr_dim; ++jj )
                {
                    matr        [i][jj]     -=  matr        [j][jj] * factor;
                    res_matr    [i][jj]     -=  res_matr    [j][jj] * factor;
                }//for
            }//for
        }//for j
 
        return  res_matr;
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
struct  T_print_matr
{
    void    operator()  ( T_matr  const   &   matr )                                const
    {
        static  const   char    LEFT_MATR_BOUND     =   '{';
        static  const   char    RIGHT_MATR_BOUND    =   '}';
 
        static  const   T_str   LEFT_ROW_BOUND      =   "( ";
        static  const   T_str   RIGHT_ROW_BOUND     =   ")";
 
        std::cout   <<  LEFT_MATR_BOUND;
 
        std::for_each
            (
                matr.begin  (),
                matr.end    (),
 
                []          ( T_row     const   &   row )
                {
                    std::cout   <<  LEFT_ROW_BOUND;
 
                    std::copy
                        (
                            row.begin                       (),
                            row.end                         (),
                            std::ostream_iterator<double>   ( std::cout, " " )
                        );
 
                    std::cout   <<  RIGHT_ROW_BOUND;
                }
            );
 
        std::cout   <<  RIGHT_MATR_BOUND;
    }
};
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::locale::global(std::locale(""));
    const   int     MATR_DIM    =   2;
 
    T_matr  a   (
                    MATR_DIM,
                    T_row( MATR_DIM )
                );
 
    a[0][1]     =   -1;
    a[1][0]     =   1;
 
    T_matr_set  matr_set;
    matr_set.insert(a);
 
    T_group
        <
            T_matr,
            std::less< T_matr >,
            T_matr_mult,
 
            T_get_invertible_matr,
            T_print_matr
        >
        group( matr_set );
 
    group.print();
 
    system("pause");
}
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.09.2014, 09:06
Привет! Вот еще темы с решениями:

Программа дискретная математика
Вообщем такая задача: нужно написать программу, которая выводит на экран...

Дискретная математика. Графы
Задание: Разработать алгоритм решения задачи (согласно приведенной таблице...

Задачи на C/C++. Дискретная математика. Посоветуйте книги (сайты)
Здравствуйте У Меня к Вам вопрос Кто-нибудь может посоветовать учебник...

Сочетания без повторений, Комбинаторика, Дискретная математика
Помогите, пожалуйста, решить данную задачу на C++ или С. Задано натуральное...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

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