Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.88/25: Рейтинг темы: голосов - 25, средняя оценка - 4.88
3 / 3 / 3
Регистрация: 31.10.2010
Сообщений: 120
1

деление двух многочленов с остатком

01.11.2011, 20:24. Просмотров 5026. Ответов 7
Метки нет (Все метки)


Подскажите как лучше реализовать деление двух многочленов с остатком.
Моя идея такая структура данных:
C
1
2
3
4
5
6
7
8
9
10
11
12
struct Variables
    {
        QChar name; //переменная
        long degree; //степень переменной
    };
 
    struct Term
    {
        long value; // коэфициент при переменных
        QVector <Variables> variables; //вектор переменных
    };
    QVector <Term> Terms;
и наверное как-то в столбик делить..
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.11.2011, 20:24
Ответы с готовыми решениями:

Задача на тему деление многочленов с остатком

Деление двух многочленов
как разделить многочлен (2x^3+3x^2+4x-3) на многочлен (x-1/2) на турбо паскале. Пожалуйста помогите.

Деление двух многочленов
Привет всем! Было дано задание реализовать деление многочленов с комплексными коэффициентами через...

Деление многочленов от двух переменных
Есть многочлен от двух переменных, заданный следующей структурой: struct Monom { int...

7
Эксперт С++
3206 / 1733 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
02.11.2011, 10:30 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
/////////////////////////////////////////////////////////////////////////////////////////
//Реализовать деление двух многочленов с остатком.
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <limits>
#include <string>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef double                  T_coef;
typedef std::vector<T_coef>     T_polynom;
typedef std::string             T_str;
/////////////////////////////////////////////////////////////////////////////////////////
void  trim
    (
        T_polynom&  polynom,
        T_coef      my_epsilon
    )
{
    //Ничтожно малые коэффициенты заменяем нулями.
    for(T_polynom::iterator  coef_it = polynom.begin();
        coef_it != polynom.end(); ++coef_it)
    {
        if(abs(*coef_it) < my_epsilon)
        {
            *coef_it = 0;
        }
    }
 
    //Пока старший член полинома равен нулю, и он не последний в векторе, удаляем его.
    while( 
                abs( *polynom.rbegin() )  ==    0
            &&  polynom.size()            >     1
         )
    {
        polynom.pop_back();
    }       
}
/////////////////////////////////////////////////////////////////////////////////////////
void  divide
    (
        T_polynom           L,
        T_polynom           R,
        T_polynom&          quotient,
        T_polynom&          remainder,
        T_coef              my_epsilon
    )
{ 
    trim(L, my_epsilon);
    trim(R, my_epsilon);    
    
    int  quotient_degree    =   std::max
                                    ( 
                                        0, 
                                        int( L.size() ) - int( R.size() ) 
                                    );
 
    quotient.clear();
    quotient.resize(quotient_degree + 1);
    
    //Пока делимое по размеру не меньше делителя, и не равно нулю.
    while( 
                L.size()        >=  R.size() 
            &&  *L.rbegin()     !=  0
         )
    {
        //Делим старший элемент делимого на старший элемент делителя.       
        //Помещаем результат в соответствующий элемент частного.
        int  res_elem_degree = L.size() - R.size();
        quotient[res_elem_degree] = *L.rbegin() / *R.rbegin();
        
        //Пробегаемся по делителю, и каждый его элемент, умноженный на quotient[res_elem_degree],
        //вычитаем из соответствующего элемента делимого.
        for(size_t  i = 0; i < R.size(); ++i)
        {            
            L[i + res_elem_degree] -= R[i] * quotient[res_elem_degree];
        }
        
        trim(L, my_epsilon);    
    }
    remainder = L;
}
/////////////////////////////////////////////////////////////////////////////////////////
T_polynom  input_polynom(const T_str&  prompt)
{
    std::cout << std::endl
              << prompt
              << std::endl
              << "Введите степень полинома: ";
    int  polynom_degree = 0;
    std::cin >> polynom_degree;
 
    std::cout << "Введите коэффициенты полинома:"
              << std::endl;
 
    T_polynom  polynom(polynom_degree + 1);
    for(int  cur_degree = polynom_degree; cur_degree >= 0; --cur_degree)
    {
        std::cout << "x^"
                  << cur_degree
                  << ": ";
 
        std::cin >> polynom[cur_degree];
    }
    return  polynom;
}
/////////////////////////////////////////////////////////////////////////////////////////
void  print_polynom
    (
        const T_str&        prompt,
        const T_polynom&    polynom
    )
{
    std::cout << std::endl
              << prompt
              << std::endl;
 
    for(int  i = polynom.size() - 1; i >= 0; --i)
    {
        std::cout << std::showpos
                  << polynom[i];        
 
        if(i > 0)
        {
            std::cout << "x";
            if(i != 1)
            {
                std::cout << "^"
                          << std::noshowpos
                          << i;                                              
            }
        }
    }
    std::cout << std::endl;
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    const T_coef    MY_EPSILON  = std::numeric_limits<T_coef>::epsilon() * 10;
    T_polynom       L           = input_polynom("ВВОД ПОЛИНОМА-ДЕЛИМОГО.");
    T_polynom       R           = input_polynom("ВВОД ПОЛИНОМА-ДЕЛИТЕЛЯ.");
 
    T_polynom       quotient;
    T_polynom       remainder;
 
    divide
        (
            L,
            R,
            quotient,
            remainder,
            MY_EPSILON
        );
 
    print_polynom
        (
            "Полином-частное:",
            quotient
        );
 
    print_polynom
        (
            "Полином-остаток:",
            remainder
        );
}
1
3 / 3 / 3
Регистрация: 31.10.2010
Сообщений: 120
02.11.2011, 11:52  [ТС] 3
разве работает для многочленов(например) x^2*z^3 +x*z^2 и x*z+1?(
0
Эксперт С++
3206 / 1733 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
02.11.2011, 12:09 4
Цитата Сообщение от Scorpion93 Посмотреть сообщение
разве работает для многочленов(например) x^2*z^3 +x*z^2 и x*z+1?(
Так вам задали деление многочленов от НЕСКОЛЬКИХ переменных?
Или вы это уже сами придумали?
0
3 / 3 / 3
Регистрация: 31.10.2010
Сообщений: 120
02.11.2011, 18:58  [ТС] 5
задали (от 3)
0
Эксперт С++
3206 / 1733 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
03.11.2011, 09:12 6
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
/////////////////////////////////////////////////////////////////////////////////////////
//Деление с остатком полиномов от трех переменных.
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <iterator>
#include <limits>
#include <cmath>
#include <set>
#include <string>
#include <utility>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string  T_str;
typedef double       T_coef;
typedef int          T_degree;
/////////////////////////////////////////////////////////////////////////////////////////
struct  T_monom
{
    T_coef      coef_;
    T_degree    X_degree_;
    T_degree    Y_degree_;
    T_degree    Z_degree_;    
    //-----------------------------------------------------------------------------------
    T_monom
        (
            T_coef      coef        = 0,
            T_degree    X_degree    = 0,
            T_degree    Y_degree    = 0,
            T_degree    Z_degree    = 0            
        )
        :
        coef_       (coef),
        X_degree_   (X_degree),
        Y_degree_   (Y_degree),
        Z_degree_   (Z_degree)
    {}
    //-----------------------------------------------------------------------------------
    bool        divides     (const T_monom&  monom)     const
    {
        return      X_degree_ <= monom.X_degree_
                &&  Y_degree_ <= monom.Y_degree_
                &&  Z_degree_ <= monom.Z_degree_;
    }
    //-----------------------------------------------------------------------------------
    T_monom     operator*   (const T_monom&  monom)     const
    {
        T_monom  res
            (
                coef_       *   monom.coef_,
                X_degree_   +   monom.X_degree_,
                Y_degree_   +   monom.Y_degree_,
                Z_degree_   +   monom.Z_degree_
            );
        return  res;
    }
    //-----------------------------------------------------------------------------------
    T_monom     operator/   (const T_monom&  monom)     const
    {
        T_monom  res
            (
                coef_       /   monom.coef_,
                X_degree_   -   monom.X_degree_,
                Y_degree_   -   monom.Y_degree_,
                Z_degree_   -   monom.Z_degree_
            );
        return  res;
    }
    //-----------------------------------------------------------------------------------
    T_monom     operator-   ()                          const
    {
        T_monom  res = *this;
        res.coef_ *= -1;
        return  res;
    }
    //-----------------------------------------------------------------------------------
    bool        operator==  (const T_monom&  monom)     const
    {
        return      coef_       ==  monom.coef_            
                &&  X_degree_   ==  monom.X_degree_
                &&  Y_degree_   ==  monom.Y_degree_
                &&  Z_degree_   ==  monom.Z_degree_;            
    }
    //-----------------------------------------------------------------------------------
    bool        operator!=  (const T_monom&  monom)     const
    {
        return  !(*this == monom);
    }
    //-----------------------------------------------------------------------------------
    bool        operator<   (const T_monom&  monom)     const
    {
        //Сортируем так, чтобы в начале стояли старшие члены.
        return      std::make_pair
                        (
                            X_degree_,
                            std::make_pair
                                (
                                    Y_degree_,
                                    Z_degree_
                                )
                        )
 
                >   std::make_pair
                        (
                            monom.X_degree_,
                            std::make_pair
                                (
                                    monom.Y_degree_,
                                    monom.Z_degree_
                                )
                        );
    }
};
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::multiset<T_monom>  T_polynom_XYZ;
/////////////////////////////////////////////////////////////////////////////////////////
void  input_monom_var_degree
    (
        const T_str&    prompt,
        T_degree&       degree
    )
{
    do
    {
        std::cout   <<  prompt;
        std::cin    >>  degree;
    }while(degree < 0);
}
/////////////////////////////////////////////////////////////////////////////////////////
T_polynom_XYZ  input_polynom_XYZ(const T_str&  prompt)
{
    std::cout << prompt
              << std::endl;              
 
    int  polynom_size = 0; 
    do
    {
        std::cout << "Введите количество одночленов в многочлене от переменных X, Y, Z: ";
        std::cin >> polynom_size;
    }while(polynom_size <= 0);
    
    std::cout << std::endl
              << "Введите "
              << polynom_size
              << " одночленов от переменных X, Y, Z."
              << std::endl;
 
    T_polynom_XYZ  polynom;
    for(int  i = 0; i < polynom_size; ++i)
    {
        T_monom  cur_monom;
        std::cout << std::endl
                  << "одночлен #"
                  << i + 1 
                  << ":"
                  << std::endl;
 
        std::cout<< "\tкоэффициент:\t";
        std::cin >> cur_monom.coef_;
 
        input_monom_var_degree
            (
                "\tстепень X:\t",
                cur_monom.X_degree_
            );
 
        input_monom_var_degree
            (
                "\tстепень Y:\t",
                cur_monom.Y_degree_
            );
 
        input_monom_var_degree
            (
                "\tстепень Z:\t",
                cur_monom.Z_degree_
            );
 
        polynom.insert(cur_monom);
    }
    std::cout << std::endl
              << std::endl;
    return  polynom; 
}
/////////////////////////////////////////////////////////////////////////////////////////
void  trim
    (
        T_polynom_XYZ&  polynom,
        T_coef          my_epsilon
    )
{
    if( !polynom.empty() )
    {
        //Обходим полином и все одночлены с одинаковыми степенями переменных объединяем в один.
        for(T_polynom_XYZ::iterator  elem_it = polynom.begin();
            elem_it != polynom.end(); )
        {
            if( polynom.count(*elem_it) > 1 )
            {
                T_polynom_XYZ::iterator  second_elem_it = elem_it;
                std::advance(second_elem_it, 1);
                for(T_polynom_XYZ::iterator  dup_elem_it = second_elem_it;
                    dup_elem_it != polynom.upper_bound(*elem_it); )
                {
                    elem_it->coef_ += dup_elem_it->coef_;
                    T_polynom_XYZ::iterator  old_dup_elem_it = dup_elem_it;
                    ++dup_elem_it;
                    polynom.erase(old_dup_elem_it);
                }
            }
 
            T_polynom_XYZ::iterator  old_elem_it = elem_it;
            ++elem_it;
            //Если коэффициент очень близок к нулю, то удаляем элемент.
            if(abs(old_elem_it->coef_)  <   my_epsilon)
            {
                polynom.erase(old_elem_it);
            }      
        }    
    }//if( !polynom.empty() )
 
    if( polynom.empty() )
    {
        polynom.insert( T_monom() );
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
void  divide
    (
        T_polynom_XYZ   L,
        T_polynom_XYZ   R,
        T_polynom_XYZ&  quotient,
        T_polynom_XYZ&  remainder,
        T_coef          my_epsilon
    )
{ 
    trim(L, my_epsilon);
    trim(R, my_epsilon); 
 
    quotient.clear();    
 
    bool  bool_res = true;
    while(
            (       
                    L.size()    >   1
                ||  *L.begin()  !=  T_monom()
            )
            &&  bool_res
         )
    {
        bool_res = false;
        T_polynom_XYZ::const_iterator  elem_for_div_it;
        //Ищем самый старший член в L, который делится на старший член R.
        for(T_polynom_XYZ::const_iterator  elem_it = L.begin();
            elem_it != L.end(); ++elem_it)
        {
            if( R.begin()->divides(*elem_it) )
            {
                bool_res            = true;
                elem_for_div_it     = elem_it;
                break;
            }
        } 
 
        if(bool_res)
        {
            //Вычисляем множитель.
            T_monom  factor = *elem_for_div_it / *R.begin();
            //Добавляем его в результат.
            quotient.insert(factor);
 
            //Вычитаем из L делитель R, умноженный на factor.
            for(T_polynom_XYZ::const_iterator  R_elem_it = R.begin();
                R_elem_it != R.end(); ++R_elem_it)
            {
                L.insert(-*R_elem_it * factor);
            }
            trim(L, my_epsilon);
        }
    }
 
    remainder = L;
    trim(quotient, my_epsilon); 
}
/////////////////////////////////////////////////////////////////////////////////////////
void  print_polynom
    (
        const T_str&            prompt,
        const T_polynom_XYZ&    polynom
    )
{
    std::cout << std::endl
              << prompt
              << std::endl;
 
    for(T_polynom_XYZ::const_iterator  elem_it = polynom.begin();
        elem_it != polynom.end(); ++elem_it)
    {
        std::cout << std::showpos
                  << elem_it->coef_ 
                  << "*x^"
                  << std::noshowpos
                  << elem_it->X_degree_
                  << "*y^"
                  << elem_it->Y_degree_
                  << "*z^"
                  << elem_it->Z_degree_
                  << std::endl;
    }
    std::cout << std::endl;
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    const T_coef    MY_EPSILON  =   std::numeric_limits<T_coef>::epsilon() * 10;
    T_polynom_XYZ   L           =   input_polynom_XYZ("ВВОД ПОЛИНОМА-ДЕЛИМОГО.");    
    T_polynom_XYZ   R           =   input_polynom_XYZ("ВВОД ПОЛИНОМА-ДЕЛИТЕЛЯ.");
 
    T_polynom_XYZ   quotient;
    T_polynom_XYZ   remainder;
 
    divide
        (
            L,
            R,
            quotient,
            remainder,
            MY_EPSILON
        );
 
    print_polynom
        (
            "Полином-частное:",
            quotient
        );
 
    print_polynom
        (
            "Полином-остаток:",
            remainder
        );
}
1
3 / 3 / 3
Регистрация: 31.10.2010
Сообщений: 120
06.11.2011, 19:35  [ТС] 7
Mr.X, в 203 строчке пишет что итерал константный..( (пробовал в 2010 студие)
0
Эксперт С++
3206 / 1733 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
06.11.2011, 22:31 8
Цитата Сообщение от Scorpion93 Посмотреть сообщение
Mr.X, в 203 строчке пишет что итерал константный..( (пробовал в 2010 студие)
Вот так будет корректнее:
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
/////////////////////////////////////////////////////////////////////////////////////////
//Деление с остатком полиномов от трех переменных.
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <iterator>
#include <limits>
#include <cmath>
#include <set>
#include <string>
#include <utility>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string  T_str;
typedef double       T_coef;
typedef int          T_degree;
/////////////////////////////////////////////////////////////////////////////////////////
struct  T_monom
{
    T_coef      coef_;
    T_degree    X_degree_;
    T_degree    Y_degree_;
    T_degree    Z_degree_;    
    //-----------------------------------------------------------------------------------
    T_monom
        (
            T_coef      coef        = 0,
            T_degree    X_degree    = 0,
            T_degree    Y_degree    = 0,
            T_degree    Z_degree    = 0            
        )
        :
        coef_       (coef),
        X_degree_   (X_degree),
        Y_degree_   (Y_degree),
        Z_degree_   (Z_degree)
    {}
    //-----------------------------------------------------------------------------------
    bool        divides     (const T_monom&  monom)     const
    {
        return      X_degree_ <= monom.X_degree_
                &&  Y_degree_ <= monom.Y_degree_
                &&  Z_degree_ <= monom.Z_degree_;
    }
    //-----------------------------------------------------------------------------------
    T_monom     operator*   (const T_monom&  monom)     const
    {
        T_monom  res
            (
                coef_       *   monom.coef_,
                X_degree_   +   monom.X_degree_,
                Y_degree_   +   monom.Y_degree_,
                Z_degree_   +   monom.Z_degree_
            );
        return  res;
    }
    //-----------------------------------------------------------------------------------
    T_monom     operator/   (const T_monom&  monom)     const
    {
        T_monom  res
            (
                coef_       /   monom.coef_,
                X_degree_   -   monom.X_degree_,
                Y_degree_   -   monom.Y_degree_,
                Z_degree_   -   monom.Z_degree_
            );
        return  res;
    }
    //-----------------------------------------------------------------------------------
    T_monom     operator-   ()                          const
    {
        T_monom  res = *this;
        res.coef_ *= -1;
        return  res;
    }
    //-----------------------------------------------------------------------------------
    bool        operator==  (const T_monom&  monom)     const
    {
        return      coef_       ==  monom.coef_            
                &&  X_degree_   ==  monom.X_degree_
                &&  Y_degree_   ==  monom.Y_degree_
                &&  Z_degree_   ==  monom.Z_degree_;            
    }
    //-----------------------------------------------------------------------------------
    bool        operator!=  (const T_monom&  monom)     const
    {
        return  !(*this == monom);
    }
    //-----------------------------------------------------------------------------------
    bool        operator<   (const T_monom&  monom)     const
    {
        //Сортируем так, чтобы в начале стояли старшие члены.
        return      std::make_pair
                        (
                            X_degree_,
                            std::make_pair
                                (
                                    Y_degree_,
                                    Z_degree_
                                )
                        )
 
                >   std::make_pair
                        (
                            monom.X_degree_,
                            std::make_pair
                                (
                                    monom.Y_degree_,
                                    monom.Z_degree_
                                )
                        );
    }
};
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::multiset<T_monom>  T_polynom_XYZ;
/////////////////////////////////////////////////////////////////////////////////////////
void  input_monom_var_degree
    (
        const T_str&    prompt,
        T_degree&       degree
    )
{
    do
    {
        std::cout   <<  prompt;
        std::cin    >>  degree;
    }while(degree < 0);
}
/////////////////////////////////////////////////////////////////////////////////////////
T_polynom_XYZ  input_polynom_XYZ(const T_str&  prompt)
{
    std::cout << prompt
              << std::endl;              
 
    int  polynom_size = 0; 
    do
    {
        std::cout << "Введите количество одночленов в многочлене от переменных X, Y, Z: ";
        std::cin >> polynom_size;
    }while(polynom_size <= 0);
    
    std::cout << std::endl
              << "Введите "
              << polynom_size
              << " одночленов от переменных X, Y, Z."
              << std::endl;
 
    T_polynom_XYZ  polynom;
    for(int  i = 0; i < polynom_size; ++i)
    {
        T_monom  cur_monom;
        std::cout << std::endl
                  << "одночлен #"
                  << i + 1 
                  << ":"
                  << std::endl;
 
        std::cout<< "\tкоэффициент:\t";
        std::cin >> cur_monom.coef_;
 
        input_monom_var_degree
            (
                "\tстепень X:\t",
                cur_monom.X_degree_
            );
 
        input_monom_var_degree
            (
                "\tстепень Y:\t",
                cur_monom.Y_degree_
            );
 
        input_monom_var_degree
            (
                "\tстепень Z:\t",
                cur_monom.Z_degree_
            );
 
        polynom.insert(cur_monom);
    }
    std::cout << std::endl
              << std::endl;
    return  polynom; 
}
/////////////////////////////////////////////////////////////////////////////////////////
void  trim
    (
        T_polynom_XYZ&  polynom,
        T_coef          my_epsilon
    )
{
    if( !polynom.empty() )
    {
        T_polynom_XYZ  new_polynom;
        //Обходим полином, и все одночлены копируем в new_polynom, при этом
        //одночлены с одинаковыми степенями переменных объединяем в один,
        //суммируя их коэффициенты.
        for(T_polynom_XYZ::const_iterator  elem_it = polynom.begin();
            elem_it != polynom.end(); )
        {            
            T_polynom_XYZ::value_type  cur_monom = *elem_it;
            //Заводим одночлен для суммирования коэффициентов.
            T_polynom_XYZ::value_type  new_monom = cur_monom;                        
            ++elem_it;
            //Обходим все степенные дубликаты текущего одночлена.
            for(; elem_it != polynom.upper_bound(cur_monom); ++elem_it)
            {
                new_monom.coef_ += elem_it->coef_;
            }            
            
            //Если коэффициент нового одночлена не очень близок к нулю, 
            //то копируем этот одночлен в новый полином.
            if(abs(new_monom.coef_)  >   my_epsilon)
            {
                new_polynom.insert(new_monom);
            }            
        } 
        std::swap(polynom, new_polynom);        
    }//if( !polynom.empty() )
 
    //Если полином опустел после суммирования коэффициентов, или был пуст изначально, то.
    if( polynom.empty() )
    {
        polynom.insert( T_monom() );
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
void  divide
    (
        T_polynom_XYZ   L,
        T_polynom_XYZ   R,
        T_polynom_XYZ&  quotient,
        T_polynom_XYZ&  remainder,
        T_coef          my_epsilon
    )
{ 
    trim(L, my_epsilon);
    trim(R, my_epsilon); 
 
    quotient.clear();    
 
    bool  bool_res = true;
    while(
            (       
                    L.size()    >   1
                ||  *L.begin()  !=  T_monom()
            )
            &&  bool_res
         )
    {
        bool_res = false;
        T_polynom_XYZ::const_iterator  elem_for_div_it;
        //Ищем самый старший член в L, который делится на старший член R.
        for(T_polynom_XYZ::const_iterator  elem_it = L.begin();
            elem_it != L.end(); ++elem_it)
        {
            if( R.begin()->divides(*elem_it) )
            {
                bool_res            = true;
                elem_for_div_it     = elem_it;
                break;
            }
        } 
 
        if(bool_res)
        {
            //Вычисляем множитель.
            T_monom  factor = *elem_for_div_it / *R.begin();
            //Добавляем его в результат.
            quotient.insert(factor);
 
            //Вычитаем из L делитель R, умноженный на factor.
            for(T_polynom_XYZ::const_iterator  R_elem_it = R.begin();
                R_elem_it != R.end(); ++R_elem_it)
            {
                L.insert(-*R_elem_it * factor);
            }
            trim(L, my_epsilon);
        }
    }
 
    remainder = L;
    trim(quotient, my_epsilon); 
}
/////////////////////////////////////////////////////////////////////////////////////////
void  print_polynom
    (
        const T_str&            prompt,
        const T_polynom_XYZ&    polynom
    )
{
    std::cout << std::endl
              << prompt
              << std::endl;
 
    for(T_polynom_XYZ::const_iterator  elem_it = polynom.begin();
        elem_it != polynom.end(); ++elem_it)
    {
        std::cout << std::showpos
                  << elem_it->coef_ 
                  << "*x^"
                  << std::noshowpos
                  << elem_it->X_degree_
                  << "*y^"
                  << elem_it->Y_degree_
                  << "*z^"
                  << elem_it->Z_degree_
                  << std::endl;
    }
    std::cout << std::endl;
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    const T_coef    MY_EPSILON  =   std::numeric_limits<T_coef>::epsilon() * 10;
    T_polynom_XYZ   L           =   input_polynom_XYZ("ВВОД ПОЛИНОМА-ДЕЛИМОГО.");    
    T_polynom_XYZ   R           =   input_polynom_XYZ("ВВОД ПОЛИНОМА-ДЕЛИТЕЛЯ.");
 
    T_polynom_XYZ   quotient;
    T_polynom_XYZ   remainder;
 
    divide
        (
            L,
            R,
            quotient,
            remainder,
            MY_EPSILON
        );
 
    print_polynom
        (
            "Полином-частное:",
            quotient
        );
 
    print_polynom
        (
            "Полином-остаток:",
            remainder
        );
}
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.11.2011, 22:31

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

Длинная арифметика: деление с остатком двух чисел, находящихся в двусвязном списке
Доброго времени суток. Подскажите, как реализовать деление с остатком двух чисел, находящихся в...

Умножение, деление и деление с остатком
Рассмотрим эти операции на примере. static void Main() { int i = 100, j = 15; double a =...

Деление с остатком
Как написать условие для примера на деление, что бы всегда пример при генерировании получался с...

Деление с остатком
Отлаживаю программу через TD. вот код: xor dx, dx ;В регистре ah находится 05h, а в al 6Ah...

Деление с остатком
Здравствуйте, форумчане! Выручите меня, пожалуйста. Задание такое: Найти остаток от деления на 89...

Деление с остатком
Всем привет! Не получается в bat файле вычислить вот это выражение (4482/22847)*8*1024 Знаю что...


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

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

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