求从1到n中1出现的次数

题目:输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。

例如输入12,从1到12这些整数中包含1 的数字有1,10,11和12,1一共出现了5次。

编程之美上的原题

基本思路1:

每次判断各位是否为1,计数。然后依次/=10即可。

时间复杂度O(N*lgN)

思路2:

可以用归纳法搞出一个递推公式。

但是如书上所述,这个递推公式是有范围限制的,n最大为1111111110。

归纳如下

如果N为0~9 ,当N>=1时,f(N)=1,否则f(N)=0。

如果N为两位数,f(N)不仅和各位有关,还和十位有关:

(1)如果个位数大于等于1,则个位出现1的次数为十位数的数字加一(加个位的一个1)。如果N的个位数为0,个位出现1的次数就是0。

(2)如果十位数字等于1,则十位上出现1的次数为个位数字加1,如果十位数大于1,则十位数上出现1的次数为10。

可写出程序如下:


 

Leave a Reply

Your email address will not be published.