本文介紹了統計數字問題的算法，計算出書的全部頁碼中分別用到多少次數字0,1,2,3,.....9，并有每一步的解題思路,需要的朋友可以參考下

一本書的頁碼從自然數1開始順序編碼直到自然數n。書的頁碼按照通常的習慣編排，每個頁碼都不含多余的前導數字0。例如第6頁用6表示而不是06或006。數字統計問題要求對給定書的總頁碼，計算出書的全部頁碼中分別用到多少次數字0,1,2,3,.....9。

這個題目有個最容易想到的n*log10(n)的算法。這是自己寫的復雜度為O(n*log10(n))的代碼：

1. void statNumber(int n) { 
2. int i, t; 
3. int count[10] = {0}; 
4. for(i = 1; i <= n; i++) { 
5. t = i; 
6. while(t) { 
7. count[t%10]++; 
8. t/=10; 
9. } 
10. } 
11. for(i = 0; i < 10; i++) { 
12. printf("%d/n", count[i]); 
13. } 
14. } 

仔細考慮m個n位十進制數的特點，在一個n位十進制數的由低到高的第i個數位上，總是連續出現10^i個0，然后是10^i個1……一直到10^i個9，9之后又是連續的10^i個0，這樣循環出現。找到這個規律，就可以在常數時間內算出第i個數位上每個數字出現的次數。而在第i個數位上，最前面的10^i個0是前導0，應該把它們減掉。

這樣，可以只分析給定的輸入整數n的每個數位，從面可以得到一個log10(n)的算法，代碼如下：

1. void statNumber(int n) { 
2. int m, i, j, k, t, x, len = log10(n); 
3. char d[16]; 
4. int pow10[12] = {1}, count[10] = {0}; 
5. for(i = 1; i < 12; i++) { 
6. pow10[i] = pow10[i-1] * 10; 
7. } 
8. sprintf(d, "%d", n); 
9. m = n+1; 
10. for(i = 0; i <= len; i++) { 
11. x = d[i] - '0'; 
12. t = (m-1) / pow10[len-i];  
13.  
14. count[x] += m - t * pow10[len-i];  
15.  
16. t /= 10; 
17. j = 0; 
18. while(j <= x-1) { 
19. count[j] += (t + 1) * pow10[len-i]; 
20. j++; 
21. } 
22. while(j < 10) { 
23. count[j] += t * pow10[len - i]; 
24. j++; 
25. } 
26. count[0] -= pow10[len-i]; /* 第i個數位上前10^i個0是無意義的 */ 
27. } 
28. for(j = 0; j < 10; j++) { 
29. printf("%d/n", count[j]); 
30. } 
31. } 

通過對隨機生成的測試數據的比較，可以驗證第二段代碼是正確的。

對兩段代碼做效率測試，第一次隨機產生20萬個整數，結果在我的電腦上，第二段代碼執行1.744秒。第一段代碼等我吃完鈑回來看還是沒反應，就強行關了它。

第二次產生了1000個整數，再次測試，結果第一段代碼在我的電腦上執行的時間是

10.1440秒，而第二段代碼的執行時間是0.0800秒。

其原因是第一段代碼時間復雜度為O(n*log10(n))，對m個輸入整數進行計算，則需要的時間為 1*log10(1) + 2*log10(2) + ... + m*log10(m)，　當n > 10時，有

n*log10(n) > n，所以上式的下界為11+12+....+m，其漸近界為m*m。對于20萬個測試數據，其運行時間的下界就是4*10^10。

同樣可得第二段代碼對于n個輸入數據的運行時間界是n*log10(n)的。

上面的代碼中有個pow10數組用來記錄10^i，但10^10左右就已經超過了2^32，但是題目給定的輸入整數的范圍在10^9以內，所以沒有影響。

原著中給出的分析如下：

考察由0,1,2...9組成的所有n位數。從n個0到n個9共有10^n個n位數。在這10^n個n位數中，0,1,2.....9第個數字使用次數相同，設為f(n)。f(n)滿足如下遞推式：

n>1:

f(n) = 10f(n-1)+10^(n-1)

n = 1:

f(n) =1

由此可知，f(n) = n*10^(n-1)。

據此，可從高位向低位進行統計，再減去多余的0的個數即可。

著者的思想說的更清楚些應該是這樣：

對于一個m位整數，我們可以把0到n之間的n+1個整數從小到大這樣來排列：

000......0

.............

199......9

200......0

299......9

.........

這樣一直排到自然數n。對于從0到199......9這個區間來說，拋去最高位的數字不看，其低m-1位恰好

就是m-1個0到m-1個9共10^(m-1)個數。利用原著中的遞推公式，在這個區間里，每個數字出現的次數

(不包括最高位數字)為(m-1)*10^(m-2)。假設n的最高位數字是x，那么在n之間上述所說的區間共有

x個。那么每個數字出現的次數x倍就可以統計完這些區間。再看最高位數字的情況，顯然0到x-1這些

數字在最高位上再現的次數為10^(m-1)，因為一個區間長度為10^(m-1)。而x在最高位上出現次數就是

n%10^(m-1)+1了。接下來對n%10^(m-1)，即n去掉最高位后的那個數字再繼續重復上面的方法。直到

個位，就可以完成題目要求了。

比如，對于一個數字34567，我們可以這樣來計算從1到34567之間所有數字中每個數字出現的次數：

從0到9999，這個區間的每個數字的出現次數可以使用原著中給出的遞推公式，即每個數字出現4000次。

從10000到19999，中間除去萬位的1不算，又是一個從0000到9999的排列，這樣的話，從0到34567之間

的這樣的區間共有3個。所以從00000到29999之間除萬位外每個數字出現次數為3*4000次。然后再統計

萬位數字，每個區間長度為10000，所以0,1,2在萬位上各出現10000次。而3則出現4567+1=4568次。

之后，拋掉萬位數字，對于4567，再使用上面的方法計算，一直計算到個位即可。

下面是自己的實現代碼：

1. void statNumber_iterative(int n) { 
2. int len, i, k, h, m; 
3. int count[10] = {0}; 
4. int pow10[12] = {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000}; 
5. char d[16]; 
6. len = log10(n); /* len表示當前數字的位權 */ 
7. m = len; 
8. sprintf(d, "%d", n); 
9. k = 0; /* k記錄當前最高位數字在d數組中的下標 */ 
10. h = d[k] - '0'; /* h表示當前最高位的數字 */ 
11. n %= pow10[len]; /* 去掉n的最高位 */ 
12. while(len > 0) { 
13. if(h == 0) { 
14. count[0] += n + 1; 
15. h = d[++k] - '0'; 
16. --len; 
17. n %= pow10[len]; 
18. continue; 
19. } 
20. for(i = 0; i < 10; i++) { 
21. count[i] += h * len * pow10[len-1]; 
22. } 
23. for(i = 0; i < h; i++) { 
24. count[i] += pow10[len]; 
25. } 
26. count[h] += n + 1; 
27. --len; 
28. h = d[++k] - '0'; 
29. n %= pow10[len]; 
30. } 
31. for(i = 0; i <= h; i++) { 
32. count[i] += 1; 
33. } 
34. /* 減去前導0的個數 */ 
35. for(i = 0; i <= m; i++) {  
36. count[0] -= pow10[i]; 
37. } 
38. for(i = 0; i < 10; i++) { 
39. printf("%d/n", count[i]); 
40. } 
41. } 

以上就是本文的全部內容，希望對大家的學習有所幫助。