<問題> フィボナッチ数は、以下の漸化式で定義される。 F (0) = 0, F (1) = 1 F (N) = F (N -1) + F (N - 2) (N > 1)
フィボナッチ数を求める再帰プログラムを作成せよ (定番のプログラム例題です)
<実行結果 例> n :7 fib (7) = 13 n :10 fib (10) = 55 n :45 fib (45) = 1134903170 (うっと思うほど、時間がかかるはず)
UNIXで実行できる場合は、timeコマンドで実行してみるとよい
実行ファイルをfibとするとき
time fib
n :45
fib (45) = 1134903170
real 0m32.773s (コマンド起動から終了までの時間。下のユーザCPU時間のほか、入出力の時間なども加算)
user 0m30.665s (ユーザのコマンドがCPUを使用した時間) (←ここに注目)
sys 0m0.007s (このコマンドにコマンド以外のシステム(OS)関係の処理が要した時間)
こちらの実行結果が出るかもしれません
time fib
n :45
fib (45) = 1134903170
9.615u 0.000s 0:10.77 89.2% 0+0k 0+0io 0pf+0w
コマンド起動から終了までに10.77秒 userに9.615 sysに0秒。
解答例 #include <stdio.h> int fib(int n); int fib(int n) { int main(void) { int n; printf("n :"); scanf("%d", &n); printf("fib (%d) = %d \n", n, fib(n)); return 0; }