我的一个朋友最近被问到这个问题：
您必须计算可能有多少个长度为“K”的二进制字符串。约束：每个 0 的左边都有一个 1。
问问题
3282 次
2 回答
2
这个问题可以改写：如果没有两个连续的 0，有多少个长度为 K 的二进制序列是可能的，但第一个元素应该是 1（否则约束失败）。让我们忘记第一个元素（我们可以这样做，因为它总是固定的）。然后我们得到了一个非常有名的任务，听起来像这样：“长度为 K-1 且没有连续 0 的二进制序列的数量是多少。” 可以找到解释，例如，here
那么答案将是 F(K+1)，其中 F(K) 是从 (1 1 2 ...) 开始的第 K 个斐波那契数。
于 2012-08-14T08:04:15.560 回答
0
∑ From n=0 to ⌊K/2⌋ of (K-n)Cn; n 是字符串中零的个数
这个想法是将每个 0 与 1 分组并找到字符串的组合数，对于 n 个零，将有 n 个分组到它们，因此字符串变成 (kn) 个元素长。不能有超过K / 2 个零，因为在每个零的最左边没有足够的零。
例如111111[10][10]1[10]，对于 K = 13，n = 3
于 2012-08-14T20:31:38.007 回答