java - 来自 Project euler 的问题 4 的改进解决方案

Question

我在 StackOverflow 中遇到了 Euler 项目中问题 4 的许多解决方案。我的问题不是再次询问已经在 StackOverflow 中实现的项目 Euler 中问题 4 的解决方案。相反，我遇到了一个改进的解决方案 Improved solution by ROMANIA_engineer .我对改进的解决方案有两个问题。不管怎样，我已经在下面发布了解决方案，供人们研究。

public static void main(String[] args) {

int max = -1;

for ( int i = 999 ; i >= 100 ; i--) {
    if ( max >= i*999 ) { 
        break;
    }
    for (int j = 999 ; j >= i ; j-- ) {             
        int p = i * j;
        if ( max < p && isPalindrome(p) ) {
            max = p;
        }
    }
}       
System.out.println(max > -1? max : "No palindrome found");
}

问题

1. Why there is a condition (max >= i * 999) ?. What are we going to achieve, by including such an inexpensive operation?

从下面的片段中，

for (int j = 999 ; j >= i ; j-- ) {             
        int p = i * j;
        if ( max < p && isPalindrome(p) ) {
            max = p;
        }
    }

2. Instead of j >= 100, it is given j >= i. I can see a lot of time is saved, however, I wanted to know the intention behind it.

Answer 1

回答问题1，之所以有检查(max >= i * 999)是因为你可能已经偶然发现了两个3位数的乘积是回文但大于 i * 999。由于外部 for 循环从 i = 999 开始，一旦找到新的最大值，新的最大值可能大于下一次迭代中递减 i 值的最大可能回文乘积。例如，如果我们找到 926 * 998 的回文乘积，其中 i = 926 和 j = 998，并且新的最大值设置为该乘积。请注意，这只是一个假设，我什至不知道该产品是否是回文。然后内部for循环在迭代i = 926时结束。然后在外部for循环的下一次迭代中，i现在是925，并且由于925 * 999小于926 * 998，因此无需继续寻找最大回文产品，因为它已经被发现。原因是此时 925 * 999 是可以向前计算的最大可能回文乘积。

回答问题2，j>=i的原因是为了避免乘积的重复计算。例如，假设条件是 j >= 100。在内部 for 循环的第一次迭代中，当 j 为 999 且 i 也为 999 时。我们最终可能会计算从 999 * 999、999 * 998 到 999 * 100 的乘积。但是，如果内部for 循环曾经达到 i 现在是 100 并且 j 是 999 的点，那么你最终将重复计算 100 * 999。请注意，这只是一个示例，它甚至可能不会达到这一点。