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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.94
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
#1

Многочлены над GF(2^m) - C++

06.11.2012, 02:35. Просмотров 2215. Ответов 39
Метки нет (Все метки)

Пишу кодер Рида-Соломона.
Дано следующее:
* http://www.cyberforum.ru/cgi-bin/latex.cgi?m - количество битов в одном символе (читай, элементов поля http://www.cyberforum.ru/cgi-bin/latex.cgi?GF(2^m));
* http://www.cyberforum.ru/cgi-bin/latex.cgi?n - длина кода (в символах);
* http://www.cyberforum.ru/cgi-bin/latex.cgi?k - длина сообщения (в символах);
* http://www.cyberforum.ru/cgi-bin/latex.cgi?g(x) - неприводимый многочлен степени http://www.cyberforum.ru/cgi-bin/latex.cgi?n-k над http://www.cyberforum.ru/cgi-bin/latex.cgi?GF(2^m)
* http://www.cyberforum.ru/cgi-bin/latex.cgi?\overline m - сообщение из 0 и 1 конечной длины.
* http://www.cyberforum.ru/cgi-bin/latex.cgi?u - сообщение, полученное из http://www.cyberforum.ru/cgi-bin/latex.cgi?\overline m путём выделения блоков длины http://www.cyberforum.ru/cgi-bin/latex.cgi?m;
* А также естественное отображение http://www.cyberforum.ru/cgi-bin/latex.cgi?A:GF^n(2^m)\to P_n(GF(2^m)); (\alpha _0\alpha _1...\alpha _{n-1})\mapsto \alpha _0+\alpha _1x+...+\alpha _{n-1}x^{n-1}
На выходе нужно получить РС-код:
* http://www.cyberforum.ru/cgi-bin/latex.cgi?v - код длины http://www.cyberforum.ru/cgi-bin/latex.cgi?n (в символах), по формуле: http://www.cyberforum.ru/cgi-bin/latex.cgi?v=A^{-1}(x^{n-k}(Au)(x)+(x^{n-k}(Au)(x) \mathrm{mod} g(x)))
http://www.cyberforum.ru/cgi-bin/latex.cgi?GF(2^m)=\{0,\alpha ^0, \alpha ^1,...,\alpha ^{2^m-2}\}, где http://www.cyberforum.ru/cgi-bin/latex.cgi?g(\alpha )=0.
По теории вроди бы всё, сейчас попробую описать прототип реализации.

Добавлено через 2 часа 17 минут
Посмотрите, пожалуйста!
Кликните здесь для просмотра всего текста
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
#ifndef RS_encoder.h
 
#include <vector>
 
const int GROUP_DEGREE = 0; // = m -- порядок группы GF(2^m)
const std::vector<int> PRIMITIVE_POLYNOMIAL (0); // примитивный полином в GF(2^m)
 
class GF 
{
private:
    int alpha_power; // представление в виде степени альфа
    std::vector<int> alpha_vector; // представление в виде вектора
    bool null; // индикатор того, что вектор нулевой
 
    void power_to_vector ();
    void vector_to_power ();
 
public:
    GF ();
    GF (int power); // используем power_to_vector
    GF (std::vector<int> vector); // используем vector_to_power
    ~GF ();
 
    GF operator+ (GF right_hand_side); // сложение
    GF operator* (GF right_hand_side); // умножение
 
    void show_alpha_vector (); //вывод на экран вектора
};
 
#endif

Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#ifndef GF_polynom.h
 
#include "GF.h"
 
class GF_polynom
{
private:
    std::vector<GF> polynom; // вектор из коэфициентов полинома,
                             // которые принадлежат GF(2^m)
public:
    GF_polynom ();
    GF_polynom (std::vector<GF> coefficients);
    ~GF_polynom ();
 
    GF_polynom operator+ (GF_polynom right_hand_side); // сложение 
    GF_polynom operator* (GF_polynom right_hand_side); // умножение
    GF_polynom operator% (GF_polynom right_hand_side); // остаток от деления
};
 
#endif

Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#ifndef RS_encoder.h
 
#include "GF_polynom.h"
#include <string>
 
const int CODE_LENGTH = 0; // длина кода
const int MESSAGE_LENGTH = 0; // длина сообщения
 
std::vector<int> str_to_int (std::string str_message); // строку в вектор
std::vector<GF> message_to_GF_message (std::vector<int> message); // вектор из 0 и 1 в 
                                                                  // вектор из элементов GF(2^m)
std::vector<GF> encode (std::vector<GF> GF_message, int n = CODE_LENGTH, int k = MESSAGE_LENGTH); // кодирование сообщения
 
#endif

Я пока не использовал ссылки и модификатор const. Завтра всё доделаю и буду приступать к написанию самих функций. Прокомментируйте, пожалуйста. Спасибо!!!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.11.2012, 02:35
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Многочлены над GF(2^m) (C++):

Многочлены - C++
http://s44.***********/i106/1001/93/421c17bb2f28.png Прошу помочь решить\ или хоть популярно объяснить.

Многочлены - C++
http://s003.***********/i202/1001/dc/6e8447711438.png

списки-многочлены. сложение - C++
Здравствуйте, задали сделать прогу, но я не понимаю каким образом это надо осуществить. Задача: Многочлен с целыми коэффициентами можно...

класс, моделирующий многочлены n – го порядка - C++
Разработайте класс, моделирующий многочлены n – го порядка от одной переменной. В классе должен быть конструктор копирования и оператор...

Построить интерполяционные многочлены Ньютона - C++
Построить интерполяционные многочлены Ньютона для функции F(x)=lg(x)-((x-1)/x) по следующим узлам: х=1, 2, 4, 8, 10; Проблемы возникают...

Интерполяционный многочлены по чебышевским узлам - C++
Всем здравствуйте!Столкнулся с проблемой: 1)Как находить узлы я знаю,и написал,и значения в ней нашел...Но как же строить сам многочлен я...

