「Fibonacci(フィボナッチ)数列」の編集履歴（バックアップ）一覧はこちら

「Fibonacci(フィボナッチ)数列」(2010/01/25 (月) 19:33:37) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

1,1,2,3,5,8,13,21･･･で表わされる数列 

Fibonacci（Leonardo of Pisa, 1180-1250頃）が記した算術書Liber abaci（1202年）に「ウサギの出生率に関する数学的解法」として発表された数列で、以下の漸化式で表される。 
F1 = 1、F2 = 1、Fn+2 = Fn+1 + Fn (n = 1, 2, 3...) 

また、一般項を表す数式もあるが、ここでは表現しにくいので省略。 
#asciiart(blockquote){
 '漸化式を用いて順次求める方法
Dim a As Integer, b As Integer, t As Integer
 a = 1
b = 0
While a < 100
    Print a
    t = a + b
    b = a
    a = t
Wend
'一般式より定義されるn項目の値
Function fib1(n As Integer) As Long
    fib1 = ((1 + Sqr(5)) / 2)^n / Sqr(5) + 0.5
    'function.sbpに定義されているipow()関数を使うと若干早くなるが
    'ヘルプに記載が無い関数なのであまりお勧めしない
    'fib1 = (ipow(1 + Sqr(5)) / 2, n) / Sqr(5) + 0.5
End Function
}
また、漸化式を下記のように行列で表現することもできる。この場合、n項目のFibonacci数は「行列をn乗する問題」に帰着することができる。 
     | Fn+2 | = | 1  1 | × | Fn+1 |
     | Fn+1 |   | 1  0 |    |  Fn  |
#asciiart(blockquote){
Function fib2(n As Integer) As Long
    Dim a As Long, b As Long, c As Long    '係数行列の成分
    Dim x As Long, x1 As Long, y As Long, y1 As Long    '解のベクトル成分
    Dim tmp1 As Long, tmp2 As Long

    a = 1    '係数行列(1,1)の初期値
    b = 1    '係数行列(1,2)および(2,1)の初期値
    c = 0    '係数行列(2,2)の初期値
    x = 1    '
    y = 0    '
    n = n - 1

    While n > 0
        If n And 1 Then
            tmp1 = x
            tmp2 = y
            x = a * tmp1 + b * tmp2
            y = b * tmp1 + c * tmp2
        End If

        n = n / 2
        tmp1 = a
        tmp2 = b
        a = tmp1 * tmp1 + tmp2 * tmp2
        b = tmp2 * (tmp1 + c)
        c = tmp2 * tmp2 + c * c
    Wend

    fib2 = x
End Function
}