鱼C论坛Python精英挑战赛（第二季02期）

Assistant

啊啊啊，没学过算法，还以为我做得很好了，原来还有比我快的，真是人外有人啊，看来我python入完门后应该再去看看算法

jerryxjr1220

Assistant 发表于 2017-8-15 09:32
啊啊啊，没学过算法，还以为我做得很好了，原来还有比我快的，真是人外有人啊，看来我python入完门后应该再 ...

你的程序确实已经挺快了，至少比我的程序还要快点，不过这期高手真的很多，惜败了

老甲鱼与小甲鱼

pythonDemo 发表于 2017-8-15 00:22
不大于5的质数是1，2，3，5，   至于4，是2*2

百度和我的小学老师告诉我，1不是质数。。。

Assistant

jerryxjr1220 发表于 2017-8-15 10:06
你的程序确实已经挺快了，至少比我的程序还要快点，不过这期高手真的很多，惜败了

谢谢夸奖，
一起加油吧！

小贱剑

我用的递归写的，果然1亿就算不出来了，看看大家怎么写的，学习学习

def hanming(n):
    if not n%2:
        return hanming(n/2)
    if not n%3:
        return hanming(n/3)
    if not n%5:
        return hanming(n/5)
    if n==1:
        return 1
num=input('请输入汉明数范围：')
count=0
for i in range(1,int(num)+1):
    if hanming(i):
        count+=1
print(count)

过客1993

gunjang 发表于 2017-8-12 18:09

好快，这算法表示看不懂了，log的知识已经还给数学老师了

gunjang

过客1993 发表于 2017-8-15 12:01
好快，这算法表示看不懂了，log的知识已经还给数学老师了

这个是第四版本了，第一版就是直接采用指数统计呀
假设n=2^a*3^b*5^c ,a,b,为大于等于0的整数
n肯定就是汉明数
然后一个个数过去

优化版本是采用log
假设3和5的指数确定了，则2^a *（3^b*5^c）< 10^100
取log2则 a<log2(10^100 / （3^b*5^c）
则a 可以取[0..int(log2(10^100 / （3^b*5^c）)]
也就是 int(log2(10^100 / （3^b*5^c）)+1个
至于为什么按5 3 2的顺序
是因为2的amax 明显 大于 5的cmax，可以减少迭代次数
贴上2 3 4 4.2版本

def gethamming2(n):
        amax = int(log(n,2))
        bmax = int(log(n,3))
        cmax = int(log(n,5))
        r = 0
        ap = 1
        for a in range(amax+1):
                abp = ap
                for b in range(bmax+1):
                        if abp > n: 
                                break
                        abcp = abp
                        for c in range(cmax+1):
                                if abcp > n:
                                        break
                                r += 1
                                abcp *= 5
                        abp *= 3
                ap *= 2
        return r        

def gethamming3(n):
        amax = int(log(n,2))
        bmax = int(log(n,3))
        r = 0
        ap = 1
        for a in range(amax+1):
                abp = ap
                for b in range(bmax+1):
                        if abp > n: 
                                break
                        r += 1 + int(log(n/abp, 5)) #1 include c==0
                        abp *= 3
                ap *= 2
        return r        

def gethamming4(n):
        bmax = int(log(n,3))
        cmax = int(log(n,5))
        r = 0
        
        cp = 1
        for c in range(cmax+1):
                cbp = cp
                for b in range(bmax+1):
                        if cbp > n: 
                                break
                        #2 loop times =[0..log2(n/cbp)]
                        r += 1 + int(log(n/cbp,2)) #1 include a==0
                        cbp *= 3
                cp *= 5
        return r

#Win7 64+Python 3.62 64 + AMD Phenom II X4 965 + DDR3*8G
st = time.time()
print(gethamming2(10**100)) #1697191
t = time.time()-st
print("V2 cost", t) #1=3.5(use **) #2=0.3240184783935547

st = time.time()
print(gethamming3(10**100)) #1697191
t = time.time()-st
print("V3 cost", t) #3=0.04100227355957031

st = time.time()
print(gethamming4(10**100)) #1697191
t = time.time()-st
print("V4 cost", t) #4=0.017000913619995117

st = time.time()
print(gethamming4_2(10**100)) #1697191
t = time.time()-st
print("V4.2 cost", t) #4.2=0.016000747680664062

gunjang

Assistant 发表于 2017-8-15 09:32
啊啊啊，没学过算法，还以为我做得很好了，原来还有比我快的，真是人外有人啊，看来我python入完门后应该再 ...

小姐姐的版本很简洁。。。
我也是刚自学的python