0

数値が入力として指定されている場合は、その数値までの数値のすべての桁の合計を求めます

たとえば、11が入力され、答えは1 + 2 .... + 9 +（1 + 0）+（1 + 1）ブルートフォース法は、a未満のすべての数値の桁の合計を計算することです。数値。すべての数値の桁の合計を実際に計算せずにそれを行う他の方法があるかどうか疑問に思って、そのメソッドiamを実装しました

4

2 に答える 2

12

これをより速く行うことができます（O（log n）操作で）。S(n)すべての数字の桁の合計とします0 <= k < n。それで

S(10*n) = 10*S(n) + 45*n

未満の数値のうち10*n、それぞれが数値k < nの最初の部分として10回表示され、最後の桁が。であるため0, 1, ..., 9です。つまり、これは最後の桁の合計が45になり、の桁の合計が10倍になりますk。

それを逆にすると、

S(n) = 10*S(n/10) + 45*(n/10) + (n%10)*DS(n/10) + (n%10)*((n%10)-1)/2

ここで、DS(k)はの単純な数字の合計ですk。最初の2つの項は上記に由来し、残りの2つはの桁の合計に由来しますn - n%10, ..., n - n%10 + (n%10 + 1)。

開始はS(n) = 0ですn <= 1。

上限を含めるには、それをと呼びますS(n+1)。

于 2012-09-11T14:19:39.557 に答える
-1

いくつか例を見てみましょう。

sum（9）= 1 + 2 + 3 + 4 ........... + 9 = 9 * 10/2 = 45

sum（99）= 45 +（10 + 45）+（20 + 45）+ .....（90 + 45）= 45 * 10 +（10 + 20 + 30 ... 90）= 45 * 10 + 10（1 + 2 + ... 9）= 45 * 10 + 45 * 10 = sum（9）* 10 + 45 * 10

sum（999）= sum（99）* 10 + 45 * 100

一般に、次の式を使用してsum（10d – 1）を計算できます。

sum（10d --1）= sum（10d-1- 1）* 10 + 45 *（10d-1）

以下の実装では、重複するサブ問題があるため、上記の式は動的計画法を使用して実装されます。上記の式は、アイデアの1つのコアステップです。以下は完全なアルゴリズムです

アルゴリズム：sum（n）

1）nの桁数から1を引いた数を求めます。この値を「d」とします。
328の場合、dは2です。

2）1から10d-1までの数字のいくつかの桁を計算します。この合計をwとします。328の場合、上記の式を使用して1から99までの桁の合計を計算します。

3）nの最上位桁（msd）を検索します。328の場合、msdは3です。

4）全体の合計は、以下の用語の合計です。

a) Sum of digits in 1 to "msd * 10d - 1".  For 328, sum of 
   digits in numbers from 1 to 299.
    For 328, we compute 3*sum(99) + (1 + 2)*100.  Note that sum of
    sum(299) is sum(99) + sum of digits from 100 to 199 + sum of digits
    from 200 to 299.  
    Sum of 100 to 199 is sum(99) + 1*100 and sum of 299 is sum(99) + 2*100.
    In general, this sum can be computed as w*msd + (msd*(msd-1)/2)*10d

b) Sum of digits in msd * 10d to n.  For 328, sum of digits in 
   300 to 328.
    For 328, this sum is computed as 3*29 + recursive call "sum(28)"
    In general, this sum can be computed as  msd * (n % (msd*10d) + 1) 
    + sum(n % (10d))

以下は、上記のアルゴリズムのC++実装です。

// C++ program to compute sum of digits in numbers from 1 to n
#include<bits/stdc++.h>
using namespace std;

// Function to computer sum of digits in numbers from 1 to n
// Comments use example of 328 to explain the code
int sumOfDigitsFrom1ToN(int n)
{
    // base case: if n<10 return sum of
    // first n natural numbers
    if (n<10)
      return n*(n+1)/2;

    // d = number of digits minus one in n. For 328, d is 2
    int d = log10(n);

    // computing sum of digits from 1 to 10^d-1,
    // d=1 a[0]=0;
    // d=2 a[1]=sum of digit from 1 to 9 = 45
    // d=3 a[2]=sum of digit from 1 to 99 = a[1]*10 + 45*10^1 = 900
    // d=4 a[3]=sum of digit from 1 to 999 = a[2]*10 + 45*10^2 = 13500
    int *a = new int[d+1];
    a[0] = 0, a[1] = 45;
    for (int i=2; i<=d; i++)
        a[i] = a[i-1]*10 + 45*ceil(pow(10,i-1));

    // computing 10^d
    int p = ceil(pow(10, d));

    // Most significant digit (msd) of n,
    // For 328, msd is 3 which can be obtained using 328/100
    int msd = n/p;

    // EXPLANATION FOR FIRST and SECOND TERMS IN BELOW LINE OF CODE
    // First two terms compute sum of digits from 1 to 299
    // (sum of digits in range 1-99 stored in a[d]) +
    // (sum of digits in range 100-199, can be calculated as 1*100 + a[d]
    // (sum of digits in range 200-299, can be calculated as 2*100 + a[d]
    //  The above sum can be written as 3*a[d] + (1+2)*100

    // EXPLANATION FOR THIRD AND FOURTH TERMS IN BELOW LINE OF CODE
    // The last two terms compute sum of digits in number from 300 to 328
    // The third term adds 3*29 to sum as digit 3 occurs in all numbers 
    //                from 300 to 328
    // The fourth term recursively calls for 28
    return msd*a[d] + (msd*(msd-1)/2)*p +  
           msd*(1+n%p) + sumOfDigitsFrom1ToN(n%p);
}

// Driver Program
int main()
{
    int n = 328;
    cout << "Sum of digits in numbers from 1 to " << n << " is "
         << sumOfDigitsFrom1ToN(n);
    return 0;
}

出力

Sum of digits in numbers from 1 to 328 is 3241
于 2015-07-05T09:43:04.830 に答える