PE0004: 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。