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

xiewen1235

初次发帖，请多支持

1. import datetime
   
2. import math
   
3. starttime = datetime.datetime.now()
   
4. Maxnum = 10**100
   
5. 
   
6. #对数化，由指数问题转化为加减问题
   
7. edge2 = math.log(Maxnum,2)
   
8. edge3 = math.ceil(math.log(Maxnum,3))
   
9. edge5 = math.ceil(math.log(Maxnum,5))
   
10. 
    
11. num = 0
    
12. log5 = math.log(5,2)
    
13. log3 = math.log(3,2)
    
14. #每次取i个5，j个3，每次通过减法得到2的区间并不断累加
    
15. for i in range(0,edge5):
    
16.     for j in range(0,edge3):
    
17.         k=  math.ceil(edge2 - i*log5 - j*log3)
    
18.         if k > 0:
    
19.             num += k
    
20. 
    
21. print ('%d 以内总共有 %d 个汉明数' %(Maxnum,num))
    
22. 
    
23. endtime = datetime.datetime.now()
    
24. alltime = endtime - starttime
    
25. print ('总共花了 %s 秒' % alltime)
    

复制代码

经检测，时间如下：
=================== RESTART: C:\Users\DELL\Desktop\Time.py ===================
1000 以内总共有 85 个汉明数
总共花了 0:00:00.014654 秒
>>>
=================== RESTART: C:\Users\DELL\Desktop\Time.py ===================
100000000 以内总共有 1105 个汉明数
总共花了 0:00:00.017279 秒
>>>
=================== RESTART: C:\Users\DELL\Desktop\Time.py ===================
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 以内总共有 1697191 个汉明数
总共花了 0:00:00.060183 秒
>>>

Gabber

我还在入门阶段，但是好想观摩下前辈们的codes啊

Assistant

你好，
5**144>10**100
3**210>10**100
2**333>10**100
这三个能否作为已知条件？

Assistant

Assistant 发表于 2017-8-13 01:45
你好，
5**144>10**100
3**210>10**100

请无视此楼

意外惊喜sad

新人来报道~
下面这个是修改过之后的程序

1. print('==================求汉明数个数========================')
   
2. import time
   
3. import numpy as np
   
4. #定义全局变量
   
5. x = input('请输入最大值中10的幂指数：')
   
6. H = [1]
   
7. x = int(x)
   
8. y = 430   #调试参数，保证2**y>10**100
   
9. T1 = list(np.logspace(1,y,y,base=2))
   
10. T2 = list(np.logspace(1,y,y,base=3))
    
11. T3 = list(np.logspace(1,y,y,base=5))  
    
12. #定义新函数f1(),判断每个列表中符合要求的数并放入列表H中
    
13. def f1(X) :
    
14.     for i in range(0,y) :
    
15.         if X[i] <=10**x :
    
16.             H.append(X[i])
    
17.         else :
    
18.             break
    
19. #定义新函数f2(),每个列表中的元素两两相乘，将符合要求的数放入H中
    
20. def f2(X,Y):
    
21.     for a in X :
    
22.         if a > 10**x :
    
23.             break   
    
24.         for b in Y :
    
25.             if b > 10**x :
    
26.                 break
    
27.             h = a*b
    
28.             if h <= 10**x :
    
29.                 H.append(h)
    
30.             else :
    
31.                 break
    
32. #运行程序主体
    
33. start = time.clock()
    
34. f1(T1)
    
35. f1(T2)
    
36. f1(T3)
    
37. f2(T1,T2)
    
38. f2(T1,T3)
    
39. f2(T2,T3)
    
40. #三三相乘，将符合要求的数放入H中        
    
41. for a in T1 :
    
42.     if a > 10**x :
    
43.         break
    
44.     for b in T2 :
    
45.         if b > 10**x :
    
46.             break
    
47.         for c in T3 :
    
48.             if c > 10**x :
    
49.                 break
    
50.             h = a*b*c
    
51.             if h <=10**x :
    
52.                 H.append(h)
    
53.             else :
    
54.                 break
    
55. print('10**',x,'以内包含的汉明数个数:',len(H))
    
56. end = time.clock()
    
57. print ('运行时间:',end-start,'s')
    

复制代码

运行结果：

1. ==================求汉明数个数========================
   
