Python中求从1到n正整数中1的个数

可以使用数学归纳法证明，对于一个数n，可以将它拆分成n = a * 10^i + b，其中a是n的最高位数字，b是除最高位数字外剩余的部分。

如果a = 0，则n的最高位数字为0，此时1的个数为：

f(n) = f(b)

如果a = 1，则n的最高位数字为1，此时1的个数为：

f(n) = f(b) + (b + 1)

如果a > 1，则n的最高位数字大于1，此时1的个数为：

f(n) = a * f(10^i-1) + 10^i

其中f(10^i-1)表示从1到10^i-1的所有数字中1的个数。

根据以上递推公式，可以写出Python程序求解从1到n正整数中1的个数：

def count_one(n):
    if n <= 0:
        return 0
    s = str(n)
    high = int(s[0])  # 最高位数字
    pow10 = 10 ** (len(s) - 1)  # 10的幂次方
    last = n - high * pow10  # 除最高位数字外剩余部分
    if high == 1:
        return count_one(pow10 - 1) + count_one(last) + last + 1
    else:
        return high * count_one(pow10 - 1) + pow10 + count_one(last)

例如，count_one(120)的结果为93，表示从1到120中1的个数为93个。