Home > Archives > 2007-04-15

2007-04-15

フィボナッチ数列

2007-04-15 (日)
ActionScript3.0 | Flash

お腹減ったなぁ。

どうも　JC の方です。

ActionScript を色々と調べていてこんなのを見つけました。

フィボナッチ数列を求める関数

function fib(i:Number):Number{
	if (i<2) {
		return 1;
	} else {
		return fib(i-2) + fib(i-1);
	}
}

何か面白そうだったのでループで回してみた。
・・・・・・・・・
・・・・・・
・・・
PC が止まった。１０回目くらいまではトレースされたがそれ以降はCPUフル稼働。

そこで考えてみた。
どうやったら早くできるか。
遅い原因は恐らく再起処理(？)を行っているからだと思う。
じゃあ早くするには？
再起じゃなく求めればいい！
って事でできたのがコレ。

var log:Array = new Array();
function fib(i:Number):Number {
	if (i<3) {
		log[i] = 1;
		return 1;
	} else {
		var l:Number = log[i - 1] + log[i - 2];
		log[i] = l;
		return l;
	}
}
var time1 = getTimer();
for (var n:Number = 1; n < 74; n++) trace(n + " : " +fib(n));
trace(getTimer() - time1);

７３項までを 5ms で終了。

ActionScript 3.0 に至っては1ms で終了。
早い。

log として配列に計算した数字を入れて、それから計算すれば
すぐに答えがでる。
log に無い項は後から計算してもすぐ終わるし、
特に再起処理を使って処理を行う必要も無い気がする。

コレを何かに使えないかなぁ？