|
|
概要
フィボナッチ数列と言ったら
生き物の増殖で有名なやつ。
最初に１匹
↓
１匹の親から１匹の子が生まれて計２匹
↓
１匹の親から１匹の子が生まれ、前に生まれた１匹の子が親になって親２匹、子１匹の計３匹
↓
２匹の親から２匹の子が生まれ、前に生まれた１匹の子が親になって親３匹、子２匹の計５匹
↓
まあなんかいろいろあって８匹
↓
まあなんかいろいろあって１３匹・・・
と、どんどん続いていく増え方。
ある世代をnとした時、n-1世代とn世代の個数を足したものがn+1世代の個数となる数列。
増え方に神秘っぽいのを感じるさ。
プログラムはJavaScriptで書いてます。
有効にしていないと実行結果は見れないです。
JavaScriptはHTMLにプログラムソースを直接書き込むだけでＯＫなんで楽。
ちょっとしたプログラムを書きたいって思った時は便利だということに気づいた。
普段は無効にしてるけど。
|
フィボナッチ数
フィボナッチ数列上の第n番目の数を求めるプログラム。
再帰を用いて繰り返し処理を行わせるんで、nが大きすぎると
メモリがやばいことになります。
俺のパソコンではn=40くらいで警告が出た。
JavaScriptは危険です。
プログラムソース：
<SCRIPT LANGUAGE="JavaScript" TYPE="text/javascript">
<!--
var n = 10;
function Fibonacci(n){
if(n == 1 || n == 2){
return 1;
}else{
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
}
document.write(Fibonacci(n));
//-->
</SCRIPT>
実行結果：n = 10
last update 2006/04/29
|
数列表示
フィボナッチ数だけを求めてもつまらない。
やっぱり増えていく様子っていうのが見たいということで、
フィボナッチ数列を表示するプログラムを作った。
フィボナッチ数を再帰的に求めるプログラムでは
数列を表示するのは難しいと思ったんで再帰を用いないプログラムに
書き換えた。
f0とf1に交互に数列が入っていきます。n=40でも警告は出ませんでした。
プログラムソース：
<SCRIPT LANGUAGE="JavaScript" TYPE="text/javascript">
<!--
var n = 40;
var f0 = 1;
var f1 = 0;
for(i = 0; i < n; i++){
if(i % 2 == 0){
f0 = f0 + f1;
document.write(f0,"<BR>");
}else{
f1=f0+f1;
document.write(f1,"<BR>");
}
}
//-->
</SCRIPT>
実行結果：n = 40
last update 2006/04/29
|
数列可視化
フィボナッチ数列がいいなぁって感じるのは、やっぱり増えていく様子を見たとき。
親が子を生んで、子は親になって、子はさらに親を生む。
これを系統図的に示したいけどJavaScriptとHTMLじゃちょっと難しいと思った。
なんで簡単にして棒の長さで示したのが以下のプログラムです。
降順に世代が、棒の長さが個体数です。良いカーブです。
プログラムソース：
<SCRIPT LANGUAGE="JavaScript" TYPE="text/javascript">
<!--
var n = 14;
var f0 = 1;
var f1 = 0;
for(i = 0; i < n; i++){
if(i % 2 == 0){
f0 = f0 + f1;
document.write("<HR WIDTH="+f0+">");
}else{
f1 = f0 + f1;
document.write("<HR WIDTH="+f1+">");
}
}
//-->
</SCRIPT>
実行結果：n = 14
last update 2006/04/29
|
一般項
フィボナッチ数の一般項は以下の式で与えられる。
F(n) = {(1 + √5)n/ 2 - (1 - √5)n/ 2} / √5
黄金比が絡んできていい感じ。けど乗数が入ってるんで計算量がすごいことになるんだろうな。
プログラムは小数の計算が絡んできて誤差が出るんで四捨五入しています。
プログラムソース：
<SCRIPT LANGUAGE="JavaScript" TYPE="text/javascript">
<!--
var n = 40;
function Fibonacci(n){
root = Math.sqrt(5);
fn = (Math.pow((1 + root) * 0.5, n)
- Math.pow((1 - root) * 0.5, n)) / root;
return Math.round(fn);
}
document.write(Fibonacci(n))
//-->
</SCRIPT>
実行結果：n = 40
last update 2006/05/28
|
戻る
|