78

フィボナッチ数は、コンピュータサイエンスの学生に人気のある再帰の紹介になり、自然の中で存続するという強い議論があります。これらの理由から、私たちの多くはそれらに精通しています。

それらは他の場所のコンピュータサイエンスにも存在します。シーケンスに基づく驚くほど効率的なデータ構造とアルゴリズム。

頭に浮かぶ主な例は2つあります。

他の数値シーケンスよりも有利なこれらの数値の特別な特性はありますか？それは空間的な品質ですか？他にどのようなアプリケーションが考えられますか？

他の再帰的な問題で発生する自然数シーケンスがたくさんあるので、私には奇妙に思えますが、カタロニア語のヒープを見たことがありません。

4

9 に答える 9

69

フィボナッチ数には、コンピューターサイエンスで優れたものにする、あらゆる種類の非常に優れた数学的特性があります。ここにいくつかあります：

  1. それらは指数関数的に速く成長します。 フィボナッチ数列が登場する興味深いデータ構造の1つは、自己平衡二分木の形式であるAVLツリーです。このツリーの背後にある直感は、各ノードがバランス係数を維持しているため、左右のサブツリーの高さが最大で1つ異なるということです。このため、高さhのAVLツリーを取得するために必要なノードの最小数は、N（h + 2）〜= N（h）+ N（h + 1）のような漸化式によって定義されると考えることができます。これはフィボナッチ数列によく似ています。数学を解くと、高さhのAVLツリーを取得するために必要なノードの数がF（h + 2）-1であることを示すことができます。Fibonacciシリーズは指数関数的に速く成長するため、これはAVLの高さを意味します。ツリーはノード数で最大で対数であり、バランスの取れたバイナリツリーについて私たちが知っていて大好きなO（lg n）ルックアップ時間を提供します。実際には、ある構造のサイズをフィボナッチ数で制限できる場合、ある操作でO（lg n）ランタイムを取得する可能性があります。これが、フィボナッチヒープがフィボナッチヒープと呼ばれる本当の理由です。デキュー分後のヒープの数が、特定の深さで持つことができるノードの数をフィボナッチ数で制限することを含むという証拠です。
  2. 任意の数は、一意のフィボナッチ数の合計として書き込むことができます。 フィボナッチ数のこの特性は、フィボナッチ検索を機能させるために重要です。一意のフィボナッチ数を可能な数に合計できない場合、この検索は機能しません。これを、 3nやカタラン数などの他の多くのシリーズと比較してください。これは、2の累乗のような多くのアルゴリズムが理由の一部でもあると思います。
  3. フィボナッチ数は効率的に計算できます。 級数を非常に効率的に生成できるという事実（O（n）の最初のn項、またはO（lg n）の任意の項を取得できます）では、それらを使用する多くのアルゴリズムは実用的ではありません。カタラン数の生成は、計算がかなり難しい、IIRCです。これに加えて、フィボナッチ数には優れた特性があります。たとえば、F（k）とF（k + 1）の2つの連続するフィボナッチ数が与えられると、2つの値を加算することで次または前のフィボナッチ数を簡単に計算できます。 （F（k）+ F（k + 1）= F（k + 2））またはそれらを引く（F（k + 1）-F（k）= F（k-1））。このプロパティは、プロパティ（2）と組み合わせていくつかのアルゴリズムで利用され、数値をフィボナッチ数の合計に分解します。たとえば、フィボナッチ検索ではこれを使用してメモリ内の値を検索します。
  4. それらは教育的に有用です。 再帰を教えるのは難しいので、フィボナッチ数列はそれを紹介するのに最適な方法です。シリーズを紹介するときに、ストレート再帰、メモ化、または動的計画法について話すことができます。さらに、フィボナッチ数の驚くべき閉形式は、誘導または無限系列の分析の演習として教えられることが多く、フィボナッチ数の関連する行列方程式は、固有ベクトルと固有値の背後にある動機として線形代数に一般的に導入されます。これが、入門クラスで注目を集めている理由のひとつだと思います。

これだけではない理由があると思いますが、これらの理由のいくつかが主な要因であると確信しています。お役に立てれば！

于 2010-12-31T18:46:32.743 に答える
4

最大公約数は別の魔法です。あまりにも多くの魔法についてはこれを参照してください。しかし、フィボナッチ数は簡単に計算できます。また、特定の名前があります。たとえば、自然数1、2、3、4、5には論理が多すぎます。すべての素数はそれらの中にあります。1..nの合計は計算可能であり、それぞれが他のものと一緒に生成できます...しかし、誰もそれらを気にしません:)

