Question

编写一个程序，利用递归函数求斐波那契数列（0，1，1，2，3，5，8，13，21…… ）前100项的和

用递归函数求，C++题目。
谢谢！

Answer 1

第一，这个题目用递归函数的话，算出结果肯定要花好长时间的。估计至少要半个多小时以上，机器差的话肯定不止。实际上用递推的话会省掉非常多的时间的。
第二，这个当数列到了40多项的时候，用int型或者__int64都是装不下的。所以后面的数据会是错误的。因此，此题又涉及到高精度的问题了。用高精度来写递归的加法。这样的话时间复杂度就更大了。估计得跑几个小时吧。
这里给你个简单的递归的求出前30项的和。如果真的要100项的话只能用高精度来写了。估计也不一定有人会帮你写。
简单的递归程序（即不考虑超出int型范围的情况）如下：
#include<iostream>
using namespace std;

int f(int n)
{
if(n==0) return 0;
if(n==1) return 1;
return f(n-1)+f(n-2);
}

int main()
{
int i,sum=0;
for(i=0;i<30;i++)
{
sum+=f(i);
}
cout<<sum<<endl;
}

Answer 2

因为用了很没有效率的递归，所以出结果有点慢
#include<iostream.h>
f(int);
main()
{
int i,s=0;
for(i=1;i<=100;i++)
{
cout<<f(i)<<'\t';
s+=f(i);
}
cout<<endl;
cout<<"前100项的和为"<<s<<endl;
}
f(int i)
{
int value;
if(i==1||i==2)
value=1;
else
value=f(i-1)+f(i-2);
return value;
}

Answer 3

答案为1.可以从第三位与第一位的差为1，第四位与前两位的和，差为1，以此类推，得100项与前98项之和的差是1.

Answer 4

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
float f1,f0,f,fsum;
int i;

f=1;f1=1,f0=0;
fsum=f0+f1;
for(i=2;i<100;i++){
fsum=fsum+f;
f0=f;
f=f+f1;
f1=f0;
}
printf("%21.0f\n",fsum);

return 0;
}

Answer 5

int fib(int n)
{
switch(n)
{
case 0:return0;break;
case 1:
case 2:return 1;break;
default:return fib(n-1) + fib(n-2);break;
}

return -1;
}

int main(void)
{
int i,j=0;
for(i = 0; i< 100; ++i) j += fib(i);

printf("%d\n", j);

return 0;
}