PE0004: Largest Palindrome Product

Project Euler Problem 4: Largest Palindrome Product

题目

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009=91*99.

Find the largest palindrome made from the product of two 3-digit numbers.

问题描述

题目要求：给定两个三位数，找到它们的乘积中最大的回文数。

解答

方法一：暴力遍历法（新手入门）

思路：生成所有3位数的乘积，逐个检查是否为回文数，记录最大值。

def find_maximum():
    ans= max(
        i*j
        for i in range(100, 1000)
        for j in range(100, 1000)
        if str(i*j) == str(i*j)[::-1]
    )
    return ans

find_maximum()

优点：代码简单，逻辑直观。 缺点：计算次数高达810,000次，效率极低。

方法二

def reverse(n):
    reversed = 0
    while n > 0:
        reversed = reversed * 10 + n % 10
        n = n // 10
    return reversed

def is_palindrome(n):
    return n == reverse(n)

largestPalindrome = 0
a = 100
def palindrome():
    global largestPalindrome, a
    while a < 1000:
        b = 100
        while b < 1000:
            product = a * b
            if is_palindrome(product) and product > largestPalindrome:
                largestPalindrome = product
            b += 1
        a += 1
    return largestPalindrome

reverse()：通过数学方法反转数字，避免字符串转换。

global变量：全局记录最大值，但嵌套循环未优化，计算量仍为810,000次。

方法三：减少重复计算

优化点：内层循环从a开始，避免重复检查i*j和j*i。

largestPalindrome = 0
a = 100
def improved_palindrome():
    global largestPalindrome, a
    while a < 1000:
        b = a  # 从a开始，避免重复
        while b < 1000:
            product = a * b
            if is_palindrome(product) and product > largestPalindrome:
                largestPalindrome = product
            b += 1
        a += 1
    return largestPalindrome

方法四：倒序搜索 + 提前终止

优化点：从999开始倒序搜索，若乘积小于当前最大值则提前终止。

largestPalindrome = 0
a = 100
def optimized_palindrome():
    global largestPalindrome, a
    while a < 1000:
        b = 999  # 从999开始
        while b >= a:
            product = a * b
            if product <= largestPalindrome:
                break  # 提前终止
            if is_palindrome(product):
                largestPalindrome = product
            b -= 1
        a += 1
    return largestPalindrome

break：当product <= largestPalindrome时跳出循环，实际计算约5,000次。

方法五：数学优化

数学原理：若乘积为回文数，至少一个数为11的倍数（仅限6位回文数）

largestPalindrome = 0
a = 999
def further_optimized_palindrome():
    global largestPalindrome, a
    while a >= 100:
        if a % 11 == 0:
            b = 999
            subtract = 1
        else:
            b = 990  # 最大11倍数
            subtract = 11
        while b >= a:
            product = a * b
            if product <= largestPalindrome:
                break
            if is_palindrome(product):
                largestPalindrome = product
            b -= subtract
        a -= 1
    return largestPalindrome

b = 990：当a非11倍数时，b仅取11的倍数，减少候选数。

subtract = 11：步长为11，跳过非11倍数。

方法六：向量化计算

代码逻辑：利用NumPy矩阵运算加速。

import numpy as np
reverse_vec = np.vectorize(reverse)

def is_palindrome_vec(n):
    return n == reverse_vec(n)

def max_palindrome_vec(n):
    num = n[is_palindrome_vec(n)]
    return np.max(num) if np.size(num) > 0 else None

def vectorized_palindrome(n):
    largestPalindrome = 0
    x = np.arange(n//10, n)
    for i in x:
        max_value = max_palindrome_vec(i * x)
        if max_value is not None and max_value > largestPalindrome:
            largestPalindrome = max_value
    return largestPalindrome

答案

答案为906609。