フィボナッチ数列を書いてみた。

フィボナッチ数列っていうのは
1,1,2,3,5,8,13,21
という感じに、今と一つ前の数字を足して次の数字を求める数列。

これをJSで書いてみると、

    function Fibonacci(x){
        var i = 0;
        var p = 1;
		var f0 = 0;
		var f1 = 1;
 	    for(i=0 ; i<x ; i++){
		    //document.write(p+"<br>");
    		f1 = p + f0;
    		f0 = p;
    		p = f1;
  		}
		document.write(p);
    }

コメントアウトを外すと、計算過程が見れます。

というかんじになるけど、これじゃあ手計算をPCにやらせただけで、処理が遅い。
ちなみにこれを１兆回まわすとブラウザがフリーズしましたw
１００万回まわすと、警告が出るものの処理は終了。
しかし、オーバーフローでアウトプットはinfinityにww

これをもっとスマートに書けないかなぁ。
数学といえば、公式か。

あれJSでルートってどうやってかくんだろう・・・
そういえば、やったことないw
で、調べてみました。
Math.sqrt()関数が平方根を計算してくれるみたい。

強引に公式をfunction化してみました。

	function Fibonacci(x){
		for (var i = 0; i < x;i++){
			document.write(fib(i));
			document.write(",");
		}  
	}
	
	function fib(i){
  		var output = (Math.pow((1+Math.sqrt(5))/2,i) - Math.pow((1-Math.sqrt(5))/2,i)) / Math.sqrt(5);
               return output;
	}

んーー、、、
実行するとわかるんだけど、小数が出る。

丸めてやればいいのかな

	function Fibonacci(x){
		for (var i = 0; i < x;i++){
			document.write(fib(i));
			document.write(",");
		}  
	}
	
	function fib(i){
		var output = Math.round((Math.pow((1+Math.sqrt(5))/2,i) - Math.pow((1-Math.sqrt(5))/2,i)) / Math.sqrt(5));
		return output;
	}

ぉ、思った通りの結果になった。

あれだなぁ
数学の公式って厳密なだけあって、いくら早くて賢いコンピュータでも、きちっと出せないのかぁ
となると数学が生まれたときにコンピュータも存在していれば、公式なんてものは生まれなかったのかもしれないなぁ。

たかがアルゴリズムと数学の公式だけど、感慨深い・・・

＊追記

つまり、ただ数列を並べたいときは一番上のアルゴリズムを。
x番目のフィボナッチ数列の値を知りたい時は一番下のアルゴリズムを使うと、PCに優しいね。
それにこの２つのロジックを組み合わせれば、
x番目〜x+10番目の数列なんかも取得できる。
ああ、変数のオーバーフローは仕方がないとしてw

べっっ別に、数学ガール読んでてやりたくなったわけじゃないんだからねっっっw