在两个半部中所有长度相等的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 教师闺蜜祝福语简短