选择一些用格雷码编码的数字 [英] Choose some numbers coding in Gray Code

问题描述

我必须编写一个程序，以格雷码显示一些数字。我已经在此页面中找到了用C ++编写的算法（> https://www.geeksforgeeks.org/given-a-number-n-generate-bit-patterns-from -0到2n-1，所以成功的模式相差一比特/ ）。

I have to write a programm that shows some numbers coding in Gray Code. I already found an algorithm written in C++ in this page ( 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，我们得到以下数字：

Example : for n = 3 we get this numbers :

000
001
011
010
110
111
101
100

现在我要删除这些数字：011，110，111，101并显示列表中其他数字。

Now I want to delete this numbers : 011 , 110 , 111 , 101 and show the other numbers remiding in the list.

我的想法是创建向量的向量。例如，当n = 3时：{{000}，{001}，{011}，{010}，{110}，{111}，{101}，{100}}。

My idea is to create a vector of vectors. Something like that for example when n = 3 : {{000},{001},{011},{010},{110},{111},{101},{100}}.

对于大小，它是这样的：

For the size it will be like this :

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

例如：vector [0] [1] = {0}和vector [1] [2 ] = {1}（如果我对大小无误）。

For example : vector[0][1] = {0} and vector[1][2] = {1} if I'm correct with the sizes.

现在要删除连续有两个 1并且在末端具有 1的数字可以使用以下代码：

Now to delete the numbers that have two "1" consecutively and have "1" in their extremity I can use this code :

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 ++编写的格雷代码中，或者也许有一种方法可以在不使用向量的情况下比较此代码中的两个数字。

Now the problem is that I don't know how to store the result in the Gray Code written in C++ in my vectors, or maybe there is a way to compare between two numbers from this code without using vectors.

推荐答案

不使用位操作，这显然会更快，因为您有矢量的向量，因此执行删除的一种方法是要使用 std :: adjacent_find 并使用谓词来查找相邻的1，并使用 std :: remove_if 删除那些符合以下条件的向量：

Without using bit manipulation, which admittedly would be faster, since you have a vector of vectors, one way to perform the removal is to use std::adjacent_find using a predicate to find the adjacent 1's, and to use std::remove_if to remove those vectors matching the criteria of having adjacent 1's.

这里是一个示例：

#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 接管并执行了其余的。

Basically, if the adjacent_find does not find adjacent 1's, the iterator returned will be end(). Thus in the findOne predicate function, after doing the easy tests for size and the extreme values, adjacent_find takes over and does the rest.

这篇关于选择一些用格雷码编码的数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！