私が忘れていた重要なことの1つは、黄金比です。これは、実際の生活に非常に重要な影響を及ぼします（たとえば、ワイドモニターが好きです:)

于 2010-12-31T18:48:43.510 に答える
1

CSと自然の理解しやすい例を使って、シンプルで簡潔な方法でうまく説明できるアルゴリズムがある場合、誰かが思いつくことができるより良い教育ツールは何でしょうか。

于 2011-01-01T04:32:51.693 に答える
1

フィボナッチ数列は、実際、自然/生命のいたるところに見られます。これらは、動物集団の成長、植物細胞の成長、スノーフレークの形状、植物の形状、暗号化、そしてもちろんコンピューターサイエンスのモデリングに役立ちます。自然のDNAパターンと呼ばれていると聞きました。

フィボナッチヒープはすでに言及されています。ヒープ内の各ノードの子の数は最大でlog（n）です。また、m個の子を持つノードを開始するサブツリーは、少なくとも（m + 2）番目のフィボナッチ数です。

ノードとスーパーノードのシステムを使用するトレントのようなプロトコルは、フィボナッチを使用して、新しいスーパーノードが必要になる時期と、それが管理するサブノードの数を決定します。フィボナッチスパイラル（黄金比）に基づいてノード管理を行います。下の写真を参照してください。ノードがどのように分割/マージされますか（1つの大きな正方形から小さな正方形に、またはその逆に分割されます）。写真を参照してください：http ：//smartpei.typepad.com/.a/6a00d83451db7969e20115704556bd970b-pi

自然界のいくつかの出来事

http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/sneezewort.GIF

http://img.blogster.com/view/anacoana/post-uploads/finger.gif

http://jwilson.coe.uga.edu/EMAT6680/Simmons/6690Pictures/pinecone3yellow.gif

http://2.bp.blogspot.com/-X5II-IhjXuU/TVbHrpmRnLI/AAAAAAAAABU/nv73Y9Ylkkw/s320/amazing_fun_featured_2561778790105101600S600x600Q85_200907231856306879.jpg

于 2011-12-16T15:59:43.750 に答える
0

明確な答えはないと思いますが、1つの可能性は、セットSを2つのパーティションS1とS2に分割し、そのうちの1つをサブパーティションS11とS12に分割する操作です。 S2-多くのアルゴリズムへのアプローチである可能性が高く、フィボナッチ数列として数値的に記述できる場合があります。

于 2010-12-31T18:40:24.923 に答える
0

別のデータ構造を追加しましょう：フィボナッチの木。ツリー内の次の位置の計算は、前のノードを追加するだけで実行できるため、これらは興味深いものです。

http://xw2k.nist.gov/dads/html/fibonacciTree.html

これは、AVLツリーに関するtemplatetypedefによる議論と密接に関連しています（AVLツリーは最悪の場合フィボナッチ構造を持つ可能性があります）。また、バッファが2の累乗ではなく、フィボナッチステップで拡張されている場合もあります。

于 2010-12-31T19:38:19.603 に答える
0

これについての雑学を追加するために、フィボナッチ数はウサギのパン粉を表します。（1、1）、2匹のウサギから始めて、その後、それらの個体数は指数関数的に増加します。

于 2012-02-14T10:45:09.987 に答える
0

[[0,1]、[1,1]]行列の累乗としてのそれらの計算は、オペレーションズリサーチの最も原始的な問題と見なすことができます（囚人のジレンマのようなものはゲーム理論の最も原始的な問題です）。

于 2016-07-18T20:20:41.907 に答える
0

連続するフィボナッチ数である周波数のシンボルは、最大深度のハフマンツリーを作成します。このツリーは、最大長のバイナリコードでエンコードされているソースシンボルに対応します。非フィボナッチソースシンボル周波数は、より短いコードで、よりバランスの取れたツリーを作成します。コードの長さは、特定のハフマンコードのデコードを担当する有限状態マシンの記述の複雑さに直接影響します。

推測：1番目（fib）の画像は38ビットに圧縮され、2番目（均一）は50ビットに圧縮されます。ソースシンボルの周波数がフィボナッチ数に近いほど、最終的なバイナリシーケンスが短くなるほど、圧縮率が高くなり、ハフマンモデルで最適になる可能性があります。

huffman.ooz.ie/?text=ABBCCCDDDDDEEEEEEEE

ここに画像の説明を入力してください

参考文献：

ブロ、M。（1993）。ハフマンコードの最大長について。情報処理レター、45（5）、219-223。doi：10.1016 / 0020-0190（93）90207-p

于 2019-02-10T14:50:19.113 に答える