输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。例如输入12,从1到12这些整数中包含**1 **的数字有1,10,11和12,1一共出现了5次。
我们用一个稍微大一点的数字21345作为例子来分析。我们把从1到21345的所有数字分成两段,即1-1235和1346-21345。先来看1346-21345中1出现的次数。1的出现分为两种情况:一种情况是1出现在最高位(万位)。从1到21345的数字中,1出现在10000-19999这10000个数字的万位中,一共出现了10000(10的4次方)次;另外一种情况是1出现在除了最高位之外的其他位中。例子中1346-21345,这20000个数字中后面四位中1出现的次数是2000次(2*1000,其中2的第一位的数值,1000是因为数字的后四位数字其中一位为1,其余的三位数字可以在0到9这10个数字任意选择,由排列组合可以得出总次数是2*1000)。
至于从1到1345的所有数字中1出现的次数,我们就可以用递归地求得了。这也是我们为什么要把1-21345分为1-1235和1346-21345两段的原因。因为把21345的最高位去掉就得到1345,便于我们采用递归的思路。
分析到这里还有一种特殊情况需要注意:前面我们举例子是最高位是一个比1大的数字,此时最高位1出现的次数10000(对五位数而 言)。但如果最高位是1呢?比如输入12345,从10000到12345这些数字中,1在万位出现的次数就不是10000次,而是2346次了,也就是除去最高位数字之后剩下的数字再加上1。
使用递归21345 ,则需要对21345的每一个10进制位,进行递归计算。对万位,千位,百位,十位,个位即首位不为0,则可以分别计算21345 1345 345 45 5
(1) 当首位最高位为1时,含有1的个数为 10000
首位可以为0 , 1 ,则后四位其中有1位为1的个数为 ,2\* 10(3)\*4 = 8000 合计18000
(2) 下面计算1345
首位为1,则为 346
其余位为 (首位可以为0) 3 \* 10(2) = 30 合计376
(3)下面计算345
首位为1 10的2次方
首位可以为(0 1 2) 等于3的情况, 3 \* 2 \*10 合计160
剩下的循环即求300- 345
(4)下面计算45
首位为1, 10的1次方
首位不计,首位可以取(0 1 2 3) 4 \* 1 合计 14
(5)下面计算5
判断长度小于1,直接返回
求1到n中任意进制的数的个数,递归公式如下:
总结对于任意的1到n,求所给定的字符c的个数
str = abcdefgh , len = strlen(abcdefgh)
(1)当首位等于\*str = c时 ,Q(abcdefgh) = abcdefgh + 1 + (\*str -'0')\*(len -1)\*10\^(len -2) + Q(bcdefgh)
(2)当首位为 \*str \> c 时 ,Q(abcdefgh) = 10\^(m-1) + (\*str - '0') \* (len - 1) \*10\^(len -2) + Q(bcdefgh)
(3)当首位为 \*str \< c时, Q(abcdefgh) = (\*str - '0') \* (len -1) \*10\^(len -2) + Q(bcdefgh)