フィボナッチ数列を返す関数
フィボナッチ数列は漸化式 \[ f_{n+2} = f_{n+1} + f_n, \quad (f_0=0,f_1=1) \] で定義される数列である。 今回は指定した個数だけ、フィボナッチ数列を返す関数を作成する。
コード例1
漸化式を用いて、再帰的に定義する。
#include <stdio.h> int fibo(int n); int main() { int i; for (i = 0; i < 21; i++) { printf("fibo(%2d) = %10d \n", i, fibo(i)); } } int fibo(int n) { if (n == 0) { return 0; } if (n == 1) { return 1; } return fibo(n - 1) + fibo(n - 2); }
実行結果
fibo( 0) = 0 fibo( 1) = 1 fibo( 2) = 1 fibo( 3) = 2 fibo( 4) = 3 fibo( 5) = 5 fibo( 6) = 8 fibo( 7) = 13 fibo( 8) = 21 fibo( 9) = 34 fibo(10) = 55 fibo(11) = 89 fibo(12) = 144 fibo(13) = 233 fibo(14) = 377 fibo(15) = 610 fibo(16) = 987 fibo(17) = 1597 fibo(18) = 2584 fibo(19) = 4181 fibo(20) = 6765
解説
再帰を用いると、直感的でわかりやすいが、数値が大きくなると非常に遅くなる。
コード例2
再帰的に関数を呼び出さない方法を考える。
#include <stdio.h> int fibo(int n); int main() { int i; for (i = 0; i < 21; i++) { printf("fibo(%2d) = %10d \n", i, fibo(i)); } } int fibo(int n) { int a = 0; int b = 1; int c; if (n == 0) { return 0; } int i; for (i = 0; i < n; i++) { c = a + b; b = a; a = c; } return c; }
実行結果
fibo( 0) = 0 fibo( 1) = 1 fibo( 2) = 1 fibo( 3) = 2 fibo( 4) = 3 fibo( 5) = 5 fibo( 6) = 8 fibo( 7) = 13 fibo( 8) = 21 fibo( 9) = 34 fibo(10) = 55 fibo(11) = 89 fibo(12) = 144 fibo(13) = 233 fibo(14) = 377 fibo(15) = 610 fibo(16) = 987 fibo(17) = 1597 fibo(18) = 2584 fibo(19) = 4181 fibo(20) = 6765
解説
若干わかりづらくなったが、こちらのほうが処理が速い。
コード例3
指定した個数のフィボナッチ数列を得る関数を作成する。
#include <stdio.h> #include <stdlib.h> int* getFibonacciSequence(int max); int main() { int max = 21; int* g = getFibonacciSequence(max); int i; for (i = 0; i < max; i++) { printf("fibo(%2d) = %10d \n", i, g[i]); } free(g); } int* getFibonacciSequence(int max) { if (max <= 0) { exit(1); } int* fi = (int*)malloc(sizeof(int) * max); if (fi == NULL) { exit(1); } if (max == 1) { fi[0] = 0; return fi; } if (max == 2) { fi[0] = 0; fi[1] = 1; return fi; } int i; fi[0] = 0; fi[1] = 1; for (i = 2; i < max; i++) { fi[i] = fi[i - 1] + fi[i - 2]; } return fi; }
実行結果
fibo( 0) = 0 fibo( 1) = 1 fibo( 2) = 1 fibo( 3) = 2 fibo( 4) = 3 fibo( 5) = 5 fibo( 6) = 8 fibo( 7) = 13 fibo( 8) = 21 fibo( 9) = 34 fibo(10) = 55 fibo(11) = 89 fibo(12) = 144 fibo(13) = 233 fibo(14) = 377 fibo(15) = 610 fibo(16) = 987 fibo(17) = 1597 fibo(18) = 2584 fibo(19) = 4181 fibo(20) = 6765
解説
直接配列を返すのではなく、mallocでメモリを確保してから、ポインタを返す。