【問題描述】
一本書的頁數(shù)為N，頁碼從1開始編起，請你求出全部頁碼中，用了多少個0，1，2，…，9。其中—個頁碼不含多余的0，如N＝1234時第5頁不是0005，只是5。
【輸入】
一個正整數(shù)N(N≤109)，表示總的頁碼。
【輸出】
共十行：第k行為數(shù)字k-1的個數(shù)。
【樣例】
count.in count.out
11 1
4
1
1
1
1
1
1
1
1
【算法分析】
簡單的對題目進行分析，發(fā)現(xiàn)枚舉每個數(shù)，然后統(tǒng)計每個數(shù)里面數(shù)字的出現(xiàn)個數(shù)的這種方法是不可取的。
我們只好從數(shù)字本身的規(guī)律出發(fā)尋找解決辦法。如果把零考慮進去，那么0000-9999這1萬個數(shù)里0-9總共出現(xiàn)了40000次，每個數(shù)字出現(xiàn)4000次。進一步推廣，考慮所有的n位數(shù)情況，從n個0到n個9，共10n個n位數(shù)，0到9十個數(shù)字平均使用，每個數(shù)字共用了n*10n-1次。
有了這樣的規(guī)律后，可以從高位向低位進行統(tǒng)計，最后再減去多余的0的個數(shù)。
以n=3657為例：(用count數(shù)組來存放0到9各個數(shù)字的使用次數(shù))
最高位(千位)為3，從0千、1千到2千，000~999重復了3次，每一次從000到999，每個基本數(shù)字都使用了3*100＝300次，重復3次，所以count[0]～count[9]各增加3*300；
另外最高位的0到2作為千位又重復了1000次，count[0]～count[2]各增加1000，3作為千位用了657次(＝n mod 100)，因此count[3]增加657；
接下來對百位6再進行類似的處理，0到9在個位和十位平均重復使用6*20次，所以count[0]～count[9]先各增加6*20，0到5作為百位重復使用了100次，所以count[0]～count[5]再各增加100，6作為百位在這里重復用了57次(＝n mod 100)；因此count[6]增加57；
對十位和個位也進行相同的處理，得出count[0]~count[9]的值；
最后再減去多算的0的個數(shù)。
那么0到底多算了多少次呢?
當沒有十位及以更高位時，個位的0，只多算了1次；
當沒有百位及以更高位時，十位的0，多算了10次；
當沒有千位及以更高位時，百位的0，多算了100次；
……
【參考代碼】
1 #include<stdio.h>
2 int main()
3 {
4 int n,len=0,m,a[10]={0},b[10]={0,1},c[10];
5 scanf("%d",&n);
6 m=n;
7 while(m>0) {len++;c[len]=m%10;m/=10;}
8 for(int i=2;i<=9;i++) b[i]=b[i-1]*10;
9 m=n;
10 for(int i=len;i>=1;i--)
11 {
12 for(int j=0;j<=9;j++) a[j]+=b[i-1]*(i-1)*c[i];
13 for(int j=0;j<=c[i]-1;j++) a[j]+=b[i];
14 a[c[i]]+=m%b[i]+1;
15 }
16 for(int i=1;i<=len;i++) a[0]-=b[i];
17 for(int i=0;i<=9;i++)
18 printf("%d\n",a[i]);
19 return 0;
20 }
21