create every day - 福野泰介の一日一創

IchigoJamで計算するフィボナッチ数列!IchigoJamとスタックで分かる再帰の本質

2017/07/05 23:55:00
#IchigoJam #KidsIT 

1,2,3,4,5とか、1,2,4,8,16とか、100,81,64,49とか、数が並んだものを数列といいます。
数列がどういう法則で続いているかクイズとか作って、出し合うのもおもしろいですね。

では、この数列の後ろに来る数は何でしょう?
0,1,1,2,3,5,8,13,21,?

0,1から始まり、数列の後ろ2つを足した数で続ける数列をフィボナッチ数列と呼びます。 ヒマワリの種など、自然界によく登場する不思議なこの数列、1202年のイタリアのフィボナッチさんの本で紹介されました。


web上の有名な辞書、ウィキペディア日本語版の表紙として2007年から2012年、使われていたそうです。(*フィボナッチ数 - Wikipedia

不思議な数列、フィボナッチは高専生にも大人気。2014年の高専インターンでは3Dプリンターで目がフィボナッチ数のサイコロ「フィボッコロ」も誕生!

IchigoJamで計算してみましょう。

10 A=0:?0,A 20 B=1:?1,B 30 FOR I=2 TO 18 40 C=A+B:?I,C 50 A=B:B=C 60 NEXT

変数AとBを使って、ふたつ後ろの数を順番に足していきます。

フィボナッチ数列 on IchigoJam web

1行で書くとこんな感じ(*IchigoJam web)

A=0:B=1:FOR I=2 TO 18:C=A+B:?I,C:A=B:B=C:NEXT

N番目のフィボナッチ数をF(N)は、N-1番目のフィボナッチ数F(N-1)とN-2番目のフォボナッチ数F(N-2)を足したものなので、これを再帰(さいき)というプログラムの手法を使って作ることもできます。

var fib = function(n) { if (n < 2) return n; return fib(n - 1) + fib(n - 2); };

(*JavaScriptでフィボナッチ数を計算)

IchigoJamでも配列をスタックとして使うことで、再帰を表現できます。
参照「IchigoJamで学ぶデータ構造「スタック」

100 @FIB 110 N=[S-1]:IF N<2 [S-1]=N:RTN 120 [S]=N-1:S=S+1:GSB@FIB 130 N=[S-2] 140 [S]=N-2:S=S+1:GSB@FIB 150 [S-3]=[S-2]+[S-1]:S=S-2 155 ?[S+1];"+";[S];"=";[S-1] 160 RTN [S]=10:S=S+1:GSB@FIB:S=S-1:?[S]

スタックに計算したいフィボナッチ数を積んで、GSB@FIBで呼び出し、戻ってきた後、ポップすると値が入っています。(*IchigoJam web で試す)

フィボナッチや数列でいろいろと遊んでみてください!

Tweet
クリエイティブ・コモンズ・ライセンス
この作品は「Creative Commons — CC BY 4.0」の下に提供されています。
CC BY 福野泰介 - Taisuke Fukuno / @taisukef / high-res profile image