统计数字问题 算法实现1-1
题意
题目来自《计算机算法设计与分析（第五版）》第七页。
一本书的页码从自然数开始顺序编码直到自然数n。
求这n个数中，使用了数字0 1 2...9各使用了多少次。
解题思路
暴力算法
使用for循环，每个数分别进行处理。
//核心代码如下
for(int i=1; i<=n; i++){
int tmp = i;
while(tmp){
c[tmp%10]++;
tmp /= 10;
}
}
递归的方式
在《算法设计与分析》这个书的课后题解中提到了一个公式，如下：
从0到9组成的n位数字，一个有$$10^n$$个数（注意，这些数都是n位，因此0的表达：n个0）。这些数字中0 1 ... 9每个数字使用的次数相同，设为$$f(n)$$。那么该函数满足如下的递归式：
\[f(n)=\begin{cases}
10f(n)+10^{n-1} & n>1 \0 & n=1
\end{cases}
\]
化为非递归的形式为：$$f(n)=n10^{n-1}$$
这是递归的基础。因为有前导零，所以后续还需要进一步处理。
比如n=3210，数的位数 = len
那么我们最容易处理的是000 到999，这里数字的使用个数，假设为k。然后因为最高位可以选0 1 2，设有p（p=3）个数（3这里不选的原因是，这里的范围仅仅到3210，没有到3999），所以0000 到2999数字的使用个数就可以具体得到，如1的使用个数就是
\[c[1]=p*k + 10^{len-1}
\]
其他的类似。
接下来处理前导0的情况：
for(int i=0; i<len; i++)//i代表位数-1，i=0时处理的是个位上的数值0，一共一个。
c[0] -= (int)pow(10.0, i);
//注意题目数说数字是从1开始的
到现在我们已经处理完了0000到2999这些数字。
剩下还有3000到3210
这里使用直接让记录最高位数字的数组+1+t（t的定义在下面），然后我们就可以处理去掉最高位的数字了。
\[t=n\%(10^{len-1})$$，这里t=210
然后这里的t有两种情况：
1. 如果t=0，比如n=200时，那么c[0] += len - 1，也就是加2
如果n=10，那么t=0，着从c[0]+=len-1，也就是加1
这样这个程序就可以结束了，不在递归了。
2. 如果t不等于0，那么需要判断一下$$len(t)!=len-1$$的情况。比如n=10010，t=10，那么中间的0也需要处理一下，$$c[0]+=(len-1-len(t))*(t+1)$$。然后再次调用这个函数即可。
需要注意的问题是输出的精度问题，因为函数`pow(a,b)`有时候输出的精度不准确，使用`round(x)`来进行处理（因为我们需要的是一个整数）。
## 代码实现
``` cpp
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int c[10];
void solve(int n){
//数n的位数
int len=log10(n)+1;
//最高位的值
int p=n/((int)round(pow(10.0,len-1)));
for(int i=0;i<10;i++){
c[i]+=p*(len-1)*(int)round(pow(10.0,len-2));
}
//每个数最高位去定一个数时，剩下位数有10^(len-1)不同的数。
for(int i=0;i<p;i++){
c[i]+=(int)round(pow(10.0,len-1));
}
//获得去掉最高位的数
int t=n % (int)round(pow(10.0,len-1));
c[p]+=1+t;//最高位需要添加
if(t==0){//如果t为0
c[0]+=len-1;//0位加len-1
return ;
}
int lenT=log10(t)+1;
if(lenT!=len-1){//若像10010这种情况，中间2个0也要相应的处理
c[0]+=(len-lenT-1)*(t+1);
}
return solve(t);
}
int main(){
int n;
while(cin>>n){
fill(c,c+10,0);
int len=log10(n)+1;
solve(n);
for(int i=0;i<len;i++){
c[0]-=(int)round(pow(10.0,i));
}
for(int i=0;i<10;i++){
cout<<i<<" : "<<c[i]<<endl;
}
}
}
```
## 参考资料
https://blog.csdn.net/m0_37579232/article/details/79651307\]
统计数字问题 算法实现1-1
原文：https://www.cnblogs.com/alking1001/p/13346212.html
