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

  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) #直接输出余数,不用除法

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

跑通很简单,但是要拿满分的话,还是有一定挑战的

  刚拿到题目的时候,我不太明白为什么要除以一个数才能得到其余的。现在看来,取余数是拿满分的关键。

  不仅仅是代码的编写,还有解决问题的思路,都需要一定的数学基础。

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