生成长度为n，等于1和0的二进制数

问题与标题中相同。我已经完成了两种方法。一个很简单。从生成长度为n，等于1和0的二进制数

2^{N - 1}

到

2^N

并为每位掩码检查生成所有位掩码，如果有相同量的1和0，如果是的话，工作。而这就是问题所在，因为我必须在这些位掩码上工作，不仅要数它们。

我来到第二种方法，它运行在O（2^{n/2}）时间，但似乎它不会生成所有位掩码，我不知道为什么。

第二种方法是这样的：生成所有位掩码从0到2^{N/2}，并具有有效位掩码（称为B）我必须做这样的事情：B＃一B

哪里〜是否定的。

因此，例如，我有N = 6，所以我要去用3.

长度。例如，以产生位屏蔽我有B = 101，所以〜乙将010 和最终位掩码将是正如我们所看到的，101010具有相同数量的1和0。

这种方法是好还是我实施的东西不好？也许还有一些有趣的方法存在？感谢

克里斯

来源

2011-12-16 Spinach

尝试递归方法：

void printMasks(int n0, int n1, int mask) { 
    if (!n0 && !n1) { 
     cerr << mask << endl; 
     return; 
    } 
    mask <<= 1; 
    if (n0) { 
     printMasks(n0-1, n1, mask); 
    } 
    if (n1) { 
     printMasks(n0, n1-1, mask | 1); 
    } 
}

呼叫printMasks传递给它的0和1的所需数量。例如，如果你需要3名者和3个零，这样称呼它：

printMasks(3, 3, 0);

来源

2011-12-16 15:14:09 dasblinkenlight

嘿，感谢它，但它不工作得那么好，我的意思是... 对于参数3,3,0 它在35号之前产生不好的位掩码，之后它提供了很好的数字。我用我的蛮力来检查它 – Spinach 2011-12-16 15:25:47

这是可能的，给定一个二进制数，以产生具有相同数量的“1”的下一个更高的二进制数，使用对足够大的字保持所有位的恒定数量的操作（假设通过两次计数除以一次操作）。

确定最不重要的'1'（提示：如果你减少数字会发生什么）和最不重要的'0'的位置（提示：如果你添加“最不重要的1”到原始数字？）您应该将最低有效位“0”更改为“1”，并将适当数量的最低有效位设置为“1”，并将中间位设置为“0”。

来源

2011-12-16 21:50:12 supercat

生成长度为n，等于1和0的二进制数

回答

相关问题