fibonacci数列是这样定义的,fibonacci数列1,1,2,3,5,8,13c语言

　　1.斐波那契数列——原题描述资源限制时间限制：1.0s内存限制：256.0MB

想要拿满分的话，资源限制一定要特别注意

　　(一个极限点10分)

　　斐波那契数列的递推公式为：f n=f n 1 f 2 f n=f _ { n-1 } f _ { n-2 } fn=fn1fn 2，其中f 1=f 2=1 f 1=f 2=1f1=f2=1。

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

　　输入格式输入包含一个整数n。

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

　　二、解题思路1。先把问题简单化，看题目，找解题方法。斐波那契数列是

斐波那契数列

。这个序列从第三项开始，每一项等于前两项之和。

　　使用表格直观显示斐波纳契数列：

　　N123456789F(n)112358132134这个问题的意思是给定一个n，求这个数列的第n项除以某个数的余数。

　　例如，假设n为7，除数为2，输出为1，以简化问题。其实我们可以先忽略除数，在最后输出之前只做除法。因此，当前的问题可以简化为：

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

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

　　2.用代码运行简化的问题。我们只需要构造一个斐波那契数列，这个想法非常简单：

　　N=int(input()) #用n项构造的斐波那契数列F=[1，1] #斐波那契数列的前两个值对于范围内的项是固定的(n): # f.append (f [item] f [item 1]) #下一项的值等于前两项的和print (f [n-1]

　　现在分数是80。我们来看看第9个采样点的评测结果，是内存溢出，第10个是运行错误。这表明在我们当前的算法中还存在一些没有考虑的情况：

　　值太大可能是测试用例输入造成的，列表中数据太多导致内存溢出；另一方面，如果输入值太大，可能会出现计算错误。针对以上两种情况，我们来做一些改进：

　　Python语句的改进，只保留自己想要的，列表中只存储两个值。在累加的过程中，超过10007时，就减去10007。3.考虑极端情况，做相应优化，解决内存溢出问题。当您使用append()方法构建斐波那契数列时，您使用了一个数组来存储它。随着n值的增加，数组占用的内存越来越大。

　　另一方面，我们只需要第n项的值，所以第n项之前的值并不是我们想要的。所以，我做了以下改进：

　　N=int(input())F=[1，1] # initial array if n=2: # n当n的值较小时，对于范围内的项(n):F . append(F[item]F[item 1])print(F[n-1]007)else:#当n大于2时，数组中只保留范围(n-2)中item的n的前两项：result=f [0] f [1] #前两项相加得到下一项的值，F[0]=F[1] #整个数组向后移动，F[1]=result #在第二个位置保存运行结果后print(result007)为了解决内存溢出的问题

　　这时候还有最后一个采样点：运行时间。

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

　　我们可以把这两个代码：

　　F[0]=F[1]F[1]=结果缩写为代码：

　　F[0]，F[1]=F[1]，结果然而，这种方法不能减少太多的运行时间。让我们考虑其他方法。

　　提到题目要除以10007，在累加的过程中，超过10007就要减去10007。这不会影响其余部分。这是它在代码中的实现方式：

　　IF 10007: result=result-10007这样的效果是有的，但是解决不了运行超时的问题。

　　这时，让我们来看看盈余提取操作：

　　斐波那契数列的递推公式是f n=f n 1 f 2 f n=f _ { n-1 } f _ { n-2 } fn=fn1fn 2。现在，我们要取f n f _ fn的余数。根据上面的余数运算公式，(F n F_n Fn% x)可以等价于((f n 1 f _ {

　　也就是说，取Fn的余数相当于取FN1F _ {n-1} FN1和FN2F _ {n-2} FN2各自余数之和，再取余数。这是代码实现：

　　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]007)else: for item in range(n-2):result=(F[0]f[1])% 10007 #计算完下一项后直接取余数，不影响结果f[0]，f [1]=f [1]，结果print (result) #直接输出余数，不用除法

　　三。总结与升华这个问题是蓝桥杯入门培训的第一个。做之前，我觉得很简单。确实，