[c言語]フィボナッチ数列を動的計画法でコーディング

再帰を使った場合

下記がサンプルコードになります。
f(n)からf(n-1)とf(n-2)を再帰的に呼び出します。
重複計算もあって、n=45で13秒かかっています。

$ cat sample.c 
#include <stdio.h>
#include <time.h>

//n >= 0
int getFibNum(int n){
	if(n <= 1){
		return n;
	}
	return getFibNum(n - 1) + getFibNum(n - 2);
}

int main(){
	time_t startTime;
	
	printf("%d\n", getFibNum(1));
	printf("%d\n", getFibNum(2));
	printf("%d\n", getFibNum(6));
	printf("%d\n", getFibNum(9));
	
	startTime = time(NULL);
	printf("%d\n", getFibNum(45));
	printf("%ldsec", time(NULL) - startTime);
	
	return 0;
}

下記が実行結果になります。

$ gcc -o sample sample.c
$ ./sample 
1
1
8
34
1134903170
13sec

動的計画法のメモ化再帰を使った場合

重複計算を避け、一度計算したら結果を記憶させておき、計算結果を再利用していきます。
0で初期化した配列を定義しておき、計算されていれば(配列の要素が!0なら)再利用し、
計算されていなければ(配列の要素が0なら)計算していきます。
n=45で1秒以下で収まりました(time関数なので精度は秒単位です)。

下記がサンプルコードになります。

$ cat sample1.c 
#include <stdio.h>
#include <time.h>

int data[100] = {};
//n >= 1
int getFibNum(int n){
	if(n <= 1){
		return n;
	}
	if(data[n]){
		return data[n];
	}else{
		data[n] = getFibNum(n - 1) + getFibNum(n - 2);
		return data[n];
	}
}

int main(){
	time_t startTime;
	
	printf("%d\n", getFibNum(1));
	printf("%d\n", getFibNum(2));
	printf("%d\n", getFibNum(6));
	printf("%d\n", getFibNum(9));
	
	startTime = time(NULL);
	printf("%d\n", getFibNum(45));
	printf("%ldsec", time(NULL) - startTime);
	
	return 0;
}

下記が実行結果になります。

$ gcc -o sample sample1.c
$ ./sample 
1
1
8
34
1134903170
0sec

動的計画法で漸化式を使った場合

漸化式を使って、n=0, 1, 2, 3.......と、順にループ処理をして計算していきます。
数学的な思考になれていると、こちらの方が自然な方法に感じるかもしれません。
再帰処理のように重複計算もないので、計算量も削減できます。

$ cat sample2.c 
#include <stdio.h>
#include <time.h>

//n >= 1
int getFibNum(int n){
	int An,  An_1, An_2;
	int i;

	if(n <= 1){
		return n;
	}
	
	An_1 = 1;
	An_2 = 0;
	
	for(i = 2; i <= n; i++){
		An = An_1 +  An_2;
		An_2 = An_1;
		An_1 = An;
	}
	
	return An;
}

int main(){
	time_t startTime;
	
	printf("%d\n", getFibNum(1));
	printf("%d\n", getFibNum(2));
	printf("%d\n", getFibNum(6));
	printf("%d\n", getFibNum(9));
	
	startTime = time(NULL);
	printf("%d\n", getFibNum(45));
	printf("%ldsec", time(NULL) - startTime);
	
	return 0;
}

下記が実行結果になります。

$ gcc -o sample sample2.c
$ ./sample 
1
1
8
34
1134903170
0sec