番号kより小さいフィボナッチ数の数。 Sub O（n）

Question

インタビュー質問：与えられた数kよりも少ない数のフィボナッチ数が存在しますか？フィボナッチ数の数をkより少なくするために、kの関数を見つけることができますか？

例：N = 6

回答：6十分

イージー（5、0、1、1、2、3）のように、ループを記述またはフィボナッチの再帰的定義を使用します。しかし、それはあまりにも簡単に聞こえます...クローズドフォーム定義を使ってこれを行う方法はありますか？ （https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression）

Answer 1

ここには、O（1）である閉じた形式のPythonソリューションがあります。それは（あなたがにリンクされているウィキペディアの記事から）ビネーの式を使用しています。

>>> 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番目のフィボナッチ数は、の数字がよりも小さい場合は、遅れを導入する必要があります。ような何か：

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

今smallerFibs(13)は、これはまだ、もちろんO(1)でまだ6が、その後smallerFibs(14) = 7.です。

Answer 2

少なくとも、この数値の増加はかなり簡単だと思います。 Binet/De-Moivre formula、

Fで _N =（φ ^Nからψ ^N）以来/ 5

| ψ | 1 < φ <、次いで

F _N ∼ φ ^N/5。このことから

はXより小さいフィボナッチ数の数は、ログ _φ（5X）ように成長することになります。