统计数字问题 算法实现1-1
统计数字问题 算法实现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)=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到现在我们已经处理完了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