39
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
08.11.2012, 17:35  [ТС] #16
Спасибо! А с делением Вы мне можете помочь?
0
I.M.
566 / 549 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
08.11.2012, 17:38 #17
С алгоритмом - вряд ли. Но если вы сможете в доступной форме изложить этот алгоритм и сказать "я вот сделал, но почему-то считает не так", то помогу, конечно
0
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
09.11.2012, 02:15  [ТС] #18
Отлично! Тогда я сейчас попробую реализовать столбиком (даже скорее не сейчас, а ближе к вечеру, поскольку сейчас есть ещё дела) и выложу здесь, а Вы посмотрите. Спасибо!
И ещё вопрос: а разве Вам проще разбираться в моём коде, чем написать собственный? Если да, то как научиться в нём разбираться, поскольку я в чужом коде вообще ничего понять не могу

Добавлено через 4 часа 35 минут
Алгоритм деления столбиком.
Имеем два многочлена http://www.cyberforum.ru/cgi-bin/latex.cgi?a(x)\in P_n и http://www.cyberforum.ru/cgi-bin/latex.cgi?div(x)\in P_m с коэффициентами из http://www.cyberforum.ru/cgi-bin/latex.cgi?GF(2^k). Не нарушая общности, положим http://www.cyberforum.ru/cgi-bin/latex.cgi?n>m. Представим каждый многочлен в виде вектора из его коэффициентов
http://www.cyberforum.ru/cgi-bin/latex.cgi?a(x)\leftrightarrow a = (a_0, a_1,...,a_n)\in (GF(2^k))^{n+1};div(x)\leftrightarrow b = (div_0, div_1,...,div_m)\in (GF(2^k))^{m+1}.
Создаём две дополнительных переменных:
http://www.cyberforum.ru/cgi-bin/latex.cgi?rem(x)\in P_v, v = n, n-1, n-2,...; rem(x)\leftrightarrow rem = (rem_1, rem_2,...,rem_v),
которая будет отображать текущий остаток от деления http://www.cyberforum.ru/cgi-bin/latex.cgi?a(x) на http://www.cyberforum.ru/cgi-bin/latex.cgi?div(x), и http://www.cyberforum.ru/cgi-bin/latex.cgi?mult(x)\in P_{v-m}, который имеет вид
http://www.cyberforum.ru/cgi-bin/latex.cgi?mult(x)=\frac{rem_v}{div_m}x^{v-m}\leftrightarrow mult = (0,0,...,0,\frac{rem_v}{div_m}).
Теперь на первом шаге умножаем http://www.cyberforum.ru/cgi-bin/latex.cgi?mult(x) на http://www.cyberforum.ru/cgi-bin/latex.cgi?div(x) и прибавляем к http://www.cyberforum.ru/cgi-bin/latex.cgi?rem, получаем
http://www.cyberforum.ru/cgi-bin/latex.cgi?mult(x)\times div(x)\leftrightarrow (0,0,...,0,\frac{rem_v}{div_m}div_0,\frac{rem_v}{div_m}div_1,...,\frac{rem_v}{div_m}div_m).
Поскольку последний коэф. равен http://www.cyberforum.ru/cgi-bin/latex.cgi?rem_v (такой же,как и у http://www.cyberforum.ru/cgi-bin/latex.cgi?rem), то при суммировании (что равно вычитанию) он сократиться. После этого мы убираем последний элемент из http://www.cyberforum.ru/cgi-bin/latex.cgi?rem(x), поскольку он равен нулю, и из http://www.cyberforum.ru/cgi-bin/latex.cgi?mult(x), поскольку он нам больше не нужен. проделываем операцию до тех пор, пока степень текущего остатка не станет меньше степени делителя.

Не по теме:

Хотел написать красиво, но с таким редактором ТеХ'а оно выглядит ужасно. Надеюсь, хоть что-то понятно...


Вот, что я пока написал, но не проверял. Гляньте, пожалуйста, уверен, там можно его переписать в лучшем виде.
Кликните здесь для просмотра всего текста
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
/* * * * * * * * * * * * * * * * * * * * * * *
                GF_polynom.cpp
* * * * * * * * * * * * * * * * * * * * * * */
 
#include "GF_polynom.h"
 
GF_polynom::GF_polynom ()
{
 
}
 
GF_polynom::GF_polynom (const GF_polynom& GF_polynom_element):
polynom (GF_polynom_element.polynom)
{
 
}
 
GF_polynom::GF_polynom (const std::vector<GF>& coefficients):
polynom (coefficients)
{
 
}
 
GF_polynom::~GF_polynom ()
{
 
}
 
GF_polynom& GF_polynom::operator= (const GF_polynom& right_hand_side)
{
    polynom.resize (right_hand_side.polynom.size());
    polynom = right_hand_side.polynom;
 
    return *this;
}
 
GF_polynom GF_polynom::operator+ (const GF_polynom& right_hand_side) const
{
    GF_polynom sum;
    sum.polynom.reserve (std::max(polynom.size(), right_hand_side.polynom.size()));
 
    for (int i = 0; i < std::min(polynom.size(), right_hand_side.polynom.size()); ++i)
        sum.polynom.push_back (polynom.at(i) + right_hand_side.polynom.at(i));
 
    if (polynom.size() < right_hand_side.polynom.size())
        for (int i = polynom.size(); i < right_hand_side.polynom.size(); ++i)
            sum.polynom.push_back (right_hand_side.polynom.at(i));
    else
        for (int i = right_hand_side.polynom.size(); i < polynom.size(); ++i)
            sum.polynom.push_back (polynom.at(i));
    
    return sum;
}
 
GF_polynom GF_polynom::operator* (const GF_polynom& right_hand_side) const
{
    GF_polynom prod;
    prod.polynom.resize (polynom.size() + right_hand_side.polynom.size());
 
    for (int i = 0; i < prod.polynom.size(); ++i)
    {
        GF sum (null_vector);
 
        for (int j = 0; j < i + 1; ++j)
            if ((j < polynom.size()) && (i - j < right_hand_side.polynom.size()))
                sum = sum + (polynom.at(j) * right_hand_side.polynom.at(i - j));
        
        prod.polynom.push_back (sum);
    }
 
    return prod;
}
 
