蓝桥杯:Fibonacci数列

举报
AI 菌 发表于 2021/08/05 01:06:07 2021/08/05
【摘要】 话不多说,首先上菜: 对于这个问题,拿到手,马上想到的是:先求Fibonacci数列,再求余数。但是极其不建议这样暴力计算。因为当n很大时,计算时间较长,还可能发生数值溢出的情况! 所以,这里给出另外一种思路:间接方式求余数 首先,科普一个求余公式:(a+b)% c = (a%c+b%c)%c 这个式子不难理解,可以代值进去试试看。 所以,不难得出:f(n)%m = ...

话不多说,首先上菜:
在这里插入图片描述
对于这个问题,拿到手,马上想到的是:先求Fibonacci数列,再求余数。但是极其不建议这样暴力计算。因为当n很大时,计算时间较长,还可能发生数值溢出的情况!
所以,这里给出另外一种思路:间接方式求余数
首先,科普一个求余公式:(a+b)% c = (a%c+b%c)%c
这个式子不难理解,可以代值进去试试看。
所以,不难得出:f(n)%m = [f(n-1)+f(n-2)]%m = [f(n-1)%m+f(n-2)%m]%m
由题目可知,最终求f(n)%m,因此令:g(n)=f(n)%m,其中m=10007。
于是求余递推公式为:g(n)=[g(n-1)+g(n-2)]%m
其中,m=10007,g(1)=g(2)=1%m=1
完整代码如下:

#include <iostream>
using namespace std;

int main()
{
	int f1=1,f2=1;
	int temp=0; //中间变量
	int output=0; //输出
	long n=0; //初始化输入
	cin>>n;
	if(n==1||n==2)
	{
		output=1;  //当n=1或2时,输出为1
	} 
	else
	{
		for(int i=3;i<=n;i++)
		{ temp=f2; f2=(f1+f2)%10007;  //当n大于2时,递推计算 f1=temp;
		}
		output=f2;
	}
	cout<<output;
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

既然说到了Fibonacci数列,那么这里也贴出C++的实现方法:

#include <iostream>
using namespace std;

int Fibonacci(int n)   //Fibonacci数列函数 
{
	if(n==1||n==2)
		return 1;
	else
		return Fibonacci(n-1)+Fibonacci(n-2);
}

int main()
{
	int n=0;
	cin>>n;
	cout<<Fibonacci(n);  //输出Fibonacci数列第n个数 
	return 0;
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

文章来源: ai-wx.blog.csdn.net,作者:AI 菌,版权归原作者所有,如需转载,请联系作者。

原文链接:ai-wx.blog.csdn.net/article/details/104537507

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。