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

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

Войти
Регистрация
Восстановить пароль
 
 
lvn1975
1 / 1 / 0
Регистрация: 17.10.2014
Сообщений: 17
#1

Разработка алгоритма и программы сжатия и восстановления массива - C++

17.10.2014, 20:57. Просмотров 586. Ответов 17
Метки нет (Все метки)

Добрый день! форумчане помогите сделать работу, возможно кому-то такая задача попадалась:
Массив (0,1) целых чисел. Разработать алгоритмы сжатия и восстановления массива. В целях анализа считать вероятность последовательности длиной К пропорциональной К.
Полное задание в файлах.
Мне хотя бы написать алгоритмы написать программу на С++ постараюсь сам, но если кто-то может написать алгоритм и программу буду благодарен.
0
Миниатюры
Разработка алгоритма и программы сжатия и восстановления массива   Разработка алгоритма и программы сжатия и восстановления массива  
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.10.2014, 20:57
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Разработка алгоритма и программы сжатия и восстановления массива (C++):

Реализация алгоритма сжатия JPEG - C++
помогите пожалуйста! после завтра диплом уже защищать, а я ни на шаг не могу сдвинуться с этой прогрммой(( нужно написать на С++ алгоритм...

помогите с реализацией алгоритма сжатия Хаффмана - C++
помогите с реализацией алгоритма сжатия Хаффмана есть код в с++ в консольном приложении, помогите сделать в форме, и чтоб выводило в...

Программирование и исследование алгоритма сжатия информации: с чего начать? - C++
Преподаватель задал задание написать программу... на тему : "Программирование и исследование алгоритма сжатия информации".. и я не могу...

Требуется реализация простейшего алгоритма сжатия данных (кодирование повторов) - C++
Требуется программная реализация простейшего алгоритма сжатия данных(кодирование повторов). Обрабатываемые данные в виде текста(файла),...

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

Восстановления состояния программы - C++
Добрый вечер, есть реальные рабочие примеры восстановления программы до состояния перед багом/крашем ? Стоит ли вообще таким...

17
SlavaSSU
216 / 161 / 45
Регистрация: 17.07.2012
Сообщений: 587
17.10.2014, 21:29 #2
lvn1975, не совсем понял задачу, но может как вариант брать каждые 32 числа этого массива и делать из них один инт, т.е. грубо говоря вместо 32 чисел у нас хранится 1 число(битовая маска).
0
lvn1975
1 / 1 / 0
Регистрация: 17.10.2014
Сообщений: 17
17.10.2014, 21:45  [ТС] #3
я понял, что массив состоит из 0 и 1 длиной К, надо вот этот массив сжать и затем восстановить, а как и по какому алгоритму не знаю . Уже голову сломал. Предмет называется разработка эффективных алгоритмов. Подошел к преподу, ничего не объяснил даже направление в какое направление двигаться.
0
SlavaSSU
216 / 161 / 45
Регистрация: 17.07.2012
Сообщений: 587
17.10.2014, 21:49 #4
lvn1975, ну вот значит можно каждые 32 числа хранить в одном инте.

Можно проще, но тогда память сократится всего в 2 раза -- это хранить позиции числа, вхождений которого меньше, т.е. если нулей меньше то хранишь позиции нулей, иначе - единиц.
0
lvn1975
1 / 1 / 0
Регистрация: 17.10.2014
Сообщений: 17
17.10.2014, 21:57  [ТС] #5
SlavaSSU, Ты знаешь как? Можешь написать?
Я тут старшекурсника спросил, он предположил с помощью метода Хоффмана, но там рассматривается либо с текстом, либо с файлами. Мне кажется здесь, что-то проще, т.к. мы только начали изучать. Может я ошибаюсь.
0
SlavaSSU
216 / 161 / 45
Регистрация: 17.07.2012
Сообщений: 587
17.10.2014, 22:47 #6
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
lvn1975, запарили сообщения не отправляться!!!


C++ (Qt)
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
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
 
using namespace std;
 
typedef unsigned int uint;
 
int main(){
 
    int k;
    cin >> k;
 
    vector<uint> rar;
    vector<int> naive;
 
    uint mask = 0;
 
    for(int i = 1; i <= k; i++)
    {
        int val;
        scanf("%d", &val);
        naive.push_back(val);
 
        if(val == 1)
            mask |= (uint(1) << (31 - ((i - 1) % 32)));
 
        if(i % 32 == 0)
        {
            rar.push_back(mask);
            mask = 0;
        }
    }
 
    rar.push_back(mask);
 
    /*for(int i = 0; i < rar.size(); i++)
        cout << rar[i] << ' ';
    cout << endl;*/
 
    //long long c = (1LL << 31) + (1LL << 28) + (1LL << 27);
    //cout << c << endl;
 
    //все сжали и сохранили в векторке
 
    //допустим пусть приходят запросы на инвертирование каких-то чисел массива
 
    int m;
    scanf("%d", &m);
 
    for(int k = 1; k <= m; k++)
    {
        int idx;
        scanf("%d", &idx);
 
        naive[idx - 1] = 1 - naive[idx - 1];
 
        int my_idx = idx / 32 + 1;
        if(idx % 32 == 0)
            my_idx--;
 
        my_idx--;
        idx = 31 - ((idx - 1) % 32);
        //cout << my_idx << ' ' << idx << endl;
        //cout << (uint(1) << idx) << endl;
        rar[my_idx] ^= (uint(1) << idx);
    }
 
    //восстановим массив
 
    int curlen = 0;
 
    vector<int> res;
 
    for(int i = 0; i < rar.size(); i++)
    {
        for(int j = 31; j >= 0 && curlen < k; j--)
            res.push_back((rar[i] & (uint(1) << j)) > 0), curlen++;
    }
 
    cout << "array == " << endl;
    for(int i = 0; i < res.size(); i++)
        cout << res[i] << ' ';
    cout << endl;
 
    cout << "naive array == " << endl;
    for(int i = 0; i < naive.size(); i++)
        cout << naive[i] << ' ';
    cout << endl;
 
    return 0;
}
0
lvn1975
1 / 1 / 0
Регистрация: 17.10.2014
Сообщений: 17
17.10.2014, 23:55  [ТС] #7
Я так понял здесь вводим длину массива
C++ (Qt)
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
 int k;
    cin >> k;
 
    vector<uint> rar;
    vector<int> naive;
 
    uint mask = 0;
 
    for(int i = 1; i <= k; i++)
    {
        int val;
        scanf("%d", &val);
        naive.push_back(val);
 
        if(val == 1)
            mask |= (uint(1) << (31 - ((i - 1) % 32)));
 
        if(i % 32 == 0)
        {
            rar.push_back(mask);
            mask = 0;
        }
    }
 
    rar.push_back(mask);
Это вводим массив из 0 и 1
int m;
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int m;
    scanf("%d", &m);
 
    for(int k = 1; k <= m; k++)
    {
        int idx;
        scanf("%d", &idx);
 
        naive[idx - 1] = 1 - naive[idx - 1];
 
        int my_idx = idx / 32 + 1;
        if(idx % 32 == 0)
            my_idx--;
 
        my_idx--;
        idx = 31 - ((idx - 1) % 32);
        cout << my_idx << ' ' << idx << endl;
        cout << (uint(1) << idx) << endl;
        rar[my_idx] ^= (uint(1) << idx);
Это вывод восстановленного массива
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 int curlen = 0;
 
    vector<int> res;
 
    for(int i = 0; i < rar.size(); i++)
    {
        for(int j = 31; j >= 0 && curlen < k; j--)
            res.push_back((rar[i] & (uint(1) << j)) > 0), curlen++;
    }
 
    cout << "array == " << endl;
    for(int i = 0; i < res.size(); i++)
        cout << res[i] << ' ';
    cout << endl;
 
    cout << "naive array == " << endl;
    for(int i = 0; i < naive.size(); i++)
        cout << naive[i] << ' ';
    cout << endl;
 system ("pause");
    return 0;
}
почему-то выводится 2 раза одно и тоже "array == " и "naive array == "
сокращение идет по нулям. А вывод сокращенного массива нет.
Правильно я понял или нет?
0
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
22.10.2014, 20:59 #8
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
/////////////////////////////////////////////////////////////////////////////////////////
//Массив (0,1) целых чисел. Разработать алгоритмы сжатия и восстановления массива. В целях 
//анализа считать вероятность последовательности длиной К пропорциональной К.
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <climits>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef unsigned    T_int;
/////////////////////////////////////////////////////////////////////////////////////////
const   T_int     BITS_PER_INT        =   sizeof( T_int )   *   CHAR_BIT;
const   T_int     DIGIT_FOR_LEFT      =   0;
const   T_int     DIGIT_FOR_RIGHT     =   1;
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string                                                 T_str;
typedef std::vector                     < T_int                 >   T_int_vect;
typedef std::set                        < T_int                 >   T_int_set;
typedef std::uniform_int_distribution   < int                   >   T_distribution;
typedef std::map                        < T_int,    T_int_vect  >   T_code_of_num;
/////////////////////////////////////////////////////////////////////////////////////////
struct  T_h_node;
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::shared_ptr < T_h_node  >   T_h_tree;
/////////////////////////////////////////////////////////////////////////////////////////
struct  T_h_node
{
    //-----------------------------------------------------------------------------------
    T_int       value_;
    T_h_tree    left_tree_;
    T_h_tree    right_tree_;
    //-----------------------------------------------------------------------------------
    T_h_node
        (
            T_int           value,
            T_h_node    *   left_tree   =   nullptr,
            T_h_node    *   right_tree  =   nullptr
        )
        :
        value_          ( value         ),
        left_tree_      ( left_tree     ),
        right_tree_     ( right_tree    )
    {}
    //-----------------------------------------------------------------------------------
    bool    operator<   ( T_h_node  const   &   h_node )                            const
    {
        return  value_  >   h_node.value_;
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::priority_queue < T_h_node  >   T_h_nodes_priority_queue;
/////////////////////////////////////////////////////////////////////////////////////////
class   T_bits_in
{
    //-----------------------------------------------------------------------------------
    T_int_vect  arr_;
    T_int       cur_ind_;
    T_int       written_bits_counter_;
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    T_bits_in( T_int     arr_size )
        :
        arr_                    ( arr_size ),
        cur_ind_                (),
        written_bits_counter_   ()
    {}
    //-----------------------------------------------------------------------------------
    void    write_bit( T_int  val )
    {
        write_n_bits
            (
                1,
                val
            );
    }
    //-----------------------------------------------------------------------------------
    void    write_as_int( T_int     num_with_bits )
    {
        write_n_bits
            (
                BITS_PER_INT,
                num_with_bits
            );
    }
    //-----------------------------------------------------------------------------------
    void    write_n_bits
        (
            T_int     bits_count,
            T_int     num_with_bits
        )
    {
        T_int     cur_bits_count   =   0;
 
        while( bits_count > 0 )
        {
            cur_bits_count          =   std::min    (
                                                        BITS_PER_INT - written_bits_counter_,
                                                        bits_count
                                                    );
 
            bits_count              -=      cur_bits_count;
            T_int   copy            =       num_with_bits;
            copy                    >>=     bits_count;
            arr_[ cur_ind_ ]        <<=     cur_bits_count;
            arr_[ cur_ind_ ]        |=      copy;
            written_bits_counter_   +=      cur_bits_count;
 
            if( written_bits_counter_   ==  BITS_PER_INT )
            {
                written_bits_counter_   =   0;
                ++cur_ind_;
 
                if  (
                        cur_ind_    ==  arr_.size() - 1
                    )
                {
                    arr_.resize
                        (
                            arr_.size() * 2
                        );
                }//if
            }//if
 
            if( bits_count > 0 )
            {
                num_with_bits   <<=     BITS_PER_INT - bits_count;
                num_with_bits   >>=     BITS_PER_INT - bits_count;
            }//if
        }//while
    }
    //-----------------------------------------------------------------------------------
    void    push_back_arr_as_bits
        (
            T_int_vect     const   &   arr
        )
    {
        std::for_each
            (
                arr.begin   (),
                arr.end     (),
 
                [=] ( T_int_vect::value_type    elem )
                {
                    write_bit( elem );
                }
            );
    }
    //-----------------------------------------------------------------------------------
    T_int_vect  int_arr()
    {
        if( written_bits_counter_ > 0 )
        {
            write_n_bits
                (
                    BITS_PER_INT - written_bits_counter_,
                    0
                );
        }//if
 
        return  T_int_vect
                    (
                        arr_.begin(),
                        arr_.begin() + cur_ind_
                    );
    }
    //-----------------------------------------------------------------------------------
};
/////////////////////////////////////////////////////////////////////////////////////////
class   T_bits_from
{
    //-----------------------------------------------------------------------------------
    T_int_vect  arr_;
    T_int       cur_ind_;
    T_int       taken_bits_counter_;
    //-----------------------------------------------------------------------------------
public:
    //-----------------------------------------------------------------------------------
    T_bits_from( T_int_vect  const   &   arr )
        :
        arr_                    ( arr ),
        cur_ind_                (),
        taken_bits_counter_     ()
    {}
    //-----------------------------------------------------------------------------------
    T_int     read_as_int()
    {
        return  read_n_bits( BITS_PER_INT );
    }
    //-----------------------------------------------------------------------------------
    T_int     read_bit()
    {
        return  read_n_bits( 1 );
    }
    //-----------------------------------------------------------------------------------
    T_int     read_n_bits( T_int    bits_count )
    {
        T_int   cur_bits_count  =   0;
        T_int   res_res         =   0;
        T_int   res             =   0;
 
        while( bits_count > 0 )
        {
            cur_bits_count  =   std::min    (
                                                BITS_PER_INT - taken_bits_counter_,
                                                bits_count
                                            );
 
            bits_count              -=      cur_bits_count;
            res                     =       arr_[ cur_ind_ ];
            arr_[ cur_ind_ ]        <<=     cur_bits_count;
            res                     >>=     BITS_PER_INT - cur_bits_count;
            res_res                 <<=     cur_bits_count;
            res_res                 |=      res;
            taken_bits_counter_     +=      cur_bits_count;
 
            if( taken_bits_counter_   ==  BITS_PER_INT )
            {
                taken_bits_counter_   =   0;
                ++cur_ind_;
            }
        }//while
 
        return  res_res;
    }
    //-----------------------------------------------------------------------------------
    T_int     read_code_and_get_value_for( T_h_tree   const   &   h_tree )
    {
        auto    cur_tree    =   h_tree;
 
        while   (
                    cur_tree->left_tree_  !=  nullptr
                )
        {
            cur_tree  =   read_bit()    ==  DIGIT_FOR_RIGHT
                            ?   cur_tree->right_tree_
                            :   cur_tree->left_tree_;
        }//while
 
        return  cur_tree->value_;
    }
    //-----------------------------------------------------------------------------------
};
0
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
22.10.2014, 21:00 #9
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
/////////////////////////////////////////////////////////////////////////////////////////
T_int_vect  generate_01_array( T_int  size )
{
    static  std::default_random_engine  rand_generator( unsigned(time(0)) );
 
    T_int         left    =   0;
    T_int         right   =   size;
 
    T_int_set   bounds;
 
    bounds.insert( left     );
    bounds.insert( right    );
 
    while( right - left >= 2 )
    {
        T_int     middle  =   T_distribution
                                (
                                    left    +   1,
                                    right   -   1
                                )
                            ( rand_generator );
 
        bounds.insert( middle );
 
        if  (
                middle  <   ( left + right ) / 2
            )
        {
            left    =   middle;
        }
        else
        {
            right   =   middle;
        }
    }//while
 
    T_int     first_val   =   T_distribution( 0,  1 )( rand_generator );
 
    auto    left_it     =   bounds.begin();
    auto    right_it    =   left_it;
    ++right_it;
 
    if( first_val   ==  0 )
    {
        ++left_it;
        ++right_it;
    }
 
    T_int_vect  int_vect( size );
 
    while   (
                right_it    !=  bounds.end()
            )
    {
        std::fill
            (
                int_vect.begin()    +   *left_it,
                int_vect.begin()    +   *right_it,
                1
            );
 
        ++left_it;
        ++right_it;
 
        if  (
                right_it    ==  bounds.end()
            )
        {
            break;
        }
 
        ++left_it;
        ++right_it;
    }//while
 
    return  int_vect;
}
/////////////////////////////////////////////////////////////////////////////////////////
T_h_tree    get_h_tree_for( T_int_set   const   &   seq_sizes_set )
{
    T_h_nodes_priority_queue    h_nodes_priority_queue;
 
    std::for_each
        (
            seq_sizes_set.begin     (),
            seq_sizes_set.end       (),
 
            [&] ( T_int   seq_size )
            {
                h_nodes_priority_queue.push
                    (
                        T_h_node( seq_size )
                    );
            }
        );
 
    while   (
                h_nodes_priority_queue.size() > 1
            )
    {
        auto    L   =   h_nodes_priority_queue.top();
        h_nodes_priority_queue.pop();
 
        auto    R   =   h_nodes_priority_queue.top();
        h_nodes_priority_queue.pop();
 
        h_nodes_priority_queue.push
            (
                T_h_node
                    (
                        L.value_    +   R.value_,
                        new     T_h_node( L ),
                        new     T_h_node( R )
                    )
            );
    }//for
 
    return  T_h_tree    (
                            new   T_h_node( h_nodes_priority_queue.top() )
                        );
}
/////////////////////////////////////////////////////////////////////////////////////////
void    set_code_of_num
    (
        T_h_tree    const   &   h_tree,
        T_code_of_num       &   code_of_num,
        T_int_vect              code_vect   =   T_int_vect()
    )
{
    if  (
            h_tree->left_tree_  ==  nullptr
        )
    {
        code_of_num[ h_tree->value_ ]   =  code_vect;
    }
    else
    {
        auto    L_deq   =   code_vect;
        L_deq.push_back( DIGIT_FOR_LEFT );
        set_code_of_num
            (
                h_tree->left_tree_,
                code_of_num,
                L_deq
            );
 
        auto    R_deq   =   code_vect;
        R_deq.push_back( DIGIT_FOR_RIGHT );
        set_code_of_num
            (
                h_tree->right_tree_,
                code_of_num,
                R_deq
            );
    }//else
}
0
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
22.10.2014, 21:01 #10
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
/////////////////////////////////////////////////////////////////////////////////////////
void    for_arr_set_seq_sizes_and_seq_sizes_set
    (
        T_int_vect  const   &   arr,
        T_int_vect          &   seq_sizes,
        T_int_set           &   seq_sizes_set
    )
{
    T_int     prev_ind    =   0;
    T_int     cur_val     =   arr.front   ();
    T_int     arr_size    =   arr.size    ();
 
    for( T_int  i = 0; i < arr_size; ++i )
    {
        if  (
                arr[i]     !=  cur_val
            )
        {
            T_int     cur_seq_size    =   i - prev_ind;
            seq_sizes.push_back     ( cur_seq_size );
            seq_sizes_set.insert    ( cur_seq_size );
            prev_ind    =   i;
            cur_val     =   ( cur_val + 1 ) % 2;
        }
    }//for
 
    seq_sizes.push_back     ( arr_size - prev_ind );
    seq_sizes_set.insert    ( arr_size - prev_ind );
}
/////////////////////////////////////////////////////////////////////////////////////////
T_int     get_bits_in_word_for( T_int_set     const   &   seq_sizes_set )
{
    T_int     max_num     =   *seq_sizes_set.rbegin();
 
    T_int     bits_in_word  =   0;
 
    do
    {
        ++bits_in_word;
    }
    while( max_num  >>= 1 );
 
    return  bits_in_word;
}
/////////////////////////////////////////////////////////////////////////////////////////
T_int_vect  encode_arr( T_int_vect  const   &   arr )
{
    T_int_vect  seq_sizes;
    T_int_set   seq_sizes_set;
 
    for_arr_set_seq_sizes_and_seq_sizes_set
        (
            arr,
            seq_sizes,
            seq_sizes_set
        );
 
    T_h_tree        h_tree  =   get_h_tree_for( seq_sizes_set );
    T_code_of_num   code_of_num;
 
    set_code_of_num
        (
            h_tree,
            code_of_num
        );
 
    T_bits_in  bits_in      (   seq_sizes.size      ()  );
 
    bits_in.write_as_int    (   seq_sizes_set.size  ()  );
    bits_in.write_as_int    (   seq_sizes.size      ()  );
 
    T_int     bits_in_word    =   get_bits_in_word_for( seq_sizes_set );
 
    bits_in.write_n_bits
        (
            CHAR_BIT,
            bits_in_word
        );
 
    std::for_each
        (
            seq_sizes_set.begin     (),
            seq_sizes_set.end       (),
 
            [&]  ( T_int   cur_size )
            {
                bits_in.write_n_bits
                    (
                        bits_in_word,
                        cur_size
                    );
            }
        );
 
    bits_in.write_bit
        (
            arr.front()
        );
 
    std::for_each
        (
            seq_sizes.begin     (),
            seq_sizes.end       (),
 
            [&]  ( T_int   cur_size )
            {
                bits_in.push_back_arr_as_bits
                    (
                        code_of_num[ cur_size ]
                    );
            }
        );
 
    return  bits_in.int_arr();
}
/////////////////////////////////////////////////////////////////////////////////////////
T_int_vect  decode_arr( T_int_vect  const   &   arr )
{
    T_bits_from  bits_from( arr );
 
    T_int     seq_sizes_set_size  =   bits_from.read_as_int   ();
    T_int     seq_sizes_arr_size  =   bits_from.read_as_int   ();
 
    T_int     bits_in_word        =   bits_from.read_n_bits   ( CHAR_BIT );
 
    T_int_set   seq_sizes_set;
 
    for( T_int  i = 0; i < seq_sizes_set_size; ++i )
    {
        seq_sizes_set.insert
            (
                bits_from.read_n_bits( bits_in_word )
            );
    }
 
    T_h_tree    h_tree          =   get_h_tree_for      ( seq_sizes_set );
 
    T_int       first_elem_val  =   bits_from.read_bit  ();
 
    T_int_vect  res;
    T_int         cur_elem_val    =   first_elem_val;
 
    for( T_int  i = 0; i < seq_sizes_arr_size; ++i )
    {
        T_int     cur_seq_len     =   bits_from.read_code_and_get_value_for( h_tree );
 
        res.insert
            (
                res.end(),
                cur_seq_len,
                cur_elem_val
            );
 
        cur_elem_val    =   ( cur_elem_val + 1 ) % 2;
    }//for
 
    return  res;
}
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::locale::global(std::locale(""));
    const   int     ARR_SIZE_MIN    =   2;
    const   int     ARR_SIZE_MAX    =   100000000;
 
    for(;;)
    {
        int     arr_size    =   0;
 
        do
        {
            std::cout   <<  "Введите длину исходного случайного массива из нулей и единиц ("
                        <<  ARR_SIZE_MIN
                        <<  ".."
                        <<  ARR_SIZE_MAX
                        <<  "): "
                        <<  std::endl;
 
            std::cin    >>  arr_size;
        }
        while   (
                        arr_size    <   ARR_SIZE_MIN
                    ||  arr_size    >   ARR_SIZE_MAX
                );
 
        T_int_vect  arr     =   generate_01_array   ( arr_size  );
        T_int_vect  code    =   encode_arr          ( arr       );
 
        std::cout   <<  "Зашифрованный массив:"
                    <<  std::endl;
 
        std::copy
            (
                code.begin                      (),
                code.end                        (),
                std::ostream_iterator< T_int >  ( std::cout,    "\t" )
            );
 
        T_int_vect  decoded_arr     =   decode_arr( code );
 
        std::cout   <<  std::endl
                    <<  "Исходный и расшифрованный массивы "
                    <<  (
                            arr     ==  decoded_arr
                                ?   ""
                                :   "НЕ "
                        )
 
                    <<  "совпали."
                    <<  std::endl
                    <<  "Сжато в "
                    <<  std::fixed
                    <<  std::setprecision(1)
                    <<  double( arr.size() ) / code.size()
                    <<  " раз."
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl
                    <<  std::endl;
    }//for
}
0
lvn1975
1 / 1 / 0
Регистрация: 17.10.2014
Сообщений: 17
22.10.2014, 22:54  [ТС] #11
Боюсь это сложно, Я понял в задаче, что создается одномерный массив из 0 и 1 длиной К, а сжать массив на величину пропорционально длины К. т.е. например массив длиной 8, а сжатие на 2 , если 32 то на 8,
01101001, здесь можно сократить 1 и 0 повторяющиеся 2 раза, вот как убрать их и создать новый массив 010101, примерно так.
0
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
22.10.2014, 23:34 #12
Цитата Сообщение от lvn1975 Посмотреть сообщение
создается одномерный массив из 0 и 1
Такой массив есть чередование последовательностей из нулей и единиц. Мне кажется, что именно об их длине идет речь, а не о длине массива. И сказано, что чем длиннее последовательность, тем больше вероятность ее появления в массиве.
0
lvn1975
1 / 1 / 0
Регистрация: 17.10.2014
Сообщений: 17
23.10.2014, 21:38  [ТС] #13
Мне кажется, что нам еще не могут дать такие сложные задачи. Мы только начали изучать алгоритмы, надо построить алгоритм и на основе его написать программу на языке Си++, а Вами написана программа слишком круто для начинающего студента, но спасибо за интересные решения.

Добавлено через 11 минут
Интересно алгоритм Хаффмана подойдет?
0
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
24.10.2014, 00:53 #14
Цитата Сообщение от lvn1975 Посмотреть сообщение
Интересно алгоритм Хаффмана подойдет?
Так це ж вин и е!
0
lvn1975
1 / 1 / 0
Регистрация: 17.10.2014
Сообщений: 17
24.10.2014, 21:45  [ТС] #15
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int m;
    scanf("%d", &m);
 
    for(int k = 1; k <= m; k++)
    {
        int idx;
        scanf("%d", &idx);
 
        naive[idx - 1] = 1 - naive[idx - 1];
 
        int my_idx = idx / 32 + 1;
        if(idx % 32 == 0)
            my_idx--;
 
        my_idx--;
        idx = 31 - ((idx - 1) % 32);
        cout << my_idx << ' ' << idx << endl;
        cout << (uint(1) << idx) << endl;
        rar[my_idx] ^= (uint(1) << idx);
Для чего это нужно, при вводе возникает ошибка.
0
24.10.2014, 21:45
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.10.2014, 21:45
Привет! Вот еще темы с ответами:

Разработка алгоритма оценки качества "Программного продукта" - C++
Добрый день уважаемые. Не давно начал делать курсовую работу по теме: &quot;Разработка системы оценки надежности программных продуктов&quot;. Так вот...

Разбор алгоритма программы - C++
Здравствуйте, у меня есть программа, вычисляющая факториал заданного числа. #include &quot;stdafx.h&quot; #include &lt;iostream&gt; ...

Разбор алгоритма программы - C++
Здравствуйте, у меня есть программа, вычисляющая факториал заданного числа. #include &quot;stdafx.h&quot; #include &lt;iostream&gt; ...

Составление алгоритма по коду программы - C++
Есть ли тут люди, которые могут помочь в составление алгоритма такой вот программки?: #include &lt;iostream&gt; #include &lt;fstream&gt; #include...


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

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

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