GF_polynom GF_polynom::operator% (const GF_polynom& divisor) const
{
    GF_polynom reminder (*this); // остаток
    GF_polynom multiplier; // множитель, на который умножаем делитель
                           // (имеет вид a * x^n )
    multiplier.polynom.resize (reminder.polynom.size() - divisor.polynom.size() + 1);
 
    for (int i = 0; i < reminder.polynom.size() - divisor.polynom.size(); ++i) 
        multiplier.polynom.at(i) = null_vector; // заполняем нулями все, кроме последнего   
    
    while (reminder.polynom.size() > divisor.polynom.size()) // пока степень остачи больше степени делителя
    {
        multiplier.polynom.at(reminder.polynom.size() - divisor.polynom.size()) = //коэффициент при x^(n-m)
            reminder.polynom.at(reminder.polynom.size() - 1) /                    // n - степень текущего остатка
            divisor.polynom.at(divisor.polynom.size() - 1);                       // m - степень делителя
 
        reminder = reminder + (divisor * multiplier); // обнуляем коэффициент
                                                      // при старшей степени
        multiplier.polynom.pop_back(); // убираем старший коэф., остаются одни нули
        reminder.polynom.pop_back(); // убираем старштй коэф., поскольку он нулевой
    }
 
    return reminder; // возвращаем остаток
}
 
std::vector<GF> GF_polynom::return_coefficients () const
{
    return polynom;
}


Добавлено через 3 часа 59 минут
Урааа!!! Наконец-то дописал весь код, осталось его исправить и протестировать. Вообщем, выкладываю "пре-альфа" версию
Кликните здесь для просмотра всего текста
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
/* * * * * * * * * * * * * * * * * * * * * * *
                    GF_table.h
* * * * * * * * * * * * * * * * * * * * * * */
 
#ifndef GF_table_h
#define GF_table_h
 
#include <vector>
 
extern const int GROUP_DEGREE; 
 
const std::vector<int> init_primitive_polynomial (const int degree); 
 
struct GF_table
{
    GF_table ();
    GF_table (const GF_table& GF_element);
    ~GF_table ();
 
    GF_table& operator= (const GF_table& right_hand_side);
 
    int power;
    std::vector<int> vector;    
};
 
std::vector<GF_table> init_GF_table (const std::vector<int>& primitive_polynomial);
 
extern const std::vector<GF_table> table;
 
extern const std::vector<int> null_vector;
extern const std::vector<int> unit_vector;
 
#endif
 
/* * * * * * * * * * * * * * * * * * * * * * *
                    GF_table.cpp
* * * * * * * * * * * * * * * * * * * * * * */
 
#include "GF_table.h"
 
const int GROUP_DEGREE = 3;
 
const std::vector<int> init_primitive_polynomial (const int degree = GROUP_DEGREE)
{
    std::vector<int> polynom (degree, 0);
    polynom.resize (degree);
 
    switch (degree)
    {
    case 2:
        for (int i = 0; i < 2; ++i)
            polynom.at(i) = 1;
 
        return polynom;
 
    case 3:
        for (int i = 0; i < 3; ++i)
            polynom.at(i) = 1;
 
        polynom.at(2) = 0;
        return polynom;
 
    case 4:
        for (int i = 0; i < 4; ++i)
            polynom.at(i) = 1;
 
        polynom.at(2) = 0;
        polynom.at(3) = 0;
        return polynom;
 
    /* case 5, 6,...*/
    }
}
 
GF_table::GF_table ()
{
    power = 0;
    vector.resize (GROUP_DEGREE);
}
 
GF_table::GF_table (const GF_table& GF_element)
{
    power = GF_element.power;
    vector = GF_element.vector;
}
 
GF_table::~GF_table ()
{
 
}
 
GF_table& GF_table::operator= (const GF_table& right_hand_side)
{
    power = right_hand_side.power;
    vector = right_hand_side.vector;
 
    return *this;
}
 
std::vector<GF_table> init_GF_table (const std::vector<int>& primitive_polynomial = init_primitive_polynomial ())
{
    std::vector<GF_table> table;
    table.resize ((1 << GROUP_DEGREE) - 1);
 
    std::vector<int> temp_vec (GROUP_DEGREE, 0);
 
    temp_vec.at(0) = 1;
    table.at(0).vector = temp_vec;
 
    for (int i = 1; i < (1 << GROUP_DEGREE) - 1; ++i)
    {
        table.at(i).vector.at(0) = 0;
 
        for (int j = 1; j < GROUP_DEGREE; ++j)
            table.at(i).vector.at(j) = table.at(i - 1).vector.at(j - 1);
 
        if (table.at(i - 1).vector.at(GROUP_DEGREE - 1) == 1)
            for (int j = 0; j < GROUP_DEGREE; ++j)
                table.at(i).vector.at(j) = (table.at(i).vector.at(j) + primitive_polynomial.at(j)) % 2;
    }
 
    return table;
}
 
const std::vector<GF_table> table (init_GF_table ());
 
const std::vector<int> null_vector (GROUP_DEGREE, 0);
const std::vector<int> unit_vector (table.at(0).vector);

Кликните здесь для просмотра всего текста
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
/* * * * * * * * * * * * * * * * * * * * * * *
                    GF.h
* * * * * * * * * * * * * * * * * * * * * * */
 
#ifndef GF_h
#define GF_h
 
#include "GF_table.h"
 
class GF 
{
private:
    int alpha_power; // представление в виде степени альфа
    std::vector<int> alpha_vector; // представление в виде вектора
    int null; // индикатор того, что вектор нулевой
 
    void power_to_vector (); // используем 
    void vector_to_power (); // GF_table
 
public:
    GF ();
    GF (const GF& GF_element);
    GF (const int power);
    GF (const std::vector<int> vector);
    ~GF ();
    
    GF& operator= (const GF& right_hand_side);
 
    GF operator+ (const GF& right_hand_side) const; // сложение
    GF operator* (const GF& right_hand_side) const; // умножение
    GF operator/ (const GF& right_hand_side) const;
 
    int return_power () const;
    std::vector<int> return_alpha_vector () const; // возврат элемента в виде вектора
};
 
#endif
 
/* * * * * * * * * * * * * * * * * * * * * * *
                    GF.cpp
* * * * * * * * * * * * * * * * * * * * * * */
 
#include "GF.h"
 
GF::GF ()
{
    alpha_power = 0;
    alpha_vector.resize (GROUP_DEGREE);
    null = 1;
}
 
