Posts pythonTip 83 Py的函数I
Post
Cancel

pythonTip 83 Py的函数I

题目描述: 要过年了,Py闲着无聊,自己定义了一个函数F(n)=3*F(n-1)+2*F(n-2)+1,定义F(0)=1,F(1)=3. 现在给你一个整数n(0 <= n <= 1000),请你计算F(n).由于这个值可能会非常大, 因此请你输出F(n)取模20132013之后的结果。

示例: 输入: n = 5 输出: 549

分析: 因为 0 <= n <= 1000。 数据量不是很大,所以直接模拟。数据量多大算是大呢? 一半而言初略估计一下超过时间复杂度超过 10^9, 就放弃了。

例如 时间复杂度为O(n^2) 那么当 n > 10000时,我就觉得,算法不行。

代码:

1
2
3
4
5
6
7
ans = [1, 3]

for i in range(2, n+1):
    r = (3 * ans[i-1] +  2 * ans[i-2] + 1) % 20132013
    ans.append(r)

print(ans[n])
This post is licensed under CC BY 4.0 by the author.
Trending Tags
Contents

pythonTip 82 数字漩涡

pythonTip 84 Py的函数II

Trending Tags