Выберите кодировку чисел в коде Грея
Я должен написать программу, которая показывает кодирование некоторых чисел в коде Грея. Я уже нашел алгоритм, написанный на C ++ на этой странице ( https://www.geeksforgeeks.org/given-a-number-n-generate-bit-patterns-from-0-to-2n-1-so-that-successive-patterns-differ-by-one-bit/ ).
Но я хочу создать новый метод для удаления чисел, которые имеют два «1» подряд и имеют «1» в конце (слева и справа).
Пример: для n = 3 мы получаем эти числа:
000
001
011
010
110
111
101
100
Теперь я хочу удалить эти номера: 011, 110, 111, 101 и показать остальные номера в списке.
Моя идея — создать вектор векторов. Примерно так, например, когда n = 3: {{000}, {001}, {011}, {010}, {110}, {111}, {101}, {100}}.
По размеру это будет так:
int m = pow(2,n);
int vector[m][n];
Например: vector [0] [1] = {0} и vector [1] [2] = {1}, если я правильно с размерами.
Теперь, чтобы удалить числа, которые имеют два «1» подряд и имеют «1» в конце, я могу использовать этот код:
while (i < m){
for (j=0; j<n-1; j++){
if (vector[i][j]==vector[i][j+1]==1 && vector[i][0]==vector[i][n-1]==1 )
i=i+1; //Don't show this number
else { cout <<vector[i][j] << endl; i=i+1; }
}
}
Теперь проблема в том, что я не знаю, как сохранить результат в коде Грея, написанном на C ++, в моих векторах, или, может быть, есть способ сравнить два числа из этого кода без использования векторов.
Решение
Это будет дополнительной работой, когда вы доберетесь до больших строк, и код не будет тривиальным для чтения. Как насчет создания простой маски? Сдвиньте пару смежных 1 бит на длину числа (num).
mask = 0b11000 // fill in the correct quantity of 0s
end_mask = 0b10001
while mask > 1
if (num && mask) == mask
remove num from array
mask = mask >> 1
if num && end_mask == end_mask
remove num from array
Другие решения
Без использования битовых манипуляций, которые, по общему признанию, будут быстрее, поскольку у вас есть вектор векторов, один из способов удаления — использовать станд :: adjacent_find используя предикат, чтобы найти соседние 1 и использовать станд :: remove_if удалить те векторы, которые соответствуют критериям наличия смежных единиц.
Вот пример:
#include <algorithm>
#include <vector>
#include <iostream>
#include <iterator>
bool findOnes(const std::vector<int>& v)
{
// less than 2 digits, so can't do anything
if ( v.size() < 2 )
return false;
// test extremes
if ( v.front() == 1 && v.back() == 1 )
return true;
// check if there are adjacent 1's
return std::adjacent_find(v.begin(), v.end(), [&](int n1, int n2)
{ return n1 == 1 && n2 == 1; }) != v.end();
}
int main()
{
//test
std::vector<std::vector<int>> vect = {{0,0,0},{0,0,1},{0,1,1},{0,1,0},{1,1,0},{1,1,1},{1,0,1},{1,0,0}};
// erase the vectors that match the criteria
vect.erase(std::remove_if(vect.begin(), vect.end(), findOnes), vect.end());
// show the final results
for ( auto& i : vect )
{
std::copy(i.begin(), i.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << "\n";
}
}
В основном, если adjacent_find не находит соседние 1, возвращенный итератор будет end(), Таким образом, в findOne Функция предиката, после выполнения простых тестов для размера и экстремальных значений, adjacent_find берет на себя и делает все остальное.