Число чисел Фибоначчи, меньшее числа k. Sub O (n)

Вопрос с интервью: Сколько чисел Фибоначчи существует меньше заданного числа k? Можете ли вы найти функцию в терминах k, чтобы число фибоначчи было меньше k?Число чисел Фибоначчи, меньшее числа k. Sub O (n)

Пример: п = 6

Ответ: 6, как (0, 1, 1, 2, 3, 5)

достаточно просто, написать цикл или использовать рекурсивное определение Фибоначчи. Однако это звучит слишком просто ... есть ли способ сделать это, используя определение закрытой формы? (https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression)

источник

2016-04-13 Pinhead

Зачем кому-то нужно это знать? Это просто головоломка или домашнее задание? «Sub O (n)» означает, что вы ищете O (log (n)) или O (1) или не заботитесь? –

Не могли бы вы принять верхнюю или нижнюю границу ответа, потому что это может быть очень легко. –

Это вопрос интервью. Позвольте мне добавить это как редактирование.Вот почему я думаю, что это слишком легко сделать O (n) – Pinhead

Здесь представлено решение Python с близкой формой, которое является O (1). Он использует формулу Бине (из статьи Википедии, что вы связаны с):

>>> from math import sqrt,log 
>>> def numFibs(n): return int(log(sqrt(5)*n)/log((1+sqrt(5))/2)) 

>>> numFibs(10) 
6

который отслеживает с 1,1,2,3,5,8

Дело в том, что второе слагаемое в формуле Бине пренебрежимо мала, и достаточно легко инвертировать результат пренебрежения им.

Вышеупомянутая формула подсчитывает количество чисел Фибоначчи, которые меньше или равныn. Он прыгает на 1 с каждым новым числом Фибоначчи. Так, например, numFibs(12) = 6 и numFibs(13) = 7. 13 - 7-й номер Фибоначчи, поэтому, если вы хотите, чтобы число чисел Фибобаччи было строго меньше, чем n, вам нужно ввести задержку. Что-то вроде:

def smallerFibs(n): 
    if n <= 1: 
     return 0 
    else: 
     return min(numFibs(n-1),numFibs(n))

Теперь smallerFibs(13) еще 6, но затем smallerFibs(14) = 7. Это, конечно, еще O(1).

источник

2016-04-13 15:34:28

Это отличное объяснение! Благодаря! – Pinhead

Я думаю, что довольно легко увидеть рост этого числа, по крайней мере. К Binet/De-Moivre formula,

е _п = (φ ^п - ψ ^п)/5

С | ψ | φ, а затем

е _п^{∼ φ п}/5.

Из этого следует, что количество чисел Фибоначчи меньше х растет как журнал _φ (5x).

источник

2016-04-13 15:24:51

Вам нужно квадратный корень –

Число чисел Фибоначчи, меньшее числа k. Sub O (n)

ответ

Смежные вопросы