フィボナッチ数を計算

Question

フィボナッチ数を計算する関数

long int f(int n)

を再帰呼出しで関数定義した場合に、与えられた非負整数 n を引数とする呼出し f(n) に対して関数 f が呼び出される回数を数え、計算されたフィボナッチ数とともにその回数を標準出力に書き出すプログラムを作りたい。

プログラムの仕様はつぎの通りです。

非負整数 n はコマンドライン引数に与えられる。
出力は、つぎの形式として1行として書き出すこと。
u [c times]
u は n 番目のフィボナッチ数の値、 c はその計算での関数呼出しの回数
u と [ の間、c と times の間には、それぞれ空白1文字をおくこと。

■実行例
コマンドライン入力

0

標準出力

0 [1 times]

コマンドライン入力

1

標準出力

1 [1 times]

コマンドライン入力

10

標準出力

55 [177 times]

#include <stdio.h>
#include <stdlib.h>
 
long int f(int n);  
int main(int argc, char *argv[]){
   ・・・
   return 0;
}
long int f(int n){
 if( n<=1 ) return n;
 return f(n-1)+f(n-2);
}

Comments

[y_waiwai]

自分なりにコードを書きましょう

Answer 1

#include <stdio.h>
#include <stdlib.h>

long int f(int n);

int count = 0;

int main(int argc, char *argv[]) {
  count = 0;
  int n = atoi(argv[1]);

  int res = f(n);
  printf("%d [%d times]\n", res, count);
  return 0;
}

long int f(int n) {
  count++;
  if (n <= 1) {
    return n;
  }
  return f(n - 1) + f(n - 2);
}

実行例

Comments

[退会済みユーザー]

ご回答有難うございます！
流石上位の方．．．！！
大変助かりました☻

[katoy]

次の点の改良もかんがえてみてください。
1. グローバル変数 count を使わないようにする。
2. 計算結果が int の範囲を超えてしまう場合に対処する。

Answer 2

プログラムの仕様ではnの上限が定められておらず、intの最大値を超えた場合に関数long int f(int n)で計算することはできません。多倍長整数を使って書き直してください。