计算4000000000以内最大的f(n)=n的值---字符串问题python实现(五)

问题:

       写一个函数,计算4 000 000 000 以内的最大的那个f(n)=n的值,函数f的功能是统计所有0到n之间所有含有数字1的数字和。比如:f(13)= 6,因为“1”在“1,2,3,4,5,6,7,8,9,10,11,12,13”中的总数是6(1,10,11,12,13)。

分析:

       一、简单方法 — 枚举

       采用“枚举法”对每个数都计算一遍1的个数,直到枚举完给定范围所有数,找到符合f(n)=n的数。此方法,代码效率极低,运算所需时间巨大。

python版本代码如下:

# -*- coding:utf-8 -*-
# 问题:写一个函数,计算4 000 000 000 以内的最大的那个f(n)=n的值,
#      函数f的功能是统计所有0到n之间所有含有数字1的数字和。比如:f(13)= 6,
#      因为“1”在“1,2,3,4,5,6,7,8,9,10,11,12,13”中的总数是6(1,10,11,12,13)。
# by chasdmeng
import time
def Calculation_One_Times(n):
    res = 0
    while n > 0:
        if n == 1:res +=1
        n /=10
    return res

if __name__ == ‘__main__‘:
    times = 0
    i = 0
    gMAX = 4000000000L
    start = time.time()
    while i < gMAX:
        times +=Calculation_One_Times(i)
        if times ==i:print "f(", i, ") = ", times
        i +=1
    end = time.time()
    print "time:",end - start

        二、高效方法 — 剪枝

       主要采用剪枝算法对代码执行效率进行优化。求解MAX(f(n)=n)具体算法构建分析如下:

       1、求数字“0~n”中“1”的个数

       基本思想:

       t位数字n,求0到n所有数字“1”的数字和,可对1到t位(1对应个位),每个位置上“1”出现的次数分别统计,然后求和。

       假设,0到n之间的自然数范围内,统计第m位为“1”的个数和,可以分四步骤。第一步骤,假设第二、三步骤的前提条件为第1到第m-1位内各位数字取固定值a。第二步骤,求大于m位的数字中有多少个数字第m位为“1”。第三步骤,求等于m位的数字中有多少个数字第m位为“1”。第四步骤,把第1到第m-1位内各位数字变化考虑进去。如下图所示。

计算4000000000以内最大的f(n)=n的值---字符串问题python实现(五)

       在第二步骤中,需要分两种情况考虑:

      (a)给定数n的第m位非0

       大于m位的数字中第m位为“1”的数字个数是n/10^m。

        (b)给定数n的第m位为0
       对于m位的数字中第m位为“1”的数字个数为(n/10^m)-1。这里举例说明,n=300,m=2,由于300的第2位为0,此时n/10^m=3,若按(a)中方法求解得出在第1位固定取a 的条件下(第一步骤中规定的)大于2位的数字中第2位为“1”的数字个数是3,这显然是错误的,因为在0到300中这样的数只有“11a”、“21a”,此时正确个数应该是n/10^m-1=2。
      (c)合并考虑

       大于m位的数字中第m位为“1”的数字个数为(n/(10^(m-1))-1)/10。构造了一个通用公式可以包含(a)、(b)两种情况。原理是,n/10^m=(n/(10^(m-1)))/10,由于是对n做除是向下取整运算,在给定数n第m位非0情况下,n/10^m=(n/(10^(m-1)))/10=(n/(10^(m-1))-1)/10;而当给定数n第m位为0情况下,(n/10^m)-1=(n/(10^(m-1))-1)/10。可以举具体数字对其验证。
       在第三步骤中,由于在第一步骤假定的前提条件,满足求等于m位的数字中第m位为“1”的个数只有1个。这里举例说明,n=300,m=2,2位数字中第2位为“1”的数仅有“1a”。
       在第四步骤中,综合第一、二、三步骤后,在第1到第m-1位内各位数字取固定值a的条件下,第m位为“1”的个数和为(n/(10^(m-1))- 1)/10+1。下面把第1到第m-1位内各位数字变化考虑进去,由于在第1到第m-1位中每一位可以放0~9之间任意数,m-1位数共有“10^m-1”个。最终,0到n之间的自然数范围内,第m位为“1”的个数和((n/(10^(m-1))- 1)/10+1)*(10^(m-1))。
       小结:对以上分析结果给予公式化定义。Cm=((n/i - 1)/10 + 1)*i,其中i=10^(m-1),n为任意自然数,Cm为0到n的数中第m位为1 的 个数和。

       求数字“0~n”中“1”个数的GetTimes()函数,python版代码如下

