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