フィボナッチ数をjavascriptで算出してみた。
はじめに
急にフィボナッチ数を解きたい!と思った。ということで、書いてみた。
オリジナル:フィボナッチ数(JavasScript)
- 5分で考えた、書いたコード
function fibonacci(p, n, max_num){ if(n > max_num){ return 0; } console.log(n); return fibonacci(n, n + p, max_num); } fibonacci(0, 1, 100)
本当にパッと思いついたもので、フィボナッチ数列の定義(アルゴリズム上での公式)を無視している。 このmax_numというのは、max_numまでの数値を算出するというモノ。普通は何番目のが欲しいか、ってのが引数になるよね。
引数の 0, 1 がきもいので、ちょっと変えた。
function fibonacci(max_num, p, n) { if(p === undefined) { p = 0;} if(n === undefined) { n = 1;} if(n > max_num) { return 0; } console.log(n); return fibonacci(max_num, n, n + p) } fibonacci(100)
デフォルト値を入力する感じ、ifが多くてパフォーマンスが落ちるかな。(この程度は気にしないレベルだと思うけど)
定義?を知った上で書きなおしてみる。
function fibonacci(n) { if(n < 2) { return 0; } else { return fibonacci(n-1) + fibonacci(n-2); } }
これが現実的な解答であるんだが、パフォーマンスがすごく悪いよね。俺のほうが早くてびっくりした。(厳密には違う解法だけど!!!)
メモ化を使ってみる
メモ化とは、一度計算した数値を配列に保存しておくことで、すぐに呼び出せるよね!ってやつ。
for で済ませるパターン
var _fibs = [0, 1]; function fib(n) { for(var i = _fibs.length; i <= n; i++){ _fibs[i] = _fibs[i-1] + _fibs[i-2]; } } function fibs(n) { fib(n); return _fibs.slice(0, n + 1); } fibs(10)
これでオッケーかな。グローバル変数を使うのは嫌なんだが...しょうがないかな。
次の記事には、「メモ化」で「再帰呼び出し」パターンのがある。
さいごに
今まで避けてきた再帰呼び出しを実際にやってみた。
意外と簡単にロジックが組め、すぐにコードで表現できるようになった。今回は少し、デフォルト値とか工夫してみた。こういうのも勉強になった。
フィボナッチ数列のような、数学が好きなので、次回もこういうやつをやってみたい。それと、Rubyで書きなおす。
頑張るぞぉ
404 Blog Not Found:アルゴリズム百選 - フィボナッチ数列にO()を学ぶ
波紋と螺旋とフィボナッチ: 数理の眼鏡でみえてくる生命の形の神秘
- 作者: 近藤滋
- 出版社/メーカー: 学研メディカル秀潤社
- 発売日: 2013/09/13
- メディア: 単行本
- この商品を含むブログ (5件) を見る
- 作者: サイモンシン,青木薫
- 出版社/メーカー: 新潮社
- 発売日: 2006/05/30
- メディア: 文庫
- 購入: 105人 クリック: 1,697回
- この商品を含むブログ (585件) を見る