蓝桥杯—入门训练—Fibonacci斐波那契数列（Python解法）

た入场券 2022-12-15 14:29 178阅读 0赞

蓝桥杯python组省一国三，如果你也对蓝桥杯python感兴趣的话可以看一下这一篇文章：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hhcnJ5X19fX19f_size_16_color_FFFFFF_t_70]  
[博客链接：蓝桥杯python一篇就够了][python]

## 题目： ##

> 资源限制:  
> 时间限制：1.0s 内存限制：256.0MB
> 
> --------------------
> 
> 问题描述:  
> Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。  
> 当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。  
> 输入格式:  
> 输入包含一个整数n。  
> 输出格式:  
> 输出一行，包含一个整数，表示Fn除以10007的余数。
> 
> --------------------
> 
> 说明：在本题中，答案是要求Fn除以10007的余数，因此我们只要能算出这个余数即可，而不需要先计算出Fn的准确值，再将计算的结果除以10007取余数，直接计算余数往往比先算出原数再取余简单。
> 
> --------------------
> 
> 样例输入:  
> 10  
> 样例输出:  
> 55  
> 样例输入:  
> 22  
> 样例输出:  
> 7704  
> 数据规模与约定:  
> 1 <= n <= 1,000,000。

*注意：先用递归或者其他方法计算出斐波那契数列值，再对10007取余会超时！*

## 代码： ##

n=int(input())#键盘读入
    F1,F2=1,1
    for i in range(3,n+1):
        F1,F2=F2%10007,(F1+F2)%10007#先取余再递推防止超时
    print(F2)

> 这个世界上根本没有正确的选择，我们只不过是要努力奋斗，使当初的选择变得正确。  
> ———村上春树

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hhcnJ5X19fX19f_size_16_color_FFFFFF_t_70]: /images/20221123/f7bf1e3ac53d4da395f11a703ddd1c25.png
[python]: https://blog.csdn.net/Harry______/article/details/109683177