提问人：Hristo 提问时间：3/17/2021 最后编辑：Hristo 更新时间：3/17/2021 访问量：196
递归函数，用于查找长度为 N 的二进制字符串的数量，该字符串以 0 开头，具有 0 和 1 的奇数序列
Recursive function that finds the number of binary strings of length N that starts with 0 and have odd sequences of 0s and 1s
问：
描述一个递归函数，该函数查找长度为 N 的二进制字符串的数量，该字符串以 0 开头，具有 0 和 1 的奇数序列。
样本输入 3
样本输出 2
我偶然发现了这个问题，无法完全理解它。对解决此/伪/真实代码的方法的解释将不胜感激。
我想出了以下解决方案，尽管我不确定序列计数是否正确。
int find(int n, int i, string str, int seqN) {
if (i == 0) {
str.append("0");
return find(n, i + 1, str, seqN);
}
if (n > i) {
return find(n, i + 1, str+"1", seqN) + find(n, i + 1, str + "0", seqN);
}
if (n == i) {
cout << str << "\n";
string sub = "01";
string sub2 = "10";
int n = 0;
n += countRecursive(str, sub);
n += countRecursive(str, sub2);
if (n%2 != 0)
{
return seqN + 1;
}
}
return seqN;
}
答：
0赞
user4371848
3/17/2021
#1
F(N-1) = 2F(N-2)
if statements:
F(1)=1
F(0)=0
长度为 3 时以 0 开头，与奇数序列的 2 个元素完全相同。 例如：0001 - 010 是 F（3），但它恰好是 F（2） 的递归，只找到奇数序列。逻辑是显而易见的，因为 0 不会影响序列的总和。 在幕后手工计算。 F（5） 中的奇数序列是数 5 个位数 1 个位数或 1 个位数 5 个位数或 5 个位数 3。它正好是 2^4 或 2^（n-1）
评论