4

特定の数字の桁の合計を簡単に計算できますが、すべての数字を何度も合計しなくても、次の数字の合計を決定するために使用できる数式またはパターンはありますか?

例えば

Sum of 1234 = 1+2+3+4 = 10
Sum of 1235 = 1+2+3+5 = 11
Sum of 1236 = 1+2+3+6 = 12

ここである種のパターンを見ることができますが、効率的な数学アルゴリズムを思いつくことはできません.

以下の方法を使用して、桁の合計を計算します。

public int sum(long n) {  
    int sum = 0;   
    while (n != 0) {    
        sum += n % 10;
        n /= 10;  
    }  
    return sum;  
}

これは正常に動作しますが、CPU を集中的に使用します。これをもっと早くしたい。一連の数字がある場合10->19、10 の桁を数えるだけでよいとします。その後、19 までそれぞれに 1 を追加します。

以前の数値の合計が既にある場合、数値の桁数の合計を計算する効率的な方法はありますか?

4

4 に答える 4

8 
DigitSum(n+1) = DigitSum(n) + 1 - (9 * NumberOfEndingZeros(n+1))

t連続した数の桁和ではなく、連続した数の桁和の合計 (n+1、n+2、...、n+t)を求めたい場合は、tより簡単です。

Sum(DigitSum(i)) for i = n+1 to n+t = a(n+t) - a(n)

ここで、 は Encyclopedia of Integer Sequencesa(i)のA037123シーケンスで、いくつかの式があります。これはかなり速いと思います：

a(n) = (1/2) * ( (n+1) * (n - 18 * sum{k>0, floor(n/10^k)} )
               + 9 * sum{k>0, (1+floor(n/10^k))*floor(n/10^k)*10^k}
               )
于 2012-09-11T07:01:29.733 に答える
5

最速の方法は、各桁を抽出して追加することです。

public static void main(String... args) {
    // check values
    int runs = 1000000;
    for (int i = 100; i < runs; i++) {
        int sum = sumDigits(i - 1);
        int sum1 = sumDigits(i);
        int sum2 = sumDigits(sum, i);
        if (sum1 != sum2) throw new AssertionError(i + ": " + sum1 + " != " + sum2);
    }
    long start = System.nanoTime();
    for (int i = 0; i < runs; i++) {
        int sum = sumDigits(i);
        // prevent optimising away.
        if (sum < 0) throw new AssertionError();
    }
    long time = System.nanoTime() - start;
    System.out.printf("sumDigits took an average of %,d ns%n", time / runs);
    long start2 = System.nanoTime();
    int lastSum = 0;
    for (int i = 0; i < runs; i++) {
        int sum = sumDigits(lastSum, i);
        lastSum = sum;
        // prevent optimising away.
        if (sum < 0) throw new AssertionError();
    }
    long time2 = System.nanoTime() - start2;
    System.out.printf("sumDigits using previous value took an average of %,d ns%n", time2 / runs);

    long large = Long.MAX_VALUE - runs - 1;

    long start3 = System.nanoTime();
    for (int i = 0; i < runs; i++) {
        int sum = sumDigits(large + i);
        // prevent optimising away.
        if (sum < 0) throw new AssertionError();
    }
    long time3 = System.nanoTime() - start3;
    System.out.printf("sumDigits took an average of %,d ns%n", time3 / runs);
    long start4 = System.nanoTime();
    int lastSum2 = sumDigits(large);
    for (int i = 0; i < runs; i++) {
        int sum = sumDigits(lastSum2, large + i);
        lastSum2 = sum;
        // prevent optimising away.
        if (sum < 0) throw new AssertionError();
    }
    long time4 = System.nanoTime() - start4;
    System.out.printf("sumDigits using previous value took an average of %,d ns%n", time4 / runs);

}

public static int sumDigits(long n) {
    int sum = 0;
    do {
        sum += n % 10;
        n /= 10;
    } while (n > 0);
    return sum;
}

public static int sumDigits(int prevSum, long n) {
    while (n > 0 && n % 10 == 0) {
        prevSum -= 9;
        n /= 10;
    }
    return prevSum + 1;
}

版画

sumDigits took an average of 32 ns
sumDigits using previous value took an average of 10 ns
sumDigits took an average of 79 ns
sumDigits using previous value took an average of 7 ns

大きな値の場合、約 70 ns を節約できます。コードに多少の複雑さが加わります。1 から 10^18 までずっと数えることはできないため、最初の sumDigit を使用して合計をブートストラップする必要があります。

于 2012-09-11T07:12:55.893 に答える
1

数字の桁数の合計nがs(n)

s(49) = 13

s(94) = 13

しかし、49+1 = 50どれがs(50) = 5、94+1 = 95どれがs(95) = 14。したがって、 の桁の合計nが 13 であることだけが与えられた場合、 の桁の合計に対して少なくとも 2 つの異なる可能な答えがありn+1ます。 n に関する追加情報が必要です。

n が 9 で終わる場合、最大で s(n) - 9 になることを知っていることが鍵だと思いますs(n+1)(ああ、ypercube の答えはここにあります)。 9), s(xxxx9 + 1) = s(xxxx9) - 9 + 1. xxx99s(xxx99 + 1) = s(xxx99) - 18 + 1などをお持ちの場合

したがって、範囲内のすべての 10、100、1000 などを数えると、これがスピードアップする可能性があります。

(繰り返しますが、ypercube が私を打ち負かしたのがわかります)。これは、A037123 の式がまさにそれを行うものであるように見えます (ただし、0 から n まで)。(それを と呼びましょうa(n))

最後に、1 から n までの合計ではなく、 n から n+r までの桁の合計の合計が必要なので、a の桁の合計の合計の式を導出できるかどうかを確認する必要があります。範囲ss(n,n+r)

それは単純に見えるだろう

ss(n,n+r) = a(n+r) - a(n-1)

于 2012-09-11T07:59:05.760 に答える
0

これはウィキペディアの式です：

これが式です


これはJavaでの私の実装です:

public static int digitSum(int x) {
    return IntStream.rangeClosed(0, (int) Math.log10(x)) // From zero to the number of digits of x in base 10...
               .map(n -> (x % (int) Math.pow(10, n + 1) -  x % (int) Math.pow(10, n)) / (int) Math.pow(10, n)) // ...yield each digit...
               .sum() // and sum;
}
于 2014-12-12T17:28:10.030 に答える