以下の改題をだされたのですが、作成したコードでは処理時間の判定に引っかかってしまいます。
コードをどのように書き直したらよいでしょうか?
作成コード
#include <stdlib.h> #define MAX 46 long int fib[MAX]; int ck[MAX]={0}; long int f_c; long int f(int n); // n番目(n>=0)のフィボナッチ数を返す int main(int argc, char *argv[]){ if(argc==1) return 0; int i; int from=atoi(argv[1]); int to=from; if(argc==3){ from=atoi(argv[1]); to=atoi(argv[2]); } if(from>to) return 0; for(i=from; i<=to; i++){ if(i==0){ printf("f(%d)=%ld [%d times]\n",i,f(i),2); } else if(i>=0){ printf("f(%d)=%ld [%d times]\n",i,f(i),i*2); } } 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 それぞれは、必要最小限の桁数で書き出すこと。
回答1件
あなたの回答
tips
プレビュー