いくつかの数字をグレイコードで選択する

Question

グレイコードでコード化された数字を示すプログラムを書く必要があります。私はすでにこのページ（https://www.geeksforgeeks.org/given-a-number-n-generate-bit-patterns-from-0-to-2n-1-so-that-successive-patterns-differ-by-one-bit/）にC++で書かれたアルゴリズムを発見しました。

しかし、2つの「1」の連続した数字を削除し、その末尾に「1」を付ける新しい方法を作成したいと考えています。

例：N = 3のために私たちは、この番号を取得：101、011、110、111、リストにremiding他の番号を示しています。

000 
001 
011 
010 
110 
111 
101 
100 

今、私はこの数字を削除したいです。

私の考えは、ベクトルのベクトルを作成することです。たとえば、n = 3の場合、{{000}、{001}、{011}、{010}、{110}、{111}、{101}、{100}}のようなものです。例えば

int m = pow(2,n); 
int vector[m][n]; 

：ベクトル[0] [1] = {0}とベクトル[1] [2] = {1}私は場合は、それは、このようになりますサイズについて

サイズで修正してください。今

連続2「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++で書かれています。あるいは、ベクタを使わずにこのコードから2つの数字を比較する方法があります。

Answer 1

これは、大きな文字列になったときに余計な作業になります。コードは読みにくいものではありません。単純なマスクを作るのはどうですか？連続した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 

Answer 2

、あなたはベクトルのベクトルを持っているので、削除を実行するための一つの方法は、隣接する1さんを見つけるために、述語を使用してstd::adjacent_findを使用して、std::remove_ifにを使用することです隣接する1を有するという基準に合致するベクトルを除去する。ここで

は一例です：

#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"; 
    } 
} 

Live Example

adjacent_findは、隣接する1さんを見つけることができなかった場合、基本的に、返されたイテレータはend()になります。したがって、findOne述語関数では、サイズと極値の簡単なテストを実行した後、adjacent_findが引き継いで残りの処理を行います。