漸化式・再帰・動的計画法

#include <stdio.h>
#include <stdlib.h> //atoi
#include <time.h>   //実行時間計測clock_t

#define none (-1)       //既出解判定用
long int f(int n);      //既出解記録初期設定、計算値返却
long int f_(int n, long int F[]);   //既出解記録と判定

//long int trb(int n);      //トリボナッチで試してみた
//long int Btm(int n, long int F[]); //ボトムアップやってみた

clock_t t1, t2;     //実行時間計測値記録用

//main--------------------------------------------------------

int main(int argc, char *argv[]){
   
   int n= atoi(argv[1]);   //コマンドラインから数値に変換して記録
   long int gn;            //出力用

   if(argc != 2)return 0;  //データがなかったら終わり
   if( (n<0) || (n>100) )return 0;     //0以上100未満で処理

   t1= clock();        // 計測開始時間記録
   gn= f(n);           //nをf();に渡して返却値を記録
   //gn= trb(n);         //再帰呼び出しだけのやつ
   t2= clock();        //計測終了時間記録

   printf("%ld\n", gn);    //結果出力
   
   
   //数値確認用
   //printf("nの数値%d\n", n);
   //printf("gnの数値%ld\n", gn);
   //printf("実行時間%.10fs\n", (double)(t2-t1)/CLOCKS_PER_SEC);

return 0;
}

//long int f(int n);-------------------------
//記憶領域の確保と初期化処理、計算値の返却
long int f(int  n){

int i;              //カウンタ  
long int r;         //返却用
long int *F;        //計算値記録用配列

//既出解記録用配列の確保
F= calloc(n+1, sizeof(long int));

//既出解記録用配列の初期化
for(i=0; i!=n+1; i++) F[i]= none;

//計算結果をrに保持
r= f_(n, F);        //トップダウンf_();へ
//r= Btm(n, F);     //ボトムアップBtm();へ

//確保した領域の解放
free(F);

//数値確認用
//printf("rの数値:%ld\n", r);

//計算結果をmainに返却
return r;
}


//long int f_(int n, long int F[]);----------
//計算結果の記録と既出解判定
long int f_(int n, long int F[]){
   
   //printf("F[%d]の数値@%ld\n", n, F[n]);
   if(F[n] != none) return F[n];   //既出解ならその値を返す
   if(n==0 || n==1){               //nが0か1なら0を記録その値を返す
       return F[n]= 0;
   }else if(n==2){                 //nが2なら1を記録その値を返す
       return F[n]= 1;
   }else{                          //上記以外は計算して記録その値を返す
       return F[n]= f_(n-1,F) + f_(n-2,F) + f_(n-3,F);
   }

}