【学习笔记】1-1 统计数字问题
【学习笔记】1-1 统计数字问题
1.问题描述
一本书的页码从自然数1开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。
算法设计： 给定表示书的总页码的十进制整数n（1≤n≤109），计算书的全部页码中分别用到多少次数字：0，1，2，····，9。
2.解法
（1）解法一：暴力解法
刚开始看到这道题，第一个想到的解法就是暴力解法。利用从页码1开始到页码n的循环，对每一个页码取其个位，十位，百位······，统计出现的0~9数字的个数，保存在数组当中。代码如下：
n： 总页码
a[10]： 存放结果
//统计数字问题
//暴力解题
#include <iostream>
using namespace std;
int main()
{
int n, i, a[10]={0};//n为总页码，数组a存放结果并进行初始化
cin>>n;
for(i=1; i<=n; i++){
int j=i;
while(j){
a[j%10]++;//提取页码各个位上的数字
j=j/10;
}
}
for(i=0; i<10; i++)
cout<<a[i]<<endl;//输出结果
return 0;
}
此方法解题思路比较简单，容易想到，但是如果问题的规模增大，耗费的时间将会很多，时间复杂度为O(nlogn)。
（2）解法二：递归解法
即采用《计算机算法设计与分析》习题解答中的思路解题。
分析与解答： 考察由0，1，2，····9组成的所有n位数。从n个0到n个9一共有10n个n为数。在这10n个n位数中，0，1，2，····9每个数字使用的次数相同，设为f(n)。f(n)=n10n-1。
可从高位向低位进行统计，再减去多余的0的个数即可。
题解的意思即是n位的所有数（从00··0~99··9，每个数有n位），n位的所有的数，出现的单个数字的总数为n10n，而因为0，1，2···9每个数字出现的概率相同，故每个数字出现次数都为n10n/10=n10n-1。（包括前导0）
举个例子，
例如总页码为4151，按照题解的思路，就是把4151分成：0000-0999，1000-1999，2000-2999，3000-3999，4000-4151几个部分。而递归即是在求出0000-3999各个数字出现的次数，和4151最高位数字4作为最高位出现的次数后，再用相同的方法求4151中的151部分各个数字出现的次数，递归调用直至页码位数为1，这时就求出了包括前导0的各数字的出现次数。
而在计算前导零个数时，其实我们只要计算从0000-3999这些数中出现的前导零的个数即可，计算时用循环解决，如下方代码。
代码如下：
n： 总页码；
bit： 总页码位数；
a[10]： 存放结果；
b： 总页码位数-1；
high： 总页码最高位的数字
last： 除去总页码最高位数字后的数
c： 00···0~99···9（共b位）中各个数字出现的次数×high
c_zero： 前导0的个数
//统计数字问题
//书中思路，递归实现
#include <iostream>
#include <cmath>
using namespace std;
void statistic(int n, int bit, int a[])//计算各个数字出现（包括前导0）的个数
{
if(bit>0){
int b=bit-1, high, last, c;
high=n/round(pow(10,b));//总页码最高位数字
last=n%(int)round(pow(10,b));//除去最高位后的数
c=high*b*round(pow(10,b-1));//计算00..0~99..9中数字个数
for(int i=0; i<10; i++)
a[i]+=c;
for(int i=0; i<high; i++)
a[i]+=round(pow(10,b));//pow（10，b）:从【0~最高位-1】各个数字作为最高位出现的次数
a[high]+=(last+1);//总页码最高位数字出现的次数
statistic(last, b, a);
}
}
void del_zero(int bit, int a[])//多余零计算
{
int c_zero=0;
for(int i=bit; i>0; i--)
c_zero=c_zero+round(pow(10,i-1));
a[0]-=c_zero;
}
void output(int a[])//输出结果
{
for(int i=0; i<10; i++)
cout<<i<<":"<<a[i]<<endl;
}
int main()
{
int n, bit, a[10]={0};
cin>>n;
bit=(int)log10(n)+1;//计算输入的总页码的位数
statistic(n, bit, a);
del_zero(bit, a);
output(a);
return 0;
}
注：现有部分数字统计个数错误的情况，而这些错误答案与正确答案相差并不多。经过我多次思考自己代码的思路和过程，坚信自己代码逻辑上没有一点问题。而最后通过在网上看一些相关的博客，发现是 pow() 函数精度所导致的问题，不得不说有点坑。于是就使用 round() 函数进行修改，最后得到正确运行结果。