Fibonacci(フィボナッチ)数列 - abwiki @ ウィキ (ActiveBasic非公式wiki)

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...)

また、一般項を表す数式もあるが、ここでは表現しにくいので省略。

'漸化式を用いて順次求める方法
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  |

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