问题描述
一本书的页码从自然数 1 开始顺序编码直到自然数 n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第 6 页用数字 6 表示，而不是 06 或 006 等。数字计数问题要求对给定书的总页码 n ，计算出书的全部页码中分别用到多少次数字0，1， 2，…，9。
问题要点
1.页码的数字不含前导的零
2.对每页的数字包含的数字进行计数
问题分析
问题的处理对象其实就只有个位的数字，也就是说我们把数字用 10 求余就可以取得个位的数字，接着除以 10 就可以取下一位的数字。
基于这样的分析我们用 C++ 语言写出了以下代码：
#include <iostream>
typedef unsigned long long ull;
using namespace std;
int n;
//用于统计数字出现次数
ull count[10];
//用于统计一个数字 n 中的数字出现次数
//并添加到 count 数组中
void count_num(int n);
int main()
{
while (cin >> n) {
for (int i = 0; i < 10; i++) {
count[i] = 0;
}
for (int i = 1; i <= n; i++) {
count_num(i);
}
for (int i = 0; i < 10; i++)
cout << i << ":" << count[i] << " ";
cout << endl;
}
return 0;
}
void count_num(int n) {
int low;
while (n != 0) { // n 总是大于 0
low = n % 10;
count[low]++;
n /= 10;
}
}
复杂度如下：
| 项目 | 复杂度 |
|---|---|
| n × m | O(nm) |
| input | O(n) |
| output | O(n) |
| 合计 | O(nm) |
但这样做如果我们需要计算 n = 109 的话，O(n2)=1018一台普通的计算机大约需要 2 分钟才算完。我们还有办法吗？问题伊始就说道不需要前导的零，这个是不是暗示呢？不管怎样，让我们试着往这方面思考。
行是知之始，知是行之成。——陶行知
补零会有什么结果呢，或者说为什么要这样做呢？会不会是补零后，我们会有另外的发现呢？带着疑问，我们对数字加了零：
01 02 03 04 05 06 07 08 09 10
0:10 1:2 2~9:1
这样做似乎没什么规律，如果把零去掉，并把 10 去掉
1 2 3 4 5 6 7 8 9
0:0 1~9:1
这样看来好像也没什么规律，如果前面加一个零呢？
0 1 2 3 4 5 6 7 8 9
0~9: 1
这样每个数字都加一就可以了！在细心一点看一看会发现，这都是一位数，如果是两位呢？
00 01 02 03 04 05 06 07 08 09
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
30 31 32 33 34 35 36 37 38 39
………………………..
80 81 82 83 84 85 86 87 88 89
90 91 92 93 94 95 96 97 98 99
0~9: 20
这样的话，再由此推到三位数呢？
000 001 002 003 004 005 006 007 008 009
010 011 012 013 014 015 016 017 018 019
…………………………………
100 101 102 103 104 105 106 107 108 109
110 111 112 113 114 115 116 117 118 119
…………………………………
580 581 582 583 584 585 586 587 588 589
590 591 592 593 594 595 596 597 598 599
…………………………………
980 981 982 983 984 985 986 987 988 989
990 991 992 993 994 995 996 997 998 999
0~9:300
如果继续推到四位数，五位数呢？把位数和上面的结果联系起来，我们可以得出这个式子:
出现次数 = 位数 × 10(位数 – 1)
这是巧合吗？实际上，我们可以以递归的形式来解释这个式子
f(1)=1
f(n)=f(n-1) * 10 + 10(n – 1)
这说明两位数是一位数的 10 倍加上十位数上每个数字出现了10次，三位数如此类推。
关于详细的证明过程，这里不累赘了。
我们为什么要推出数字出现次数与所有相关位数的关系呢？我们企图从直观上毫无规律之中找出规律。这些规律必然会带有各种条件，既然我们有了一个所有相关位数都的出现次数是一样的规律，那么我们如何使用这个规律呢？
如果我们把求到了的所有相关位数的数字出现次数减去额外补的零的个数那么我们就得到了准确的每个数字出现的次数。我们在处理问题的时候，可以一步一步地接近我们想得到的。我们按照上面推出所有相关位数的数字出现次数的思路可以得出第 n 位的补零次数为:
f(1) = 1
f(n) = 10 * f(n – 1)
接下来便是如何根据特定的自然数 n 来计算 0~9 各个数字出现的次数。我们来考察一个随意的数字 156 ：
000 001 002 003 004 005 006 007 008 009
010 011 012 013 014 015 016 017 018 019
…………………………………
100 101 102 103 104 105 106 107 108 109
110 111 112 113 114 115 116 117 118 119
…………………………………
150 151 152 153 154 155 156
我们不能直接通过位数来得到正确的答案，但发现 156 大于 100，意味着我们可以当作两位数 (00~99) 来计算一遍，结果为 0~9:20 ,那么我们就只剩下：
000 001 002 003 004 005 006 007 008 009
010 011 012 013 014 015 016 017 018 019
…………………………………
100 101 102 103 104 105 106 107 108 109
110 111 112 113 114 115 116 117 118 119
…………………………………
150 151 152 153 154 155 156
可以知道，我们少算 100 个零。另外，我们可以知道总共多出的零的个数为 111 (100 + 10 + 1) 个。接下来就需要计算 100~156 的部分，接下来会表示得详细一点。
100 101 102 103 104 105 106 107 108 109
110 121 112 113 114 115 116 117 118 119
120 121 122 123 124 125 126 127 128 129
130 131 132 133 134 135 136 137 138 139
140 141 142 143 144 145 146 147 148 149
150 151 152 153 154 155 156
我们稍微观察一下便可以发现如果去了最高位，那么就会得到 5 个一位的情况。
(待续)