GF::GF (const GF& GF_element)
{
    alpha_power = GF_element.alpha_power;
    alpha_vector = GF_element.alpha_vector;
    null = GF_element.null;
}
 
GF::GF (const int power)
{
    alpha_power = power;
    power_to_vector ();
    null = 0;
}
 
GF::GF (const std::vector<int> vector)
{
    alpha_vector = vector;
    vector_to_power ();
}
 
GF::~GF ()
{
 
}
 
GF& GF::operator= (const GF& right_hand_side)
{
    alpha_power = right_hand_side.alpha_power;
    alpha_vector = right_hand_side.alpha_vector;
    null = right_hand_side.null;
 
    return *this;
}
 
void GF::power_to_vector ()
{
    alpha_vector = table.at(alpha_power).vector;
}
 
void GF::vector_to_power ()
{
    if (alpha_vector != null_vector)
    {
        int i = 0;
        while (table.at(i).vector != alpha_vector)
            ++i;
 
        alpha_power = i;
        null = 0;
    }
    else
        null = 1;   
}
 
GF GF::operator+ (const GF& right_hand_side) const
{
    if (null == 1) 
        return right_hand_side;
    if (right_hand_side.null == 1)
        return *this;
 
    GF sum;
 
    for (int i = 0; i < GROUP_DEGREE; ++i)
        sum.alpha_vector.at(i) = (alpha_vector.at (i) + right_hand_side.alpha_vector.at (i)) % 2;
    
    if (sum.alpha_vector == null_vector)
    {
        sum.null = 1;
        return sum;
    }
 
    sum.vector_to_power ();
 
    return sum;
}
 
GF GF::operator* (const GF& right_hand_side) const
{
    if (null == 1)
        return *this;
    if (right_hand_side.null == 1)
        return right_hand_side;
 
    GF prod;
 
    prod.alpha_power = (alpha_power + right_hand_side.alpha_power) % ((1 << GROUP_DEGREE) - 1);
    
    prod.power_to_vector ();
    
    return prod;
}
 
GF GF::operator/ (const GF& right_hand_side) const
{   
    if (alpha_power - right_hand_side.alpha_power < 0)
    {
        GF div ((alpha_power - right_hand_side.alpha_power) % 
            ((1 << GROUP_DEGREE) - 1) + ((1 << GROUP_DEGREE) - 1));
        return div;
    }
    else
    {
        GF div ((alpha_power - right_hand_side.alpha_power) % ((1 << GROUP_DEGREE) - 1));
        return div;
    }
}
 
int GF::return_power () const
{
    return alpha_power;
}
 
std::vector<int> GF::return_alpha_vector () const
{
    return alpha_vector;
}

Кликните здесь для просмотра всего текста
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
/* * * * * * * * * * * * * * * * * * * * * * *
                GF_polynom.h
* * * * * * * * * * * * * * * * * * * * * * */
 
#ifndef GF_polynom_h
#define GF_polynom_h
 
#include "GF.h"
 
class GF_polynom
{
private:
    std::vector<GF> polynom; // вектор из коэфициентов полинома,
                             // которые принадлежат GF(2^m)
public:
    GF_polynom ();
    GF_polynom (const GF_polynom& GF_polynom_element);
    GF_polynom (const std::vector<GF>& coefficients);
    ~GF_polynom ();
 
    GF_polynom& operator= (const GF_polynom& right_hand_side);
 
    GF_polynom operator+ (const GF_polynom& right_hand_side) const; // сложение 
    GF_polynom operator* (const GF_polynom& right_hand_side) const; // умножение
    GF_polynom operator% (const GF_polynom& divisor) const; // остаток от деления
 
    void shift (const int shift_value);
 
    std::vector<GF> return_coefficients () const; // возвращает коэффициенты многочлена
};
 
#endif
 
/* * * * * * * * * * * * * * * * * * * * * * *
                GF_polynom.cpp
* * * * * * * * * * * * * * * * * * * * * * */
 
#include "GF_polynom.h"
 
GF_polynom::GF_polynom ()
{
 
}
 
GF_polynom::GF_polynom (const GF_polynom& GF_polynom_element):
polynom (GF_polynom_element.polynom)
{
 
}
 
GF_polynom::GF_polynom (const std::vector<GF>& coefficients):
polynom (coefficients)
{
 
}
 
GF_polynom::~GF_polynom ()
{
 
}
 
GF_polynom& GF_polynom::operator= (const GF_polynom& right_hand_side)
{
    polynom.resize (right_hand_side.polynom.size());
    polynom = right_hand_side.polynom;
 
    return *this;
}
 
GF_polynom GF_polynom::operator+ (const GF_polynom& right_hand_side) const
{
    GF_polynom sum;
    sum.polynom.reserve (std::max(polynom.size(), right_hand_side.polynom.size()));
 
    for (int i = 0; i < std::min(polynom.size(), right_hand_side.polynom.size()); ++i)
        sum.polynom.push_back (polynom.at(i) + right_hand_side.polynom.at(i));
 
    if (polynom.size() < right_hand_side.polynom.size())
        for (int i = polynom.size(); i < right_hand_side.polynom.size(); ++i)
            sum.polynom.push_back (right_hand_side.polynom.at(i));
    else
        for (int i = right_hand_side.polynom.size(); i < polynom.size(); ++i)
            sum.polynom.push_back (polynom.at(i));
    
    return sum;
}
 
GF_polynom GF_polynom::operator* (const GF_polynom& right_hand_side) const
{
    GF_polynom prod;
    prod.polynom.resize (polynom.size() + right_hand_side.polynom.size());
 
    for (int i = 0; i < prod.polynom.size(); ++i)
    {
        GF sum (null_vector);
 
        for (int j = 0; j < i + 1; ++j)
            if ((j < polynom.size()) && (i - j < right_hand_side.polynom.size()))
                sum = sum + (polynom.at(j) * right_hand_side.polynom.at(i - j));
        
        prod.polynom.push_back (sum);
    }
 
    return prod;
}
 
