时间限制：1.0s 内存限制：256.0MB
想要拿满分的话，资源限制一定要特别注意！
（一个限制点10分）
Fibonacci数列的递推公式为： F n = F n − 1 + F n − 2 F_n=F_{n-1}+F_{n-2} Fn=Fn−1+Fn−2，其中 F 1 = F 2 = 1 F_1=F_2=1 F1=F2=1。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
输入格式输入包含一个整数n。
输出格式输出一行，包含一个整数，表示Fn除以10007的余数。
二、解题思路 1. 先将问题简化，读懂题目并找到解题方法Fibonacci数列即斐波那契数列，这个数列从第3项开始，每一项都等于前两项之和。
用一个表格直观地展示一下斐波那契数列：
n123456789F(n)112358132134这道题的意思就是给定一个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-1} + F_{n-2} Fn=Fn−1+Fn−2 ，现在要对 F n F_n Fn取余， 根据上述取余运算的公式，( F n F_n Fn % x)可以等价于(( F n − 1 F_{n-1} Fn−1 % x + F n − 2 F_{n-2} Fn−2 % x) % x)
用代码实现就是这样：
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 三、总结与升华这题是蓝桥杯入门训练的第一题，做之前，我觉得很简单。确实，跑通很简单，但是要拿满分的话，还是有一定挑战的。
刚开始拿到题目时，我不太理解为什么要除以一个数取其余数，现在看来，取余数是拿满分的关键所在。
不光是代码的编写，解题的思路也很重要，还需要一定的数学基础。