数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究长度为n且两半和相等的二进制数的所有可能性？
我们将在这里查看n位二进制数（n由用户指定）的所有可能性，其中每半边的和相同。例如，如果数字是10001，则10和01相同，因为它们的和相同，并且它们位于不同的半边中。我们将在此处生成所有此类数字。
算法
genAllBinEqualSumHalf(n, left, right, diff)
left和right最初为空，diff保持left和right之间的差
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
更新于： 31-Jul-2019
190次浏览
广告