GF_polynom GF_polynom::operator% (const GF_polynom& divisor) const
{
    GF_polynom reminder (*this); // остаток
    GF_polynom multiplier; // множитель, на который умножаем делитель
                           // (имеет вид a * x^n )
    multiplier.polynom.resize (reminder.polynom.size() - divisor.polynom.size() + 1);
 
    multiplier.shift (reminder.polynom.size() - divisor.polynom.size());// заполняем нулями все, кроме последнего
    
    while (reminder.polynom.size() > divisor.polynom.size()) // пока степень остачи больше степени делителя
    {
        multiplier.polynom.at(reminder.polynom.size() - divisor.polynom.size()) = //коэффициент при x^(n-m)
            reminder.polynom.at(reminder.polynom.size() - 1) / divisor.polynom.at(divisor.polynom.size() - 1);                        // m - степень делителя
 
        reminder = reminder + (divisor * multiplier); // обнуляем коэффициент
                                                      // при старшей степени
        multiplier.polynom.pop_back(); // убираем старший коэф., остаются одни нули
        reminder.polynom.pop_back(); // убираем старштй коэф., поскольку он нулевой
    }
 
    return reminder; // возвращаем остаток
}
 
void GF_polynom::shift (const int shift_value)
{
    polynom.reserve (polynom.size() + shift_value);
 
    for (int i = 0; i < shift_value; ++i)
        polynom.push_back (null_vector);
}
 
std::vector<GF> GF_polynom::return_coefficients () const
{
    return polynom;
}

Кликните здесь для просмотра всего текста
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
/* * * * * * * * * * * * * * * * * * * * * * *
                RS_encoder.h
* * * * * * * * * * * * * * * * * * * * * * */
 
#ifndef RS_encoder_h
#define RS_encoder_h
 
#include "GF_polynom.h"
#include <string>
 
extern const int CODE_LENGTH; // длина кода
extern const int MAX_ERRORS; // количество исправляемых ошибок
extern const int MESSAGE_LENGTH; // длина сообщения
 
const GF_polynom init_GF_primitive_polynomial (const std::vector<int>& primitive_polynomial);
 
std::vector<int> str_to_int (const std::string& str_message); // строку в вектор
std::vector<GF> message_to_GF_message (const std::vector<int>& message); // вектор из 0 и 1 в 
                                                                         // вектор из элементов GF(2^m)
GF_polynom encode (const std::vector<GF>& GF_message); // кодирование сообщения
std::vector<int> GF_code_to_vector (const std::vector<GF>& code);
 
#endif
 
/* * * * * * * * * * * * * * * * * * * * * * *
                RS_encoder.cpp
* * * * * * * * * * * * * * * * * * * * * * */
 
#include "RS_encoder.h"
 
const int MAX_ERRORS = 0;
const int CODE_LENGTH = 1 << GROUP_DEGREE - 1;
const int MESSAGE_LENGTH = 1 << GROUP_DEGREE - 1 - 2 * MAX_ERRORS;
 
const GF_polynom init_GF_primitive_polynomial (const std::vector<int>& primitive_polynomial = 
                                                init_primitive_polynomial(GROUP_DEGREE))
{
    std::vector<GF> GF_primitive_polynomial;
 
    for (auto iter = primitive_polynomial.begin(); iter != primitive_polynomial.end(); ++iter)
    {
        if (*iter == 0)
            GF_primitive_polynomial.push_back (null_vector);
        else
            GF_primitive_polynomial.push_back (unit_vector);
    }
 
    GF_primitive_polynomial.push_back (unit_vector);
 
    GF_polynom polynom (GF_primitive_polynomial);
    return polynom;
}
 
std::vector<int> str_to_int (const std::string& str_message)
{
    std::vector<int> int_message;
 
    for (auto iter = str_message.begin(); iter != str_message.end(); ++iter)
        int_message.push_back (*iter - '0');
 
    return int_message;
}
 
std::vector<GF> message_to_GF_message (const std::vector<int>& int_message)
{
    std::vector<int> message (int_message);
    message.reserve (GROUP_DEGREE * MESSAGE_LENGTH);
 
    for (int i = message.size(); i < GROUP_DEGREE * MESSAGE_LENGTH; ++i)
        message.push_back (0);
 
    std::vector<GF> GF_message;
 
    for (int i = 0; i < MESSAGE_LENGTH; ++i)
    {
        std::vector<int> one_symbol;
 
        for (int j = i * GROUP_DEGREE; j < (i + 1) * GROUP_DEGREE; ++j)
            one_symbol.push_back (message.at(j));
 
        GF_message.push_back (one_symbol);
    }
 
    return GF_message;  
}
 
GF_polynom encode (const std::vector<GF>& GF_message)
{
    GF_polynom u(GF_message);
    GF_polynom g(init_GF_primitive_polynomial());
    GF_polynom v;
 
    u.shift (2 * MAX_ERRORS);
 
    v = u + (u % g);
 
    return v;
}
 
std::vector<int> GF_polynom_to_vector (const GF_polynom& code)
{
    std::vector<GF> GF_messge (code.return_coefficients());
 
    std::vector<int> message;
 
    for (auto gf_iter = GF_messge.begin(); gf_iter != GF_messge.end(); ++gf_iter)
    {
        std::vector<int> temp (gf_iter->return_alpha_vector());
 
        for (auto iter = temp.begin(); iter != temp.end(); ++iter)
            message.push_back (*iter);
    }
 
    return message;
}

Чтобы вам не разбираться в тонкостях кода -- задавайте вопросы по каждому участку, а я постараюсь на них как можно более полно ответить.
Моя конечная цель была найти http://www.cyberforum.ru/cgi-bin/latex.cgi?v(x) = x^{n-k}u(x) + (x^{n-k}u(x) \mathrm {mod} g(x)).
0
I.M.
566 / 549 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
09.11.2012, 12:27 #19
C++
1
2
3
 multiplier.polynom.at(reminder.polynom.size() - divisor.polynom.size()) = //коэффициент при x^(n-m)
            reminder.polynom.at(reminder.polynom.size() - 1) /                    // n - степень текущего остатка
            divisor.polynom.at(divisor.polynom.size() - 1);                       // m - степень делителя
