求出第一個大於100000的費式數列是第幾項

用遞迴的寫法

/**
  * FIB use recursive
  * 
  * @param big_number
  * @return big than big_number is
  */
 public static int fib_slow(long big_number) {
  long f = 1;
  int ans = 0;
  for (long i = 0; f < big_number; i++) {
   f = fib(i);
   ans++;
  }
  return ans;
 }

 public static long fib(long n) {
  if (n == 0 || n == 1)
   return n;
  else
   return (fib(n - 2) + fib(n - 1));
 }

用單一迴圈的寫法，所花的時候只有O(n)

/**
  * FIB not use recursive
  * 
  * @param number
  * @return big than big_number is
  */
 public static int fib_quick(long number) {
  long a, b, c;
  /* A[0]=0,A[1]=1 has been count in first time, so ans=2*/
  int ans = 2;
  a = 0;
  b = 1;
  c = a + b;
  while (c < number) {
   /* A[n+2]=A[n]+A[n+1]; */
   c = a + b;
   /* next ...., let A be a=A[n+1],b=A[n+2] */
   a = b;
   b = c;
   ans++;
  }
  return ans;
 }

code