递推序列第n项求解算法实现求助

问题根源 #

你的代码存在两个核心错误：

1. 计算顺序错误：在计算a[2*i+1]时，a[2*i+2]还未被赋值（仍是初始的0），导致a[2*i+1]被错误计算，进而a[2*i+2]的结果也完全错误。
2. 递推关系误解：你没有意识到a[2*i+2]本质是第一个递推公式中2*(i+1)的情况，可直接通过a[i+1]+1计算，无需依赖未定义的反向推导。

修正后的代码 #

n = int(input())

# 数组长度设为n+2，确保当n为奇数时能容纳a[n+1]（计算a[n]需要用到）
a = [0] * (n + 2)
a[0] = a[1] = 1

# 先计算所有偶数索引（包括可能的n+1）
max_even = n if n % 2 == 0 else n + 1
for k in range(2, max_even + 1, 2):
    a[k] = a[k // 2] + 1

# 计算所有>=3的奇数索引
for k in range(3, n + 1, 2):
    m = (k - 1) // 2
    # 利用已计算的a[k+1]和第二个递推公式变形得到a[k]
    a[k] = a[k + 1] + a[m]

print(a[n])

验证示例 #

手动计算的序列前几项与代码输出一致：

• a[0] = 1，a[1] = 1
• a[2] = a[1]+1 = 2
• a[3] = a[4]+a[1] = (a[2]+1)+1 = 3+1=4
• a[4] = a[2]+1 =3
• a[5] =a[6]+a[2]=(a[3]+1)+2=5+2=7

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