一、Fibonacci数列-原题描述

资源限制

时间限制：1.0s 内存限制：256.0MB

想要拿满分的话，资源限制一定要特别注意！
（一个限制点10分）

问题描述

Fibonacci数列的递推公式为：$F_n=F_{n-1}+F_{n-2}$，其中$F_1=F_2=1$。

当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。

输入格式

输入包含一个整数n。

输出格式

输出一行，包含一个整数，表示Fn除以10007的余数。

二、解题思路

1. 先将问题简化，读懂题目并找到解题方法

Fibonacci数列即斐波那契数列，这个数列从第3项开始，每一项都等于前两项之和。

用一个表格直观地展示一下斐波那契数列：

n	1	2	3	4	5	6	7	8	9
F(n)	1	1	2	3	5	8	13	21	34

这道题的意思就是给定一个n，求这个数列的第n项除以某一个数的余数。

• 举个例子，假设n为7，除数是2，则输出为1

将问题化简，我们其实可以先不考虑除数，只需要在最后输出之前除就可以了 ，所以，现在的问题可以化简为：

• 求斐波那契数列某一项具体的值

明确目标以后，我们就可以来编写代码了，这里我选择Python

2. 用代码跑通简化后的问题

我们只需要构造一个斐波那契数列就可以了，思路也非常简单：

n = int(input()) # 构造有n项的斐波那契数列
F = [1, 1] # 斐波那契数列前两个值是固定的
for item in range(n): #
	F.append(F[item] + F[item + 1]) # 下一项的值等于前两项相加
	
print(F[n - 1]%10007) #将第n项对应的值取出并除10007

我们测评一下，看看能得多少分：

现在的得分是80分，我们看一下第9个采分点的评测结果是内存超限，第10个是运行错误。说明我们当前的算法还有一些情况没有考虑到：

• 数值过大可能是测试用例的输入很大导致的，列表中数据太多导致内存超限；
• 另一方面，输入数值过大，有可能会发生计算错误的情况。

针对上面这两种情况，我们做一下改进：

• Python语句的改进
• 只保留想要的，列表里只存放2个值
• 累加过程中，超过10007时，就减去10007

3. 考虑极端情况，并做相应优化

解决内存超限的问题

原来使用append()方法构建一个斐波那契数列时，用一个数组存放它，随着n值的增大，数组占的内存也越来越大。

另一方面，我们只需要第n项的值，所以第n项以前的值都不是我们想要的，所以，我做出如下改进：

n = int(input())
F = [1, 1] # 初始数组
if n <= 2: # n值较小时
    for item in range(n):
        F.append(F[item] + F[item + 1])
    print(F[n - 1]%10007)
else: # n大于2时，数组内只保留n的前两项
    for item in range(n - 2):
        result = F[0] + F[1] # 前两项相加得到下一项的值
        F[0] = F[1] # 数组整体后移
        F[1] = result # 将运行结果保存在第二个位置
    print(result%10007)

解决内存超限的问题后，就可以拿到90分了：

这时还剩下最后一个采分点：运行时间

解决运行超时的问题

减少运行时间，一方面可以优化我们的程序代码，另一方面就是找到题目深层次的数学规律。

我们可以将这两句代码：

F[0] = F[1]
F[1] = result

缩写成一句代码：

F[0], F[1] = F[1], result

不过，这样的做法不能将运行时间降低太多，我们再考虑其他的方法。

题目提到要除以10007，而累加过程中，超过10007时就减去10007，这样做不影响余数。用代码实现起来就是这样：

if result > 10007:
    result = result - 10007

这样做的效果是有的，但是也不能解决运行超时的问题。

这时我们看一下取余的操作：
  斐波那契数列的递推公式为$F_n=F_{n-1}+F_{n-2}$ ，现在要对$F_n$取余， 根据上述取余运算的公式，($F_n$ % x)可以等价于(($F_{n-1}$ % x + $F_{n-2}$ % x) % x)

• 即对Fn取余，相当于对$F_{n-1}$和$F_{n-2}$各自取余之和再取余

用代码实现就是这样：

n = int(input())
F = [1, 1]
if n <= 2:
    for item in range(n):
        F.append(F[item] + F[item + 1])
    print(F[n - 1]%10007)
else:
    for item in range(n - 2):
        result = (F[0] + F[1]) % 10007 # 计算出下一项后直接取余数，不影响结果 
        F[0], F[1] = F[1], result
    print(result) # 直接输出余数，不需要再除10007

三、总结与升华

这题是蓝桥杯入门训练的第一题，做之前，我觉得很简单。确实，跑通很简单，但是要拿满分的话，还是有一定挑战的。

刚开始拿到题目时，我不太理解为什么要除以一个数取其余数，现在看来，取余数是拿满分的关键所在。

不光是代码的编写，解题的思路也很重要，还需要一定的数学基础。