【问题描述】
一本书的页数为N,页码从1开始编起,请你求出全部页码中,用了多少个0,1,2,…,9。其中—个页码不含多余的0,如N=1234时第5页不是0005,只是5。
【输入】
一个正整数N(N≤109),表示总的页码。
【输出】
共十行:第k行为数字k-1的个数。
【样例】
count.in count.out
11 1
4
1
1
1
1
1
1
1
1
【算法分析】
简单的对题目进行分析,发现枚举每个数,然后统计每个数里面数字的出现个数的这种方法是不可取的。
我们只好从数字本身的规律出发寻找解决办法。如果把零考虑进去,那么0000-9999这1万个数里0-9总共出现了40000次,每个数字出现4000次。进一步推广,考虑所有的n位数情况,从n个0到n个9,共10n个n位数,0到9十个数字平均使用,每个数字共用了n*10n-1次。
有了这样的规律后,可以从高位向低位进行统计,最后再减去多余的0的个数。
以n=3657为例:(用count数组来存放0到9各个数字的使用次数)
最高位(千位)为3,从0千、1千到2千,000~999重复了3次,每一次从000到999,每个基本数字都使用了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的个数。
那么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