Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.55/11: Рейтинг темы: голосов - 11, средняя оценка - 4.55
12 / 12 / 13
Регистрация: 14.02.2013
Сообщений: 755
1

Работа с битами, вывести на экран все комбинации двух единиц и двух нулей

04.01.2015, 15:13. Просмотров 2002. Ответов 16
Метки нет (Все метки)

Здравствуйте, не могу решить такую задачу:
К примеру есть 4 бита: 1010. Нужно функция которая выведет на экран все комбинации двух единиц и двух нулей
И отсортирует их от меньшего к большему:
Код
0011
0101
0110
1001
1010 <---
1100
нужно чтоб функция была быстрой и могла работать с очень длинными строками.
То-есть функция должна принимать три параметра, размер строки и количество нулей и единиц
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
04.01.2015, 15:13
Ответы с готовыми решениями:

В двоичном числе определить количество соседств двух нулей и двух единиц
Нужна помощь в написании кода на C++. Буду очень благодарен Дано короткое целое неотрицательное...

Найти и вывести на экран группы, которые состоят с двух единиц
дана строка,что состоит из групп нулей и единиц.Каждая группа отделяется друг от друга одним или...

Данная строка, состоящая из групп нулей и единиц. Найти и вывести на экран группы, состоящие только из нулей
Данная строка, состоящая из групп нулей и единиц. Каждая группа отделяется друг от друга одним или...

Вывести все возможные расположения двух единиц в массиве из четырех элементов
Функция, выводящая все возможные расположения двух единиц в массиве из четырех элементов, то есть...

16
267 / 170 / 40
Регистрация: 25.08.2014
Сообщений: 1,087
Записей в блоге: 1
04.01.2015, 15:31 2
Вот тебе подсказка:
Есть операция побитового сдвига. << - влево, >> - вправо. Функцию пишешь с пределом сдвига, если ещё остались не выставленные единицы, то снова вызываешь эту функцию с новыми пределами сдвига. Потом как все функции отработают сдвигаешься. Обычная рекурсия.
0
Эксперт C
24167 / 14877 / 3136
Регистрация: 24.12.2010
Сообщений: 31,824
04.01.2015, 15:33 3
tdo22, Долго медитировал над условием, но так и не понял, что тебе нужно...
0
12 / 12 / 13
Регистрация: 14.02.2013
Сообщений: 755
04.01.2015, 15:42  [ТС] 4
Enno, я думал над операциями битового сдвига, но как мне написать функцию так, чтоб всегда было определенное количество нулей и единиц ?
0
267 / 170 / 40
Регистрация: 25.08.2014
Сообщений: 1,087
Записей в блоге: 1
04.01.2015, 15:56 5
Количество нулей = длина строки - количество единиц. Единица ставится функцией. Рекурсивно вызываешь на глубину N, больше чем N единиц не будет, ибо функция больше чем N раз для одной строки не вызовется.
1
Модератор
8201 / 6071 / 811
Регистрация: 14.02.2011
Сообщений: 21,062
04.01.2015, 16:03 6
Цитата Сообщение от tdo22 Посмотреть сообщение
К примеру есть 4 бита: 1010.
и где они хранятся?
у си нет типа с размером в 4 бита
0
541 / 162 / 79
Регистрация: 23.09.2013
Сообщений: 316
04.01.2015, 16:18 7
Извольте:
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 <iostream>
#include <algorithm>
 
void ShowAllPermutationsFromFirst(std::string first_permutation_string) {
  while (std::next_permutation(begin(first_permutation_string),
                               end(first_permutation_string))) {
    std::cout << first_permutation_string << '\n';
  }
}
 
std::string CreateFirstPermutation(size_t number_of_zeros,
                                   size_t number_of_ones) {
  std::string zeros_string(number_of_zeros, '0');
  std::string ones_string(number_of_ones, '1');
  return zeros_string + ones_string;
}
 
void ShowPermutations(size_t number_of_zeros, size_t number_of_ones) {
  ShowAllPermutationsFromFirst(
      CreateFirstPermutation(number_of_zeros, number_of_ones));
}
 
int main() {
  ShowPermutations(2, 2);
  return 0;
}
Пруф работоспособности:

http://ideone.com/46Q4iO

На тему скорости работы - предложите мне бенчмарк для оценки скорости.
0
12 / 12 / 13
Регистрация: 14.02.2013
Сообщений: 755
04.01.2015, 16:35  [ТС] 8
Melg,
выдает ошибку:
Код
C:\Users\*****\C++\Sort\main.cpp|18|error: 'begin' was not declared in this scope
0
541 / 162 / 79
Регистрация: 23.09.2013
Сообщений: 316
04.01.2015, 16:46 9
Нужно заменить begin(blabla); на blabla.begin();
Пожалуйста:
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
#include <iostream>
#include <algorithm>
 
void ShowAllPermutationsFromFirst(std::string first_permutation_string) {
    do {
        std::cout << first_permutation_string << '\n';
    }
  while (std::next_permutation(first_permutation_string.begin(),
                               first_permutation_string.end()));
}
 
std::string CreateFirstPermutation(size_t number_of_zeros,
                                   size_t number_of_ones) {
  std::string zeros_string(number_of_zeros, '0');
  std::string ones_string(number_of_ones, '1');
  return zeros_string + ones_string;
}
 
void ShowPermutations(size_t number_of_zeros, size_t number_of_ones) {
  ShowAllPermutationsFromFirst(
      CreateFirstPermutation(number_of_zeros, number_of_ones));
}
 
