Нумерация клеток заданной полоски

alisa208

Помогите пожалуйста с заданием! Дана полоска длиной 2k клеток и шириной в одну клетку. Полоску несколько раз сгибают пополам так, чтобы ее правая половина оказывалась под левой. Сгибают до тех пор, пока сверху остается больше одной клетки. Написать программу, которая пронумерует клетки так, что после завершения сгибания полоски номера клеток в полученной колонке будут упорядочены: 1, 2, 3 , 4 , ..., 2k.
2 ответа

alisa208

Дана полоска длиной 2^k клеток и шириной в одну клетку. Полоску несколько раз сгибают пополам так, чтобы ее правая половина оказывалась под левой. Сгибают до тех пор, пока сверху остается больше одной клетки. Написать программу, которая пронумерует клетки так, что после завершения сгибания полоски номера клеток в полученной колонке будут упорядочены: 1, 2, 3 , 4 , ..., 2^k.


alisa208

//Дана полоска длиной 2^k клеток и шириной в одну клетку.
//Полоску несколько раз сгибают пополам так, чтобы ее правая
//половина оказывалась под левой. Сгибают до тех пор, пока
//сверху остается больше одной клетки. Написать программу,
//которая пронумерует клетки так, что после завершения сгибания
//полоски номера клеток в полученной колонке будут упорядочены:
//1, 2, 3 , 4 , ..., 2^k.
///////////////////////////////////////////////////////////////////////////////
#include <cmath>
#include <iostream>
#include <vector>
///////////////////////////////////////////////////////////////////////////////
typedef std::vector     < int   >   T_values;
typedef T_values                    T_strip;
typedef T_values                    T_end_values;
///////////////////////////////////////////////////////////////////////////////
T_values    get_indexes_of_bent_strip_with_size
    (
        int             len,
        T_end_values    end_left_values     =   T_end_values(),
        T_end_values    end_right_values    =   T_end_values()
    )
{
    if  (
            end_left_values.empty()
        )
    {
        end_left_values     .push_back  ( 0         );
        end_right_values    .push_back  ( len - 1   );
    }
 
    if( len == 1 )
    {
        return  end_left_values;
    }
    else
    {
        end_left_values.insert
            (
                end_left_values     .end    (),
                end_right_values    .rbegin (),
                end_right_values    .rend   ()
            );
 
        end_right_values    =   end_left_values;
        len     /=  2;
        auto    delta   =   len - 1;
 
        for( size_t  i{}; i < end_right_values.size(); ++i )
        {
            end_right_values[i]     +=  (
                                            i   %   2
                                                ?   -delta
                                                :   delta
                                        );
        }//for
 
        return  get_indexes_of_bent_strip_with_size
                    (
                        len,
                        end_left_values,
                        end_right_values
                    );
    }//else
}
///////////////////////////////////////////////////////////////////////////////
void    set_bent_strip_cells_numbering( T_strip     &   strip )
{
    auto    bent_strip_indexes  =   get_indexes_of_bent_strip_with_size
                                        (
                                            strip.size()
                                        );
 
    for( size_t  i{}; i < bent_strip_indexes.size(); ++i )
    {
        strip   [
                    bent_strip_indexes[i]
                ]
 
            =   i + 1;
    }
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    const   int     K_MIN   =   0;
    const   int     K_MAX   =   10;
 
    int     k{};
 
    do
    {
        std::cout   <<  "k ("
                    <<  K_MIN
                    <<  ".."
                    <<  K_MAX
                    <<  "): ";
 
        std::cin    >>  k;
    }
    while   (
                    k       <   K_MIN
                ||  K_MAX   <   k
            );
 
    T_strip     strip   (
                            pow( 2, k )
                        );
 
    set_bent_strip_cells_numbering( strip );
 
    for( auto   cell    :   strip )
    {
        std::cout   <<  cell
                    <<  '\t';
    }//for
 
    std::cout   <<  std::endl;
}