[送分]老的不能再老的题目了,斐波那契序列
题目很简单,给定n,求f(n)
要求:最简便!
如果你的方法比我想的还简单(或者和我一样),得所有分,否则得一半,其余“顶”帖的平分,如果你觉得自己的方法还没有上一回帖的简单,只需“顶”,不用解答
抛砖引玉:
f(n)=f(n-1)+f(n-2),递归实现~~~
[解决办法]
有
http://blog.sina.com.cn/u/56daf12d010003f8
只能顶了..
[解决办法]
int fun(int n)
{
if ((n==1) || (n==2))
return 1;
return fun(n-1)+fun(n-2);
}
[解决办法]
int fun(int n)
{
if ((n==1) || (n==2))
return 1;
return fun(n-1)+fun(n-2);
}
======================================
当n很大的时候很耗时间,而且,如果给定了n计算之后,再计算m <n时又要重复计算,最好是用一个数组记录已经计算出来的结果,如果给定的n大于数组的数目再进行计算。
[解决办法]
酱紫算, 找个好的大数库, 算到 1 < <25 也是很快的, http://topic.csdn.net/t/20051219/16/4468145.html
#include <stdio.h>
double fib_d( unsigned NN )
{
double X1 = 1 , X2 = 1 , X3 , R1 = NN&1 , R2 = NN&1;
while(NN/=2)
{
X3 = ( X1 * X1 + 5 * X2 * X2 ) / 2;
X2 = ( X1 * X2 ); X1 = X3;
if( NN&1 )
{
if( !R1 )
R1 = X1 , R2 = X2;
else
X3 = (R1*X1+5*R2*X2)/2 , R2 = (R1*X2+R2*X1)/2 , R1=X3;
}
}
return R2;
}
int main()
{
unsigned x ;
fib_d( 13 );
for( x = 0; x < 100; ++x )
{
printf( "fib %d == %g\n " , x , fib_d(x) );
}
return 0;
}
[解决办法]
mov ax, n ; ax for n
mov bx, 1 ; bx for fab(n+1)
mov cx, 1 ; cx for fab(n-1)
mov dx, bx ; dx for fab(n)
loop: add bx, cx
mov cx, dx
dec ax
jns loop
[解决办法]
#include <iostream>
using namespace std;
const int N = 10;
int main(int argc, char* argv[])
{
long lFabOdd(1), lFabEven(1);
int i(0);
while(i <N)
{
lFabOdd += lFabEven;
lFabEven += lFabOdd;
i += 2;
}
if(i> N)
{
cout < < lFabOdd;
}
else
{
cout < < lFabEven;
}
return 0;
}
[解决办法]
日
顶
这种好事居然没让我抢到
[解决办法]
先顶一下,不过为什么大家都用递归呢?难道循环不好用吗?至少比递归要快一点吧?
[解决办法]
直接用公式就行了
f(n) = 1 /√5 * ((((1 + √5) / 2)^n) - (((((1 - √5) / 2)^n))
[解决办法]
a,b,k=0,1,10
while k:
a,b=b,a+b;
k=k-1
[解决办法]
f(n) = 1 /√5 * [((1 + √5) / 2)^(n+1) - ((1 - √5) / 2)^(n+1)]
公式计算乘法运算规模 O(n)
我觉得这样递归:
n=2i:f(n)=f(i)f(i)+f(i-1)f(i-1)
n=2i+1:f(n)=f(i)f(i+1)+f(i-1)f(i)
递归效率很高的。规模是O(log2(n))