3

我一直在尝试解决Project Euler 中的问题 20 ：

嗯！表示 n (n 1) ... 3 * 2 * 1 例如，10！= 10 * 9 ... 3 * 2 * 1 = 3628800，以及数字 10 中的数字之和！是 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27。求数字 100 中的数字之和！

这是我到目前为止想出的。我已经用这段代码得到了正确的答案（648），但是我有点 OC，因为我的代码是一个无限循环。在 while 循环内结果变为 0 后，它就不会停止。有人可以帮我解决这个问题吗？

public static BigInteger problem20(int max){
    BigInteger sum = BigInteger.valueOf(0);
    BigInteger result = BigInteger.valueOf(1);
    BigInteger currentNum = BigInteger.valueOf(0);

    for(long i = 1; i<=max; i++){
        result  = result.multiply(BigInteger.valueOf(i));
        //System.out.println(result);
    }

    while (!result.equals(0)) {
        sum = sum.add(result.mod(BigInteger.valueOf(10)));
        result = result.divide(BigInteger.valueOf(10));
        System.out.println(sum + " "+ result);
    }
    return sum;
}
4

4 回答 4

5

这就是问题：

while (!result.equals(0))

result是 a BigInteger，它永远不会等于 a Integer。尝试使用

while (!result.equals(BigInteger.ZERO))
于 2011-10-14T16:38:34.257 回答
1

另一种可能性是使用while (fact.compareTo(BigInteger.ZERO) > 0).

我建议您使用BigInteger.ZERO，BigInteger.ONE并BigInteger.TEN在可能的地方使用。

例子：

import java.math.BigInteger;

public class P20 {

    public static void main(String[] args) {
        System.out.println(getSum(100));
    }

    private static long getSum(int n) {
        BigInteger fact = BigInteger.ONE;
        for (int i = 2; i <= n; i++) {
            fact = fact.multiply(BigInteger.valueOf(i));
        }
        long sum = 0;
        while (fact.compareTo(BigInteger.ZERO) > 0) {
            sum += fact.mod(BigInteger.TEN).longValue();
            fact = fact.divide(BigInteger.TEN);
        }
        return sum;
    }

}

它需要4 毫秒。

可以使用以下观察来改进它：

  • 总和不受零的影响 => 你不需要乘以 10 和 100 而不是 20, 30, ... 使用 2, 3, ... 就足够了。当然，您可以使用以下事实来概括此规则5*k * 2*j可被 整除10。
于 2014-11-21T23:32:04.810 回答
0

请将您的代码修改为：

    while (!result.equals(BigInteger.valueOf(0))) {
        sum = sum.add(result.mod(BigInteger.valueOf(10)));
        result = result.divide(BigInteger.valueOf(10));
        System.out.println(sum + " "+ result);
    }
于 2011-10-14T16:54:10.183 回答
0

这是另一种方法。在这种情况下，计算总和的复杂度是 O(1)。

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main{
    public static void main(String[] args){
BigInteger b = BigInteger.valueOf(1);
        for(int i=2;i<=5;i++){
            b = b.multiply(BigInteger.valueOf(i));
        }
        //System.out.println(b);

计算下面的总和

final BigInteger NINE = BigInteger.valueOf(9);
            if(b == BigInteger.ZERO){
                System.out.println(b);
            }else if(b.mod(NINE) == BigInteger.ZERO){
                System.out.println(NINE);
            }else{
                System.out.println(b.mod(NINE));
            }

        }`
}
于 2017-06-13T09:25:00.160 回答