问题描述：
一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数
字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2，…，9。
一、思路：
- 以数字1为例子，我们把求1出现的次数，转化为求1~n中，各个位出现1的次数的总和。即个位上出现1的次数，十位上出现1的次数，百位上出现1的次数……的总和。
取变量m，当m=1时，即求个位上出现1的总次数，m=100时，即求百位上出现1的总次数。假设n=3141592，求百位上1出现的总次数，我们把n分为两部分，分别是整除m后得到部分a=n/100=31415,和整除m后的余数部分b=n%100=92。
- 对于31415，我们求0~31415中，个位1出现的次数，即31415/10=3141，又因为31415%10=5大于1，所以0~31415中，各位出现1的总次数为3141+1=3142.实际上，31415是除以100后得到的数，所以每个1，出现了100次。如3141100~3141199，百位上的1出现了100次，所以这时候百位上的1出现次数为(31415/10+1)*100=314200次。
- 再考察第二部分b=92.因为a%10=5，而不是1。所以第二部分没有贡献1。假设n=9999150，那么a=n/100=99991，由a部分计算得百位上出现1的次数为a/10*100=9999000次。而a%10=1，那么第二部分b=50将会有作用，贡献的1的次数为b+1，即9999100~9999150百位上供50+1，即51次1.所以当n=9999150时，百位上出现1的次数为9999050次。
- 通过上述思路，我们可以分别计算个位出现1的次数，十位出现1的次数……，通过相加，我们可以得到1~n中，1出现的总次数。
- 通过上述思路，我们可以分别计算0~9出现的总次数。
- 数字0的情况有点特殊，进行特殊处理。因为不会出现01，02，03等等0开头的数字，所以在统计数字零时，每个位计算出来的count，如果count>=1，则需要先count–，再进行计算。
二、复杂度分析
根据上述算法，我们通过逐渐计算n的个位，十位，百位……即每次m*=10，所以时间复杂度是O(lg n)，在空间方面，每次固定使用常量a和b，估空间负责度不依赖于n，所以空间复杂度啊为O(1)。
数据测试结果如下：采取了临界值1和1000000000（10^9）
| n=1 | n=10^9 | n=100 | n=555555 | n=99 | n=200 | 201 | |
| 0的个数 | 0 | 788888898 | 11 | 271605 | 9 | 31 | 21 |
| 1的个数 | 1 | 900000001 | 21 | 382716 | 20 | 140 | 141 |
| 2的个数 | 0 | 900000000 | 20 | 382716 | 20 | 41 | 42 |
| 3的个数 | 0 | 900000000 | 20 | 382716 | 20 | 40 | 40 |
| 4的个数 | 0 | 900000000 | 20 | 382716 | 20 | 40 | 40 |
| 5的个数 | 0 | 900000000 | 20 | 333336 | 20 | 40 | 40 |
| 6的个数 | 0 | 900000000 | 20 | 271605 | 20 | 40 | 40 |
| 7的个数 | 0 | 900000000 | 20 | 271605 | 20 | 40 | 40 |
| 8的个数 | 0 | 900000000 | 20 | 271605 | 20 | 40 | 40 |
| 9的个数 | 0 | 900000000 | 20 | 271605 | 20 | 40 | 40 |
三、程序运行截图如下：
四、源代码
代码中，通过类Solution封装了void calEveryDigitNumber（int n)函数：
class Solution
{
private:
/**************************************
Author:siukwan
Date:2015-09-25
Description:计算digit出现的次数
***************************************/
static int calOneDigit(int n, int digit)
{
int ans = 0;//返回的结果
for (long long m = 1; m <= n; m *= 10)
{//m采用long long类型，避免溢出，从计算个位出现digit的次数开始
int a = n / m;
int b = n % m;
int count = a / 10;
if (a % 10 > digit) count++;//如果a的余数部分大于digit，则会多出现m个digit
if (digit == 0 && count >=1 ) count--;//0需要特殊处理，因为没有01，02，03……
ans += count * m;//计算a部分出现digit的次数
if (a % 10 == digit )
ans += (b + 1);//如果余数恰好等于digit，结合b部分统计额外出现digit的次数
}
return ans;
}
public:
/**************************************
Author:siukwan
Date:2015-09-25
Description:计算0~9出现的次数,并输出结果
***************************************/
static void calEveryDigitNumber(int n)
{
for (int i = 0; i < 9; i++)
{
int count = calOneDigit(n, i);
printf("%d出现的次数：%d\n", i, count);
}
}
};
整个程序的代码如下：
#include<stdio.h>
#include<iostream>
using namespace std;
class Solution
{
private:
/**************************************
Author:siukwan
Date:2015-09-25
Description:计算digit出现的次数
***************************************/
static int calOneDigit(int n, int digit)
{
int ans = 0;//返回的结果
for (long long m = 1; m <= n; m *= 10)
{//m采用long long类型，避免溢出，从计算个位出现digit的次数开始
int a = n / m;
int b = n % m;
int count = a / 10;
if (a % 10 > digit) count++;//如果a的余数部分大于digit，则会多出现m个digit
if (digit == 0 && count >=1 ) count--;//0需要特殊处理，因为没有01，02，03……
ans += count * m;//计算a部分出现digit的次数
if (a % 10 == digit )
ans += (b + 1);//如果余数恰好等于digit，结合b部分统计额外出现digit的次数
}
return ans;
}
public:
/**************************************
Author:siukwan
Date:2015-09-25
Description:计算0~9出现的次数,并输出结果
***************************************/
static void calEveryDigitNumber(int n)
{
for (int i = 0; i < 9; i++)
{
int count = calOneDigit(n, i);
printf("%d出现的次数：%d\n", i, count);
}
}
};
int main(void)
{
int n = 0;
while (1)
{
printf("算法实现题1-1：统计数字问题\n1）本程序会统计1~n的n个数字中，0~9分别出现的次数；\n2）n的取值范围为0<=n<=10^9；\n请输入页码n:");
cin >> n;
if (n <= 0 || n>1000000000)
{
printf("n的取值范围为0<=n<=10^9，请重新输入!\n");
continue;
}
Solution::calEveryDigitNumber(n);
}
return 0;
}