Fibonacci序列判断与halves函数代码隐藏测试失败求助

问题描述 #

我正在解决两个编程问题：

1. 定义谓词isFib，给定一个正整数，验证该数是否属于Fibonacci序列（序列为1, 1, 2, 3, 5, 8…，满足F(n) = F(n-1) + F(n-2)）；
2. 必须递归实现函数halves，接收两个正整数a和b，返回包含a（转换为float类型）以及所有大于b的a的连续半值的降序列表。

已编写的代码 #

1. isFib函数 #

def isFib(n):
    num1 = 1
    num2 = 1
    while True:
        if num2 <= n:
            if num2 == n:
                return True
            else:
                tempnum = num2
                num2 += num1
                num1 = tempnum
        else:
            return False

2. halves函数 #

def halves(a, b):
    a > 0 and b > 0
    if a//1 != a or b//1 != b or b == 0:
        return None
    halves = []
    while a > b:
        halves.append(a)
        a = a/2
    return [float(x) for x in halves]

测试情况 #

我自己的测试用例输出符合预期：

• 测试：print(halves(100,3))（注：原测试中写的metades是笔误，实际应为halves）
  输出：[100.0, 50.0, 25.0, 12.5, 6.25, 3.125]
• 测试：print(halves(1,3))
  输出：[]
• 测试：print(halves(32,2))
  输出：[32.0, 16.0, 8.0, 4.0]

但系统提示代码“未通过一个或多个隐藏测试”，需要排查原因。

问题排查 #

一、halves函数的核心问题：未按要求递归实现 #

题目明确要求递归实现halves，但你写的是迭代版本（用while循环），这是导致隐藏测试不通过的最可能原因。

除此之外，还有几个小问题：

1. 无效的参数校验代码：第一行a > 0 and b > 0只是做了判断，没有任何实际作用，应该整合到后续的校验逻辑里。
2. 参数校验逻辑不严谨：用a//1 != a判断是否为整数，无法区分100（int）和100.0（float），但题目要求接收正整数，应该明确判断输入是否为int类型且大于0。
3. 变量名冲突：函数内部用halves = []覆盖了函数名，虽然不影响当前逻辑，但属于不良编程习惯，建议改为result之类的名称。
4. 冗余的类型转换：先append整数a，最后再统一转float，不如直接在append时转为float更高效。

修正后的递归版halves函数

def halves(a, b):
    # 校验输入是否为正整数
    if not (isinstance(a, int) and isinstance(b, int) and a > 0 and b > 0):
        return None
    # 基线条件：当前a不大于b，返回空列表
    if a <= b:
        return []
    # 递归逻辑：当前a转float，加上后续半值的结果
    return [float(a)] + halves(a / 2, b)

二、isFib函数的潜在问题 #

当前isFib的逻辑是对的，但存在效率问题：当n极大时，循环会非常耗时。可以用斐波那契数的数学性质优化：一个数x是斐波那契数，当且仅当5x²+4或5x²-4是完全平方数。

优化后的isFib函数

import math

def isFib(n):
    if n <= 0:
        return False
    # 利用数学判定规则
    x = 5 * n * n + 4
    y = 5 * n * n - 4
    sqrt_x = math.isqrt(x)
    sqrt_y = math.isqrt(y)
    return sqrt_x * sqrt_x == x or sqrt_y * sqrt_y == y

这个版本能瞬间处理极大的n，避免循环带来的性能问题，也能覆盖所有边界情况。

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