基礎から学ぶVBAプログラミング教室

教えることは、二度学ぶこと

スポンサーリンク

VBAでフィボナッチ数列を書いてみた(再帰なし/あり)

f:id:excel-accounting:20180804182502p:plain:w450

夏といえばひまわり!

ひまわりといえば…?

フィボナッチ数列!

ひまわりの種の並びはフィボナッチ数列になっているそうですよ。

あとは、松ぼっくりとか、カタツムリの殻とか。


さて、本題にはいります!

フィボナッチ数列とは?

1,1,2,3,5,8,13,21・・・

第1項=1
第2項=1

として、

【2つ前の数字】と【1つ前の数字】の合計を並べたものです。

※ネットで色々みると、フィボナッチ数列の第1項は0と書いてあったり、1と書いてあったりします。

この記事では第1項=1としてプログラムを実装します。

VBAでフィボナッチ数列の第n項を求める

「再帰あり」と「再帰なし」の2パターンで書いてみました。

再帰処理についてはこちらの記事もあわせてご覧ください!
www.excel-prog.com

再帰なしのパターン

Sub フィボナッチ数を求める_再帰なし()

    Dim x As Variant '第n項の2つ前の値
    Dim y As Variant '第n項の1つ前の値
    
    x = 1 '第1項の値
    y = 1 '第2項の値
    
    '★★★求めたい項を指定★★
    Dim n As Long: n = 10
    
    '計算回数をカウント※第1,2項の値はセットしているので、第3項から計算開始
    Dim cnt As Long: cnt = 3
    
    Do While cnt <= n
    
        Dim total As Variant
        total = x + y
        
        x = y
        y = total
            
        cnt = cnt + 1
        
    Loop
    
    '★★★答え★★★
    Debug.Print "第" & n & "項→" & total

End Sub

Do~Loop文でやってることはこんな感じです。

f:id:excel-accounting:20180804164133p:plain

桁あふれを考慮して、x,y,totalはVariant型にしています。

第50項だと12,586,269,025になるんですね!

再帰ありのパターン

Sub フィボナッチ数を求める_再帰あり()
    
    '★★★求めたい項を指定★★
    Dim n As Long: n = 10

    Dim total As Variant
    total = Fib(n)
    
    Debug.Print "第" & n & "項→" & total

End Sub

Function Fib(n As Long) As Variant

    If n = 1 Or n = 2 Then
        Fib = 1
    Else
        Fib = Fib(n - 2) + Fib(n - 1)
    End If

End Function

Fib(10) = Fib(8) + Fib(9)

のように、【2つ前の値】と【1つ前の値】を合計します。

実行時間を比較してみる

「再帰処理はメモリを食うから遅くなる」みたいな内容をよく見るので、実験です。

第20項あたりから差がつくようです。

第n項 再帰なし 再帰あり (参考)計算値
20 0.001~2秒 0.004秒 6,765
25 0.023秒 75,025
30 0.216秒 832,040
35 2.29秒 9,227,465
36 3.772秒 14,930,352
37 6.145秒 24,157,817
38 9.934秒 39,088,169
39 16.065秒 63,245,986
40 26.358秒 102,334,155
45 応答なし 1,134,903,170
50 やめておく 12,586,269,025

再帰なしは速し!

50項でも余裕!


「VBAで書いてみた」シリーズの他の記事もぜひ見ていってくださいね!

スポンサーリンク