#include <stdio.h>
#include <time.h>
#include <stdlib.h>
int Fib(int n){
    if(n==0) return 0;
    int a[n+1];
    a[0]=0;
    a[1]=1;
    for(int i=2;i<=n;i++){
        a[i]=a[i-2]+a[i-1];
    }
    return a[n];
}
int Fib1(int n){
    if(n==0){
        return 0;
    }else if(n==1){
        return 1;
    }else{
        return Fib1(n-2)+Fib1(n-1);
    }
}
int main(){
	clock_t ti[3];
	ti[0] = clock();
	printf("%d\n",Fib(20));
	ti[1] = clock();
	printf("Fib(20)の時間= %d\n", ti[1]-ti[0]);
    printf("%d\n",Fib1(20));
	ti[2] = clock();
	printf("Fib1(20)の時間= %d\n", ti[2]-ti[1]);
    return 0;
}