這裡我們將看到所有可能的n位元二進位數(n由使用者給出),其中每一半的和相同。例如,如果數字是 10001,這裡 10 和 01 是相同的,因為它們的總和相同,並且它們位於不同的一半。這裡我們將產生該類型的所有數字。
left和right最初為空,diff保存差異左右之間
Begin if n is 0, then if diff is 0, then print left + right end if return end if if n is 1, then if diff is 0, then print left + 0 + right print left + 1 + right end if return end if if 2* |diff| <= n, then if left is not blank, then genAllBinEqualSumHalf(n-2, left + 0, right + 0, diff) genAllBinEqualSumHalf(n-2, left + 0, right + 1, diff-1) end if genAllBinEqualSumHalf(n-2, left + 1, right + 0, diff + 1) genAllBinEqualSumHalf(n-2, left + 1, right + 1, diff) end if End
#include <bits/stdc++.h> using namespace std; //left and right strings will be filled up, di will hold the difference between left and right void genAllBinEqualSumHalf(int n, string left="", string right="", int di=0) { if (n == 0) { //when the n is 0 if (di == 0) //if diff is 0, then concatenate left and right cout << left + right << " "; return; } if (n == 1) {//if 1 bit number is their if (di == 0) { //when difference is 0, generate two numbers one with 0 after left, another with 1 after left, then add right cout << left + "0" + right << " "; cout << left + "1" + right << " "; } return; } if ((2 * abs(di) <= n)) { if (left != ""){ //numbers will not start with 0 genAllBinEqualSumHalf(n-2, left+"0", right+"0", di); //add 0 after left and right genAllBinEqualSumHalf(n-2, left+"0", right+"1", di-1); //add 0 after left, and 1 after right, so difference is 1 less } genAllBinEqualSumHalf(n-2, left+"1", right+"0", di+1); //add 1 after left, and 0 after right, so difference is 1 greater genAllBinEqualSumHalf(n-2, left+"1", right+"1", di); //add 1 after left and right } } main() { int n = 5; genAllBinEqualSumHalf(n); }
100001 100010 101011 110011 100100 101101 101110 110101 110110 111111
以上是長度為n的所有可能的二進制數,兩半部的和相等?的詳細內容。更多資訊請關注PHP中文網其他相關文章!