def GetTimes(n):
    temp = n
    temp2 =1
    ret = 0
    i = 1
    while temp/i:
        ret +=(((temp/i-1)/10)+1)*i
        if(((temp/i)%10) == 1):
            ret -=i
            ret +=temp2
        i*=10
        temp2=n%i+1
    return ret

       2、从0到n位最大数之间1的总个数,寻找数学规律

       当n=1,2,3,...,6,...时,分别计算从0到n位最大数之间1的总个数,部分数据如下:

       0~9          :1
       0~99        :20 = 10*1 + 10
       0~999      :300 = 10*20 + 100
       0~9999    :4000 = 10*300 + 1000
       0~99999  :50000 = 10*4000 + 10000
       0~999999:600000 = 10*50000 + 100000
       …                   

       从中,可以发现如下规律:

       a1 = 1
       a2 = 10*a1 + 10
       …
       an = 10*an - 1 + 10^(n - 1)
       即0~9…9(n个9)之间1的个数为an=10*an-1+10^(n-1)个。

       这样,当计算任意一个数字n的0到n之间所有数字1的个数和时,可以采用将数字n拆分成0~9、0~99... 等部分进行之间计算。例如:n=123,可将n拆分为0~99和100~123计算:(1)0~99对应1的个数和直接可知为20;(2)百位数1的个数为23+1个;(3)剩下的0~23继续拆分为0~9、10~19、20~23,共两个0~9个数为2;(4)因为23中十位数2>1,十位为1的个数10;(5)现在就剩下20~23了,个数为1。所以,0~123中1的个数为20+24+2+10+1=57。

       因此,在求任意数0~n内所有1的个数和时,可以首先建立“int  gTable[10]”结构用于存放a1、a2、a3、...、a9、a10,其中an表示0~n内所有1的个数,然后将数n拆分为0~9、0~99... 等部分直接使用gTable的值进行计算。这种方式可以提高算法效率。

       生成gTable[]结构的TimesTable()函数,python版代码如下:

