鱼C论坛

 找回密码
 立即注册
楼主: jerryxjr1220

[技术交流] 鱼C论坛Python精英挑战赛(第二季02期)

[复制链接]
发表于 2017-8-12 21:13:03 | 显示全部楼层
初次发帖,请多支持
  1. import datetime
  2. import math
  3. starttime = datetime.datetime.now()
  4. Maxnum = 10**100

  5. #对数化,由指数问题转化为加减问题
  6. edge2 = math.log(Maxnum,2)
  7. edge3 = math.ceil(math.log(Maxnum,3))
  8. edge5 = math.ceil(math.log(Maxnum,5))

  9. num = 0
  10. log5 = math.log(5,2)
  11. log3 = math.log(3,2)
  12. #每次取i个5,j个3,每次通过减法得到2的区间并不断累加
  13. for i in range(0,edge5):
  14.     for j in range(0,edge3):
  15.         k=  math.ceil(edge2 - i*log5 - j*log3)
  16.         if k > 0:
  17.             num += k

  18. print ('%d 以内总共有 %d 个汉明数' %(Maxnum,num))

  19. endtime = datetime.datetime.now()
  20. alltime = endtime - starttime
  21. 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 秒
>>>




评分

参与人数 1贡献 +2 收起 理由
jerryxjr1220 + 2 答题奖励,Time=0.137s

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-12 22:05:14 | 显示全部楼层
我还在入门阶段,但是好想观摩下前辈们的codes啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-13 01:45:06 From FishC Mobile | 显示全部楼层
你好,
5**144>10**100
3**210>10**100
2**333>10**100
这三个能否作为已知条件?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-13 02:21:08 From FishC Mobile | 显示全部楼层
Assistant 发表于 2017-8-13 01:45
你好,
5**144>10**100
3**210>10**100

请无视此楼
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-13 12:36:02 | 显示全部楼层
本帖最后由 意外惊喜sad 于 2017-8-14 18:31 编辑

新人来报道~
下面这个是修改过之后的程序
  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
复制代码

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
jerryxjr1220 + 1 + 1 答题奖励

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-13 15:00:26 | 显示全部楼层
  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)
复制代码

评分

参与人数 1荣誉 +1 鱼币 +1 贡献 +1 收起 理由
jerryxjr1220 + 1 + 1 + 1 答题奖励,Time=0.492s

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-13 15:52:55 | 显示全部楼层
高效版本,找出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. print(len(hanmingshu(10**100)))
复制代码

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
jerryxjr1220 + 1 + 1 答题奖励,Time=3.14s

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-13 15:57:13 | 显示全部楼层
高效版本 找出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. print(len(hanmingshu(10**100)))
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-13 16:09:10 | 显示全部楼层
本帖最后由 qitan888 于 2017-8-13 16:16 编辑

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

  1. #!/bin/python
  2. #coding=utf-8

  3. # 网站上搜来的一个函数,求第 n 个汉明数。算是解题的基础吧。
  4. # 参考链接:http://blog.csdn.net/crowhe1993/article/details/52863242

  5. def hamming(n):
  6.     k1,k2,k3 = 0,0,0
  7.     res = [1]
  8.     for i in range(1,n):
  9.         s1 = res[k1]*2
  10.         s2 = res[k2]*3
  11.         s3 = res[k3]*5
  12.         min_val = min(s1,s2,s3)
  13.         res.append(min_val)
  14.         if res[i] == s1:
  15.             k1 +=1
  16.         if res[i] == s2:
  17.             k2 += 1
  18.         if res[i] == s3:
  19.             k3+= 1
  20.     return res[-1]

  21. # 初步查找范围,由于数比较大,采用指数方式

  22. def hamno(n):
  23.     m = hamming(n)
  24.     i = 0
  25.     while m <= 10**100:
  26.         i += 1
  27.         n = n*2
  28.         m = hamming(n)
  29.         print("正在进行第{}次初步计算".format(i))
  30.     print("初步计算结束,锁定范围为:({},{})".format(int(n/2),n))
  31.     return int(n/2)

  32. # 精确查找,使用二分法查找方式

  33. def binary(n):
  34.     i = 0
  35.     n = hamno(n)
  36.     a=range(n,n*2)
  37.     x = 0
  38.     z = len(a) - 1
  39.     while x < z:
  40.         i += 1
  41.         print("正在进行第{}次精确计算".format(i))
  42.         y = int((x+z)/2)
  43.         if hamming(a[y]) < 10**100:
  44.             x = y+1
  45.         elif hamming(a[y]) > 10**100:
  46.             z = y
  47.         else:
  48.             return a[y]
  49.     return a[z]

  50. if __name__ == "__main__":
  51.     n = 1
  52.     print("精确计算结束,10**100(包含)内汉明数的个数为:{}".format(binary(n)))
复制代码

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
jerryxjr1220 + 1 + 1 答题奖励

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-13 16:46:54 | 显示全部楼层
  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)

复制代码

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
jerryxjr1220 + 1 + 1 答题奖励

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-13 18:01:15 | 显示全部楼层
  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)))
复制代码

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
jerryxjr1220 + 1 + 1 答题奖励

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-14 11:31:43 | 显示全部楼层
代码已更新~请以最终版为准!谢谢谢谢~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-14 14:07:36 | 显示全部楼层
本帖最后由 古堡主人。 于 2017-8-14 16:16 编辑
  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)
复制代码

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
jerryxjr1220 + 1 + 1 答题奖励,对于10**100穷举是算不出来的

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-14 14:34:40 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-8-14 16:58:58 | 显示全部楼层
不是精英,也来挑战一下自己,
  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荣誉 +1 鱼币 +1 收起 理由
jerryxjr1220 + 1 + 1 答题奖励,Time=1.47s

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-14 21:16:24 | 显示全部楼层
  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))
复制代码

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
jerryxjr1220 + 1 + 1 答题奖励,Time=3.84s

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-14 22:02:15 | 显示全部楼层
之前发过一个但是好像运算速度比较慢,我是一个初学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.     #*******************************这里是关键*************************************
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-14 22:37:49 | 显示全部楼层
  1. import math

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


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

评分

参与人数 1荣誉 +1 鱼币 +1 收起 理由
jerryxjr1220 + 1 + 1 答题奖励,Time=3.59s

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

不大于5的质数是1,2,3,5,   至于4,是2*2
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-15 09:32:44 | 显示全部楼层
啊啊啊,没学过算法,还以为我做得很好了,原来还有比我快的,真是人外有人啊,看来我python入完门后应该再去看看算法
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 23:30

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表