在两个半部中所有长度相等的n的所有可能二进制数？
在这里，我们将看到所有可能的n位二进制数（n由用户给出），其中每半的总和是相同的。例如，如果数字为10001，则10和01相同，因为它们的总和相同，并且分别位于不同的一半。在这里，我们将生成该类型的所有数字。
算法
genAllBinEqualSumHalf（n，左，右，diff）
左和右最初是空的，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;
//左右字符串将被填充，di将保留左右之间的差异
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);
//在左右后加0-
genAllBinEqualSumHalf(n-2, left+"0", right+"1", di-1);
//在左后加0，在右后加1，所以相差少1-
}
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
热门推荐
10 送给同桌的祝福语简短
11 哥哥新婚祝福语创意简短
12 庆祝论坛周年祝福语简短
13 经典祝福语简短情侣句子
14 宝宝生病简短祝福语大全
15 徒弟调走祝福语简短语
16 高考祝福语 简短12字
17 迟到的过年祝福语简短
18 租房明天搬家祝福语简短