如何正确查找两个三位数乘积中的最大回文数

雨墨吖_2528

发布时间：2026-02-18 15:25:00

303人浏览过

来源于php中文网

原创

如何正确查找两个三位数乘积中的最大回文数

本文解析两段用于求解“两个三位数乘积中最大回文数”的python代码差异，指出第二段代码逻辑缺陷在于未维护最大值状态，仅保存最后一个回文结果；并提供修正方案与优化建议。

本文解析两段用于求解“两个三位数乘积中最大回文数”的python代码差异，指出第二段代码逻辑缺陷在于未维护最大值状态，仅保存最后一个回文结果；并提供修正方案与优化建议。

在欧拉计划第4题中，目标是找出由两个三位数相乘得到的最大回文数（如 9009 = 91 × 99）。看似结构相似的两段代码，却产生截然不同的结果——第一段输出正确答案 906609，而第二段通常输出更小的回文（如 580085 或其他非最大值）。根本原因不在于语法错误，而在于算法逻辑的设计缺陷。

? 核心问题：状态管理缺失

第一段代码使用变量 highest 持续追踪当前找到的最大回文：

highest = 0
# ...
if PalDetect(product) and (product > highest):
    highest = product  # ✅ 仅当更大时才更新

这是一种典型的“贪心更新”策略：遍历所有乘积，只保留满足「是回文且严格大于当前记录」的值，最终 highest 必然收敛至全局最大值。

第二段代码则仅用 product 存储最新匹配的回文：

if PalDetect(i*j):
    product = i*j  # ❌ 无条件覆盖，丢失历史最大值信息

由于嵌套循环按 i（外层）和 j（内层）升序执行（100→999），最后被赋值的回文对应的是 i=999, j=999 附近某组解——但该解未必是回文，更未必是最大。实际上，程序会持续覆盖 product，最终输出的是循环结束前最后一次触发 PalDetect 的乘积，而非最大值。

✅ 正确实现：明确状态语义 + 边界优化

以下是修复后的健壮版本，融合了逻辑清晰性与基础性能优化：

def is_palindrome(n):
    s = str(n)
    return s == s[::-1]

max_palindrome = 0
# 优化：避免重复计算（i*j 与 j*i 等价），且从大到小遍历可提前剪枝
for i in range(999, 99, -1):
    for j in range(i, 99, -1):  # j ≤ i 避免重复；从 i 开始保证 j 不超 i
        product = i * j
        if product <= max_palindrome:  # 剪枝：若已小于当前最大值，跳过
            break
        if is_palindrome(product):
            max_palindrome = product

print(max_palindrome)  # 输出：906609

? 关键改进说明：

变量命名 max_palindrome 比 highest 更具语义准确性；

外层 i、内层 j 均降序遍历，使较大乘积优先被检查，配合 product

j 从 i 开始而非 100，消除 i×j 与 j×i 的冗余计算（因乘法交换律）；

将回文判断封装为独立函数 is_palindrome()，提升可读性与复用性。