2. 请输入最大值中10的幂指数：8
   
3. 10** 8 以内包含的汉明数个数: 1105
   
4. 运行时间: 0.03742721926610512 s
   
5. >>>
   
6. ==================求汉明数个数========================
   
7. 请输入最大值中10的幂指数：2
   
8. 10** 2 以内包含的汉明数个数: 34
   
9. 运行时间: 0.02984148582876169 s
   
10. >>>
    
11. ==================求汉明数个数========================
    
12. 请输入最大值中10的幂指数：100
    
13. 10** 100 以内包含的汉明数个数: 1697190
    
14. 运行时间: 27.276055697650705 s

复制代码

Assistant

1. e,f,g,count,n = 1,1,1,0,10**100
   
2. while e <= n:
   
3.     while e <= n:
   
4.         while e <= n:
   
5.             count += 1
   
6.             e *= 2
   
7.         f *= 3
   
8.         e = g * f
   
9.     g *= 5
   
10.     f = 1
    
11.     e = g
    
12. print(count)
    

复制代码

michaelol

高效版本，找出10**100以内的汉明数只要7秒  答案 1697191个

1. def hanmingshu(n):
   
2.     hanming=set()
   
3.     factor=[2,3,5]
   
4.     hanming_temp=set()
   
5.     hanming_tempnew=set()
   
6.     hanming_temp.add(1)
   
7.     hanming_tempmin=min(hanming_temp)
   
8.     if n==1:
   
9.         hanming.update(hanming_temp)
   
10.         return hanming
    
11.     else:
    
12.         hanming.update(hanming_temp)
    
13.         while(hanming_tempmin*2<=n):
    
14.             for i in hanming_temp:
    
15.                 for j in factor:
    
16.                     if i*j<=n:
    
17.                         hanming_tempnew.add(i*j)
    
18.                     else:
    
19.                         break
    
20.             hanming.update(hanming_tempnew)
    
21.             hanming_temp.clear()
    
22.             hanming_temp.update(hanming_tempnew)
    
23.             hanming_tempmin=min(hanming_temp)
    
24.             hanming_tempnew.clear()
    
25.     return hanming
    
26. 
    
27. print(len(hanmingshu(10**100)))

复制代码

michaelol

高效版本 找出10**100以内的汉明数 需要7秒 答案1697191个

1. def hanmingshu(n):
   
2.     hanming=set()
   
3.     factor=[2,3,5]
   
4.     hanming_temp=set()
   
5.     hanming_tempnew=set()
   
6.     hanming_temp.add(1)
   
7.     hanming_tempmin=min(hanming_temp)
   
8.     if n==1:
   
9.         hanming.update(hanming_temp)
   
10.         return hanming
    
11.     else:
    
12.         hanming.update(hanming_temp)
    
13.         while(hanming_tempmin*2<=n):
    
14.             for i in hanming_temp:
    
15.                 for j in factor:
    
16.                     if i*j<=n:
    
17.                         hanming_tempnew.add(i*j)
    
18.                     else:
    
19.                         break
    
20.             hanming.update(hanming_tempnew)
    
21.             hanming_temp.clear()
    
22.             hanming_temp.update(hanming_tempnew)
    
23.             hanming_tempmin=min(hanming_temp)
    
24.             hanming_tempnew.clear()
    
25.     return hanming
    
26. 
    
27. print(len(hanmingshu(10**100)))

复制代码

qitan888

借鉴了网上的一个汉明数的函数
主要思路，先按照指数方式初步计算，然后通过二分法精确计算，代码如下：

1. #!/bin/python
   
2. #coding=utf-8
   
3. 
   
4. # 网站上搜来的一个函数,求第 n 个汉明数。算是解题的基础吧。
   
5. # 参考链接：http://blog.csdn.net/crowhe1993/article/details/52863242
   
6. 
   
7. def hamming(n):
   
8.     k1,k2,k3 = 0,0,0
   
9.     res = [1]
   
10.     for i in range(1,n):
    
11.         s1 = res[k1]*2
    
12.         s2 = res[k2]*3
    
13.         s3 = res[k3]*5
    
14.         min_val = min(s1,s2,s3)
    
15.         res.append(min_val)
    
16.         if res[i] == s1:
    