на
C++
1
*multiplier.polynom.rbegin() = (*reminder.polynom.rbegin()) / (*divisor.polynom.rbegin());
C++
1
2
3
4
5
6
7
GF_polynom& GF_polynom::operator= (const GF_polynom& right_hand_side)
{
    polynom.resize (right_hand_side.polynom.size());
    polynom = right_hand_side.polynom;
 
    return *this;
}
на
C++
1
2
3
4
5
6
GF_polynom& GF_polynom::operator= (const GF_polynom& right_hand_side)
{
    polynom = right_hand_side.polynom;
 
    return *this;
}
И еще раз пройдитесь по всему коду. Решите, где использовать resize, а где reserve.
1
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
09.11.2012, 14:11  [ТС] #20
Как я понял, резерв мы используем с пушбэками, а рисайз -- с операцией обращения (эт), верно? Какой вариант предпочтительнее использовать или в этом нет разницы?
Первые два листинга я тестировал: они вроди как работают... Сегодня-завтра попробую протестировать два остальных.
В 1-ом Вашем замечании я тоже сперва хотел так сделать, но не знал, где ставить звёздочку (точнее я использовал стрелочку) и оно мне выдавало ошибку
0
I.M.
566 / 549 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
09.11.2012, 14:20 #21
В принципе, можно просто вызывать пушбеки. Но тогда может получится ситуация, что вектор будет слишком часто выделять себе новую память. Чтобы этого избежать рекомендуется вначале вызывать reserve. Тогда вектор выделит себе заданное кол-во памяти и в пушбекам не будет выделять дополнительную.
resize нужен тогда, когда требуется создать вектор определенного размера со значениями по умолчанию. т.е. запись std::vector<my_class> vector_name(100); означает, что создается вектор на 100 элементов, у каждого из которых будет вызван конструктор. собственно, если вам эти значения по умолчанию не нужны, то лучше пушбеком пользоваться. Например, тут resize бесполезен:
C++
1
2
3
4
std::vector<my_class> v;
v.resize(100);
for (int i = 0; i < v.size(); ++i)
   v[i] = my_class(i);
0
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
10.11.2012, 20:34  [ТС] #22
Аааа, помогите!!! Программа не хочет правильно умножать многочлены
Пишу такой код:
Кликните здесь для просмотра всего текста
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
/* * * * * * * * * * * * * * * * * * * * * * *
                main.cpp
* * * * * * * * * * * * * * * * * * * * * * */
 
#include <iostream>
#include "RS_encoder.h"
 
int main()
{
    std::string str_mess1, str_mess2;
 
    std::cout << "IT'S POLYNOM TEST" << std::endl << std::endl;
    std::cout << "Group degree = " << GROUP_DEGREE << std::endl;
    std::cout << "Maximum message length = " << MESSAGE_LENGTH * GROUP_DEGREE << " bits" << std::endl;
    std::cout << "Maximum number of errors = " << MAX_ERRORS << " symbols" << std::endl;
    std::cout << "--------------------------------------------" << std::endl;
 
    std::cout << "input 1st message: ";
    std::cin >> str_mess1;
    GF_polynom polynom1 (message_to_GF_message (str_to_int (str_mess1)));
 
    std::cout << std::endl << "input 2nd message: ";
    std::cin >> str_mess2;
    GF_polynom polynom2 (message_to_GF_message (str_to_int (str_mess2)));
 
    std::cout << std::endl << "------------------------------------------" << std::endl;
 
    std::vector<GF> temp_GF_vec (polynom1.return_coefficients());
    
    std::cout << "1st messege, transformed to polynom:" << std::endl;
    std::cout << "degree\tvector\tpower" << std::endl;
    int temp_degree = 0;
    for (auto gf_vec_iter = temp_GF_vec.begin(); gf_vec_iter != temp_GF_vec.end(); ++ gf_vec_iter)
    {
        std::cout << temp_degree << "\t";
        std::vector<int> temp_vec (gf_vec_iter->return_alpha_vector());
        for (auto iter = temp_vec.begin(); iter != temp_vec.end(); ++iter)
            std::cout << *iter;
        std::cout << "\t" << gf_vec_iter->return_power() << std::endl;
        ++temp_degree;
    }
 
    
    temp_GF_vec = polynom2.return_coefficients();
    
    std::cout << "2nd messege, transformed to polynom:" << std::endl;
    std::cout << "degree\tvector\tpower" << std::endl;
    temp_degree = 0;
    for (auto gf_vec_iter = temp_GF_vec.begin(); gf_vec_iter != temp_GF_vec.end(); ++ gf_vec_iter)
    {
        std::cout << temp_degree << "\t";
        std::vector<int> temp_vec (gf_vec_iter->return_alpha_vector());
        for (auto iter = temp_vec.begin(); iter != temp_vec.end(); ++iter)
            std::cout << *iter;
        std::cout << "\t" << gf_vec_iter->return_power() << std::endl;
        ++temp_degree;
    }
 
    GF_polynom polynom3 = polynom1 * polynom2;
 
    temp_GF_vec = polynom3.return_coefficients();
    
    std::cout << "Product of polynom1 and polynom2:" << std::endl;
    std::cout << "degree\tvector\tpower" << std::endl;
    temp_degree = 0;
    for (auto gf_vec_iter = temp_GF_vec.begin(); gf_vec_iter != temp_GF_vec.end(); ++ gf_vec_iter)
    {
        std::cout << temp_degree << "\t";
        std::vector<int> temp_vec (gf_vec_iter->return_alpha_vector());
        for (auto iter = temp_vec.begin(); iter != temp_vec.end(); ++iter)
            std::cout << *iter;
        std::cout << "\t" << gf_vec_iter->return_power() << std::endl;
        ++temp_degree;
    }
 
    std::cin.get();
    std::cin.get();
}

