鱼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亿就算不出来了，看看大家怎么写的，学习学习

1. def hanming(n):
   
2.     if not n%2:
   
3.         return hanming(n/2)
   
4.     if not n%3:
   
5.         return hanming(n/3)
   
6.     if not n%5:
   
7.         return hanming(n/5)
   
8.     if n==1:
   
9.         return 1
   
10. num=input('请输入汉明数范围：')
    
11. count=0
    
12. for i in range(1,int(num)+1):
    
13.     if hanming(i):
    
14.         count+=1
    
15. 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版本

1. def gethamming2(n):
   
2.         amax = int(log(n,2))
   
3.         bmax = int(log(n,3))
   
4.         cmax = int(log(n,5))
   
5.         r = 0
   
6.         ap = 1
   
7.         for a in range(amax+1):
   
8.                 abp = ap
   
9.                 for b in range(bmax+1):
   
10.                         if abp > n:
    
11.                                 break
    
12.                         abcp = abp
    
13.                         for c in range(cmax+1):
    
14.                                 if abcp > n:
    
15.                                         break
    
16.                                 r += 1
    
17.                                 abcp *= 5
    
18.                         abp *= 3
    
19.                 ap *= 2
    
20.         return r       
    
21. 
    
22. def gethamming3(n):
    
23.         amax = int(log(n,2))
    
24.         bmax = int(log(n,3))
    
25.         r = 0
    
26.         ap = 1
    
27.         for a in range(amax+1):
    
28.                 abp = ap
    
29.                 for b in range(bmax+1):
    
30.                         if abp > n:
    
31.                                 break
    
32.                         r += 1 + int(log(n/abp, 5)) #1 include c==0
    
33.                         abp *= 3
    
34.                 ap *= 2
    
35.         return r       
    
36. 
    
37. def gethamming4(n):
    
38.         bmax = int(log(n,3))
    
39.         cmax = int(log(n,5))
    
40.         r = 0
    
41.        
    
42.         cp = 1
    
43.         for c in range(cmax+1):
    
44.                 cbp = cp
    
45.                 for b in range(bmax+1):
    
46.                         if cbp > n:
    
47.                                 break
    
48.                         #2 loop times =[0..log2(n/cbp)]
    
49.                         r += 1 + int(log(n/cbp,2)) #1 include a==0
    
50.                         cbp *= 3
    
51.                 cp *= 5
    
52.         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