再帰
フィボナッチ数列
Nim
メモ化
けものフレンズ

フィボナッチ数列
  欲しい!

そんな人のための記事です。

Nim で 再帰

まず、普通のコードならこうです(個人差があります)。

import strutils
proc fibonacci(x: int): int=
  if x < 2:
    return x
  else:
    return fibonacci(x - 1) + fibonacci(x - 2)

var n = readLine(stdin).parseInt
echo fibonacci(n)

しかし、これでいいのでしょうか?
これでは、下図のようにどんどん計算回数が膨れ上がってしまいます。1

image.png

こんなことでは、日が暮れて夜が明けて、遊び疲れて捕まってしまいます。

SI☆KA☆SI

人類には、紙とペンがあります。
それと同じように、コンピュータにも、スタックと配列があります。
ならば、使え!!!

Nimのseqによるテーブルを用いる

やっと本題DA☆

とりあえずコード。

import strutils
var
  fibo_table = @[0, 1]
  calculated = 1

proc fibonacci(x: int): int=
  if x > calculated:
    fibo_table.add(( fibonacci(x - 1) + fibonacci(x - 2) ))
    calculated = x
  return fibo_table[x]

var n = readLine(stdin).parseInt
echo fibonacci(n)

importparseIntのためなので気にしない。
fibo_tableは計算済みの数を格納するテーブルです。
calculatedは計算済みを表す数値です。

if x > calculatedとしているのは、計算済みかどうかの判別です。これにより、必要のない計算をしないで済みます。

ここ大事!
fibo_table.add(hoge)により、計算済みの値をテーブルに格納しています。
また、小さいxから計算されるので、順番も揃っています。
Cのような言語ではこのaddにあたる操作が難しいので、あえてNimを選びました(Nimはいいぜ)!

あとはxを計算済みにして、return
パパッとやって、終わり!

ちなみに、$F_0+F_1,F_1+F_2,F_2+F_3…$という計算を一回ずつしかしてないので、第n項を求めるときの計算回数は高々n回程度のはずです。
やったね!
fibonacci.gif

あとがき

どうでした?わかりました?
こういうのはいろんな時に役立つので(適当)、役立ててみてください!

ちなみに、普通バージョンのフィボナッチ数プログラムと比べると、一目瞭然、とても速いです。
30項ぐらいで差が出始めます。
50,60になると普通バージョンではほぼ無理ですが、今回のプログラムではintがオーバーフローしないギリギリの92まで、それも爆速で解けました。
しかも、テーブルはグローバルなので他のプロシージャにも利用可能だし、動的な配列なので、必要以上にメモリを消費しないと思います。
すっごーい!

おまけ

3行目をfibo_table = @["けもの", "フレンズ"]にしてみました。
fibokemo.gif


 
 
 
 
 
 
 
 
 
 
 
 
 

内緒のお話

この記事を一通り書き上げた後に調べてみたら、メモ化という意外と知られている手法らしく、Wikipediaに載ってた。
メモ化 - Wikipedia
開き直ってタグに登録してやった後、さらに気づいた。qiitaに被っている記事がある。しかもNim。
nimで、メモ化で、フィボナッチ数列の値を計算しておく。 - Qiita
本当に、申し訳ございません。
悲しいです。

 



  1. この図は、二分木をブラウザにカッコよく描画する様より改変してお借りしました。Thanks!