今天公司的一道面试题目

Question

正如我们所知道的, Fibonacci定义了一个数列, 那么数列中的每个数都等于它前两个数的和(除了数列的前两个数), 举例来说:1, 1, 2, 3, 5, 8, 13, 21, 34,...等等.
要求:
1)在Java中实现两个函数来生成第n位的Fibonacci数:fibo1和fibo2. 这两个函数都接受一个整型参数n并且返回第n位的Fibonacci数.请使用递归来实现fibo1, 使用循环实现fibo2. 

Answer 1

int fibo1(int n)
{ int a=1,b=1;
  for(int i =2;i< n ;i+=2)
 {
     a = a + b;
     b = b + a;
    
  }
  if( n %2 == 0)
  return b;
  else
  return a;
}
int fibo2(int n)
{  
   int re;
   if(n>2)
     re= fibo2(n-1) +  fibo2( n -2);
   else
 re = 1;  return re;
}

Answer 2

本人觉得递归不是最好的方法
fibo2(n-1) +  fibo2( n -2);
如果传入的n>2;
则fibio2(3) to  fibio2(n-2)都会被计算辆次
如果给的n值太大的话很容易造成栈满
大家看看下面的代码:
public static long fibo2(int n)
  {
   if(n<=2)
   return 1;
   else
   {
   long []fibo=new long[n];
   fibo[0]=1;
   fibo[1]=1;
   for(int i=2;i<n;i++)
   {
   fibo[i]=fibo[i-1]+fibo[i-2];
   }
   return fibo[n-1];
   }
  }

Answer 3

0,1,1,2,3,5,8,13,21,34,55,89,144,233…的通项公式为：
Fn = 1/sqrt(5)*( ((1+sqrt(5))^(n+1)-((1-sqrt(5))/2)^(n+1) )