java – 需要帮助优化解决方案的项目欧拉问题#12

前端之家收集整理的这篇文章主要介绍了java – 需要帮助优化解决方案的项目欧拉问题#12前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
我一直很乐意与Project Euler的挑战,我注意到,我的解决方案12是我的最慢速度,每次跑步达到593.275毫秒.这是我的解决方案第二,在每次穿越〜1254.593毫秒.我所有的其他答案都需要不到3 ms的时间才能在1 ms以内运行.

我的Java解决方Problem 12

主要():

int index = 1;
long currTriangleNum = 1;

while (numDivisors(currTriangleNum) <= 500) {
    index++;
    currTriangleNum += index;
}

System.out.println(currTriangleNum);

numDivisors():

public static int numDivisors(long num) {  
    int numTotal = 0;

    if (num > 1)
        if (num % 2 == 0) {
            for (long i = 1; i * i <= num; i++)
                if (num % i == 0)
                    numTotal+=2;
        } else {
            // halves the time for odd numbers
            for (long i = 1; i * i <= num; i+=2)
                if (num % i == 0)
                    numTotal+=2;
    }
    else if (num == 0)
        return 0;
    else if (num == 1)
        return 1;
    else (num < 0)
        return numDivisors(num *= -1);

    return numTotal;
 }

.

围绕解决方案论坛,有些人发现these formulas(n =(p ^ a)(q ^ b)(r ^ c)…& d(n)=(a 1)(b 1) )…)为他们工作,但我个人不明白它会如何更快;手也可以更快,但不是在程序中.

.

基本思想过程如下:

我们想要计算48个除数的数量.通过查看下面的因子树,我们可以得出结论:48 =(2 ^ 4)(3 ^ 1)[n =(p ^ a)(q ^ b) ^ C)…].

48
 /  \
2   24
   /  \
  2   12
     /  \
    2   06
       /  \
      2    3

知道这一点,我们构造公式d(48)=(4 1)(11)[d(n)=(a 1)(b 1)(c 1)…]来确定48个有10个因素.

d(n)  = (a+1)(b+1)(c+1)...
d(48) = (4+1)(1+1)
d(48) = (5)(2)
d(48) = 10

.

如何优化我的代码?这些公式是最好的解决方案吗?我觉得找到所有的主要因素,然后执行公式将比我已经有的程序需要更长的时间.

非常感谢,

瑞斯蒂昂

编辑:

在任何人开始发布链接之前,我已经在SO中查看了类似的问题,没有任何运气 – 我只是想不到他们的方法的实现会比我已经有了更快的运行.

EDIT2:

我的第二次尝试在Eratosthenes筛选(对于问题10):

int p = 3,n = 2000000;
long total = 0;
boolean[] sieve = new boolean[n];

for (int i = 3; i < n; i += 2)
    sieve[i] = true;

sieve[2] = true;

while (p * p < n) {
    for (int i = p; i < n; i++)
        if (sieve[i] && (i % p) == 0)
            sieve[i] = false;
    p++;

    while (!sieve[p])
        p++;
}

for (int i = 0; i < n; i++)
    if (sieve[i])
        total += i;

System.out.println(total);

运行在〜985.399 ms – 不会比其他方法快得多,但尚未优化.然而,它是有效的.

解决方法

使用基础的数学结构,这将大大改变程序的运行时间.这也适用于问题10,顺便说一下如果你在几毫秒内无法做到这一点,那么你使用了一个非常低效的算法.事实上,我建议你首先处理问题10,因为问题12建立在它上面.

我将为下面的问题12提供一个更好的算法,但首先,这是一个观察结果,应该显着加快你的程序.如果两个数字x和y是互质的(即除1以外没有公约数),则d(x·y)= d(x)·d(y).特别地,对于三角形数,d(n·(n 1))= d(n)·d(n 1).因此,不是迭代三角形数n·(n 1),而是遍历n:这将大大减少传递给d(n)的参数的大小.

如果你做这个优化,你会注意到你连续两次计算d(n)(一次为d((n-1)1),一次为d(n)).这表明缓存d的结果是一个好主意.下面的算法是这样做的,但是也可以自下而上而不是自顶向下地计算,这是更有效的,因为乘法比分解更快.

Problem 10可以通过sieve of Eratosthenes的简单应用来解决.填充大小为2000000的布尔数组(即位向量),以便如果我是素数,则使用筛[i] == true;然后总结筛选[i] == true的数字.

Problem 12可以通过Eratosthenes筛子的泛化来解决.而不是筛选[i]一个布尔值,表示我是否是素数,使它成为一个数字,表示它是非素数的方式的数量,即i的除数的数量.修改Eratosthenes的基本筛子很容易做到这一点:而不是将筛[x * y]设为假,添加1.

几个后续项目欧拉问题受益于类似的方法.

您可能遇到的一个问题是,在问题12中,不清楚何时停止计算筛子.你可以采取两种方式:
1.根据需要通过块计算筛子,本身就是一个有价值的编程练习(这将需要更复杂的代码,第二种方法)
2.或者从高估一个约束开始:找到一个有超过500个除数的三角形数字,你知道你会在那个数字之前或者那个数字上停止.

如果你意识到只需要关心奇数就可以获得更多的时间,因为如果n是奇数,则d(2 ^ k·n)=(k 1)·d(n),并且仅发现k和n 2 ^ k·n)在二进制计算机上是快速的.我会把这个优化的细节作为一个练习.

原文链接:https://www.f2er.com/java/126216.html

猜你在找的Java相关文章