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