登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

白杨

坚持是一种品质,用心是一种习惯! 生活仍在继续……追逐编程质量与效率

 
 
 

日志

 
 

(三十)在从1到n的正数中1出现的次数  

2012-05-02 21:26:21|  分类: 每天一道--数据结 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:输入一个整数 n ,求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数。例如输入 12 ,从 1 到 12 这些整数中包含 1 的数字有 1 , 10 , 11 和 12 ,1 一共出现了5 次。

分析:

         我们曾遇到过求给定数num的二进制表示中1出现的次数,但此题是求十进制数中1出现的次数。简单的来想,可以用除法、取余来求的一个数中1的个数,然后再从1到n循环即可解决。但当n比较大时,速度会比较慢。我们现在来尝试从另一种思路来寻求一种更高效的方法。

        我们可以换一种思路,分别求每位出现1的次数,然后再将每位出现1的次数相加即是所求。 不妨假设要求的数是abcde(a>0),一般地,我们求第3位,也就是百位数字出现1的次数,可分为如下三种情况:

          (1),当c=0 时,则该位出现1的数分析如下:

          00100--00199

          01100--01199

          02100--02199

          ……

         0b100--0b199

         上面一共是b*100,对于a,我们进行类似的分析,从0b200到0(b+1)099的数字中,百位数字是不会出现1的:

         0(b+1)100--0(b+1)199

         0(b+2)100--0(b+2)199

         ……

         0(b+9)100--0(b+9)199

         0(b+10)100--0(b+10)199即1b199

       从0b200到1b199,共有10*(b*100)个百位数字为1的数字。那么类似的可以知道,从1b200到2b199同样有10*b*100个百位数字为1的数字。依次类推,从2b200到3b199,……,(a-2)b200到(a-1)b199,由于c=0,因此百位出现1的最大的数字应该为a(b-1)199;那么一共有多少个这样的数据段呢?应该比较容易看出来,一共有a个。由此可以看出当c=0时,低位数字是不影响本位数字为1的数字的个数的。

由以上分析可知,百位数字为1的数字共有a*10*100+b*100=ab*100个;

        (2),当c=1时,则该位出现1的数分析如下:

         在(1)情况分析的基础上,因为c=1,所以从a(b-1)200到ab1de中,仍有百位数字为1的数字存在,且比较容易知道一共有de+1个:即从ab100一直到ab1de,由此可以发现,此时低位数字影响了本位数字为1的数字的个数。

        所以,此种情况,百位数字为1的数字共有:ab*100+de+1

        (3),当c>1时,则该位出现1的数分析如下:

         仍然在(1)分析的基础上,因为c>1,所以从a(b-1)200到ab199(因为c>1,所以abcde>ab199,而ab200到abcde中百位数字是不会出现1的)中,仍有1*100个百位数字为1的数字,在此情况下,我们同样可以发现,此时低位数字又不影响本位数字为1的数字的个数了。

        所以,此种情况,百位数字为1的数字共有:ab*100+1*100=(ab+1)*100.

分析到这里,我想就应该比较容易写出程序了吧^_^

  评论这张
 
阅读(2322)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018