1

我遇到了这个面试难题，想知道它的准确答案。

您可以生成 2^n 个不同的 n 位数二进制序列。在这些序列中，具有两个 1 的序列将被视为无效，否则将视为有效。

For example for N=3 sequences can be:
000 -> v 
001 -> v
010 -> v
011 -> iv
100 -> v
101 -> v
110 -> iv
111 -> iv       So output should be: 5

因此，制定策略（提供给我的提示：f(n) 以 f(n-1) 表示），它可以告诉 N 位数可以具有的有效序列的数量。

4

1 回答 1

2

更新

原来是

答案(n 位) = fibonacci(n+2)，如果 fibonacci(0) = 0，且 fibonacci(1) = 1

分析

1 位

0
1

2位

00
01
--
10
11 // x

现在你看，如果一个序列以 1 结尾，它只能再追加 0。

3位

000
001
--
010
011 // x
--
100
101

一般来说，[n] 位中有多少个 0 和多少个 1

f[1](0) = 1 = 斐波那契(2) = 斐波那契(1+1)
f[1](1) = 1 = 斐波那契(1) = 斐波那契(1)
f[n](0) = f[n-1](0) + f[n-1](1) = 斐波那契(n+1)
f[n](1) = f[n-1](0) = 斐波那契(n)
f[n] = f[n](0)+f[n](1) = 斐波那契(n+1) + 斐波那契(n) = 斐波那契(n+2)

斐波那契(0) = 0
斐波那契(1) = 1
斐波那契(2) = 1
于 2011-06-23T07:15:35.693 回答