You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

求高效方案:从完美立方列表中找出三不同数和为完美立方的组合

高效实现方法优化思路

你原来的三重循环存在两个核心问题:一是时间复杂度为O(n³),当列表较长时(比如对应6000000以内的立方数,n约181,三重循环要执行约600万次),效率极低;二是没有判断三个数字是否不同,且用numpy.cbrt判断立方数可能存在浮点数精度误差。

下面是几种更高效的优化方案,核心思路是减少循环层数+利用集合快速查找+避免重复计算:

预处理:生成立方数集合与列表

先一次性生成所有符合条件的立方数,同时存入集合(支持O(1)时间查找)和列表,为后续操作打好基础:

max_cube = 6000000
# 计算最大底数,加1避免取整漏掉边界值
max_root = int(max_cube ** (1/3)) + 1
# 生成立方数列表和集合
cubes = [x**3 for x in range(1, max_root)]
cube_set = set(cubes)

方案一:双重循环+集合查找(O(n²)复杂度)

先遍历所有两两不同的立方数对,计算它们的和,再检查是否存在第三个不同的立方数,使得三者之和也是立方数。通过索引范围限制避免重复计算:

result_sums = set()  # 用集合存结果,自动去重

for i in range(len(cubes)):
    a = cubes[i]
    # 从i+1开始遍历,避免重复计算a和b的组合(比如a=1,b=8与a=8,b=1)
    for j in range(i+1, len(cubes)):
        b = cubes[j]
        sum_ab = a + b
        # 目标立方数d³必须大于sum_ab(因为c是正立方数)
        min_d = int(sum_ab ** (1/3)) + 1
        for d in range(min_d, max_root):
            d_cube = d ** 3
            c = d_cube - sum_ab
            # 检查c是立方数,且与a、b都不同,同时c>b保证三元组唯一不重复
            if c in cube_set and c != a and c != b and c > b:
                result_sums.add(d_cube)

# 输出排序后的结果
for s in sorted(result_sums):
    print(s)

方案二:反向遍历目标立方数(进一步减少无效计算)

先遍历所有可能的目标立方数d³,再找两个不同的立方数a、b,使得d³ - a - b也是一个不同的立方数,同时通过提前break跳过无效循环:

result_sums = set()

for d_cube in cubes:
    for i in range(len(cubes)):
        a = cubes[i]
        if a >= d_cube:
            break  # a已大于等于目标和,后续b更大,a+b必然超过d_cube,直接跳出
        for j in range(i+1, len(cubes)):
            b = cubes[j]
            sum_ab = a + b
            if sum_ab >= d_cube:
                break  # a+b已超过目标和,后续b更大,无需继续
            c = d_cube - sum_ab
            # 检查c是立方数且与a、b都不同
            if c in cube_set and c != a and c != b:
                result_sums.add(d_cube)

for s in sorted(result_sums):
    print(s)

额外优化细节

  1. 去重处理:用集合存储最终结果,自动过滤不同三元组产生的相同和。
  2. 精度规避:用集合查找代替浮点数立方根判断,彻底避免精度误差。
  3. 循环剪枝:通过索引范围限制和提前break,跳过大量无需计算的无效情况。

内容的提问来源于stack exchange,提问作者Aayan Shaikh

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.07.25 14:27:10