-2

我需要一个快速算法，它将所有可能的数字生成到一个数组中，直到给定数字 N 二进制。

e.g N=3
Then the array should be {0,0,0},{0,0,1}.....{1,1,1}
N<=17.

到目前为止，我已经尝试过这是一个递归解决方案。

void print_digits(int n, std::string const& prefix = "") {
    if (!n) {
        printf("%s,",prefix.c_str());
        return;
    }
    print_digits(n-1, prefix + '0');
    print_digits(n-1, prefix + '1');
}

我需要一个更好的算法。

4

3 回答 3

3

C++ 中的所有整数都以二进制表示形式直接存储在内存中。因此，如果您只想存储 N 个数字，您应该直接将它们“按原样”写入数组

std::vector<unsigned> Numbers;
// if N is length of the number, calculate the maximum as 2^N - 1
long long Max = 1 << N - 1;
for (unsinged i = 0; i < Max; ++i)
    Numbers.push_back(i);

如果您想以二进制表示形式编写它们，这也非常简单，即使您想自己编写所有代码。（请原谅，因为这只是一个简单的示例实现）

void PrintAsBits(unsigned value) {
    for (int i = sizeof(unsigned) * 8 - 1; i >= 0; --i)
        cout << ((1 << i) & value) ? 1 : 0;
    cout << '\n';
}
于 2013-01-03T14:25:35.677 回答
0

以防万一有人再关心，下面的代码实现了原始规范，它要求一种填充二维数组的方法，其中每个值都表示为一个数值数组，其元素对应于其值的二进制数字，以大端顺序排列.

#include <iostream>

static const int DIGIT_COUNT = 10;

static const int VALUE_COUNT = 1 << DIGIT_COUNT;
unsigned char g_binarray[VALUE_COUNT][DIGIT_COUNT];

void Populate() {
    for(int i=0; i<VALUE_COUNT; ++i) {
        unsigned char (&curr)[DIGIT_COUNT] = g_binarray[i];
        for(int di=0; di<DIGIT_COUNT; ++di) {
            curr[di] = unsigned char((i >> (DIGIT_COUNT - 1 - di)) & 1);
        }
    }
}

void DumpArray() {
    static const char *digits = "01";
    for(int i=1; i<VALUE_COUNT; ++i) {
        for(int di=0; di<DIGIT_COUNT; ++di) {
            std::cout << digits[!!g_binarray[i][di]];
        }
        std::cout << "    " << i << std::endl;
    }
}

int main(int argc, char* argv[]) {
    Populate();
    DumpArray();
    return 0;
}
于 2013-01-03T17:05:32.280 回答
-1

正如我在 1 篇文章中所写：

示例：如果您需要长度为 4，那么您必须有 2^4 = 16 个不同的数组。

您可以使用这个简单的 Java 代码来生成所有数组：

for (int i=0; i < 16; i++) {
        System.out.println(Integer.toBinaryString(i));
}

这个的输出：

0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111

于 2013-01-16T13:17:32.863 回答