а оно мне неправильно считает. Например:
http://www.cyberforum.ru/cgi-bin/latex.cgi?m=2 и примитивный полином http://www.cyberforum.ru/cgi-bin/latex.cgi?g(x)=x^2+x+1. Тогда, если http://www.cyberforum.ru/cgi-bin/latex.cgi?g(\alpha )=0, то http://www.cyberforum.ru/cgi-bin/latex.cgi?GF(2^2)=\{0,\alpha ^0,\alpha ^1,\alpha ^2\}=\{0,1,\alpha ,1+\alpha \}=\{00,10,01,11\} и http://www.cyberforum.ru/cgi-bin/latex.cgi?\alpha ^3=\alpha ^0. Допустим, наш код не умеет исправлять ошибки (т.е. умеет только их выявлять): http://www.cyberforum.ru/cgi-bin/latex.cgi?t=0, len(M)=2\cdot (2^2-1-2\cdot 0)=2\cdot 3=6. Вводим два сообщения:
http://www.cyberforum.ru/cgi-bin/latex.cgi?M_1=101011=\alpha ^0\alpha ^0\alpha ^2, M_1(x)=\alpha ^0+\alpha ^0x+\alpha ^2 x^2
http://www.cyberforum.ru/cgi-bin/latex.cgi?M_2=110110=\alpha ^2\alpha ^1\alpha ^0, M_2(x)=\alpha ^2 +\alpha ^1x+\alpha ^0x^2
Тогда
http://www.cyberforum.ru/cgi-bin/latex.cgi?M_1(x)\cdot M_2(x)=\alpha ^0\cdot \alpha ^2 + (\alpha ^0\cdot \alpha ^1 +\alpha ^0\cdot \alpha ^2)x+(\alpha ^0\cdot \alpha ^0+\alpha ^0\cdot\alpha ^1+\alpha ^2\cdot \alpha ^2)x^2+(\alpha ^0\cdot\alpha ^0+\alpha ^2\cdot\alpha ^1)x^3+\alpha ^2\cdot\alpha ^0 x^4=
http://www.cyberforum.ru/cgi-bin/latex.cgi?=\alpha ^2+(\alpha ^1+\alpha ^2)x+(\alpha ^0+\alpha ^1+\alpha ^4)x^2+(\alpha ^0+\alpha ^3)x^3+\alpha ^2x^4=
Найдём http://www.cyberforum.ru/cgi-bin/latex.cgi?\alpha ^4=\alpha ^{1+3}=\alpha ^1\cdot\alpha ^3=\alpha ^1\cdot\alpha ^0=\alpha ^{1+0}=\alpha ^ 1 и заменим все альфы векторами:
http://www.cyberforum.ru/cgi-bin/latex.cgi?=11+(01+11)x+(10+01+01)x^2+(10+10)x^3+11x^4=11+10x+10x^2+00x^3+11x^4=\alpha ^2+\alpha ^0x+\alpha ^0x^2+\alpha ^2x^4
Т.е.
http://www.cyberforum.ru/cgi-bin/latex.cgi?M_1(x)\cdot M_2(x)=\alpha ^2+\alpha ^0x+\alpha ^0x^2+\alpha ^2x^4, M_1\cdot M_2=1110100011,
а программа выдаёт
http://www.cyberforum.ru/cgi-bin/latex.cgi?M_1(x)\cdot M_2(x)=\alpha ^2+\alpha ^2x+\alpha ^1x^2+\alpha ^0 x^3+\alpha ^2x^4, M_1\cdot M_2=1111011011
Помогите, пожалуйста!

Добавлено через 10 минут
И ещё вопрос: как вставить в начало массива N нулей. Я делал так:
реверсим массив, далее в цикле пушбэкаем N нулей и ещё раз реверсим. Есть какой-то более простой способ?
0
I.M.
566 / 549 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
10.11.2012, 21:09 #23
Цитата Сообщение от vlad_light Посмотреть сообщение
И ещё вопрос: как вставить в начало массива N нулей. Я делал так:
реверсим массив, далее в цикле пушбэкаем N нулей и ещё раз реверсим. Есть какой-то более простой способ?
А в массиве уже есть элементы? думаю, что да. можно использовать метод insert
http://www.cplusplus.com/reference/stl/vector/insert/
точнее, вот такую его реализацию:
C++
1
void insert ( iterator position, size_type n, const T& x );
А по первому вопросу. Могу предложить использовать отладчик и пройти по коду по шагам.
1
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
10.11.2012, 21:14  [ТС] #24
использовать отладчик
я не знаю, что это Можете мне рассказать, где это в МС ВС 2010 есть?
А с инсерт нужно использовать резерв или рисайз?

Добавлено через 2 минуты
C++
1
2
3
4
5
void GF_polynom::shift (const int shift_value)
{
    polynom.reserve (polynom.size() + shift_value);
    polynom.insert (polynom.begin(), shift_value, null_vector);
}
вот так нормально?
0
I.M.
566 / 549 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
10.11.2012, 21:30 #25
Цитата Сообщение от vlad_light Посмотреть сообщение
А с инсерт нужно использовать резерв или рисайз?
Инсерт, по-моему, сам озаботится о выделении памяти. И выделит ее один раз, если нужно. Поэтому можно просто вызывать инсерт.
Да, так нормально.
Отладчик? Нажимайте не F5, а F10 и начнете двигаться в программе по шагам. Если нажать F11, То провалитесь внутрь метода, если F10, то пройдете его, не заходя внутрь.
По-моему, среди прочих кнопок у VS по умолчанию вынесены кнопки для отладки. Хотя в этом уже не уверен)
1
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
11.11.2012, 19:11  [ТС] #26
Благодарствую:-) будем пробовать...

Добавлено через 21 час 40 минут
Исправил умножение. Сложность была в том, что было сложно разобраться с длинами массивов: массив длины N - это многочлен длины N-1, причём на месте N-2 стоит коэффициент при степени N-1. Короче очень запутано всё получается В итоге надо было в одном месте прибавить, а в другом -- отнять еденичку. Также добавил возможность удалять нули перед умножением, чтоб не делать лишние операции. Умножает вроди как правильно, проверьте граммотность кода, пожалуйста.
Кликните здесь для просмотра всего текста
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
GF_polynom GF_polynom::operator* (const GF_polynom& right_hand_side) const
{   
    GF_polynom left_multiplier (*this);
    GF_polynom right_multiplier (right_hand_side);
 
    while (left_multiplier.polynom.rbegin()->return_alpha_vector() == null_vector)
        left_multiplier.polynom.pop_back();
 
    while (right_multiplier.polynom.rbegin()->return_alpha_vector() == null_vector)
        right_multiplier.polynom.pop_back();
 
    GF_polynom prod;
    prod.polynom.reserve (left_multiplier.polynom.size() + right_multiplier.polynom.size() - 1);
 
    for (int k = 0; k < left_multiplier.polynom.size() + right_multiplier.polynom.size() - 1; ++k)
    {
        GF sum (null_vector);
 
        for (int i = std::max (0, k - (int) right_multiplier.polynom.size() + 1); 
                            i <= std::min (k, (int) left_multiplier.polynom.size() - 1); ++i)
            sum = sum + (left_multiplier.polynom.at(i) * right_multiplier.polynom.at(k - i));
 
        prod.polynom.push_back (sum);
    }
 
    return prod;
}

