python - 找到 2 个 3 位数字乘法的最大回文数限制

Question

为什么下面的代码停在回文值：580085，而问题的正确答案是906609这个乘法的结果：993*913

    #!/usr/bin/env python
    # Find the largest palindrome made from the product of two 3-digit numbers.

    # Reverse algorithm
    def flipNumber( number ):
        nmbList     = list(str(number))

        i           = len( nmbList )
        reverseList = list()

        # reverse the list
        for x in nmbList:
            reverseList.append( nmbList[i-1] )
            i -= 1

        # join list items to one number & cast it to integer
        return int(''.join(reverseList))


    # Figure out if numbers are palindrome
    def isPalindrome( number ):
        return number == flipNumber( number )

    def multiplyRun(  ):
        for i in range( 100, 999 ):
            for y in range( 100, 999 ):
                if isPalindrome( i * y ):
                    maxPalind = i * y

        return maxPalind

    # simple tests
    # print( flipNumber( 90819 ) )
    # print( isPalindrum( 9009, 9009 ) )
    # print( isPalindrum( 9109, 9009 ) )
    # print( isPalindrum( 9009, 9019 ) )
    # print( isPalindrum( 9019, 9019 ) )
    # print( isPalindrum( 9119, 9119 ) )

    print(multiplyRun(  ))

如果我在第二个 for 循环中将第二个 100 更改为 600（或更高），我会得到正确的结果。真是令人难以置信，因为这些嵌套循环应该跨越所有范围......我做错了什么！？（可能是我没有看到的非常愚蠢的东西..）

Answer 1

你没有验证你有一个更大的回文。

580085 是 995 * 583。所以如果你从 600 开始你不会发现这个，但它低于理想的解决方案，并且比实际解决方案更高。

Answer 2

这是找到回文的更好方法：

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

Answer 3

正如 Guvante 所说，您正在查看两个因素（995 和 583）是否更大，而不是最终回文是否更大。

正确的代码是：

def multiplyRun(  ):
    for i in range( 100, 999 ):
        for y in range( 100, 999 ):
            if isPalindrome( i * y ):
                if i * y > maxPalind:
                    maxPalind = i * y

    return maxPalind

Answer 4

我认为没有蛮力的解决方案。

public long solveBestSolution(int nbChiffre) 
{
long chiffreMax = (long)Math.pow(10, nbChiffre);    
// Tip 1 : 111 * 111 is a palindrome
long chiffreMin = 1111111111111111111L % chiffreMax;
long max = chiffreMin * chiffreMin -1;

    // Tip2 : Take j >= i
    for (long i = chiffreMax - 1 ; i >= chiffreMin; i--) {
        for (long j = chiffreMax - 1; j >= i; j--) {
            long res = j * i;
            if(res > max)
            {
                if(this.checkPalindrome(res))
                {
                    max = res;
                }
            }
            else
            {
                // Tip 3
                break;
            }
        }
    }

    return max;
}