2019年合肥市蜀山区第18届信息学竞赛试题第1题求和
【题目描述】
斐波拉契数列,又称黄金分割数列,因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3）。斐波拉契数列的前两项分别为1,1。以后每项为前两项之和。现在输入n,要求斐波拉契数列前n项的和(1<=n<=5000)。
【输入】
输入只有一个数n，表示求斐波拉契数列前n项的和。
【输出】
输出斐波拉契数列前n项的和
【输入样例】
【输出样例】
【数据规模及约定】
对于40%的数据，n<=10
对于100%的数据，n<=5000
【思路一（40分）】：递推算法；
#include<bits/stdc++.h>
using namespace std;
long long int a[5001],n,sum=1;
int main()
{
scanf("%d",&n);
a[1]=1;
for(int i=3;i<=n;i++)
{
a[i]=a[i-1]+a[i-2];//递推基：斐波那契数列以如下被以递推的方法定义
sum+=a[i];
}
printf("%lld",sum);
}82 61305790721611591
83 99194853094755497
84 160500643816367088
85 259695496911122585
86 420196140727489673
87 679891637638612258
88 1100087778366101931
89 1779979416004714189
90 2880067194370816120
91 4660046610375530309
92 7540113804746346429
93 -6246583658587674878
94 1293530146158671551
95 -4953053512429003327
96 -3659523366270331776
97 -8612576878699335103
98 6174643828739884737
可见，第93个就超过long long 的范围了。所以只能得40分。
【思路二（100分）】：高精度；
#include<bits/stdc++.h>
using namespace std;
string wc(string a,string b)//高精度加法
{
reverse(a.begin(),a.end());
reverse(b.begin(),b.end());
int s=0;
string ans;
for(int i=0;i<max(a.size(),b.size());i++)
{
if(i<a.size())s+=a[i]-48;
if(i<b.size())s+=b[i]-48;
ans=char(s%10+48)+ans;
s/=10;
}
if(s!=0)
ans='1'+ans;//进位
return ans;
}
int main()
{
int n;
scanf("%d",&n);
if(n==1||n==2)//特判
{
printf("%d",n);
return 0;
}
string f[n+1],ans="2";
f[1]="1";
f[2]="1";
for(int i=3;i<=n;i++)
{
f[i]=wc(f[i-1],f[i-2]);//递推，f[i]=f[i-1]+f[1-2];
ans=wc(ans,f[i]);
}
cout<<ans;
return 0;
}如果觉得这篇文章好的话，请点赞+关注+订阅专栏。谢谢