フィボナッチ数列を定義する
漸化式での定義
フィボナッチ数列は数学者レオナルド・フィボナッチに因んで名付けられた数で、漸化式を使って次のように表現することができます。
\begin{align}
F_0&=0\\
F_1&=1\\
F_{n+2}&=F_{n+1}+F_{n} (n \geq 0)
\end{align}
これを計算して１項目から順に並べると
1,1,2,3,5 \cdots
となります。C++での実装例は以下の通り。
#include <stdio.h>
#define N 15
int main() {
int i;
int* F;
F = new int[N+1];
F[0] = 0;
F[1] = 1;
printf("1 -> %d \r\n", F[1]);
for (i = 2; i < N+1; i++) {
F[i] = F[i - 2] + F[i - 1];
printf("%d -> %d \r\n", i, F[i]);
}
delete[] F;
}
C++として振る舞うコードはメモリの動的確保を行う部分
F = new int[N+1];
//省略
delete[] F;
であるので、malloc等に置き換えればC言語として実行することができます。mallocで実行するにはヘッダーに
#include <cstdlib> // for malloc
を追加し
F = (int *)malloc(sizeof(int)*(N+1));
//省略
free(F);
とすると動くと思います。
フィボナッチ数列の一般解を使った定義
漸化式的な計算はメモリが必要だったりと面倒です。そこで一般解を使って各項を計算することを考えます。フィボナッチ数列の一般解はすでに得られていて
\begin{align}
F(n)&=\frac{\phi^n-(-\phi)^{-n}}{\sqrt{5}} \\
\phi&=\frac{1+\sqrt{5}}{2}
\end{align}
となります。一般解を用いてフィボナッチ数列を計算するC++での実装例は以下の通り。
#include <stdio.h>
#include <math.h>
#define n 15
int main(){
int i;
double phi = (1 + sqrt(5)) / 2;
for (i = 1; i <= n; i++) {
printf("%d -> %f\r\n",i, (pow(phi,i) - pow(-phi,-i)) / sqrt(5));
}
}
ここで累乗は
#include <math.h>
を追加し
int y;
y=pow(a,x);
とすれば
y=a^x
を計算できます。
フィボナッチ数列の関係式
フィボナッチ数列にはいくつかの関係が知られています。これをプログラムで計算して確かめてみます。
フィボナッチ数列の特别な和公式
\begin{align}
\sum_{i=1}^\infty \frac{F_i}{10^{i+1}} = \frac{1}{89}
\end{align}
#include <stdio.h>
#include <math.h>
#define N 30
const double phi = (1 + sqrt(5)) / 2;
double Fibonacci(int);
int main() {
int i, n;
double psi = 0;
for (i = 1; i <= N; i++) {
n = i + 1;
psi = psi + Fibonacci(i) / pow(10, n);
printf("%f -> %f \r\n",1/89.0, psi);
}
}
double Fibonacci(int i) {
return (pow(phi, i) - pow(-phi, -i)) / sqrt(5);
}
フィボナッチ数列の逆数和
\begin{align}
\psi=\sum_{i=1}^\infty \frac{1}{F_i} = 3.3498 \cdots
\end{align}
#include <stdio.h>
#include <math.h>
#define n 30
const double phi = (1 + sqrt(5)) / 2;
double Fibonacci(int);
int main() {
int i;
double psi = 0;
for (i = 1; i <= n; i++) {
psi = psi + 1 / Fibonacci(i);
printf("%d -> %f\r\n",i, psi);
}
}
double Fibonacci(int i) {
return (pow(phi, i) - pow(-phi, -i)) / sqrt(5);
}
フィボナッチ数列の比の極限
\begin{align}
\lim_{n \to \infty } \frac{F_{n+1}}{F_n}= \phi = \frac{1 + \sqrt{5}}{2}
\end{align}
#include <stdio.h>
#include <math.h>
#define n 30
const double phi = (1 + sqrt(5)) / 2;
double Fibonacci(int);
int main() {
int i;
for (i = 2; i <= n; i++) {
printf("%f -> %f\r\n", phi, Fibonacci(i) / Fibonacci(i - 1));
}
}
double Fibonacci(int i) {
return (pow(phi, i) - pow(-phi, -i)) / sqrt(5);
}
連続する１０個のフィボナッチ数列の和と７番目の数との関係
\begin{align}
\sum_{i=1}^{10} F_{n+i} = 11 \times F_{n+7}
\end{align}
#include <stdio.h>
#include <math.h>
#define N 9
const double phi = (1 + sqrt(5)) / 2;
double Fibonacci(int);
int main() {
int i;
double psi = 0;
for (i = 1; i <= 10; i++) {
psi = psi + Fibonacci(N + i);
}
printf("%f -> %f \r\n", 11*Fibonacci(N+7), psi);
}
double Fibonacci(int i) {
return (pow(phi, i) - pow(-phi, -i)) / sqrt(5);
}