0或1组合,使得我们没有立即按顺序排列两个1

Question

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

说我们有4位数的输入

1010 1000 0000 0101 0001 0010 0100 1001 

我不确定哪个algos会生成0和1的组合？

Answer 1

答案由Fibonacci序列给出.

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"开头,您可以看到与Fibonacci序列有关系的原因:

  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增加而迅速增长.如果你想得到一个确切的答案,你需要使用一个可以处理任意大整数的库.