计算 n 位字符串的数量，使得在字符串的每个前缀中，零的数量至少是一的数量的 k 倍

Question

我们如何计算 n 位字符串的数量，使得在字符串的每个前缀中，零的数量至少是 1 的数量的 k 倍？

示例：

(1) 当 n = 5 且 k = 3 时，有 3 个这样的字符串：00000、00001 和 00010。在每个字符串中，每个初始子字符串的零数至少是 1 数的三倍。

(2) n = 6, k = 2, 有8个这样的字符串: 000000, 000001, 000010, 000011, 000100, 000101, 001000, 001001.

我实现了递归计数，但我需要比那个更有效的算法或公式。如果有人能在输出中找到一种模式以避免在递归上浪费时间，那就太好了。

为了澄清问题，我将说明一些限制条件， 1<=n<=1000； 1<=k<=n

任何想看代码的人，这是我实现的递归代码-

#include <iostream>
using namespace std;

int count;
int k;

// c0 is no. of 0s and c1 is no. of 1s
void rec(int c0, int c1, int n)
{
    if(n>=0)
    {
        if(!n)
        {
            count++;
        }

        rec(c0+1,c1,n-1);

        if((c1+1)*k<=c0)
        {
            rec(c0,c1+1,n-1);
        }
    }
}

int main()
{
    int n;

    cin>>n>>k;
    rec(k,0,n-k);
    cout<<count;

    return 0;
}

Answer 1

通过构造而不是反复试验找到合法的字符串。

从左边开始对字符串位置进行编号，从 1 开始。为了符号方便，让 j = k+1。第一个 1 不能早于位置 j 出现；第二个不早于位置 2j，依此类推。

例如，对于 (6, 2) 的情况，j=3。第一个 1 可以出现在位置 3 的任意位置；第二个只能出现在位置 6.

编写一个 DP 函数来完成这个决策过程。暂时忘记生成字符串，我们只需要每个元素 a[i] 不小于 i*j 的所有数组。对于上述情况，第一个决策点是针对初始元素的。选项包括

[]
[3]
[4]
[5]
[6]

第一个和最后一个是终端搜索；其他的得到扩展以获得可能的第二个元素，产生

[3, 6]
[4, 6]
[5, 6]

...这些很容易转换为八种所需的解决方案。

你能从那里实现递归吗？

Answer 2

虽然可能存在涉及组合分析的更复杂的解决方案，但生成动态规划解决方案非常简单，该解决方案的运行时间为 O(n²) 并且需要额外的 O(n) space。由于此解决方案的内部循环仅涉及一次加法，因此在 n 变大之前速度非常快，尽管除了最小的问题外，您确实需要多精度算法来解决所有问题。

动态编程涉及颠覆递归；在动态规划中，我们不是从目标问题开始并将其递归分解为更简单的问题，而是以某种适当的顺序解决所有更简单的问题，以便在我们需要它们之前获得中间结果。当相同的更简单的问题在递归过程中多次出现时，它是有效的，这与记忆递归的用例相同。不过，DP 比记忆更有效，因为中间计算的正确排序通常意味着在任何给定时间需要记住其值的中间计算数量的显着减少。（它还避免了检查所需的中间值是否已经计算的开销，尽管这通常并不重要。）

在这种情况下，我们将使用一个非常简单的递归，它基于以下事实：任何长度为 m 的有效二进制序列都是长度为 m-1 的有效二进制序列，后跟0 或 1。（并非总是可以将 1 放在有效二进制序列的末尾，因为这可能违反计数约束。但是总是可以删除恰好位于有效二进制序列的结尾。）

我们实际要计算的是长度为 n 且长度为 m 的有效序列的数量。那么长度为n的有效序列的个数可以通过将m的不同值的所有计数相加得到。而我们可以区分三种情况：

