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

Question

我在 Whosebug 中遇到了 Euler 项目中问题 4 的许多解决方案。我的问题不是再次询问已经在 Whosebug 中实施的项目 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");
}

问题

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;
        }
    }

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。注意这只是一个例子，它甚至可能不会达到这一点。

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

Improved solution of problem 4 from Project euler

java

algorithm

palindrome