Найдите сумму цифр в числе 100!(Мой цикл while не остановился бы) - PullRequest
Новая
       20

Найдите сумму цифр в числе 100!(Мой цикл while не остановился бы)

3 голосов
/ 14 октября 2011

Я пытался решить Проблема 20 в Project Euler:

n!означает 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, потому что мой код представляет собой бесконечный цикл.После того, как результат стал 0 в цикле while, он просто не остановился.Кто-нибудь может мне помочь исправить это? 

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 ]

5 голосов
/ 14 октября 2011

Это проблема: 

while (!result.equals(0))

result - это BigInteger, которое никогда не будет равно Integer. Попробуйте использовать 

while (!result.equals(BigInteger.ZERO))
1 голос
/ 22 ноября 2014

Другая возможность - использовать 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.
0 голосов
/ 13 июня 2017

Вот еще один способ сделать то же самое. В этом случае сложность вычисления суммы составляет 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));
            }

        }`
}
0 голосов
/ 14 октября 2011

Пожалуйста, измените ваш код на: 

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