int main() {
  ShowPermutations(2, 2);
  return 0;
}
Добавлено через 2 минуты
Еще один косяк поправил с отображением первого положения:
http://ideone.com/7OAmy5
0
183 / 128 / 49
Регистрация: 25.12.2014
Сообщений: 426
04.01.2015, 16:48 10
Задача, как я понял "вывести все n-разрядные двоичные числа, в которых ровно n/2 единичных битов (ну и нуликов, получается, тоже ровно n/2), число n-чётное".
tdo22, верно?
0
12 / 12 / 13
Регистрация: 14.02.2013
Сообщений: 755
04.01.2015, 16:50  [ТС] 11
Заработало, спасибо.
Но почему-то программа работает не всегда правильно.
Если вызвать функцию так:
C++
1
ShowPermutations(5, 3);
то выводит:
Код
00001011
00001101
00001110
00010011
00010101
00010110
00011001
00011010
00011100
00100011
00100101
00100110
00101001
00101010
00101100
00110001
00110010
00110100
00111000
01000011
01000101
01000110
01001001
01001010
01001100
01010001
01010010
01010100
01011000
01100001
01100010
01100100
01101000
01110000
10000011
10000101
10000110
10001001
10001010
10001100
10010001
10010010
10010100
10011000
10100001
10100010
10100100
10101000
10110000
11000001
11000010
11000100
11001000
11010000
11100000
Первая строка 00001011, хотя по идее должна быть 00000111
И еще вопрос, какое максимальное количество единиц и нулей ?
Можно туда засунуть к примеру 8 000 000 нулей и 5 000 000 единиц ?

Добавлено через 38 секунд
TrueTerm, Да, но единиц у ноликов может очень-очень много
0
183 / 128 / 49
Регистрация: 25.12.2014
Сообщений: 426
04.01.2015, 16:53 12
tdo22,
Цитата Сообщение от tdo22 Посмотреть сообщение
ShowPermutations(5, 3);
Тогда задача такая: "вывести в порядке возрастания все двоичные числа, в которых ровно n единиц и m нулей".
0
12 / 12 / 13
Регистрация: 14.02.2013
Сообщений: 755
04.01.2015, 16:55  [ТС] 13
TrueTerm, Да, задача такая.
0
541 / 162 / 79
Регистрация: 23.09.2013
Сообщений: 316
04.01.2015, 17:03 14
Лучший ответ Сообщение было отмечено tdo22 как решение

Решение

Пожалуйста скопируйте последнюю версию кода:
http://ideone.com/7OAmy5
я уже исправил не отображение 1ой мутации.
1
183 / 128 / 49
Регистрация: 25.12.2014
Сообщений: 426
04.01.2015, 17:21 15
Возможный алгоритм (нерекурсивный). Заполняем строчку (массив) требуемым количеством нулей (сначала) и единиц (потом) - это будет наименьшее число. Чтобы получить следующее, просматриваем строчку справа налево пока не встретится сочетание "01" (нолик слева от единицы).
Раз это самое правое сочетание, значит имеем "(...)01(p единиц)(k нулей)", где p и\или k могут быть равны 0, (...)-оставшаяся слева часть строки, может быть пустая. Создаём строку "(...)10(k нулей)(p единиц)" -это будет следующее число.
Так продолжаем, пока удаётся найти 01. Если не удалось, значит у нас сейчас "111...1110000...0000" т.е. самое последнее сочетание и работа на этом закончена.
1
12 / 12 / 13
Регистрация: 14.02.2013
Сообщений: 755
04.01.2015, 19:04  [ТС] 16
TrueTerm, а можно Ваш пример на c++ ?
а то я что-то не совсем понял
0
Эксперт C
24167 / 14877 / 3136
Регистрация: 24.12.2010
Сообщений: 31,824
04.01.2015, 19:32 17
Цитата Сообщение от TrueTerm Посмотреть сообщение
Тогда задача такая: "вывести в порядке возрастания все двоичные числа, в которых ровно n единиц и m нулей".
Цитата Сообщение от tdo22 Посмотреть сообщение
Да, задача такая.
Ну вот, наконец-то мне, тупенькому, стало понятно, о чем речь идет. Задача сводится к генерации всех сочетаний по N (количество единиц) из N+M (M - количество нулей). Таких задач на форуме - немеряно. Да и Гугл в состоянии дать хорошую подборку алгоритмов. И большинство из них будет генерировать сочетания в лексикографическом порядке (просто так удобнее). Для больших N и M вопрос в подходящем представлении (тоже не Бином Ньютона) и ... во времени. Вы представляете примерно, сколько будет С130000005000000 ?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
04.01.2015, 19:32

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Комбинации нулей и единиц в строке длинной S
Помогите пожалуйста написать программку. Пользователем вводится длина строки s, а программа должна...

Сгенерировать и вывести на экран массив 10x10 из нулей и единиц
Сгенерировать и вывести на экран массив 10x10 из нулей и единиц так, чтобы нулей было в несколько...

Найти и вывести на экран самую короткую группу нулей и единиц
Здравствуйте, помогите решить задачу: дана строка, состоящая из групп нулей и единиц. Найти и...

Задано последовательность групп нулей и единиц. Вывести на экран наименьшую группу
Задано последовательность групп нулей и единиц. Вывести на экран наименьшую группу.

Вывести на экран все числа из двух диапазонов
Ребята все привет, помогите начинающему программисту решить задачу Пользователь вводит 4 числа....

Вывести на экран те числа, у которых сумма первых двух цифр равна сумме двух последних
39. Дан массив из n четырехзначных натуральных чисел. Вывести на экран только те, у которых сумма...


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

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

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