Математическое уравнение для числа действительных последовательностей (не имеющих двух 1 вместе) из N-битного числа

Question

Я столкнулся с этой загадкой интервью и хочу знать ее точный ответ.

Вы можете сгенерировать 2 ^ n другой двоичной последовательности из n-битного числа. Среди этих последовательностей последовательность, имеющая две единицы вместе, будет считаться недействительной, в противном случае она действительна.

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-битное число.

Answer 1

Обновление

Оказывается,

Ответ (n бит) = Фибоначчи (n + 2), если Фибоначчи (0) = 0, и Фибоначчи (1) = 1

---

Анализ * * +1010 1 бит 0 1 2 бита 00 01 -- 10 11 // x Теперь вы видите, что если последовательность заканчивается на 1, к ней можно добавить только 0. 3 бита 000 001 -- 010 011 // x -- 100 101 В общем, сколько 0 и сколько 1 в [n] битах f[1](0) = 1 = fibonacci(2) = fibonacci(1+1) f[1](1) = 1 = fibonacci(1) = fibonacci(1) f[n](0) = f[n-1](0) + f[n-1](1) = fibonacci(n+1) f[n](1) = f[n-1](0) = fibonacci(n) f[n] = f[n](0)+f[n](1) = fibonacci(n+1) + fibonacci(n) = fibonacci(n+2) fibonacci(0) = 0 fibonacci(1) = 1 fibonacci(2) = 1