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

@lvn1975 · Регистрация: 17.10.2014

Author24 — интернет-сервис помощи студентам

Добрый день! форумчане помогите сделать работу, возможно кому-то такая задача попадалась:
Массив (0,1) целых чисел. Разработать алгоритмы сжатия и восстановления массива. В целях анализа считать вероятность последовательности длиной К пропорциональной К.
Полное задание в файлах.
Мне хотя бы написать алгоритмы написать программу на С++ постараюсь сам, но если кто-то может написать алгоритм и программу буду благодарен.

@SlavaSSU · 17.10.2014, 21:29

lvn1975, не совсем понял задачу, но может как вариант брать каждые 32 числа этого массива и делать из них один инт, т.е. грубо говоря вместо 32 чисел у нас хранится 1 число(битовая маска).

@lvn1975 · 17.10.2014, 21:45 **[ТС]**

я понял, что массив состоит из 0 и 1 длиной К, надо вот этот массив сжать и затем восстановить, а как и по какому алгоритму не знаю . Уже голову сломал. Предмет называется разработка эффективных алгоритмов. Подошел к преподу, ничего не объяснил даже направление в какое направление двигаться.

@SlavaSSU · 17.10.2014, 21:49

lvn1975, ну вот значит можно каждые 32 числа хранить в одном инте.

Можно проще, но тогда память сократится всего в 2 раза -- это хранить позиции числа, вхождений которого меньше, т.е. если нулей меньше то хранишь позиции нулей, иначе - единиц.

@lvn1975 · 17.10.2014, 21:57 **[ТС]**

SlavaSSU, Ты знаешь как? Можешь написать?
Я тут старшекурсника спросил, он предположил с помощью метода Хоффмана, но там рассматривается либо с текстом, либо с файлами. Мне кажется здесь, что-то проще, т.к. мы только начали изучать. Может я ошибаюсь.

@SlavaSSU · 17.10.2014, 22:47

lvn1975, запарили сообщения не отправляться!!!

C++ (Qt)

#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;
}

@lvn1975 · 17.10.2014, 23:55 **[ТС]**

Я так понял здесь вводим длину массива

C++ (Qt)

 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)

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)

 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 == "
сокращение идет по нулям. А вывод сокращенного массива нет.
Правильно я понял или нет?

@Mr.X · 22.10.2014, 20:59

C++

/////////////////////////////////////////////////////////////////////////////////////////
//Массив (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_;
    }
    //-----------------------------------------------------------------------------------
};

@Mr.X · 22.10.2014, 21:00

C++

/////////////////////////////////////////////////////////////////////////////////////////
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
}

@Mr.X · 22.10.2014, 21:01

C++

/////////////////////////////////////////////////////////////////////////////////////////
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
}

@lvn1975 · 22.10.2014, 22:54 **[ТС]**

Боюсь это сложно, Я понял в задаче, что создается одномерный массив из 0 и 1 длиной К, а сжать массив на величину пропорционально длины К. т.е. например массив длиной 8, а сжатие на 2 , если 32 то на 8,
01101001, здесь можно сократить 1 и 0 повторяющиеся 2 раза, вот как убрать их и создать новый массив 010101, примерно так.

@Mr.X · 22.10.2014, 23:34

Сообщение от lvn1975

создается одномерный массив из 0 и 1

Такой массив есть чередование последовательностей из нулей и единиц. Мне кажется, что именно об их длине идет речь, а не о длине массива. И сказано, что чем длиннее последовательность, тем больше вероятность ее появления в массиве.

@lvn1975 · 23.10.2014, 21:38 **[ТС]**

Мне кажется, что нам еще не могут дать такие сложные задачи. Мы только начали изучать алгоритмы, надо построить алгоритм и на основе его написать программу на языке Си++, а Вами написана программа слишком круто для начинающего студента, но спасибо за интересные решения.

Добавлено через 11 минут
Интересно алгоритм Хаффмана подойдет?

@Mr.X · 24.10.2014, 00:53

Сообщение от lvn1975

Интересно алгоритм Хаффмана подойдет?

Так це ж вин и е!

@lvn1975 · 24.10.2014, 21:45 **[ТС]**

C++ (Qt)

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);

Для чего это нужно, при вводе возникает ошибка.

@lvn1975 · 26.10.2014, 16:07 **[ТС]**

SlavaSSU, Спасибо твой вариант интересен

C++

#include "stdafx.h"
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
#include <clocale>
using namespace std;
 
typedef unsigned int uint;
 
