フィボナッチインタビュー

フィボナッチ数列の計算は、候補者が原則として少なくとも何らかの方法でアルゴリズムを実行できることを確認したいときにインタビューでしばしば与えられるため、古典的なアルゴリズムのタスクです。 あなたが同じ候補者だとします。 タスクが与えられました：JavaScriptで、n番目のフィボナッチ数を返す関数fib(n)



記述します。 ゼロのフィボナッチ数はゼロであると考えます。 引数の検証は不要です。 あなたのオプションは何ですか？

1.より簡単に、人々があなたに手を差し伸べる。

最も簡単な解決策は平凡なサイクルです。

 const fib = n => { let prev = 0, next = 1; while(n-- && (next = prev + (prev = next))); return prev; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

冗談。 もちろん、あなたはそのように書く必要はありません-もちろん、あなたがフルタイムの難読化者の地位についてインタビューされない限り。

 const fib = n => { let prev = 0, next = 1; for(let i = 0; i < n; i++){ next = prev + next; prev = next - prev; } return prev; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

変動クーポンが不足していますか？ チポク

わかりました、わかりやすくするために、これを書きましょう：

 const fib = n => { let prev = 0, next = 1; for(let i = 0; i < n; i++){ let temp = next; next = prev + next; prev = temp; } return prev; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これは、クラシックでシンプルかつエレガントなオプションです。 しかし、おそらく他の概念についての知識を実証したいですか？ たとえば...

2.再帰を理解するには、再帰を理解する必要があります

たとえば、はい、再帰を実行できることを示すことができます。 たとえば、次のように：

 const fib = n => { if(n <= 1){ return n; }else{ return fib(n - 1) + fib(n - 2); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このオプションを覚えておいてください。 これはやる価値がありません。 すべきではありません。 不可能です。 決して。 これは子犬を蹴るよりも悪く、小さなホロコーストに匹敵します。



理由を尋ねるかもしれません。 この場合、このコードを実行して、たとえば50フィボナッチ数を計算してみてください。 ある程度の遅れを感じると思います。 冗談。 このコードをスーパーコンピューター上で実行しなければ、結果を待つことはないでしょう。 前の例の単純で非再帰的なコードは、フィボナッチ数列の50番目のメンバーを、「50」という言葉やその音節を言うよりも速くカウントするという事実にもかかわらず。



O表記の大まかな言語で表現されたこのようなソリューションは、O（e ⁿ ）の時間の複雑さを持ちます。 つまり、この関数の実行時間は、nの増加とともに指数関数的に増加します。 つまり、nが増加すると、実行時間が増加します。 大まかに言えば、 fib(45)



が1時間待たなければならなかった場合、 fib(46)



は2時間、 fib(47)



-4時間というようになります。 筆者は、スクリプトを書くことに最初に手を加えたタイプセッターであっても、すべての読者が状況の恐ろしさを実感できるほど細かく考えています。

これは正しいですが、あまりにも失礼です。 関数呼び出しの数のより正確な推定値〜（1 + sqrt（5））fib（n）と、「単純な再帰メソッドを使用してフィボナッチ数を計算するには、フィボナッチ数自体の3.2倍の関数呼び出しが必要です」 タウス

そして、別の計算方法を取得します。 単純な再帰メソッドを実行し、関数呼び出しの数をカウントし、3.2で除算するだけです！ サーベルユーザー

インタビュー中にこの問題を再帰的に解決する必要がある場合、これはおそらくトラップです。 線形時間で動作する「正しい」再帰は、たとえば次のようになります。

 const fib2 = n => { if(n == 0){ return [0, 1]; }else{ const [prev, next] = fib2(n - 1); return [next, prev + next]; } } const fib = n => fib2(n)[0];
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

要約すると、フィボナッチ数は再帰の古典的な教科書の例であるという事実にもかかわらず、実際にはこれは再帰を適用するための最も便利なケースではありません。 ただし、さらに知識を誇示することもできます。

3.メモリアル機能

途方もなく効果のない解決策を最後の段落から潜在的に非常に迅速な解決策に変える魔法の方法があります（問題がないわけではありませんが）。 彼の名前はメモ化です。 そして、あなたがロシア語を話せば-再度計算するのではなく、以前の呼び出しの結果を覚えているだけです。



基本的に、そのソリューション内では何も変更することはできません- memoize



ラッパー関数を追加するだけです。 ここでは、明確にするために、引数が1つだけの関数にその簡略バージョンを使用します。

 //   ,       ,     const oldFib = n => { if(n <= 1){ return n; }else{ return oldFib(n - 1) + oldFib(n - 2); } } const memoize = f => { const cache = {}; return arg => cache[arg] || (cache[arg] = f(arg)); } const fib = memoize(oldFib);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

出来上がり！ これで、 fib



関数はクロージャを介してcache



オブジェクトにアクセスできます。 以前に検出されていない引数で呼び出された場合、計算された値はcache



保存されます。 同じ引数を使用した新しい関数呼び出しでは、値を再計算する必要はなく、単にキャッシュから取得されます。 「悪い」古いfib



関数の主な問題は、同じ値が数回再計算されることでした。 たとえば、 fib(45)



を計算するには、 f(44)



1回、2回f(43)



、3回f(42)



、5回f(41)



などを計算する必要がありました。





そのため、以前の値は一度計算され、再要求されたときにキャッシュから取得されます。 45番目のフィボナッチ数を計算できる速度がどれほど速くなるか想像できますか？ 真剣に、あなたは何時だと思いますか？



実際、少し遅いです。 私は意図的に古典的な間違いを犯しました。これは再帰関数をメモするときによく起こります。 fib(45)



「ボンネットの下」 fib(45)



呼ばれると、 oldFib(45)



が呼び出され、 oldFib(44)



とoldFib(43)



が必要に応じてoldFib(43)



れます...キャッチを感じますか？ 以下、通常の、メモされていない関数への呼び出しが既にあります。 もちろん、 fib(45)



再度呼び出すと、すぐにキャッシュから結果が得られますが、最初の呼び出しはまったくスピードアップしませんでした。 これを修正するには、まだレンチの下にあるoldFib



を取得する必要があります。

 const oldFib = n => { if(n <= 1){ return n; }else{ return fib(n - 1) + fib(n - 2); } } const memoize = f => { const cache = {}; return arg => cache[arg] || (cache[arg] = f(arg)); } const fib = memoize(oldFib);
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

いいね！ これで、 fib(45)



の最初の呼び出しは、ループのあるバージョンに匹敵する速度で動作します。 そして、さらなる課題は一般に一定の時間で機能します...おっと！ 再びだまされました。 キーを使用してオブジェクトのプロパティの値を取得するのは簡単な操作ですが、それでもO（1）は平均でしかなく、最悪の場合はO（n）に低下する可能性があります。 これを非常に良くするために、この場合、 cache



のタイプをオブジェクトから配列に変更できます。



もちろん、メモ化にはメモリが必要であることも忘れてはなりません。 また、時間の複雑さを軽減する一方で、メモリの複雑さはO（1）からO（n）に増加します。



他にどのように自慢できますか？ たとえば、数学の深い知識を示す

4.ビネット氏

繰り返しの関係を明示的な式に変換する方法については、特別な素晴らしい科学があります。 ここではその詳細には触れません。 フィボナッチ数については、かなり単純な引数を使用して、Binet式と呼ばれる次の式を導出できるとのみ言います。

$$

$$F_n = \ frac {\ left（\ frac {1 + \ sqrt5} {2} \ right）^ n-\ left（\ frac {1-\ sqrt5} {2} \ right）^ n} {\ sqrt5}$$

ただし、これは非常に数学的な言語なので、JavaScriptで記述します。

 const fib = n => { const a = (1 + 5 ** 0.5) / 2; const b = (1 - 5 ** 0.5) / 2; return (a ** n - b ** n) / 5 ** 0.5; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

最初のいくつかの数字を運転しましょう。 素晴らしい、すべてがうまくいくようです。 ここに13、ここに21、ここに34、ここに... 54.9999999999999999？



はい、もちろん、そのような結果は論理的です。 ビネットの式は数学的に正確ですが、コンピューターは有限の精度の一部で動作し、それらを操作するときにエラーが蓄積する可能性があります。 ただし、修正することはできます。 分子で減算される値は常に小さいことがわかっているため、式を次の状態に単純化できます。

$$

$$F_n = \左\ lfloor \ frac {\左（\ frac {1 + \ sqrt5} {2} \右）^ n} {\ sqrt5} \右\ rceil$$

ここで、奇妙な未完成の角括弧は、最も近い整数、つまり丸めを意味します。 コードを書き換えます：

 const fib = n => { const a = (1 + 5 ** 0.5) / 2; return Math.round(a ** n / 5 ** 0.5); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

はい、それははるかに優れています。 55と89の両方を見ることができ、お気に入りのフィボナッチ数でさえ144です（これは12の2乗に等しいので大好きです）。 数値76まではすべて正常です。これは3416454622906707に等しく、関数は3416454622906706を計算します。小数の精度が制限されているという問題は解消されていないため、それをさらに深く押し上げて、表示されないことを期待しました。 この例が示すように、彼らは無駄に望みました。



実際、他の方法でこのメソッドを保存できます。 しかし、それについては以下で詳しく説明します。 それまでの間-冗談はさておき。 過酷でハードコアで残忍な方法について話しましょう。

5.白うさぎに従ってください。

彼らは、あなたが問題を抱えていて、正規表現でそれを解決できるという考えがあなたに生じた場合、2つの問題があると言います。 逆に、行列は正規表現です。 多くの問題は、マトリックスの言語で再定式化された場合、それ自体で簡単に解決されます。



フィボナッチ数については、マトリックス言語のそれらについて、この明白なアイデンティティを書くことができます：

$$

$$\ begin {pmatrix} 0＆1 \\ 1＆1 \ end {pmatrix} \ begin {pmatrix} F_ {n-1} \\ F_n \ end {pmatrix} = \ begin {pmatrix} F_n \\ F_ {n +1} \ end {pmatrix}$$

つまり、連続するフィボナッチ数のペアを取得し、そのような単純な行列で乗算すると、次のペアが得られます。 そして、これから論理的結論が得られます：ゼロと最初のフィボナッチ数のペア、つまりゼロと1を取り、それらにこの行列をn乗すると、n番目とenのペアに最初のフィボナッチが加えられます。 つまり、人間的に言えば：

$$

$$\ begin {pmatrix} 0＆1 \\ 1＆1 \ end {pmatrix} ^ n \ begin {pmatrix} 0 \\ 1 \ end {pmatrix} = \ begin {pmatrix} F_n \\ F_ {n + 1} \ end {pmatrix}$$

ベクトルを放棄することで、これをもう少し単純化できます。 実際、必要な値はすべてマトリックス自体に含まれています。

$$

$$\ begin {pmatrix} 0＆1 \\ 1＆1 \ end {pmatrix} ^ n = \ begin {pmatrix} F_ {n-1}＆F_ {n} \\ F_ {n}＆F_ {n + 1 } \ end {pmatrix}$$

すごいですね。 彼がフィルハーモニーではない場合、お尻の調和のために何を理解するかは変わりません。 私が意味する-なぜそのような困難は突然のものなのか。 そして答えは簡単です-急速な累乗。



たとえば、2 ¹⁰を計算するために必要な基本乗算はいくつですか？ 普通の人は9と言います。 2〜4回。 2〜4回。 8倍は16です。 などなど。 ずるい人はその4つを言うでしょう。

$$

$$2 \ cdot 2 = 4 \\ 4 \ cdot 4 = 16 \\ 2 \ cdot 16 = 32 \\ 32 \ cdot 32 = 1024$$

プログラマーが言うでしょう。 彼はこの数字を暗記しているので、何も掛ける必要はありません。 ただし、上記のメモ化の問題については説明しました。



したがって、素早いべき乗法は行列にも適用でき、したがって、関数の漸近的な時間の複雑さをO（n）からO（log n）に減らすことができます。 そして、これは非常にクールです-もちろん、この複雑さが私たちにとって本当に重要でない限り。 コードを書きましょう：

 //    ,          const mul = ( [ [a1, a2], [a3, a4] ], [ [b1, b2], [b3, b4] ]) => [ [a1 * b1 + a2 * b3, a1 * b2 + a2 * b4], [a3 * b1 + a4 * b3, a3 * b2 + a4 * b4] ]; const matrix = [ [0, 1], [1, 1] ]; // ,   const id = [ [1, 0], [0, 1] ] const fib = n => { let result = id; const bits = n.toString(2); //        for(const bit of bits){ result = mul(result, result); if(bit == "1"){ result = mul(result, matrix); } } return result[1][0]; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

それで、私たちはWild Westで最速のアルゴリズムを得ました。 そして、彼は、以前のもののほとんどとは異なり、インタビューで非皮肉な方法で実証することができます。 そして、いくつかの数学的能力のある場所では、彼から期待されるでしょう。

PS

ビネット式に基づいてメソッドを保存する方法について発言することを約束しました。 答えはこの記事にあります。 そこで、国民経済のニーズのために、5つの有理数の根という特別なクラスを作成しました。これは、精度を損なうことなく、整数と5の根の算術演算の結果を格納できます。 このクラスを取得し、丸めメソッドを追加して、ビネット式を使用してフィボナッチ数を検索するために使用できます。 そして、急激な累乗を適用して亜酸化窒素を注入します。



そして、最も興味深いのは、プロセスで得られる数値、実行される演算を注意深く見ると、この方法が異なる行列の下でのみ同じ行列乗算であることが明らかになることです。 唯一の違いは、数値を2次元配列に格納するか、特別なクラスのオブジェクトのフィールドに格納するかです。



それだけです 誰も必要としない数字を見つける他の興味深い方法を見逃していると思われる場合は、コメントに必ず書いてください。

まだ高速倍増などの方法があります。 O（ログ）の行列乗算のように機能しますが、漸近（および実際）の定数は小さくなります。 要するに、2つの式がそこで使用されており、それらの式に基づいて、インデックスの半分まで再帰的にすばやくロールバックできます。



F _2n = F _n *（2 * F _{n + 1} -F _n ）

F _{2n + 1} = F _n ² + F _{n + 1} ²



ところで、実装は非常にコンパクトです。

さまざまな方法の速度の比較

just_maksim