Python实现递推序列第n项遇问题：小n有效大n结果错误求修正

原代码的核心问题是循环次数计算错误，导致递推的项数和目标n不匹配，同时存在变量未定义的风险（比如n=1/2时），多余的特殊处理也没必要。

错误点拆解 #

1. 循环逻辑错位：range(n//2-1)的计算方式无法对应到目标项Uₙ，比如n=5时，循环仅执行1次，最终得到的s是U₃，但实际U₅需要基于U₄和U₃计算，原代码没有覆盖到这一步。
2. 变量作用域问题：当n≤2时，循环不会执行，s和t未定义，直接打印会触发报错。
3. 冗余的特殊处理：n=3的结果可以通过正常递推得到，无需单独判断。

修正方案一：基础递推版（逻辑直观，适合小n） #

直接从第3项开始，逐项递推到第n项，逻辑清晰不易出错：

n = int(input())
if n == 1 or n == 2:
    print(1)
else:
    u_prev_prev = 1  # U₁
    u_prev = 1        # U₂
    for i in range(3, n+1):
        u_current = u_prev - 2 * u_prev_prev
        # 更新前两项，为下一次循环准备
        u_prev_prev, u_prev = u_prev, u_current
    print(u_prev)

修正方案二：快速幂优化版（适合极大n，时间复杂度O(logn)） #

如果n非常大（比如1e18），基础递推效率太低，可以用矩阵快速幂优化递推过程：

def matrix_mult(a, b):
    # 计算2x2矩阵乘法
    return [
        [a[0][0]*b[0][0] + a[0][1]*b[1][0], a[0][0]*b[0][1] + a[0][1]*b[1][1]],
        [a[1][0]*b[0][0] + a[1][1]*b[1][0], a[1][0]*b[0][1] + a[1][1]*b[1][1]]
    ]

def matrix_pow(mat, power):
    # 矩阵快速幂
    result = [[1,0], [0,1]]  # 单位矩阵
    while power > 0:
        if power % 2 == 1:
            result = matrix_mult(result, mat)
        mat = matrix_mult(mat, mat)
        power = power // 2
    return result

n = int(input())
if n == 1 or n == 2:
    print(1)
else:
    # 递推关系对应的变换矩阵：[Uᵢ, Uᵢ₋₁] = [Uᵢ₋₁, Uᵢ₋₂] * [[1, 1], [-2, 0]]
    transform_mat = [[1, 1], [-2, 0]]
    mat_powered = matrix_pow(transform_mat, n-2)
    # 初始向量是[U₂, U₁] = [1, 1]，相乘后取第一个元素就是Uₙ
    u_n = mat_powered[0][0] * 1 + mat_powered[0][1] * 1
    print(u_n)

内容的提问来源于stack exchange，提问作者Codeer