int main()
{
    setlocale(LC_CTYPE, "rus");
    int k, m, i, j, v, c;
    
   
 
    vector<uint> rar;
    vector<int> res;
    uint mask = 0;
    printf("Введите длину массива:  ");
    cin >> k;
    m=k/2;
    printf("Ведите массив из 0 и 1: \n");
    for(i = 1; i <= k; i++)
    {
        
        scanf("%d", &v);
       /* naive.push_back(val);*/
 
        if(v == 1)
            mask |= (uint(1) << ((m-1) - ((i-1) % m)));
 
        if(i % m == 0)
        {
            rar.push_back(mask);
            mask = 0;
        }
    }
 
    rar.push_back(mask);
    printf("Сжатый массив:  ");
    for(i = 0; i < rar.size(); i++)
        cout << rar[i] << ' ';
    cout << endl;
 
 
 
    //все сжали и сохранили в векторке
 
    //допустим пусть приходят запросы на инвертирование каких-то чисел массива
 
 
  
 
    //восстановим массив
 
    c = 0;
    for( i = 0; i < rar.size(); i++)
    {
        for(j = m-1; j >= 0 && c < k; j--)
            res.push_back((rar[i] & (uint(1) << j)) > 0), c++;
    }
    printf("Восстановленный массив: ");
    
    for(i = 0; i < res.size(); i++)
        cout << res[i] << ' ';
    cout << endl;
 
    
 system ("pause");
    return 0;
}

Я тут не много переработал.
По какому ты алгоритму делал (как он называется)
И можешь объяснить как это работает словами

C++

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;*/

Благодарю заранее

C++

Введите длину массива:  8
Ведите массив из 0 и 1:
0
0
1
1
1
0
1
0
Сжатый массив:  3 10 0
Восстановленный массив: 0 0 1 1 1 0 1 0
Для продолжения нажмите любую клавишу . . .

@SlavaSSU · 26.10.2014, 16:25

lvn1975, m надо присвоить 32 а не k / 2.

нет названия у алгоритма, просто берешь и хранишь 32 числа, каждое из которых 0 или 1 в одном беззнаковом инте.

@lvn1975 · 26.10.2014, 17:37 **[ТС]**

SlavaSSU, А если длина массива 10.
можешь объяснить как работает эта часть программы

C++

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;*/

А по алгоритму Хаффмана написать программу

@Mr.X 3225 / 1752 / 436 Регистрация: 03.05.2010 Сообщений: 3,867
	22.10.2014, 23:34	12
	Сообщение от lvn1975 создается одномерный массив из 0 и 1 Такой массив есть чередование последовательностей из нулей и единиц. Мне кажется, что именно об их длине идет речь, а не о длине массива. И сказано, что чем длиннее последовательность, тем больше вероятность ее появления в массиве. 0

@lvn1975 1 / 1 / 1 Регистрация: 17.10.2014 Сообщений: 17
	23.10.2014, 21:38 [ТС]	13
	Мне кажется, что нам еще не могут дать такие сложные задачи. Мы только начали изучать алгоритмы, надо построить алгоритм и на основе его написать программу на языке Си++, а Вами написана программа слишком круто для начинающего студента, но спасибо за интересные решения. Добавлено через 11 минут Интересно алгоритм Хаффмана подойдет? 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	17.10.2014, 21:29	2
	lvn1975, не совсем понял задачу, но может как вариант брать каждые 32 числа этого массива и делать из них один инт, т.е. грубо говоря вместо 32 чисел у нас хранится 1 число(битовая маска). 0

@lvn1975 1 / 1 / 1 Регистрация: 17.10.2014 Сообщений: 17
	17.10.2014, 21:45 [ТС]	3
	я понял, что массив состоит из 0 и 1 длиной К, надо вот этот массив сжать и затем восстановить, а как и по какому алгоритму не знаю . Уже голову сломал. Предмет называется разработка эффективных алгоритмов. Подошел к преподу, ничего не объяснил даже направление в какое направление двигаться. 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	17.10.2014, 21:49	4
	lvn1975, ну вот значит можно каждые 32 числа хранить в одном инте. Можно проще, но тогда память сократится всего в 2 раза -- это хранить позиции числа, вхождений которого меньше, т.е. если нулей меньше то хранишь позиции нулей, иначе - единиц. 0

@lvn1975 1 / 1 / 1 Регистрация: 17.10.2014 Сообщений: 17
	17.10.2014, 21:57 [ТС]	5
	SlavaSSU, Ты знаешь как? Можешь написать? Я тут старшекурсника спросил, он предположил с помощью метода Хоффмана, но там рассматривается либо с текстом, либо с файлами. Мне кажется здесь, что-то проще, т.к. мы только начали изучать. Может я ошибаюсь. 0

@lvn1975 1 / 1 / 1 Регистрация: 17.10.2014 Сообщений: 17
	22.10.2014, 22:54 [ТС]	11
	Боюсь это сложно, Я понял в задаче, что создается одномерный массив из 0 и 1 длиной К, а сжать массив на величину пропорционально длины К. т.е. например массив длиной 8, а сжатие на 2 , если 32 то на 8, 01101001, здесь можно сократить 1 и 0 повторяющиеся 2 раза, вот как убрать их и создать новый массив 010101, примерно так. 0

@Mr.X 3225 / 1752 / 436 Регистрация: 03.05.2010 Сообщений: 3,867
	24.10.2014, 00:53	14
	Сообщение от lvn1975 Интересно алгоритм Хаффмана подойдет? Так це ж вин и е! 0

@SlavaSSU 221 / 166 / 47 Регистрация: 17.07.2012 Сообщений: 587
	26.10.2014, 16:25	17
	lvn1975, m надо присвоить 32 а не k / 2. нет названия у алгоритма, просто берешь и хранишь 32 числа, каждое из которых 0 или 1 в одном беззнаковом инте. 0

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

Решение