Форум программистов, компьютерный форум CyberForum.ru

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

Войти
Регистрация
Восстановить пароль
 
SMYH
2 / 2 / 0
Регистрация: 23.10.2013
Сообщений: 38
#1

Булевые массивы "веса" от 1 - n - C++

15.06.2014, 20:32. Просмотров 249. Ответов 2
Метки нет (Все метки)

Задача в том, что нужно создать все булевые массивы одной длины, количество "1" в которых равно 1,2...n.
То есть для случая l = 4 и n = 1 ответ очевиден.
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
bool** arr = new bool*[length];
    for(int i = 0; i<length; i++){
        arr[i] = new bool[length];
        for(int j = 0; j<length; j++){
            if(i==j){
                arr[i][j] = 1;
            }
            else{
                arr[i][j] = 0;
            }
        }
    }

arr - это:
Кликните здесь для просмотра всего текста

1000
0100
0010
0001

Для 1 все просто. Для n>1 намного сложнее. Может у кого-нибудь есть какие-то идеи. Я думал использовать циклический сдвиг, т.к. все "вектора" представляют собой сдвинутые другие. Под спойлером это ясно показано.
Кликните здесь для просмотра всего текста

Для веса 2.
>>
1100
0110
0011
1001
Другая "орбита"
1010
0101


P.S. В теории информации эта задача называется "Перебор всех векторов ошибок".
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.06.2014, 20:32     Булевые массивы "веса" от 1 - n
Посмотрите здесь:
C++ Курсовая работа "Разработка конвертации мер массы и веса"
Ищу статьи и книги по теме "Структуры; массивы структур" C++
C++ Написать контрольные вопросы по теме "Массивы объектов" (теория)
Из текстового файла прочитать в массивы пары "символ - число" C++
Придумать задачу на массивы с использованием логической операции "И" C++
C++ Контест "Массивы. Вставка и удаление элементов"
C++ Помогите найти ошибки: "Указатели на массивы"
C++ Язык Си "Одномерные массивы". Сортировка по возрастанию
Игра "Угадай слова" через массивы! C++
Помогите написать программы на "Одномерные массивы" C++
C++ С++ исправить задачу "двумерные массивы"
Массивы структур "Футбольная команда" C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mr.X
Эксперт С++
3048 / 1693 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
16.06.2014, 11:03     Булевые массивы "веса" от 1 - n #2
Рекурсивный вариант:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/////////////////////////////////////////////////////////////////////////////////////////
//Задача в том, что нужно создать все булевые массивы одной длины, количество "1" 
//в которых равно 1,2...n.
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string     T_str;
/////////////////////////////////////////////////////////////////////////////////////////
void  print_binary_numbers_with_size_and_units_total
    (
        int                 size,
        int                 units_total,
        T_str   const   &   prefix,
        int             &   num_counter
    )
{
    if( size == 0 )
    {
        std::cout   <<  '#'
                    <<  ++num_counter
                    <<  '\t'
                    <<  prefix
                    <<  std::endl;
        return;
    }
 
    if( units_total     <   size )
    {
        print_binary_numbers_with_size_and_units_total
            (
                size - 1,
                units_total,
                prefix + '0',
                num_counter
            );
    }
 
    if( units_total > 0 )
    {
        print_binary_numbers_with_size_and_units_total
            (
                size - 1,
                units_total - 1,
                prefix + '1',
                num_counter
            );
    }//if
}
/////////////////////////////////////////////////////////////////////////////////////////
void  print_prompt_and_input_val_not_less_than
    (
        T_str   const   &   prompt,
        int             &   val,
        int                 left_bound
    )
{
    do
    {
        std::cout   <<  prompt;
        std::cin    >>  val;
    }
    while( val < left_bound );
}
/////////////////////////////////////////////////////////////////////////////////////////
int  main()
{
    std::locale::global(std::locale(""));
    for(;;)
    {
        int     size    =   0;
 
        print_prompt_and_input_val_not_less_than
            (
                "Длина двоичного числа\t\t: ",
                size,
                1
            );
 
        int     units_total     =   0;
 
        print_prompt_and_input_val_not_less_than
            (
                "Количество единиц в числе\t: ",
                units_total,
                0
            );
 
        int     num_counter     =   0;
        print_binary_numbers_with_size_and_units_total
            (
                size,
                units_total,
                T_str(),
                num_counter
            );
        std::cout   <<  "\n\n\n\n\n\n";
    }//for
}
Добавлено через 5 минут
Нерекурсивный вариант:
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
/////////////////////////////////////////////////////////////////////////////////////////
//Задача в том, что нужно создать все булевые массивы одной длины, количество "1" 
//в которых равно 1,2...n.
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string     T_str;
/////////////////////////////////////////////////////////////////////////////////////////
void  print_binary_numbers_with_size_and_units_total
    (
        int     size,
        int     units_total
    )
{
    T_str   s       ( size - units_total,   '0' );
    s   +=  T_str   ( units_total,          '1' );
 
    int     num_counter     =   0;
 
    for(;;)
    {
        std::cout   <<  '#'
                    <<  ++num_counter
                    <<  "\t"
                    <<  s
                    <<  std::endl;
 
        T_str::size_type    pos     =   s.rfind( "01" );
 
        if( pos ==  T_str::npos )
        {
            break;
        }
 
        std::swap
            (
                s[ pos     ],
                s[ pos + 1 ]
            );
 
        //Если в конце нули, то реверсируем участок от pos + 2 до конце.
        for (
                int  L = pos + 2, R = size - 1;
 
                    L       <   R
                &&  s[L]    ==  '1'
                &&  s[R]    ==  '0';
 
                ++L, --R
            )
        {
            std::swap
                (
                    s[L],
                    s[R]
                );
        }//for
    }//for
}
/////////////////////////////////////////////////////////////////////////////////////////
void  print_prompt_and_input_val_not_less_than
    (
        T_str   const   &   prompt,
        int             &   val,
        int                 left_bound
    )
{
    do
    {
        std::cout   <<  prompt;
        std::cin    >>  val;
    }
    while( val < left_bound );
}
/////////////////////////////////////////////////////////////////////////////////////////
int  main()
{
    std::locale::global(std::locale(""));
    for(;;)
    {
        int     size    =   0;
 
        print_prompt_and_input_val_not_less_than
            (
                "Длина двоичного числа\t\t: ",
                size,
                1
            );
 
        int     units_total     =   0;
 
        print_prompt_and_input_val_not_less_than
            (
                "Количество единиц в числе\t: ",
                units_total,
                0
            );
 
        print_binary_numbers_with_size_and_units_total( size, units_total );
        std::cout   <<  "\n\n\n\n\n\n";
    }//for
}
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
16.06.2014, 11:30     Булевые массивы "веса" от 1 - n #3
если не поянтно будет объясню!

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
#include <iostream>
 
using namespace std;
 
int main()
{
    int len, need;
    cin >> len >> need;
    for(int mask = 0; mask < (1 << len); mask++)
    {
        int cntbit = 0;
        for(int i = 0; i < len; i++)
            if(mask & (1 << i))
                cntbit++;
        if(cntbit == need)
        {
            for(int i = 0; i < len; i++)
                if(mask & (1 << i))
                    cout << 1;
                else
                    cout << 0;
            cout << endl;
        }
    }
    return 0;
}
Ответ Создать тему
Опции темы

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