HDU ACM Steps：Fibonacci

题目描述

2007年到来了。经过2006年一年的修炼，数学神童zouyu终于把0到100000000的Fibonacci数列
(f[0]=0,f[1]=1;f[i] = f[i-1]+fi-2)的值全部给背了下来。
接下来，CodeStar决定要考考他，于是每问他一个数字，他就要把答案说出来，不过有的数字太长了。所以规定超过4位的只要说出前4位就可以了，可是CodeStar自己又记不住。于是他决定编写一个程序来测验zouyu说的是否正确。

输入

输入若干数字n(0 <= n <= 100000000)，每个数字一行。读到文件尾。

输出

输出f[n]的前4个数字（若不足4个数字，就全部输出）。

输入样例

0
1
2
3
4
5
35
36
37
38
39
40

输出样例

0
1
1
2
3
5
9227
1493
2415
3908
6324
1023

思路

1.首先我们要清楚:
Fibonacci定义式：$F(n)=F(n-1)+F(n-2)$F(n)=F(n−1)+F(n−2)
Fibonacci通项公式：$F(n)=\frac{1}{\sqrt{5}}\times{[{(\frac{1-\sqrt{5}}{2})}^n-{(\frac{1+\sqrt{5}}{2})}^n]}$F(n)=5​1​×[(21−5​​)n−(21+5​​)n]
通项公式取对数：$log_{10}F(n)=log_{10}{(\frac{1}{\sqrt{5}}\times{[{(\frac{1-\sqrt{5}}{2})}^n-{(\frac{1+\sqrt{5}}{2})}^n]})} \approx log_{10}{\frac{1}{\sqrt{5}}}+nlog_{10}{\frac{1+\sqrt{5}}{2}}$log10​F(n)=log10​(5​1​×[(21−5​​)n−(21+5​​)n])≈log10​5​1​+nlog10​21+5​​
2.Fibonacci数列在1e9内的数只有44位。需要利用对数来解答。
小于10000的数：Fibonacci的前20项，按照定义式计算即可
大于10000的数：
先求出$x=log_{10}{F(n)}，然后通过x=[x]+(x)得到(x)$x=log10​F(n)，然后通过x=[x]+(x)得到(x)。$10^{(x)}*10000$10(x)∗10000的整数部分便是答案（不是很理解的话可以看一下另外一道题：https://blog.csdn.net/weixin_45718149/article/details/104631540）
注：$[x]：x的整数部分；(x)：x的小数部分$[x]：x的整数部分；(x)：x的小数部分

代码

#include<stdio.h>
#include<math.h>
//typedef long long ll;

int n;
int F[21];//储存前20个数 小于10000 

int Fibonacci(int n)//记忆化搜索 
{
	if(!n) return F[n]=0;
	else if(n==2||n==1) return F[n]=1;
	if(!F[n]) return F[n]=Fibonacci(n-1)+Fibonacci(n-2);
	return F[n];
}
void func(int n) 
{
	double ans=log10(1.0/sqrt(5))+n*log10((1+sqrt(5))/2);
	
	ans=ans-(long long)ans;//(x)=x-[x];
	ans=pow(10,ans);
	printf("%d\n",(int)(ans*1000));
}

int main()
{
	Fibonacci(20);
	while(~scanf("%d",&n))
	{
		if(n<21) 
		printf("%d\n",F[n]);
		else func(n);
	}
	return 0;
 }