def TimesTable(n):
    return [GetTimes(10**(i+1) - 1) for i in xrange(n)]

       3、采用剪枝算法搜索0~n之间满足f(q)=q的数

       由于若对0~n的所有数据进行枚举验证f(q)=q,当n值很大时运算相当费时,从本文开头给出的“最简单方法”中可以感受到代码效率有多么低。为了优化算法提高效率可采用减枝算法,其思想是对0~n之间所有数建立搜索树,对不符合条件的搜索树进行剪枝,这样就可以极大缩小搜索范围,提高算法效率。如何构建剪枝规则呢?首先对这个问题进行数学化描述:

       定义1:设 f(x)=y,其中x∈ (0,n),f为x与对应的(0,x)上所有数字1的个数总和y的映射。

       先观察下f(n)的特点,可以发现f(n)是一个单调递增函数,这样可以归纳出它的特性:

       性质1:若有f(m)=a,f(t)=b,且m<t,则存在q∈(m,t)满足f(q)=q成立的条件是:b>m 且a< t。

       现在就可以应用“性质1”进行减枝操作。具体来说通过“性质1”可知,当对0~n的所有数据进行枚举验证f(q)=q时,若当f(t)=b<m或f(m)=a>n,则在[m,t]范围内不存在满足f(q)=q成立的数q,这样就可忽略掉[m,t]内这些自然数,直接跳到n+1往后继续枚举。在应用剪枝算法枚举符合条件的f(q)=q时,是以t-m为步长在0~n内逐段排查是否可剪枝,若t-m范围内不满足剪枝条件则进行枚举搜索。因此在进行剪枝算法时[m,t]的范围取多大适合呢?这是需要慎重考虑的问题,合理的[m,t]取值能让大幅提升算法执行效率。下面就对[m,t]步长L取值进行分析。

       [m,t]的取值依据是能最大化提升算法效率,由于在“2、从0到n位最大数之间1的总个数,寻找数学规律。”中设置了“int  gTable[10]”结构用于计算f(n),gTable分别表示0~9中1个数和1、0~99中1个数和20、0~999中1的个数和300...,可见是以10^p倍增长,而且f(n)还需要使用gTable去求解,因此初步考虑将[m,t]步长L=10^p,虽然[m,t]取10的倍数,但p具体取多少,还需要继续分析。

        对于任意s位数m,设s位数的最大值为max(s),则f(max(s))=gTable[s-1],假定取[m,t]步长L=10^s也就是 t=m+10^s,设f(m)=a、f(m+10^s)=b,则有m<max(s)<m+10^s,由于f()为单调增函数,推出gT[s-1]=f(max(s))<f(m+10^s)=b,a<gTable[s-1],又因为在0~10^10-1的范围内有max(s)>gTable[s-1](可以举例验证),推出a<gTable[s-1]<max(s)<10+10^s,即a<m+10^s。f(m+10^s)=f(10^s-1)+m+1+f(m)=b,即b>m,因此根据性质1可知m=d*10^s时,取[m,t]步长L=10^s恒不满足减枝条件,同理步长L=10^(s+1)也无法满足剪枝条件,因此只能往下取值。对于任意s位数m,取步长L<=10^(s-1)某些数内可以满足减枝条件,举例来说,m=20,s=2,L=10^(s-1)=10,则在[20,30]内f(20)=12、f(30)=13,根据性质1可以剪枝掉[20,30]范围内的数。综上所述,对任意s位数m,m∈ (0,n),剪枝算法初始步长L=10^(s-1)   。

       性质2:若有f(m)=a,f(t)=b,且m<t,满足b>m 且a< t时,有f(q)=q,且q∈(m,b]。

       性质2是由性质1推到而来,性质2中将原来性质1中q∈(m,t)缩小为q∈(m,b)。首先在0~10^10-1的范围内满足性质1条件下可知b∈(m,t],设f(b+1)=c,则在(b+1,t)内f(b+1)=c、f(t)=b根据性质1不存在q∈(b+1,t)使f(q)=q成立。所以,在(m,t)内使f(q)=q成立的q∈(m,b]。

        剪枝算法整体思想是:n位数m,步长L=10^(n-1),在区间(m-1,m+L-1判断是否满足f(m-1)>boundary或f(m+L-1)<m ,满足就直接跳到m=m+L计算,否则在区间(m-1,f(m+L-1)+L-1)上置步长L=L/10递归重复执行剪枝判断,当递归到步长L=1时,进行逐值枚举f(number)是否等于number。由于算法中m是从0开始枚举取值,以10的倍数递增,因此所有的m都应满足abc*10^s格式,也就是说,m取到的是10的倍数。因此有如下性质。

       性质3:m=abc*10^(n-1),L=10^(n-1),可知f(m-1+L)=f(m-1)+gTable[n-2]+count_one_m*L,其中count_one_m=f(m)-f(m-1),也就是代表数字m本身包含1的个数。

       剪枝算法CalculationTimes()函数,python版代码如下 : 

def CalculationTimes(number, weight, count_one, count, table):
    if weight == 0:
        count += count_one
        if number == count:
            print "f(", number, ") = ", number
        return count
    L=10**weight
    maxcount = count + table[weight - 1]
    maxcount += count_one*L
    if count > (number + L -1):
        return maxcount
    if maxcount < number:
        return maxcount
    L /= 10
    for i in range(10):
        if i == 1:
            count = CalculationTimes(number + i*L, weight - 1, count_one + 1, count, table)
        elif i == maxcount/n - 9:
            return maxcount
        else:
            count = CalculationTimes(number + i*L, weight - 1, count_one , count, table)
    return count

       其中,对应前面剪枝算法思想,这里number代表m,weight代表步长L=10^(s-1) 中的s-1,count_one表示数n中各个位置上1的个数,比如n=112,这count_one=2,table代表gTable[],count代表f(m-1)。具体解释如下:

if weight == 0:
        count += count_one
        if number == count:
            print "f(", number, ") = ", number
        return count
此部分代码判断当前步长L若为1(L=10^weight)计算f(number),f(number)通过count+=count_one实现,这是由于在步长L=1前提下,f(number)等于f(number-1)加上数字mumber本身1的个数count_one,既f(number)=f(number-1)+count_one,若f(number)=number,则输出,否则返回当f(number)。

    L=10**weight
    maxcount = count + table[weight - 1]
    maxcount += count_one*L
    if count > (number + L -1):
        return maxcount
    if maxcount < number:
        return maxcount

此部分代码功能执行剪枝操作,首先设置步长L=10^weight,根据性质3得f(number+L-1)=count+table[weight-1]+count_one*L,然后根据性质1判断是否可以剪枝,若符合条件直接忽略(number-1,number+L-1)范围内数字并跳转到number+L再计算。

    L /= 10
    for i in range(10):
        if i == 1:
            count = CalculationTimes(number + i*L, weight - 1, count_one + 1, count, table)
        elif i == maxcount/n - 9:
            return maxcount
        else:
            count = CalculationTimes(number + i*L, weight - 1, count_one , count, table)
    return count
若不满足剪枝条件执行此部分代码。首先根据前面描述的剪枝算法整体思想将步长缩短L=L/10,然后根据性质2仅需递归计算(number-1,f(number+L-1)范围内数即可,当i==1时,number+i*L这个数本身将多出一个”1“需要将count_one值加1,当i==maxcount/n-9时,number+i*L将超出范围终止计算。

       最后,给出整体实现代码。

# -*- coding:utf-8 -*-
# 问题:写一个函数,计算4 000 000 000 以内的最大的那个f(n)=n的值,
#      函数f的功能是统计所有0到n之间所有含有数字1的数字和。比如:f(13)= 6,
#      因为“1”在“1,2,3,4,5,6,7,8,9,10,11,12,13”中的总数是6(1,10,11,12,13)。
# by chasdmeng
import time 
def GetTimes(n):
    temp = n
    temp2 =1
    ret = 0
    i = 1
    while temp/i:
        ret +=(((temp/i-1)/10)+1)*i
        if(((temp/i)%10) == 1):
            ret -=i
            ret +=temp2
        i*=10
        temp2=n%i+1
    return ret
def TimesTable(n):
    return [GetTimes(10**(i+1) - 1) for i in xrange(n)]
def CountOne(n):
    count = 0
    while n:
        if (n%10) == 1:count +=1
        n /=10
    return count
def CalculationTimes(number, weight, count_one, count, table):
    if weight == 0:
        count += count_one
        if number == count:
            print "f(", number, ") = ", number
        return count
    L=10**weight
    maxcount = count + table[weight - 1]
    maxcount += count_one*L
    if count > (number + L -1):
        return maxcount
    if maxcount < number:
        return maxcount
    L /= 10
    for i in range(10):
        if i == 1:
            count = CalculationTimes(number + i*L, weight - 1, count_one + 1, count, table)
        elif i == maxcount/n - 9:
            return maxcount
        else:
            count = CalculationTimes(number + i*L, weight - 1, count_one , count, table)
    return count

if __name__ == ‘__main__‘:
    n = 0
    weight = 0
    count = 0
    count_one = 0
    gMAX = 4000000000L
    start = time.time()
    table = TimesTable(10)
    while n < gMAX:
        count = CalculationTimes(n, weight, count_one , count, table)
        L = 10**weight
        n += L
        if (n/L)/10 == 1: weight +=1
        count_one = CountOne(n)
    end = time.time()
    print "time:",end - start

                                                                                                                                                         by       chasdmeng

参考文献:

      博客:http://blog.csdn.net/livelylittlefish/article/details/2768348

      书籍:《程序员面试宝典(第4版)》P240,面试例题5





计算4000000000以内最大的f(n)=n的值---字符串问题python实现(五),布布扣,bubuko.com

计算4000000000以内最大的f(n)=n的值---字符串问题python实现(五)

上一篇:对学习C++的一些忠告


下一篇:Android网络开启、关闭整理