0

我的要求是代码找到两位数字组合的数量只有 0 和 1 对于 X 数字大小可能从 1 .. 1000 变化，这样没有时间两个 1 可以立即按顺序排列，但 0 是可能的

说我们有4位数字的输入

1010 1000 0000 0101 0001 0010 0100 1001

我不确定哪个算法可以生成这样的 0 和 1 组合？

4

3 回答 3

7

答案由斐波那契数列给出。

f(n) = f(n-1) + f(n-2)

以下是前几个结果：

length     number of combinations
1          2   (0, 1)
2          3   (00, 01, 10)
3          5   (000, 001, 010, 100, 101)
4          8   (0000, 0001, 0010, 0100, 0101, 1000, 1001, 1010)

如果您分别考虑以“0”或“10”开头的字符串，您可以看到为什么与斐波那契数列有关系：

  number of sequences of n digits
= number of sequences starting with 0, followed by n-1 more digits
+ number of sequences starting with 10, followed by n-2 more digits

不允许以“11”开头的序列。

如果使用适当的技术，斐波那契数可以非常快速地计算出来，但您应该知道答案会随着增加而迅速maxlen增长。如果你想得到一个准确的答案，你需要使用一个可以处理任意大整数的库。

于 2012-04-27T06:02:20.567 回答
1

10一个想法是通过使用单词和0（和1，但仅在最后）来构建完整的字符串。

build(sofar, maxlen):
  if len(sofar) > maxlen: return
  if len(sofar) == maxlen: found(sofar); return
  if len(sofar) == maxlen - 1: build(sofar + "1", maxlen)
  build(sofar + "10", maxlen)
  build(sofar + "0", maxlen)

该算法仅生成有效序列的证明留给您。与该算法生成所有有效序列的证明相同。

于 2012-04-27T06:06:34.980 回答
0

如果有一个函数将这些值生成到数组中，另一个函数只检查数组中某个值的当前索引是否为“1”并检查下一个值是否为“1”？如果为真，则丢弃；否则，有效。

于 2012-04-27T06:06:02.097 回答