题解 | #牛牛的Fib序列#
牛牛的Fib序列
http://www.nowcoder.com/practice/8fc8fa4c7b084f2bbcfb6d09df4f4838
牛牛的Fib序列
描述
牛牛重新定义了斐波那契数列，牛牛定义f(n) = f(n-1)+f(n+1); f(1)=a, f(2)=b， 现在给定初始值 a, b，现在求第n项f(n)%1000000007的值。其中 1<=|x|, |y|, n<=10^9
示例
牛牛重新定义了斐波那契数列，牛牛定义f(n) = f(n-1)+f(n+1); f(1)=a, f(2)=b， 现在给定初始值 a, b，现在求第n项f(n)%1000000007的值。其中 1<=|x|, |y|, n<=10^9
示例
输入：1,2,3
返回值：1
说明：f(2)=f(3)+f(1), 所以f(3) = f(2)-f(1)=2-1=1
方法一
思路分析
首先我们可以根据常规解法，利用求解斐波那契数列的思想求解本题，不过首先需要根据题目中所给的推导公式，从而得出函数的推导公式，推导过程如下：
根据推导公式得到函数的递推公式，根据递推公式写出代码。不过由于超出内存限制无法通过
核心代码
# # # @param a int整型 # @param b int整型 # @param n int整型 # @return int整型 # class Solution: def solve(self, a, b, n): mod=1000000007 array=[0 for i in range(n)] array[0]=a; array[1]=b; for i in range(2,n): array[i]=array[i-1]-array[i-2] return array[n%6-1]%mod复杂度分析
- 时间复杂度：时间复杂度为$O(n)$
- 空间复杂度：空间上需要的额外空间$O(n)$
方法二
思路分析
通过推到可以得到所给的函数是一个周期函数，具体的推导过程如下。
图解+推导过程
核心代码
# # # @param a int整型 # @param b int整型 # @param n int整型 # @return int整型 # class Solution: def solve(self, a, b, n): array=[a,b,b-a,-a,-b,a-b] return array[n%6-1]%1000000007
复杂度分析
- 时间复杂度：由题目可推导出函数是一个周期函数，因此在常数时间内计算得到周期内的函数结果，总的时间复杂度为$O(1)$
- 空间复杂度：使用的额外空间为常数级的$O(1)$