The Fibonacci Sequence

バージョン 2.2.0.0 (1.03 MB) 作成者: John D'Errico
Efficient computation of Fibonacci and Lucas numbers
ダウンロード: 1.2K
更新 2017/2/5

ライセンスの表示

Often I see students asking for help on a tool to compute the Fibonacci numbers. Or, I'll find them asking for help on a Project Euler problem. Or, a student has been assigned the problem of computing the fibonacci numbers using a recursive implementation. After all, these numbers lend themselves splendidly to teaching a student to use recursion.
The problem is that a direct, simple, recursive scheme is a poor one for the Fibonacci numbers, unless the recursion is written very carefully.
This tool teaches you how to compute the Fibonacci numbers in a variety of ways, good, bad, ugly. I teach the concept of memoization, a vitally important tool for many recursive schemes, not only for Fibonacci numbers. (If you do teach a student recursion, use it as an excuse to also teach them about memoization!)
Of course, I also employ some additional tricks to compute the n'th Fibonacci number without needing to compute every lower order number in the sequence. Some useful identities are introduced to achieve that task.
Since these numbers get very large, very rapidly, I return them in my VPI class, but don't be mistaken, these tools are indeed efficient. For example, to compute both the 1000'th Fibonacci and Lucas numbers, the time required was only 0.013 seconds.
>> tic,[F,L] = fibonacci(1000);toc
Elapsed time is 0.013347 seconds.

These are big numbers, each having over 200 decimal digits.

>> F
F =
43466557686937456435688527675040625802564660517371780402481729089536
555417949051890403879840079255169295922593080322634775209689623239873322
471161642996440906533187938298969649928516003704476137795166849228875
>> L
L =
97194177735908175207981982079326473737797879155345685082728081084772
518818444815269080619149045968297679578305403209347401163036907660573971
740862463751801641201490284097309096322681531675707666695323797578127

引用

John D'Errico (2024). The Fibonacci Sequence (https://www.mathworks.com/matlabcentral/fileexchange/34766-the-fibonacci-sequence), MATLAB Central File Exchange. 取得済み .

MATLAB リリースの互換性
作成: R2011a
すべてのリリースと互換性あり
プラットフォームの互換性
Windows macOS Linux
カテゴリ
Help Center および MATLAB AnswersLogical についてさらに検索
謝辞

ヒントを与えたファイル: image segmentation

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

FibonacciSequence/html/

バージョン 公開済み リリース ノート
2.2.0.0

Final version.

2.1.0.0

Uploaded the wrong version as version 2.0. 2.1 is correct

1.1.0.0

Allows efficient computation of the modulus of large Fibonacci/Lucas numbers.

1.0.0.0

Repaired a bug in computing the mods of Fibonacci & Lucas numbers