Java-为什么我的代码没有产生正确的结果？

Question

我正在解决 ProjectEuler 的问题 4:

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.

我无法正确理解。这是我的代码:

public static long reverseNumber(long number){
    long reversed = 0;

    while(number != 0) {
        long digit = number % 10;
        reversed = reversed * 10 + digit;
        number /= 10;
    }
    return reversed;
}

long sum,finalSum=1,revSum;
for (int i=100;i<1000;i++){
    for (int j=100;j<1000;j++){               
        sum=i*j;
        revSum=reverseNumber(sum);
        if (sum==revSum){
            finalSum=sum;
        }
    }
}
System.out.println(finalSum);

这是我在网上找到的一些代码，它运行得很好:

int maxPalin = -1;
for (int i = 100; i < 1000; i++) {
    for (int j = 100; j < 1000; j++) {
        int prod = i * j;
        if (prod > maxPalin){
            if (reverseNumber(prod)>maxPalin) {
                maxPalin = prod;
            }
        }
    }
}
System.out.println(Integer.toString(maxPalin));

但是我的有什么问题吗？

Answer 1

目标是找到最大回文数，它是 100 到 999 之间两个数字的乘积。代码的问题是您假设找到的最后一个回文数是最大的。这个假设是错误的。

对于您找到的每个回文，您应该检查它是否大于您找到的最后一个回文，然后再选择它作为最大回文的候选者。

顺便说一句，您发布的第二个代码段也是不正确的，因为它实际上并没有检查当前产品是否是回文(即 prod==reverseNumber(prod))。

正确的实现是:

public static void maxp () {
    int maxPalin = -1;
    for (int i = 100; i < 1000; i++) {
        for (int j = 100; j < 1000; j++) {
            int prod = i * j;
            if (reverseNumber(prod) == prod && prod > maxPalin) {
                maxPalin = prod;
            }
        }
    }
    System.out.println(maxPalin);
}

您的代码返回的回文不是最大回文(995 和 583 的乘积):

580085

第二个片段返回一个根本不是回文的数字:

980099

正确答案是 913 和 993 的乘积:

906609

您的实现未找到它，因为您用稍后迭代中发现的回文覆盖了它，该回文是较高的 i 与较小的 j 的乘积。