17.             k1 +=1
    
18.         if res[i] == s2:
    
19.             k2 += 1
    
20.         if res[i] == s3:
    
21.             k3+= 1
    
22.     return res[-1]
    
23. 
    
24. # 初步查找范围，由于数比较大，采用指数方式
    
25. 
    
26. def hamno(n):
    
27.     m = hamming(n)
    
28.     i = 0
    
29.     while m <= 10**100:
    
30.         i += 1
    
31.         n = n*2
    
32.         m = hamming(n)
    
33.         print("正在进行第{}次初步计算".format(i))
    
34.     print("初步计算结束，锁定范围为：({},{})".format(int(n/2),n))
    
35.     return int(n/2)
    
36. 
    
37. # 精确查找，使用二分法查找方式
    
38. 
    
39. def binary(n):
    
40.     i = 0
    
41.     n = hamno(n)
    
42.     a=range(n,n*2)
    
43.     x = 0
    
44.     z = len(a) - 1
    
45.     while x < z:
    
46.         i += 1
    
47.         print("正在进行第{}次精确计算".format(i))
    
48.         y = int((x+z)/2)
    
49.         if hamming(a[y]) < 10**100:
    
50.             x = y+1
    
51.         elif hamming(a[y]) > 10**100:
    
52.             z = y
    
53.         else:
    
54.             return a[y]
    
55.     return a[z]
    
56. 
    
57. if __name__ == "__main__":
    
58.     n = 1
    
59.     print("精确计算结束，10**100（包含）内汉明数的个数为：{}".format(binary(n)))

复制代码

ba21

1. def hamming(n):
   
2.     hm=[1,2,3]
   
3.     while(1):
   
4.         m2=True
   
5.         m3=True
   
6.         m5=True      
   
7.         hmTemp=[]
   
8.         lastHm=hm[-1]
   
9.         
   
10.         if lastHm % 5 == 0:
    
