生成長度爲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的二進制數

回答

相關問題