math - 如何找到具有以下约束的二进制数的个数 :

Question

给定二进制数 n 和最大连续出现次数 m，求不同可能的二进制数的个数。此外，最左边和最右边的位必须为 1。

例如 n = 5，m = 3。

计数为 7:10001100111010110111110011101111101

请注意，我们排除了 11111，因为其中存在太多连续的 1。

这是我最近遇到的一道面试题，一直困扰着我。我不想强制检查每个数字的合法性，因为 n 可以大于 32。

Answer 1

如果二进制序列以“1”开头且最多有 m 个连续的“1”位，则我们称它为几乎有效。

对于 i = 1, ..., n 和 j = 0, ..., m 让 a(i, j) 是长度为 i 且恰好以 j 连续“1”数字结尾的几乎有效序列的数量。

然后

• a(1, 1) = 1 和 a(1, j) = 0 for j != 1，因为“1”是唯一几乎有效的序列长度为一。
• 对于 n >= 2 和 j = 0 我们有 a(i, 0) = a(i-1, 0) + a(i -1, 1) + ... + a(i-1, m)，因为将“0”附加到任何几乎有效的长度 i-1 序列都会给出几乎有效的序列长度 i 以“0”结尾。
• 对于 n >= 2 和 j > 0 我们有 a(i, j) = a(i-1, j-1) 因为将“1”附加到一个几乎有效的序列，尾随 i-1 给出一个长度为 j 且尾随 i 的几乎有效的序列一个。

最后，想要的数字是长度为 n 且尾随“1”的几乎有效序列的数量，所以这是

f(n, m) = a(n, 1) + a(n, 2) + ... + a(n, m)

写成 C 函数:

int a[NMAX+1][MMAX+1];
int f(int n, int m)
{
    int i, j, s;

    // compute a(1, j):
    for (j = 0; j <= m; j++)
        a[1][j] = (j == 1);

    for (i = 2; i <= n; i++) {
        // compute a(i, 0):
        s = 0;
        for (j = 0; j <= m; j++)
            s += a[i-1][j];
        a[i][0] = s;

        // compute a(i, j):
        for (j = 1; j <= m; j++)
            a[i][j] = a[i-1][j-1];
    }

    // final result:
    s = 0;
    for (j = 1; j <= m; j++)
        s += a[n][j];
    return s;
}

甚至可以改进存储要求，因为只需要矩阵 a 的最后一列。运行时复杂度为 O(n*m)。