11.             firstHmindex=hm.index(lastHm//5)            
    
12.         else:
    
13.             firstHmindex=0
    
14.             
    
15.         for m in hm[firstHmindex:]:
    
16.             if m*2>lastHm and m2:
    
17.                 m2=False
    
18.                 hmTemp.append(m*2)
    
19.                 break #如果*2都已经比最大的丑数大了，则退出
    
20.                
    
21.             if m*3>lastHm and m3:
    
22.                 m3=False
    
23.                 hmTemp.append(m*3)
    
24.             
    
25.             if m*5>lastHm and m5:
    
26.                 m5=False
    
27.                 hmTemp.append(m*5)
    
28.                
    
29.       
    
30.         cm=min(hmTemp)
    
31.         hm.append(cm)
    
32.         if cm>=n:
    
33.             break  
    
34.     return len(hm)
    
35. 
    

复制代码

guoxike

1. import math as m
   
2. def hanming(n):
   
3.     hanm=[]
   
4.     m2=round(m.log(n,2)+0.5)
   
5.     m3=round(m.log(n,3)+0.5)
   
6.     m5=round(m.log(n,5)+0.5)
   
7.    
   
8.     for i in range(m2):
   
9.         for j in range(m3):
   
10.             for k in range(m5):
    
11.                 if 2**i*3**j*5**k<=n:
    
12.                     hanm.append(2**i*3**j*5**k)
    
13.     #hanm.sort()
    
14.     print("%d以内的汉明数有%d个 " %(n,len(hanm)))

复制代码

凤凰0620

代码已更新~请以最终版为准！谢谢谢谢~

古堡主人。

1. Allprime=[7]
   
2. Allham=[1,2,3,4,5,6]
   
3. hamcount=0
   
4. for i in range(7,10**6+1):
   
5.     hamorprime=True
   
6.     juestham=False
   
7.     for j in Allprime:
   
8.         if i%j==0:
   
9.             hamorprime=False
   
10.             break
    
11.     if hamorprime:#判断是不是质数
    
12.         for p in range(2,i-1):
    
13.             if i%p==0:#是汉明数不是质数
    
14.                 #hamcount+=1
    
15.                 #print(hamcount,end=' ')
    
16.                 print(i,end=' ')
    
17.                 Allham.append(i)
    
18.                 juestham=True
    
19.                 break
    
20.         if not juestham:#是质数不是汉明数
    
21.             Allprime.append(i)
    
22.    
    
23. print('All down')
    
24. print(Allprime)

复制代码

amanionly

chunchun2017

不是精英，也来挑战一下自己，

1. def daiming(n):
   
2.     list0 = [1,2,3,4,5]
   
3.     index1 = 2 #T2
   
4.     index2 = 1 #T3
   
5.     index3 = 1 #T5
   
6.     min0 = 5
   
7.     while (min0<n) :
   
8.         x = 2*list0[index1]
   
9.         y = 3*list0[index2]
   
10.         z = 5*list0[index3]
    
11.         min0 = ((x if x<y else y ) if (x if x<y else y)<z else z)
    
12.         if (min0 == x):
    
13.              index1+=1
    
14.         if (min0 == y):
    
15.              index2+=1
    
16.         if (min0 == z):
    
17.              index3+=1
    
18.         list0.append(min0)
    
19.     print(len(list0))
    
20. import time
    
21. tt=time.time()
    
22. daiming(10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000)
    
23. print('time used:{}'.format(time.time()-tt))
    

复制代码

运行结果：
1697191

人间四月尽

1. import time
   
2. #创建汉明数数组
   
3. ugly = [1]
   
4. #设定更新下标值
   
5. a = b = c = 0
   
6. #获取时间
   
7. t1 = time.time()
   
8. while ugly[-1] < 10**100:
   
9.         #下一个汉明数必然产生于其中
   
10.         next = min(2 * ugly[a], 3 * ugly[b], 5 * ugly[c])
    
11.         ugly.append(next)
    
12.         #更新下标值
    
13.         while 2 * ugly[a] <= ugly[-1]:
    
14.                 a += 1
    
15.         while 3 * ugly[b] <= ugly[-1]:
    
16.                 b += 1
    
17.         while 5 * ugly[c] <= ugly[-1]:
    
18.                 c += 1
    
19. #获取时间
    
20. t2 = time.time()
    
21. #打印程序运行时间
    
22. print(t2 - t1)
    
23. print(len(ugly))

复制代码

古堡主人。

之前发过一个但是好像运算速度比较慢，我是一个初学python，我说一下我的想法估计高手可以实现

1. Allprime=[2,3]
   
2. g=range(4,10**100,z)
   
3. for i in g:
   
4.     #判断i是否可以整除Allprime中所有的元素，只要一个可以整除，这个数就可以排除了，执行下一个循环，
   
5.     #如果都没有开始判断这个数是不是质数，如果不是，那么这个数是汉明数，记录并进入下一个循环，
   
6.     #否则这个数是质数
   
7.     #*******************************关键在这里*************************************
   
8.     #从g中剔除，这个质数的所有小于10**100的倍数，加入这个数字是7则g中剔除range(8,10**100,7)
   
9.     #这就相当把数据量减少了1/7,
   
10.     #遇到个质数就这没剔除一部分那么20以内的质数就可以剔除1/7+1/11+1/13+1/17+1/19就大约（以为存在同时是多个质数的公倍数，就相当于重复计算了）可以减去42.2%计算量
    
11. 
    
12. 
    
13.     #*******************************这里是关键*************************************

复制代码

bozhen

1. import math
   
2. 
   
3. nu = 10**100
   
4. xx = int(math.log(nu, 2)) + 1
   
5. yy = int(math.log(nu, 3)) + 1
   
6. zz = int(math.log(nu, 5)) + 1
   
7. nu_list = []
   
8. n = 1
   
9. for x in range(0, xx):
   
10.         for y in range(0, yy):
    
11.                 for z in range(0, zz):
    
12.                         n = (2**x) * (3**y) * (5**z)
    
13.                         if n < nu + 1:
    
14.                                 nu_list.append(n)
    
15.                         if n  > nu:
    
16.                                 break
    
17. print(len(nu_list))

复制代码

执行结果：
1697191
[Finished in 2.9s]

pythonDemo

老甲鱼与小甲鱼 发表于 2017-8-11 10:31
嗯，那个我理解有点问题，不大于5的质数不是只有2,3,5吗，为什么可以组合出1,4这种数，数学不太好，百度定 ...

不大于5的质数是1，2，3，5，   至于4，是2*2

Assistant

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