对于 Euler 项目中的问题 4,我在 StackOverflow 中遇到了许多解决方案。我的问题不是再次询问已经在 StackOverflow 中实现的 Euler 项目中问题 4 的解决方案。相反,我遇到了一个改进的解决方案改进的解决方案 由 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");
}
问题
- 为什么有条件 (max >= i * 999) ?。通过包括这样一个廉价的操作,我们将要实现什么?
从下面的片段,
for (int j = 999 ; j >= i ; j-- ) {
int p = i * j;
if ( max < p && isPalindrome(p) ) {
max = p;
}
}
- 取而代之的
j >= 100
是j >= i
。我可以看到节省了很多时间,但是,我想知道它背后的意图。
回答问题1,之所以有支票,(max >= i * 999)
是因为你可能已经偶然发现了一个回文但大于的两个三位数的乘积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
。当 j 是 999 并且 i 也是 999 时,在内部 for 循环的第一次迭代中。我们最终可能会计算从 999 * 999、999 * 998 一直到 999 * 100 的乘积。但是,如果内部for 循环曾经达到过 i 现在是 100 并且 j 是 999 的点,然后您最终将重复计算 100 * 999。请注意,这只是一个示例,它甚至可能达不到这一点。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句