如何推导给定数列第n项通项公式,替代循环避免竞赛超时?
数列闭式通项公式推导
原递推逻辑梳理
原代码的循环执行规则和题目给出的数列完全对应:
- 初始状态(循环0次):
a₀ = 5 - 单次循环的递推规则:
aₖ = 2 * aₖ₋₁ + 2
逐次计算的结果依次为5、12、26、54、110、222、446,和题目给出的序列完全匹配。
闭式公式推导
通过凑等比数列的方式可以快速推导无需循环的通项:
- 对递推式变形,等式两侧同时加2:
aₖ + 2 = 2 * (aₖ₋₁ + 2) - 构造新数列
bₖ = aₖ + 2,代入后递推关系简化为标准等比数列:bₖ = 2 * bₖ₋₁,公比为2 - 计算新数列初始值:循环0次时
a₀=5,因此b₀ = 5 + 2 =7 - 根据等比数列通项公式,
bₖ = b₀ * 2ᵏ =7 * 2ᵏ,反向代回即可得到原数列通项:aₖ = 7*2ᵏ -2
可直接替换循环的实现
将原循环逻辑直接替换为O(1)时间复杂度的公式计算:
# 原循环实现(时间复杂度O(n),n过大时会超时) x = 5 for i in range(n): x = x * 2 + 2 # 替换为闭式公式实现(时间复杂度O(1),无超时风险) x = 7 * (2 ** n) - 2
公式校验
逐一代入数列项验证准确性:
- n=0:
7*1 -2 =5,匹配初始值 - n=1:
7*2 -2 =12,匹配数列第二项 - n=3:
7*8 -2 =54,匹配数列第四项 - n=6:
7*64 -2 =446,匹配数列最后一项
公式计算结果和循环迭代结果完全一致,适用于任意大的n值。
内容的提问来源于stack exchange,提问作者Peter Kováč
相关产品推荐
相关产品推荐

