| 蓝桥杯试题入门训练之Fibonacci数列 | 您所在的位置：网站首页 › 斐波那契数列图形python › 蓝桥杯试题入门训练之Fibonacci数列 |
蓝桥杯试题入门训练之Fibonacci数列
|
一、Fibonacci数列-原题描述
资源限制
时间限制：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我们测评一下，看看能得多少分： 针对上面这两种情况，我们做一下改进： Python语句的改进只保留想要的，列表里只存放2个值累加过程中，超过10007时，就减去10007 3. 考虑极端情况，并做相应优化 解决内存超限的问题原来使用append()方法构建一个斐波那契数列时，用一个数组存放它，随着n值的增大，数组占的内存也越来越大。 另一方面，我们只需要第n项的值，所以第n项以前的值都不是我们想要的，所以，我做出如下改进： n = int(input()) F = [1, 1] # 初始数组 if n 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) 即对Fn取余，相当于对 F n − 1 F_{n-1} Fn−1和 F n − 2 F_{n-2} Fn−2各自取余之和再取余用代码实现就是这样： n = int(input()) F = [1, 1] if n |
现在的得分是80分，我们看一下第9个采分点的评测结果是内存超限，第10个是运行错误。说明我们当前的算法还有一些情况没有考虑到：【本文地址】