页码计数

【问题描述】

    一本书的页数为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位数情况,从n0n9,共10nn位数,09十个数字平均使用,每个数字共用了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 

 


posted on 2011-08-18 19:26 AK 阅读(3331) 评论(2)  编辑 收藏 引用 所属分类: ACM

评论

# re: 页码计数 2015-09-23 19:56 greenty

a[c[i]]+=m%b[i]+1;


b[i]可能为0;  回复  更多评论   

# re: 页码计数 2015-11-01 11:32 syh

您好,您这篇题解中 “3作为千位用了657次(=n mod 100),因此count[3]增加657;” 应该是count[3]增加675+1次(加上3000中的‘3’)。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年7月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿(1)

随笔分类

随笔档案

资源连接

搜索

最新评论

阅读排行榜

评论排行榜