0

如果给定一个数字作为输入，则查找该数字之前所有数字的总和

例如输入 11 则答案为 1+2....+9+(1+0)+(1+1) number.I 已经实现了该方法，我想知道是否有任何其他方法可以在不实际计算每个数字的数字总和的情况下做到这一点

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。前两项来自上述，其余两项来自 的数字之和n - n%10, ..., n - n%10 + (n%10 + 1)。

开始是S(n) = 0为了n <= 1。

要包括上限，请将其称为S(n+1)。

于 2012-09-11T14:19:39.557 回答
-1

让我们举几个例子。

总和(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 = 总和(9)*10 + 45*10

总和（999）=总和（99）*10 + 45*100

一般来说，我们可以使用以下公式计算 sum(10d – 1)

总和(10d - 1) = 总和(10d-1 - 1) * 10 + 45*(10d-1)

在下面的实现中，上面的公式是使用动态规划实现的，因为存在重叠的子问题。上述公式是该想法的核心步骤之一。下面是完整的算法

算法：sum(n)

1) 求 n 中的位数减一。让这个值是'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 回答