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

s326280

对于 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");
}

问题

  1. 为什么有条件 (max >= i * 999) ?。通过包括这样一个廉价的操作,我们将要实现什么?

从下面的片段,

for (int j = 999 ; j >= i ; j-- ) {             
        int p = i * j;
        if ( max < p && isPalindrome(p) ) {
            max = p;
        }
    }
  1. 取而代之的j >= 100j >= i我可以看到节省了很多时间,但是,我想知道它背后的意图。
Chris Gong

回答问题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] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

Project Euler 问题 4 的错误解决方案

需要帮助来优化Project Euler问题#12的解决方案

我在 C++ 中对 Project Euler 的 #2 的解决方案有什么问题?

我对Euler Project#3的解决方案太慢

Haskell Wiki上的Euler Project#2解决方案

解决项目Euler#4的问题

Python似乎正在缓慢解决Project Euler问题#21

需要帮助解决Project Euler问题#35 python吗?

Project-Euler-问题20

我对Euler 17项目的解决方案出了什么问题?

如何使该Project Euler解决方案在Python中以与Java相同的速度执行?

Project Euler解决方案9代码无法正常工作

Haskell-Project Euler 4

为什么我的问题 2(项目 euler)的 JavaScript 解决方案在控制台上显示无穷大?

为什么此问题中的4遍解决方案的性能比1遍解决方案的性能更快?

Project Euler#4算法的可能优化

我的 Project Euler 程序 4 的 java 代码有什么问题?(找出 2 个 3 位数字的最大回文数)

UEFI解决方案问题

.NET 4 / Crystal Reports问题还有其他解决方案吗?

Ruby Project Euler 26,想不出问题的答案

Project Euler 问题的 JavaScript 结果不正确

Project Euler 问题 #1 - 没有得到正确答案

Project Euler 问题 - 1 没有返回我期望的值

来自 MATLAB 的简单 MLE 解决方案

项目Euler#3-解决方案永远运行

项目Euler解决方案8,需要说明

Java中的项目Euler 23-接近解决方案

Project Euler问题8,用C语言编写(适用于4位数字,不适用于13位)

PROJECT EULER P4 无法得到答案