[collect]读《编程之美》有感：1的个数-数字x的个数

原文地址：

http://blog.csdn.net/hinyunsin/article/details/6321406

题目是这样的：

给定一个十进制的正整数N，写下从1开始，到N的所有整数，然后数一下其中出现的所有”1″的个数。

例如：

N=2，写下1,2。这样只出现了1个”1″。

N=12，我们会写下1,2,3,4,5,6,7,8,9,10,11,12。这样1的个数是5.

问题是：

写出一个函数f(N)，返回1到N之间出现”1″的个数，比如f(12)=5
在32为整数范围内，满足条件”f(N)=N”的最大的N是多少？

书中的解法二是：通过分析”小于等于N的数在每一位上可能出现1的次数”之和来得到这个结果。下面是分析过程/方法：

给定一个数字N，假定从低位（个位）到高位（十位，百位，千位。。。），他的第i位为B，i位的高位部分为A，i位的地位部分为C，因此，我们得到这样的计算公式：

N=A*10ⁱ+B*10^i-1+C，我们用N=(A)B(C)来描述：例如i=3，那么12345=12*10³+3*10²+45，12345=(12)3(45)（A=12，B=3，C=45）

在i这个位置，B为1的数值有哪些：

1：假设B>1，从(0)1(*)~(A)1(*)（*表示C中每一位均可以是任意数字）范围内的数字都小于(A)B(C)，总共有：(A+1)*10ⁱ个

例如12345，其中(0)1(00)~(12)1(99)就是第3为为1的所有情况，大小时13*10³个

2：假设B=1，则从(0)1(*)~(A-1)1(*)范围内和(A)1(0~C)范围内的所有数字都<=(A)B(C)，总共有：A*10ⁱ+(C+1)个

3：假设B=0，则从(0)1(*)~(A-1)1(*)范围内的所有数字都小于(A)B(C)，总共有：A*10ⁱ 个

稍微思考一下，会发现，这个方式不只是对查找1的个数有用，对于1~9这9个数字的个数均有效，唯一不同的是，这里的B不再同1比较大小，而是跟要统计的数字比较大小

因此我们得到这样通用的解法：

给定一个十进制的正整数N，写下从1开始，到N的所有整数，然后数一下其中出现的所有”x”的个数，其中1<=x<=9。分析方法：

N=A*10ⁱ+B*10^i-1+C，我们用N=(A)B(C)来描述：例如i=3，那么12345=12*10³+3*10²+45，12345=(12)3(45)（A=12，B=3，C=45）

在i这个位置，B为1的数值有哪些：

1：假设B>x，从(0)x(*)~(A)x(*)（*表示C中每一位均可以是任意数字）范围内的数字都小于(A)B(C)，总共有：(A+1)*10ⁱ个

例如12345，其中(0)1(00)~(12)1(99)就是第3为为1的所有情况，大小时13*10³个

2：假设B=x，则从(0)x(*)~(A-1)x(*)范围内和(A)x(0~C)范围内的所有数字都<=(A)B(C)，总共有：A*10ⁱ+(C+1)个

3：假设B<x，i 个

对于整数零，稍微有点特殊：

假设B>0，如果A>0，也就是i不是N的最高位，则从(1)0(*)~(A)0(*)（而不是(0)x(*)~(A)x(*)，因为这里x=0）范围内的数字都小于(A)B(C)，总共是是A*10ⁱ个，如果A=0，这样的数字是不存在的
假设B=0，则A>0，从(1)0(*)~(A)0(*)范围内和(A)0(0~*)范围内的所有数字都<=(A)B(C)，总共有：(A-1)*10ⁱ+(C+1)个
最后要+1，因为0没有被计算进去，对于任意正整数，0总是小于它的。

贴上python代码如下：

#!/usr/bin/python
#coding=utf-8
#Filename: numCount.py
'''
Create on 2011-04-12
@author: boyce
@contact: [email protected]
@version 1.0
'''
def sums(val, num):
    iCount = 0	#总数初值设为0
    iFactor = 1	#提前设置权值为1，即个位
    iLowerNum = 0
    iCurrNum = 0
    iHigherNum = 0

    if num == 0:
        while (val / iFactor) != 0:
            iLowerNum = val - (val / iFactor) * iFactor
            iCurrNum = (val / iFactor) % 10
            iHigherNum = val / (iFactor * 10)
            if iCurrNum == 0:
                iCount += (iHigherNum - 1) * iFactor + iLowerNum + 1
            elif iHigherNum > 0:
                iCount += iHigherNum * iFactor
            iFactor *= 10
        return iCount + 1

    while (val / iFactor) != 0:
        iLowerNum = val - (val / iFactor) * iFactor
        iCurrNum = (val / iFactor) % 10
        iHigherNum = val / (iFactor * 10)
        if iCurrNum < num:
            iCount += iHigherNum * iFactor
        elif iCurrNum == num:
            iCount += iHigherNum * iFactor + iLowerNum + 1
        else:
            iCount += (iHigherNum + 1) * iFactor
        iFactor *= 10
    return iCount

if __name__ == '__main__':
    num = 33333
    print '0: ', sums(num, 0)
    print '1: ', sums(num, 1)
    print '2: ', sums(num, 2)
    print '3: ', sums(num, 3)
    print '4: ', sums(num, 4)
    print '5: ', sums(num, 5)
    print '6: ', sums(num, 6)
    print '7: ', sums(num, 7)
    print '8: ', sums(num, 8)
    print '9: ', sums(num, 9)

后记：我自己后来也照着这个思路写了个PHP版的，但是和这个Python版的比起来太搓了，就没有放上来……

29 6 月, 2014

admin

Programing

algorithm, Python