どうも！LSSです！！
今回はまた、Try Kotlinで「フィボナッチ数列」を算出してみます！
- フィボナッチ数列とは？
- フィボナッチ数列のもうひとつの特徴『黄金比』
- Try Kotlinでコードを書いてみました
- コード解説
- 再帰呼び出しを実行したら、どんな風に計算される？
- 再帰呼び出しの怖いところ
- 「数列」を出力するためにmainの内容を書き換えます
- ついでに、『黄金比』への収束、も試してみます
フィボナッチ数列とは？
昔、フィボナッチさんという人が考えた事なんですが、「最初に0があり、次に1がある」状態
0,1
から始まり、その次に「前の数＋前の前の数を足した数」がくる、つまり「0＋1」で
0,1,1
になる。以降、ずっと「前の数＋前の前の数を足した数」を続けていく、というルールで数を続けていくと、
0,1,1,2,3,5,8,13,21,34…
という数の並びになります。
この「数の並び」が「フィボナッチ数列」と呼ばれているもので、13とか21とか、フィボナッチ数列の途中に出てくるものを「フィボナッチ数」というそうです。
この「前の数＋前の前の数を足した数」というルール自体に特に深い意味はなさそうですが、不思議とこの「フィボナッチ数列」「フィボナッチ数」が、「自然界の様々なところに現れている」んだそうです。
※コメントで教えていただいたのですが、実はこのルール、深い意味があるようです。まだLSSは理解していませんが^^; Φ様ありがとうございます^^
フィボナッチ数列のもうひとつの特徴『黄金比』
「なぜか自然界によく現れる」という以外にもうひとつの特徴があります。
人間が「美しい」と感じる比率『黄金比』というものがあって、
1 : 1.6180339887（以下略）
という比率が『黄金比』と言われているそうです。
が、フィボナッチ数列をずーーーっと続けていくと、
「あるフィボナッチ数をその１つ前のフィボナッチ数で割った値が、数列が進むごとに『黄金比』に近づいていく」んだそうです。
ちょっと試しに『黄金比』に近い比率の長方形を描いてみますね。
↑美しい比率…らしいｗ
Try Kotlinでコードを書いてみました
↑こんな感じですね。
コードとしては、
fun fibo(a:Int):Int{
if (a<2){
return a
}else{
return fibo(a-1)+fibo(a-2)
}
}
fun main(args: Array<String>) {
println(fibo(6))
}
こんな感じです。
コード解説
フィボナッチ数を返す関数「fibo()」を定義しました。
fun fibo(a:Int):Int{
if (a<2){
return a
}else{
return fibo(a-1)+fibo(a-2)
}
}
↑この部分ですね。
一行目の
fun fibo(a:Int):Int
は、
「fibo関数自体はInt型（整数型）の値を返す関数で、引数としてInt型（整数型）の値を受け取り、引数をaという変数として扱います！」
という事を表現しています。
そのfibo関数の中で、
if (a<2){
return a
}
「引数が2よりも小さかった場合（0とか1とか）はreturn aで引数をそのままfibo関数の値として返す」という事を書いています。
fibo(0)=0
fibo(1)=1
という結果になる、という事ですね。
「引数が2以上だった場合（2とか3とか4とか5とか…）」はelse{}の内容が実行されます。
return fibo(a-1)+fibo(a-2)
↑この部分。
「fibo関数の値を計算する中にfibo関数を参照している部分が入っている」
こういうのを「再帰呼び出し」って言います。
再帰呼び出しを実行したら、どんな風に計算される？
fun fibo(a:Int):Int{
if (a<2){
return a
}else{
return fibo(a-1)+fibo(a-2)
}
}
↑この関数に対して、例えば
fibo(2)
を問い合わせたとします。
まず、2という引数が変数aに代入され、
if (a<2)
の判定には当てはまらないため、elseの方が実行されます。
return fibo(a-1)+fibo(a-2)
returnは、「fibo(2)の値は、fibo(a-1)+fibo(a-2)ですよ」と返そうとするんですね。
ところがその中にfibo(a-1)とかfibo(a-2)とかが入っているので、まずそれを計算しなくてはいけません。
a=2なので、
fibo(1)+fibo(0)
という事になります。
そこでfibo(2)関数はfibo(1)関数とfibo(0)関数を呼び出すわけです。
fibo(1)を問い合わせると、今度はaを1として判定します。
※この場合、aはさっきの「2が代入されたa」とは別物扱いとされます。
今度は
if (a<2)
の判定に合格するので
return a
が実行されて、
fibo(1)=1
という結果が返ります。
同様に、fibo(0)のほうも
fibo(0)=0
という結果が返るので、
fibo(2)の問い合わせだった、
return fibo(a-1)+fibo(a-2)
は「1+0」の1が返り、
fibo(2)=1
という結果になります。
再帰呼び出しの怖いところ
fibo(2)を一回実行するだけで、fibo(1)とfibo(0)を別途呼び出して実行しているわけです。
ではこれがfibo(3)になると、
fibo(2)（→fibo(1) fibo(0)） fibo(1)
と、余計に４回繰り返す事になり（計５回）、引数がちょっと増えるだけで呼び出す回数はとんでもない事になっていきます^^;;;
で、Try Kotlin、どうやら「計算に10秒以上かかったら停止」という安全措置が働いているようで、
fibo(45)
ぐらいが限界でしたｗ（ちなみにfibo(45)=1134903170でした）
「数列」を出力するためにmainの内容を書き換えます
fun fibo(a:Int):Int{
if (a<2){
return a
}else{
return fibo(a-1)+fibo(a-2)
}
}
fun main(args: Array<String>) {
var t=""
for (i in 0..30){
t+=fibo(i).toString()+","
}
println(t)
}
↑こんな風に赤文字部分を書き換えました！
フィボナッチ数を順にカンマ区切りで並べた文字列を作り、最後に出力する、という内容です。
結果は、
0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,
↑こういう文字列が出力されました。
無事、フィボナッチ数列を出力するプログラムが書けましたね^^
ついでに、『黄金比』への収束、も試してみます
fun fibo(a:Int):Int{
if (a<2){
return a
}else{
return fibo(a-1)+fibo(a-2)
}
}
fun main(args: Array<String>) {
var t=""
var g=""
for (i in 0..20){
t+=fibo(i).toString()+","
g+=(fibo(i+1).toFloat()/fibo(i)).toString()+" "
}
println(t)
println(g)
}
↑さらに赤文字部分を書きくわえました！
結果は…
↑こんな感じ。
比率を計算している部分を抜粋すると、
Infinity 1.0 2.0 1.5 1.6666666 1.6 1.625 1.6153846 1.6190476 1.617647 1.6181818 1.6179775 1.6180556 1.6180258 1.6180371 1.6180328 1.6180345 1.6180338 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034 1.618034
↑こうなります。
『黄金比』に近づいていきながらも、どうやら先にKotlinのFloat型の桁数制約に引っかかっているようですねｗ
※もっと多くの桁数を扱えるDouble型というのもありますが、今回はそこまでやらなくてもいいかな^^;
あと、最初が「Infinity」になっているのは「0で割る割り算」をしようとしているからです。
…という事で、今回は「フィボナッチ数列」を出力してみました。
「再帰呼び出し」をやってみるには手ごろな題材であると同時に、実はWikiにも書かれていますが、
「フィボナッチ数列を再帰呼び出しで計算するのは効率が悪い」
という事をも、身をもって体験しましたｗｗｗ
てなとこで、今回はこのへんで！
次回もまた、よろしくお願いします^^
