在两个半部中所有长度相等的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 高中新生祝福语 简短
17 装修祝福语男生搞笑简短
18 生日开业蛋糕祝福语简短