// ideoneでは正常に作動しなかったため、online GDPを用いて実験しました。
// 結果は、再帰を用いた方が短い時間で求めることができました。
// また、実行回数が少ないと、ほとんど差がなく、用いない方が早いこともあると気づきました。

#include <stdio.h>
#include <time.h>
#include <stdlib.h>


int saiki(int n){
	if(n<2){
		return 1;
	}
	return saiki(n-1)+saiki(n-2);
}

int fun(int n){
	int i;
	int a[n+1];
	for(i=0;i<=n;i++){
	if(i<2){
		a[i]=1;
	} else {
		a[i]=a[i-1]+a[i-2];
	}
	}
	return a[n];
}

int main(void) {
	clock_t ti[40];
	int i;
	double sum;
	for(i=0;i<40;i++){
		ti[i] = clock();
		sum=sum+ti[i]-ti[i-1];
		printf("fun(%d)=%d、時間=%d 時間差=%d\n",i,saiki(i),ti[i],ti[i]-ti[i-1]);
		if(i<=1) sum=0;
	}
	printf("ave=%f\n",sum/38);
	for(i=0;i<40;i++){
		ti[i] = clock();
		sum=sum+ti[i]-ti[i-1];
		printf("saiki(%d)=%d、時間=%d 時間差=%d\n",i,fun(i),ti[i],ti[i]-ti[i-1]);
		if(i<=1) sum=0;
	}
	printf("ave=%f\n",sum/38);
	return 0;
}