欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU ACM Steps:Fibonacci

程序员文章站 2024-01-15 17:50:10
...

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(n1)+F(n2)F(n)=F(n-1)+F(n-2)
Fibonacci通项公式F(n)=15×[(152)n(1+52)n]F(n)=\frac{1}{\sqrt{5}}\times{[{(\frac{1-\sqrt{5}}{2})}^n-{(\frac{1+\sqrt{5}}{2})}^n]}
通项公式取对数log10F(n)=log10(15×[(152)n(1+52)n])log1015+nlog101+52log_{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}}
2.Fibonacci数列在1e9内的数只有44位。需要利用对数来解答。
小于10000的数:Fibonacci的前20项,按照定义式计算即可
大于10000的数:
先求出x=log10F(n)x=[x]+(x)(x)x=log_{10}{F(n)},然后通过x=[x]+(x)得到(x)10(x)1000010^{(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;
 }
相关标签: ACM Steps

上一篇: Python显示进度条的方法

下一篇: