/*				written by izumi@ieee.org, 19-Jan-2010

	実装法の違いに関する考察

	問題：フィボナッチ数列のｎ番目の要素を計算する関数を考える。
	次の３通りの実装について、それぞれのメリット、デメリットを述べよ。

	コンパイル例
		gcc -Wall -ofibo.exe fibo.c

	実行例
		fibo.exe 1 2 3 4 5 10 20 30 40

*/

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

int count;
double SQRT5,FIBOP,FIBOM;

int fibo1(int n){
  int f;
  if (n<=0){
    f = 0;
  } else if (n==1){
    f = 1;
  } else if (n>1){
    f = fibo1(n-1)+fibo1(n-2);
  } else {
    f = 0;
  }
  count++;

  return f;
}


int fibo2(int n){
  int i, f1, f2, f;
  if (n>0){
    f1 = 0;
    f2 = 1;
    for (i=1;i<=n;i++) {
      f=f1+f2;
      f2=f1;
      f1=f;
      count++;
    }
  } else {
    f = 0;
  }

  return f;
}


int fibo3(int n){
  int f;
  if (n>0) {
    double nd, fd;
    nd =((double) n);
    fd = (pow(FIBOP,nd)-pow(FIBOM,nd))/SQRT5;
    f = ((int) fd);
  } else {
    f = 0;
  }
  count++;
  return f;
}

int main(int argc, char **argv) {
  int n, i;
  int f1,f2,f3;
  int c1,c2,c3;

  SQRT5=sqrt(5.0);
  FIBOP=(1.0+SQRT5)/2.0;
  FIBOM=(1.0-SQRT5)/2.0;

  for (i=1;i<argc;i++) {
    n=atof(argv[i]);

    count=0;
    f1=fibo1(n);
    c1=count;
    printf("fibo1(%3d)=%10d count=%10d\n",n,f1,c1);

    count=0;
    f2=fibo2(n);
    c2=count;
    printf("fibo2(%3d)=%10d count=%10d\n",n,f2,c2);

    count=0;
    f3=fibo3(n);
    c3=count;
    printf("fibo3(%3d)=%10d count=%10d\n",n,f3,c3);

  }

  return 0;
}