Fibonacci

フィボナッチ数列の第n項(第一引数に指定した数値)の値を求めます。

構文
Fibonacci( n )
引数
n
求める項
戻値

プログラム

////////////////////////////////////////////////// // 【引数】 // n : 求める項 // 【戻値】 // ////////////////////////////////////////////////// FUNCTION Fibonacci(n) IFB RESIZE(Fibonacci) >= n THEN IFB Fibonacci[n] <> EMPTY THEN RESULT = Fibonacci[n] EXIT ENDIF ENDIF SELECT n CASE 0 IFB RESIZE(Fibonacci) < n THEN RESIZE(Fibonacci, n) Fibonacci[0] = 0 ENDIF RESULT = 0 EXIT CASE 1 IFB RESIZE(Fibonacci) < n THEN RESIZE(Fibonacci, n) Fibonacci[1] = 1 ENDIF RESULT = 1 EXIT DEFAULT IFB RESIZE(Fibonacci) < n THEN RESIZE(Fibonacci, n) Fibonacci[n] = Fibonacci(n - 1) + Fibonacci(n - 2) ENDIF SELEND RESULT = Fibonacci[n-1] + Fibonacci[n-2] FEND

この関数を利用するにはフィボナッチ数列の結果を格納しておくためのグローバル変数の宣言が必須。

PUBLIC Fibonacci[-1]

プログラム実行例

フィボナッチ数列の第0~50項までを表示

PUBLIC Fibonacci[-1] FOR n = 0 TO 50 PRINT Fibonacci(n) NEXT ////////////////////////////////////////////////// // 【引数】 // n : 求める項 // 【戻値】 // ////////////////////////////////////////////////// FUNCTION Fibonacci(n) IFB RESIZE(Fibonacci) >= n THEN IFB Fibonacci[n] <> EMPTY THEN RESULT = Fibonacci[n] EXIT ENDIF ENDIF SELECT n CASE 0 IFB RESIZE(Fibonacci) < n THEN RESIZE(Fibonacci, n) Fibonacci[0] = 0 ENDIF RESULT = 0 EXIT CASE 1 IFB RESIZE(Fibonacci) < n THEN RESIZE(Fibonacci, n) Fibonacci[1] = 1 ENDIF RESULT = 1 EXIT DEFAULT IFB RESIZE(Fibonacci) < n THEN RESIZE(Fibonacci, n) Fibonacci[n] = Fibonacci(n - 1) + Fibonacci(n - 2) ENDIF SELEND RESULT = Fibonacci[n-1] + Fibonacci[n-2] FEND
結果
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903
2971215073
4807526976
7778742049
12586269025

フィボナッチ数列

フィボナッチ数列とは、各項が前2つを足した値になる数列。第0項が0、第1項が1。

フィボナッチ数列は、次の漸化式で定義されます。

\(F_{0} = 0 \\ \\F_{1} = 1 \\ \\F_{n+2} = F_{n} + F_{n+1} (n \geq 0)\)

第0~15項の値は次の通りです。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610

フィボナッチ数列の漸化式をそのままプログラムに起こした例。

同じ計算を何度も繰り返し行うので効率が悪いです。

FUNCTION Fibonacci(n) SELECT n CASE 0 RESULT = 0 EXIT CASE 1 RESULT = 1 EXIT SELEND RESULT = Fibonacci(n – 1) + Fibonacci(n – 2) FEND