m 太大；有太多的，以至于不可能构造一个序列，其中的数量至少是零的数量的 k 倍。很容易检查这种情况；零的数量是 n - m（因为所有不是一的东西都必须是零），所以如果 m > k(n - m)，m 就太大了。一点点代数会表明这与说 m > n / (k + 1).
m 为零。恰好有一个有效的长度为 n 且没有任何序列：n 零的序列。并且无论 k.
对于m的每个大于0且小于上面第1点中的截止值的值，我们可以通过考虑m来计算有效序列的数量两个可能的最后一个值：一个有效序列必须是长度为 n-1 的有效序列和 m-1 的序列，后跟另一个序列，或者是长度为 n-1 的有效序列和 m 后跟一个零。

将所有这些放在一起，我们可以递归计算：

Count[n, m] = 1                               if m = 0
            = Count[n-1, m-1] + Count[n-1, m] if 0 < m ≤ n / (k + 1)
            = 0                               if m > n / (k + 1)

现在，让我们将该递归转化为动态规划解决方案。

很明显，给定 n 的 Count[n, ...] 的所有值仅取决于 Count[n-1, ...] 的值。因此，如果我们计算 Count[n-1,...] 的所有值，我们可以使用它们来生成 Count[n, ...] 值的向量，之后我们不再需要记住 Count[n-1, ...] 的任何值。所以我们显然只需要保留两个长度为1 + (n / (k + 1))的向量。但我们可以做得更好，因为 Count[n, m] 的值仅取决于 Count[n-1, m] 和 Count[n-1, m-1]。如果我们从 m.

的最大有效值开始反向计算，这个事实让我们可以使用单个向量进行计算。

因此，计算长度为 n 的有效位序列的最终解决方案，其中每个前缀至少有 k 个零：

创建长度为 1 + (n / (k + 1)) 的向量 Count。将 Count[0] 设置为 1，将所有其他元素设置为 0。
对于从 1 到 n（含）的每个 i：
- 从i / (k + 1)到1（含）的每个j：
  - 将 Count[j-1] 添加到 Count[j]
Return Count

Answer 3

    // Trivial recursive solution
    // It appears that one on the recursive calls
    // can be removed as tail recursion
    // Appending multiple '0's, just until another '1' is possible,
    // seems to be a nice optimisation, but will complicate the
    // final logic (at the end-of string) and will need a few
    // extra conditions.

#include <stdio.h>

char buff[100];

unsigned recurse(unsigned zeros, unsigned ones, unsigned x, unsigned len)
{
unsigned count=0;
unsigned pos = zeros+ones;

if (pos == len) {
        buff[pos] =0;
        printf("%s\n", buff);
        return 1;
        }

buff[pos] = '0';
count += recurse(zeros+1, ones, x, len);
        // if no '1' is possible yet,
        // we could loop here, adding more '0' bits
        // , but we must take care not to exceed len
        // and to maintain the count correctly
        // (and possibly yield the resulting string)

if (ones < zeros /x) {
        buff[pos] = '1';
        count += recurse(zeros, ones+1, x, len);
        }

return count; // number of solutions, given the prefix [0..pos]
}

int main(int argc, char **argv)
{
unsigned x,n, result;
sscanf(argv[1], "%u", &n);
sscanf(argv[2], "%u", &x);

result = recurse(0,0, x, n);
printf("Result=%u\n", result);
return 0;
}

Answer 4

#include <iostream>
using namespace std;

int main()
{
    int t,i,j,m,n,k,sum;
    
    sum=0;
    
    cin>>n>>k;
    m=n/(k+1);
    
    int count[m+1]={0};
    count[0]=1;
    
    for(i=k+1;i<=n;i++)
    {
        for(j=i/(k+1);j>=1;j--)
        {
            count[j]=count[j]+count[j-1];
        }
    }
    
    for(i=0;i<m+1;i++)
    {
        sum=sum+count[i];
    }
    
    cout<<sum<<endl;
    
    return 0;
}

根据上面给出的建议，我认为这就是您要找的。

计算 n 位字符串的数量，使得在字符串的每个前缀中，零的数量至少是一的数量的 k 倍

Count the number of n-bit strings such that, in each prefix of the string, the number of zeroes is at least k times the number of ones

algorithm

permutation

combinatorics