Пошёл разбираться с делением.

Не по теме:

Скажите, а это нормально, что я такого рода код пишу уже целую неделю или это ооочень медленно?

0
I.M.
566 / 549 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
11.11.2012, 19:47 #27
Цитата Сообщение от vlad_light Посмотреть сообщение
C++
1
2
3
4
while (left_multiplier.polynom.rbegin()->return_alpha_vector() == null_vector)
* * * * left_multiplier.polynom.pop_back();
while (right_multiplier.polynom.rbegin()->return_alpha_vector() == null_vector)
* * * * right_multiplier.polynom.pop_back();
Лучше заменить на связку find + erase
Вот накидал вам пример: http://liveworkspace.org/code/f999b09ec01348ae32f5082b0eeb0bae
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
 
template <typename TContent>
void erase_start_nulls(std::vector<TContent>& i_vector, const TContent& null_element)
{
   auto it = std::find_if(i_vector.begin(), i_vector.end(), [&](const TContent& i){ return i!=null_element; });
   i_vector.erase(i_vector.begin(), it);
}
 
int main()
{
   std::array<int, 5> arr = {{0, 0, 0, 42, 7}};
   std::vector<int> data(arr.cbegin(), arr.cend());
   
   erase_start_nulls(data, 0);
      
   for (int i : data)
      std::cout << i << " ";
   return 0;
}

Собственно, шаблона не пугайтесь) Более того, вы можете взять его в свою программу.

По поводу длительности - ничего в этом плохого нет. Вы параллельно осваиваете математику и язык. Это же непросто

Добавлено через 1 минуту
Цитата Сообщение от vlad_light Посмотреть сообщение
C++
1
i <= std::min (k, (int) left_multiplier.polynom.size() - 1);
Ах да, забыл сказать. Это лучше вытащить в отдельную переменную. Компилятор, конечно, может быть это и оптимизирует, но не факт. Тут же ваши типы данных.
1
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
11.11.2012, 20:44  [ТС] #28
Лучше заменить на связку find + erase
я, если честно, не очень понял, что оно делает Что-то типа: ищем в массиве ноль, фиксируем итератор, а затем удаляем все элементы до этого итератора? Мне нужно с конца нули убрать, тогда оно будет выглядеть:
C++
1
2
3
4
5
auto iter = std::find_if (polynom.rbegin(), polinom.rend(), /*не понял что это*/)
{
  return i != null_vector;
}
polynom.erase (iter, polynom.end());
Вон тот последний параметр -- это, как я понял элемент, который мы ищем, а потом ставим итератор на место найденного элемента, так? И в последней строке нужно писать iter или ++iter ?
0
I.M.
566 / 549 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
11.11.2012, 21:36 #29
Если убрать надо с конца, то тот же код будет выглядеть так:
Кликните здесь для просмотра всего текста
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
#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
 
template <typename TContent>
void erase_end_nulls(std::vector<TContent>& i_vector, const TContent& null_element)
{
   auto rit = std::find_if(i_vector.rbegin(), i_vector.rend(), [&](const TContent& i){ return i!=null_element; });
   if (rit != i_vector.rend())
   {
      i_vector.erase(rit.base(), i_vector.end());
   }
}
 
int main()
{
   std::array<int, 5> arr = {{42, 7, 0, 0, 0}};
   std::vector<int> data(arr.cbegin(), arr.cend());
   
   erase_end_nulls(data, 0);
      
   for (int i : data)
      std::cout << i << " ";
   return 0;
}

Да, идея тут такая - мы находим первый итератор, указывающей не на ноль, а затем удаляем все элементы от/до этого итератора.
можете заменить find_if на обычный цикл, который вам будет гораздо понятнее.
например
C++
1
2
3
4
5
6
7
8
for (auto rit = v.rbegin(); rit != v.rend(); ++rit)
{
   if (*rit != null_element)
   {
      v.erase(rit.base(), v.end());
      break;
   }
}
1
vlad_light
4 / 4 / 0
Регистрация: 24.09.2012
Сообщений: 178
12.11.2012, 03:54  [ТС] #30
Помогите, а то шо-то голова не варит Написал такой код:
C++
1
2
3
4
5
6
7
8
for (auto iter = polynom.rbegin(); iter != polynom.rend(); ++iter)
    {
        if (iter->return_alpha_vector() != null_vector)
        {
            polynom.erase (iter.base(), polynom.end());
            break;
        }
    }
но, если там все нули, то он ничего не делает. Как по-быстренькому сделать так, чтоб он мне все нули, кроме первого удалял?
0
12.11.2012, 03:54
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.11.2012, 03:54
Привет! Вот еще темы с ответами:

Как запрограммировать математические многочлены, формулы? - C++
Каким образом запрограммировать математические вычисления вида: (a1+a2+… + an)/n ( a1+(a2+a3)/2+(a4+a5+a6)/3+… +(a'n-k'+...+an)/k ) / p...

Алгоритм генерации типовых задач по теме "Многочлены" - C++
Помогите с алгоритмом) никак не могу написать алгоритм генерации((( Например, деление многочленов

Выразить через основные симметрические многочлены моногенные многочлены - Алгебра
Здравствуйте. помогите пожалуйста понять как делать следующее задание &quot;Выразить через основные симметрические многочлены моногенные...

Многочлены - Математический анализ
Здравствуйте. Я хотела бы с вами посоветоваться. Мне нужно найти рациональные корни многочлена, причем коэффициенты многочлена могут быть...


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

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

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