计算 1 到 n 范围内所有数字的位数之和

在这个问题中，我们必须找到 1 到 n 范围内所有数字的位数之和。例如，54 的位数之和为 5 + 4 = 9，同样，我们必须找到所有数字及其位数之和。

我们知道可以生成 10^{d - 1} 个数字，其位数为 d。要找到所有数字 d 的数之和，我们可以使用递归公式。

sum(10^d- 1)=sum(10^d-1- 1)*10+45*(10^d-1)

输入和输出

输入:
此算法取范围的上限，假设为 20。
输出:
从 1 到 n 的所有数字的数字之和。这里的结果是 102

算法

digitSumInRange(n)

输入: 范围的上限。

输出 − 范围内所有数字的数字和 (1-n)。

Begin
   如果 n < 10，则
      返回 n(n+1)/2
   数字 := 数字中的位数
   d := 数字 – 1
   定义大小为数字的位置数组
   place[0] := 0
   place[1] := 45

   对于 i := 2 到 d，执行
      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;          //当一位数字用公式求和时
   int digit = log10(n)+1;       //数字的位数
      int d = digit-1;           //将位数减少 1
   
   int *place = new int[d+1];    //创建数组以存储 1 到 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));    //计算 10 的幂
   int msd = n/power;             //找到最高有效位
   return msd*place[d] + (msd*(msd-1)/2)*power +
      msd*(1+n%power) + digitSumInRange(n%power);    //递归求和
}
int main() {
   int n;
   cout << "输入范围的上限:";
   cin >> n;
   cout << "范围内的数字总和(1 至 " << n << ")为:" << digitSumInRange(n);
}

输出

输入范围的上限:20
范围内的数字总和(1 至 20)为:102

相关文章

• 计算 1 到 n 范围内所有数字的位数之和