面试Gibonacci数列问题求解咨询（附尝试代码）

问题核心错误 #

你的代码存在两个关键问题：

1. 递推逻辑不符合题目定义：没有根据n的奇偶性选择对应的加减规则，统一使用了减法；
2. 循环范围错误：range(2, n)会导致无法计算到第n项，比如当n=2时循环不会执行，直接返回第二项而非计算后的结果。

根据题目中Gibonacci数列的定义：

• G(0) = x
• G(1) = y
• 当n为偶数且n>1时，G(n) = G(n-1) + G(n-2)
• 当n为奇数且n>1时，G(n) = G(n-1) - G(n-2)

修正后的实现 #

空间优化版（推荐） #

不需要存储整个序列，仅维护前两项的值即可，空间复杂度O(1)：

def gibonacci(n, x, y):
    if n == 0:
        return x
    elif n == 1:
        return y
    a, b = x, y
    for i in range(2, n + 1):
        if i % 2 == 0:
            c = b + a
        else:
            c = b - a
        a, b = b, c
    return b

保留序列存储的版本 #

如果需要保留整个数列的记录，修正循环范围和递推逻辑：

def gibonacci(n, x, y):
    if n == 0:
        return x
    elif n == 1:
        return y
    sequence = [x, y]
    for i in range(2, n + 1):
        if i % 2 == 0:
            next_term = sequence[i-1] + sequence[i-2]
        else:
            next_term = sequence[i-1] - sequence[i-2]
        sequence.append(next_term)
    return sequence[-1]

验证示例 #

以x=0, y=1为例：

• n=2（偶数）：G(2)=1+0=1，修正代码返回1；
• n=3（奇数）：G(3)=1-1=0，修正代码返回0；
• n=4（偶数）：G(4)=0+1=1，修正代码返回1；
• n=5（奇数）：G(5)=1-0=1，修正代码返回1；

以上结果完全符合题目定义的递推规则。

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