计算从1到n的所有数字的数字总和
在此问题中，我们必须找到范围为1到n的所有数字的数字总和。例如，54的数字总和为5+4=9，像这样，我们必须找到所有数字及其数字总和。
我们知道可以生成10个d-1数字，其位数为d。为了找到所有这些数字d的总和，我们可以使用一个递归公式。
sum（10d-1）=sum（10d-1-1）*10+45*（10d-1）
输入输出
Input: This algorithm takes the upper limit of the range, say it is 20. Output: Sum of digits in all numbers from 1 to n. Here the result is 102
算法
digitSumInRange(n)
输入： 范围的上限。
输出-范围(1-n)中所有数字的数字总和。
Begin
if n < 10, then
return n(n+1)/2
digit := number of digits in number
d := digit – 1
define place array of size digit
place[0] := 0
place[1] := 45
for i := 2 to d, do
place[i] := place[i-1]*10 + 45 * ceiling(10^(i-1))
power := ceiling(10^d)
msd := n/power
res := msd*place[d] + (msd*(msd-1)/2)*power +
msd*(1+n mod power) + digitSumInRange(n mod power)
return res
done
End示例
#include<iostream>
#include<cmath>
using namespace std;
int digitSumInRange(int n) {
if (n<10)
return n*(n+1)/2; //when one digit number find sum with formula
int digit = log10(n)+1; //number of digits in number
int d = digit-1; //decrease digit count by 1
int *place = new int[d+1]; //create array to store sum upto 1 to 10^place[i]
place[0] = 0;
place[1] = 45;
for (int i=2; i<=d; i++)
place[i] = place[i-1]*10 + 45*ceil(pow(10,i-1));
int power = ceil(pow(10, d)); //computing the power of 10
int msd = n/power; //find most significant digit
return msd*place[d] + (msd*(msd-1)/2)*power +
msd*(1+n%power) + digitSumInRange(n%power); //recursively find the sum
}
int main() {
int n;
cout << "Enter upper limit of the range: ";
cin >> n;
cout << "Sum of digits in range (1 to " << n << ") is: " << digitSumInRange(n);
}输出结果
Enter upper limit of the range: 20 Sum of digits in range (1 to 20) is: 102