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

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

Войти
Регистрация
Восстановить пароль
 
 
tdo22
10 / 10 / 1
Регистрация: 14.02.2013
Сообщений: 728
#1

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

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

Здравствуйте, не могу решить такую задачу:
К примеру есть 4 бита: 1010. Нужно функция которая выведет на экран все комбинации двух единиц и двух нулей
И отсортирует их от меньшего к большему:
Код
0011
0101
0110
1001
1010 <---
1100
нужно чтоб функция была быстрой и могла работать с очень длинными строками.
То-есть функция должна принимать три параметра, размер строки и количество нулей и единиц
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.01.2015, 15:13
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Работа с битами, вывести на экран все комбинации двух единиц и двух нулей (C++):

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

Вывести на экран элементы массива, сумма первых двух цифр равна сумме двух последних - C++
//Массив из n четырехзначных натуральных чисел. //Вывести па экран только те, у которых сумма первых двух цифр равна сумме двух...

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

В строке, состоящей из групп нулей и единиц, найти и вывести на экран короткую группу - C++
В строке, состоящей из групп нулей и единиц, найти и вывести на экран короткую группу. Прога виводит только один сивол. Когда вводишь 111...

Вывести на экран все варианты выкидывания двух кубиков - C++
Задали крч задачу суть : вывести на экран все варианты выкидывания двух кубиков 1 1 1 2 ... и так далее ... 6 6 Надо сделать...

Как сделать из двух чисел третье, уникальное для любой комбинации первых двух? - C++
Hi :) Есть два числа, допустим: int a и int b, как можно их &quot;сопряч&quot;, то есть что - то с ними сделать, что бы получить третье число,...

16
Enno
267 / 170 / 38
Регистрация: 25.08.2014
Сообщений: 1,088
Записей в блоге: 1
04.01.2015, 15:31 #2
Вот тебе подсказка:
Есть операция побитового сдвига. << - влево, >> - вправо. Функцию пишешь с пределом сдвига, если ещё остались не выставленные единицы, то снова вызываешь эту функцию с новыми пределами сдвига. Потом как все функции отработают сдвигаешься. Обычная рекурсия.
0
Байт
Эксперт C
16550 / 10820 / 1640
Регистрация: 24.12.2010
Сообщений: 20,888
04.01.2015, 15:33 #3
tdo22, Долго медитировал над условием, но так и не понял, что тебе нужно...
0
tdo22
10 / 10 / 1
Регистрация: 14.02.2013
Сообщений: 728
04.01.2015, 15:42  [ТС] #4
Enno, я думал над операциями битового сдвига, но как мне написать функцию так, чтоб всегда было определенное количество нулей и единиц ?
0
Enno
267 / 170 / 38
Регистрация: 25.08.2014
Сообщений: 1,088
Записей в блоге: 1
04.01.2015, 15:56 #5
Количество нулей = длина строки - количество единиц. Единица ставится функцией. Рекурсивно вызываешь на глубину N, больше чем N единиц не будет, ибо функция больше чем N раз для одной строки не вызовется.
1
ValeryS
Модератор
6707 / 5116 / 482
Регистрация: 14.02.2011
Сообщений: 17,190
04.01.2015, 16:03 #6
Цитата Сообщение от tdo22 Посмотреть сообщение
К примеру есть 4 бита: 1010.
и где они хранятся?
у си нет типа с размером в 4 бита
0
Melg
538 / 159 / 64
Регистрация: 23.09.2013
Сообщений: 314
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
tdo22
10 / 10 / 1
Регистрация: 14.02.2013
Сообщений: 728
04.01.2015, 16:35  [ТС] #8
Melg,
выдает ошибку:
Код
C:\Users\*****\C++\Sort\main.cpp|18|error: 'begin' was not declared in this scope
0
Melg
538 / 159 / 64
Регистрация: 23.09.2013
Сообщений: 314
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
TrueTerm
167 / 115 / 38
Регистрация: 25.12.2014
Сообщений: 382
04.01.2015, 16:48 #10
Задача, как я понял "вывести все n-разрядные двоичные числа, в которых ровно n/2 единичных битов (ну и нуликов, получается, тоже ровно n/2), число n-чётное".
tdo22, верно?
0
tdo22
10 / 10 / 1
Регистрация: 14.02.2013
Сообщений: 728
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
TrueTerm
167 / 115 / 38
Регистрация: 25.12.2014
Сообщений: 382
04.01.2015, 16:53 #12
tdo22,
Цитата Сообщение от tdo22 Посмотреть сообщение
ShowPermutations(5, 3);
Тогда задача такая: "вывести в порядке возрастания все двоичные числа, в которых ровно n единиц и m нулей".
0
tdo22
10 / 10 / 1
Регистрация: 14.02.2013
Сообщений: 728
04.01.2015, 16:55  [ТС] #13
TrueTerm, Да, задача такая.
0
Melg
538 / 159 / 64
Регистрация: 23.09.2013
Сообщений: 314
04.01.2015, 17:03 #14
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Пожалуйста скопируйте последнюю версию кода:
http://ideone.com/7OAmy5
я уже исправил не отображение 1ой мутации.
1
TrueTerm
167 / 115 / 38
Регистрация: 25.12.2014
Сообщений: 382
04.01.2015, 17:21 #15
Возможный алгоритм (нерекурсивный). Заполняем строчку (массив) требуемым количеством нулей (сначала) и единиц (потом) - это будет наименьшее число. Чтобы получить следующее, просматриваем строчку справа налево пока не встретится сочетание "01" (нолик слева от единицы).
Раз это самое правое сочетание, значит имеем "(...)01(p единиц)(k нулей)", где p и\или k могут быть равны 0, (...)-оставшаяся слева часть строки, может быть пустая. Создаём строку "(...)10(k нулей)(p единиц)" -это будет следующее число.
Так продолжаем, пока удаётся найти 01. Если не удалось, значит у нас сейчас "111...1110000...0000" т.е. самое последнее сочетание и работа на этом закончена.
1
04.01.2015, 17:21
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.01.2015, 17:21
Привет! Вот еще темы с ответами:

Дана строка, состоящая из групп нулей и единиц. Найти и вывести на экран группы с четным количеством символов - C++
Помогите с решение задачи на Macrosoft Visual C++ Дана строка, состоящая из групп нулей и единиц. Найти и вывести на экран группы с...

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

Получить все n-элементные последовательности из нулей и единиц содержащие ровно m единиц (m<=n) - C++
Получить все n-элементные последовательности из нулей и единиц содержащие ровно m единиц (m&lt;=n) Помогите, пожалуйста

Вывести сумму элементов последовательности до двух нулей (do/while) - C++
Задана последовательность целых чисел.Написать программу,которая выводит сумму элементов этой последовательности.Но нужно вывести сумму...


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

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

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