質問: フィボナッチ数-動的計画法、計算のプログラミングについて教えてください。 ???の部分にはどのようにコードを書いたらよいでしょうか? #include #include long int f_c; long int f(int n); // n番目(n>=0)のフィボナッチ数を返す int main(int argc, char *argv[]){ ??? return 0; } long int f(int n){ f_c++; if( n<=1 ) return n; return f(n-1)+f(n-2); } 以下課題内容 フィボナッチ数を計算する関数 long int f(int n) を再帰呼出しを使って実装したものにトップダウンの動的計画法を適用した場合を考える。与えられた非負整数 n を引数とする関数呼出し f(n) を行なったときに生じる関数呼出し( f 自身の呼出し、および、そこから(直接に/再帰的に)呼び出される関数の呼出し)の回数を数え、 計算されたフィボナッチ数とともにその回数を標準出力に書き出すプログラムを作れ。 プログラムの仕様はつぎの通りとする。 コマンドライン引数に非負整数値が1個または2個与えられる。 1個与えられた場合、その値 n を引数として呼出し f(n) を行う。 2個与えられた場合、それらの値を m1、m2 とすると m 1 ≦ n ≦ m 2 である全ての値 n について小さい方から順に関数呼出し f(n) を行う。 m1>m2 のときは関数呼出しは何も行わずに実行を終了する。 出力は、関数呼出し f(n) を行うごとにその結果をつぎの形式で1行として標準出力に書き出す。 f(n)=v [c times] v はフィボナッチ数の値、 c はその関数呼出し回数 v と [ の間、c と times の間には、それぞれ空白1文字をおくこと。 数値 n、v、c それぞれは、必要最小限の桁数で書き出すこと。 実行例 コマンドライン入力 0 標準出力 f(0)=0 [2 times] コマンドライン入力 6 3 標準出力 コマンドライン入力 3 6 標準出力 f(3)=2 [6 times] f(4)=3 [8 times] f(5)=5 [10 times] f(6)=8 [12 times]
回答: #include #include #define N 1000 long int f_c; long int fibo[N]; long int f(int n); // n番目(n>=0)のフィボナッチ数を返す int main(int argc, char *argv[]) { // テスト用データ //argc = 3;argv[0] = "fib";argv[1] = "3";argv[2] = "6"; int m1,m2; for (int i = 2;i < N;i++) { fibo[i] = -1; } fibo[0] = 0; fibo[1] = 1; switch (argc) { case 2: m1 = atoi(argv[1]); printf("f(%d)=%ld",m1,f(m1)); printf(" (%ld times)\n",f_c); break; case 3: m1 = atoi(argv[1]); m2 = atoi(argv[2]); if (m1 <= m2) { for (int i = m1;i <= m2;i++) { f_c = 0; for (int i = 2;i < N;i++) { fibo[i] = -1; } printf("f(%d)=%ld",i,f(i)); printf(" (%ld times)\n",f_c); } } break; } return 0; } long int f(int n){ f_c++; if (fibo[n] != -1) { return fibo[n]; } fibo[n] = f(n - 1) + f(n - 2); return fibo[n]; }