求从1到n的正整数中1出现的次数，

求从1到n的正整数中1出现的次数，

题目：输入一个数字n，求从1到n的正整数出现的次数。

例如：输入13，则包含1的数字有 1 10 11 12 13 这5个数，但是1出现的次数为6次。再比如输入29，则1出现1 10-19 21 这些数字，1共出现可知为13个。

本题目据说是google的一到面试题，刚开始思路有了，到最后完整实现用了一定时间。

最容易想到的方法：遍历，将所有1到n的数字都拿来遍历一边，计数1出现的次数。如果在面试的时候，采用此方法，肯定会被pass掉的。

接下来就是寻找规律，可以发现个位数里面只有1 出现1， 十位数中中内10-19这几个数字都有1，但是其他的20-29,30-39，，，90-99每个里面只有1个1。所有十位数中1出现的总和是20个。可以知道十位数的个位上出现10次，十位上出现10次。于是所有N位数出现1的个数可以通过如下递归函数得到。

def funit(width):
    if width == 1:
        return 1
    else:
        return 10 ** (width - 1) + 10 * funit(width -1)

从上面的函数计算可以funit(1) =1 , funit(2)=20, funit(3)=300,这些数字都是对应所有的位数，相当于9,99,999内1的个数为1 20 300。

如果我们那654举例子，百位上肯定会出现10^2共100此，十位上会出现10^1 + 6*funit(2)共计6*20+10=130次，个位上出现10^0+5*funit(1)共6次，最后可知100+130+6=236次。

所以计算的公式应该为f(x) = 10**(width(x)-1) + x[0]*funit(width(x)-1) + f(x[1:])

特别需要注意的是当出现1的时候，比如125，实际百位上出现了（125-100）+1 = 26次，但是上面公司第一项得到的是10**2=100，所以遇到1需要特殊处理。

十位上出现1的时候，也需要特别处理，比如10中1的出现次数为2,11次数为4,12次数为5， 依次类推，当数字大于11后1出现的次数为个位数+3，见下面的函数。

def special(bit):
    if bit == '10':
        return 2
    elif bit == '11':
        return 4
    else:
        return int(bit[1]) + 3

有了以上分析，最后求1出现的次数的实现为：

def get_countof1(bit):
    test = str(bit)
    if len(test) == 1:
        if bit >= 1:
            return 1
        else:
            return 0
    if len(test) == 2:
        if test[0] == '1':
            return special(test)
        else:
            return 10 + int(test[0])*funit(1) + get_countof1(int(test[1]))
    else:
        if test[0] == '1':
            sure_count = 1 + int(test[1:])
        else:
            sure_count = 10 ** (len(test) - 1)
        return sure_count + int(test[0])*funit(len(test)-1) + get_countof1(int(test[1:]))

附：循环遍历的代码:

def get_traverse(number):
    sum = 0
    for i in xrange(number+1):
        temp = str(i)
        for j in xrange(len(temp)):
            if temp[j] == '1':
                sum += 1
    return sum

简单测试：

本人写的太啰嗦了，其实就是找规律递归，速度肯定快很多。可以粗略估计循环计算时间复杂度为O(width(n)*n), 而采用递归计算复杂度应该为0(c) c只与width(n) 有关。可以认为是个常量。看看对如下几组数据的测试结果。如果采用循环，如第二个表。

测试数据递归	结果	用时(real)
987654	595336	0m0.159s
9876543	6941015	0m0.153s
98765432	79286694	0m0.158s
987654321	891632373	0m0.169s

测试数据循环	结果	时间(real)
987654	595336	0m1.129s
9876543	6941015	0m12.750s
98765432	79286694	2m13.896s
987654321	891632373	25m15.260s