鱼C论坛

 找回密码
 立即注册
查看: 6197|回复: 47

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

[复制链接]
发表于 2017-8-10 22:26:40 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 jerryxjr1220 于 2017-8-14 23:50 编辑

鱼C论坛Python精英挑战赛第二季又开始啦!

本季挑战赛依旧会有精彩的题目供大家挑战,大量鱼币奖励等你赢取!


                               
登录/注册后可看大图


本期题目:汉明数

汉明数是指没有大于5的质因子组成的正整数,所以前几个汉明数是1,2,3,4,5,6,8,9,10,12,15.

100以内(包含100)共有34个汉明数,而10**8以内(包含10**8)共有1105个汉明数。

问10**100以内(包含10**100)共有多少汉明数?

注:通过本题可以体会python对于大数运算的优势,要是换成其他语言,10**100的计算可能就会导致溢出了。

比赛规则:
本题为纯算法题,要求输出结果正确,运行时间最短的鱼油即为优胜者。比赛截止日期:8月14日24时。

优胜者奖励100鱼币,由@小甲鱼 老师倾情赞助!

@冬雪雪冬 @~风介~ @SixPy

评分

参与人数 2荣誉 +10 鱼币 +10 贡献 +10 收起 理由
康小泡 + 5 + 5 + 5 支持楼主!
冬雪雪冬 + 5 + 5 + 5 支持楼主!

查看全部评分

本帖被以下淘专辑推荐:

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

使用道具 举报

发表于 2017-8-10 23:05:00 | 显示全部楼层
本帖最后由 冬雪雪冬 于 2017-8-11 08:02 编辑

抛砖引玉吧,这个没有优化,我的机器上用时25s,希望能看到大家优秀的程序。
  1. '''先说说思路,既然这个数是2,3,5因子组成的,那么此数必然是2的倍数乘3的倍数乘5的倍数。
  2. 2的倍数不超过2**n2 > 1e100,3和5一样。
  3. 依次做3重循环如果不大于1e100,就统计一次。'''
  4. import math
  5. n2 = int(math.log2(1e100)) + 1 #计算2的倍数上限,下同,
  6. n3 = int(math.log2(1e100)/math.log2(3)) + 1 #其实用log10更方便1e100都不用算了
  7. n5 = int(math.log2(1e100)/math.log2(5)) + 1
  8. count = 0
  9. for i2 in range(n2):
  10.     for i3 in range(n3):
  11.         for i5 in range(n5):
  12.             if (2 ** i2) * (3 ** i3) * (5 ** i5) <= 1e100:
  13.                 count += 1
  14. print(count)
复制代码


结果是1697191,不知对不对?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

发表于 2017-8-10 23:24:31 | 显示全部楼层
本帖最后由 冬雪雪冬 于 2017-8-11 08:04 编辑

优化一下,用时减少到3s多
思路与前面一样,这里用对数来计算,把乘方变成了乘法,把乘法变成了加法,所以计算效率提高。
  1. import math
  2. n2 = int(math.log2(1e100)) + 1
  3. n3 = int(math.log2(1e100)/math.log2(3)) + 1
  4. n5 = int(math.log2(1e100)/math.log2(5)) + 1
  5. lg2 = math.log10(2)
  6. lg3 = math.log10(3)
  7. lg5 = math.log10(5)
  8. count = 0
  9. for i2 in range(n2):
  10.     for i3 in range(n3):
  11.         for i5 in range(n5):
  12.             if lg2 * i2 + lg3 * i3 + lg5 * i5 <= 100:
  13.                 count += 1
  14. print(count)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-10 23:30:27 | 显示全部楼层
本帖最后由 冬雪雪冬 于 2017-8-11 08:06 编辑

加上break语句,用时1.4s
当i5循环大于100后就停止计算,同理i3的计算也在超过后停止,为什么i2不判断,大家想一下。
  1. import math, time
  2. st = time.time()
  3. n2 = int(math.log2(1e100)) + 1
  4. n3 = int(math.log2(1e100)/math.log2(3)) + 1
  5. n5 = int(math.log2(1e100)/math.log2(5)) + 1
  6. lg2 = math.log10(2)
  7. lg3 = math.log10(3)
  8. lg5 = math.log10(5)
  9. count = 0
  10. for i2 in range(n2):
  11.     for i3 in range(n3):
  12.         for i5 in range(n5):
  13.             if lg2 * i2 + lg3 * i3 + lg5 * i5 <= 100:
  14.                 count += 1
  15.             if lg2 * i2 + lg3 * i3 + lg5 * i5 > 100:
  16.                 break
  17.         if lg2 * i2 + lg3 * i3 > 100:
  18.             break
  19. print(count)
  20. print(time.time() - st)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-10 23:44:09 | 显示全部楼层
本帖最后由 小锟 于 2017-8-11 10:06 编辑

  1. # 观察前几个汉明数[1,2,3,4,5,6,8,9,10,12,15],
  2. # 开始列表为1,然后增加了1*2 , 1*3 ,2*2 ,1*5,2*3,,4*2,3*3
  3. # 发现由前面的已知n项我们可以推出n+1项
  4. # 5之前的质数有[2,3,5]
  5. # 因此只用求出前n项中的元素与[2,3,5]的乘积取最小值就是第n+1项
  6. # 用一个列表来记录位置



  7. n = 10 ** 100
  8. #只有第一项的汉明数
  9. a = [1]
  10. #判断最小值是否重复
  11. chongfu = {1}
  12. #记录位置的列表
  13. nums = [0,0,0]

  14. count = 1
  15. while True :
  16.     b = [a[nums[0]] * 2 , a[nums[1]] * 3 ,a[nums[2]] * 5]
  17.     min_num = min(b)
  18.     if min_num > n:break
  19.     min_num_index = b.index(min_num)
  20.     nums[min_num_index] += 1
  21.     if min_num in chongfu:continue
  22.     chongfu.add(min_num)
  23.     a.append(min_num)
  24.     count += 1
  25. print(count)
复制代码

评分

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

查看全部评分

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

使用道具 举报

发表于 2017-8-11 10:31:45 | 显示全部楼层
嗯,那个我理解有点问题,不大于5的质数不是只有2,3,5吗,为什么可以组合出1,4这种数,数学不太好,百度定义太晦涩,求解
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-11 12:31:32 | 显示全部楼层

已优化

本帖最后由 凤凰0620 于 2017-8-14 16:47 编辑

  1. import time
  2. start =time.clock()

  3. def get_hanmings(a=[]):
  4.         start = 0
  5.         c=[]
  6.         b=[1,2,3,4,5]
  7.         for i in b[start:]:
  8.             for j in a[start:]:
  9.                     c.append(i*j)      
  10.         start +=  1
  11.         return c

  12. a=[1,2,3,4,5]
  13. pre_result = [1,2,3,4,5]
  14. while pre_result[-1]<=10**135:
  15.     b = get_hanmings(a)
  16.     a = list(set(b)-set(a))
  17.     for i in a:
  18.         pre_result.append(i)

  19. result=[]
  20. for i in pre_result:
  21.     if i <= 10**100:
  22.         result.append(i)

  23. print(len(result))
  24. end = time.clock()
  25. print('Running time: %s Seconds'%(end-start))
复制代码


最终版本,经过调整,while的范围在135左右,既能保证结果的完整,又能尽量节省时间
最后结果1697191个


在代码里加入了计时之后运行,平均运行成绩在12秒多

后记:我研究了一下规律,发现用差集进行迭代可以避免重复,结果实验了一下竟然超快的!!!!!!!!激动人心

运行结果

运行结果

评分

参与人数 1荣誉 +1 鱼币 +1 贡献 +1 收起 理由
jerryxjr1220 + 1 + 1 + 1 答题奖励,你的答案是什么?

查看全部评分

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

使用道具 举报

发表于 2017-8-11 13:05:46 | 显示全部楼层
谢谢奖励,不过我后来修改了又~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-11 16:38:32 | 显示全部楼层
本帖最后由 hhhhhq 于 2017-8-12 17:00 编辑

#可以算出2**332 < 10**100 < 2**333,3**209 < 10**100 < 3**210,5**143 < 10**100 < 5**144,且2*(3**209)>10**100
  1. sum = 0
  2. for a in range(0,333):
  3.     x1 = 2**a
  4.     for b in range(0,210):
  5.         x2 = (3**b) * x1
  6.         if x2 > 10**100:
  7.             break
  8.         for c in range(0,144):
  9.             x3 = (5**c) * x2
  10.             if x3 > 10**100:
  11.                 break
  12.             sum += 1

  13. print(sum)
复制代码


#sb了,改一下。。答案是1697191

评分

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

查看全部评分

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

使用道具 举报

发表于 2017-8-11 17:10:38 | 显示全部楼层
本帖最后由 过客1993 于 2017-8-11 17:46 编辑
  1. a = b = c = 0
  2. num_list = [1]
  3. x = 10 ** 100
  4. minnum = 0
  5. while minnum < x:
  6.     minnum = min(num_list[a] * 2, num_list[b] * 3, num_list[c] * 5)
  7.     num_list.append(minnum)
  8.     if minnum == num_list[a] * 2:
  9.         a += 1
  10.     if minnum == num_list[b] * 3:
  11.         b += 1
  12.     if minnum == num_list[c] * 5:
  13.         c += 1

  14. print len(num_list)
复制代码


ps: python2.7
比速度,函数注释就一律不写了,主要原因是懒

评分

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

查看全部评分

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

使用道具 举报

发表于 2017-8-11 23:47:55 | 显示全部楼层
  1. import datetime
  2. def test(limit):
  3.     a=0
  4.     b=0
  5.     c=0
  6.     number=0
  7.     count=0
  8.     while number<=limit:
  9.         while number<=limit:
  10.             while number<=limit:
  11.                
  12.                 count+=1
  13.                 c+=1
  14.                 number=(2**a)*(3**b)*(5**c)
  15.             b+=1
  16.             c=0
  17.             number=(2**a)*(3**b)*(5**c)
  18.         a+=1
  19.         b=0
  20.         number=(2**a)*(3**b)*(5**c)

  21.    
  22.     print(count)


  23. a= datetime.datetime.now()
  24. test(10**100)
  25. b= datetime.datetime.now()
  26. print("运行时间为:%s"%(b-a))
复制代码


刚刚跟着小甲鱼学了一个多月python,还是菜鸟一只。先是写了一个遍历所有数字的方法,发现运行了半小时还是没有出结果。于是换了种思路,运行之后发现2s就出结果真的很激动。不过答案1697191是否正确真的也没有百分之百的把握,速度可能也不够快,总之重在参与。
借此机会谢谢小甲鱼和各位版主。

评分

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

查看全部评分

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

使用道具 举报

发表于 2017-8-12 00:12:32 | 显示全部楼层
  1. m = 10**100
  2. counts = 0

  3. for i in range(1000):
  4.     if 2**i > m:
  5.         break
  6.     for j in range(1000):
  7.         if 3**j > m:
  8.             break
  9.         for k in range(1000):
  10.             if 2**i*3**j*5**k > m:
  11.                 break
  12.             counts += 1
  13.             
  14. print(counts)
复制代码


%time %run qqq.py
1697191
Wall time: 3.32 s

评分

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

查看全部评分

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

使用道具 举报

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

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

使用道具 举报

发表于 2017-8-12 11:21:12 | 显示全部楼层
  1. def binary_find_index(array,n,l=334):
  2.     begin=0
  3.     end=l-1
  4.     while True:
  5.         mid=(begin+end)//2
  6.         if array[mid]<=n:
  7.             if n<array[mid+1]:
  8.                 return mid
  9.             begin=mid
  10.         else:
  11.             end=mid
  12.             
  13. x=1
  14. fiveAndThree=[1]
  15. for i in range(144):
  16.     x*=5
  17.     fiveAndThree.append(x)
  18. two=[1]
  19. x=1
  20. for i in range(333):
  21.     x=x<<1
  22.     two.append(x)

  23. result=0
  24. for i in range(210):
  25.     j=0
  26.     while fiveAndThree[j]<=10**100:
  27.         x=fiveAndThree[j]
  28.         index=binary_find_index(two,x)
  29.         if x<<(332-index)<=10**100:
  30.             result+=333-index
  31.         else:
  32.             result+=332-index
  33.         fiveAndThree[j]=x*3
  34.         j+=1
  35.         
  36. print(result)
复制代码


1697191

评分

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

查看全部评分

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

使用道具 举报

发表于 2017-8-12 16:07:17 | 显示全部楼层
  1. number = []
  2. for a in range(2,10**100):
  3.     if a%2!=0 and a%3!=0 and a%5!=0:
  4.         number.append(a)
  5. count=0
  6. for i in range(1,(10**100)+1):
  7.     for b in number:
  8.         if i%b==0:
  9.             count+=1
  10.             break
  11.         
  12. print('共有%d个汉明数' % (10**100-count))
复制代码

算的太久了,很期待别人的答案,这是我挑选的时间最短的了

评分

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

查看全部评分

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

使用道具 举报

发表于 2017-8-12 16:31:35 | 显示全部楼层

  1. def Ham(num):
  2.     count = 0
  3.     han_list=[]
  4.     for each in range(num+1):
  5.         han_list.append(0)
  6.         if each==1 or each==2 or each==3 or each==5:
  7.             count +=1
  8.             han_list[each]=1
  9.         elif each%2 == 0 and han_list[int(each/2)]:
  10.             count +=1
  11.             han_list[each]=1
  12.         elif each%3 ==0 and han_list[int(each/3)]:
  13.             count +=1
  14.             han_list[each]=1
  15.         elif each%5 ==0 and han_list[int(each/5)]:
  16.             count +=1
  17.             han_list[each]=1
  18.     return count
复制代码

评分

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

查看全部评分

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

使用道具 举报

发表于 2017-8-12 16:56:25 | 显示全部楼层
本帖最后由 michaelol 于 2017-8-13 15:58 编辑

高效版本
需要7秒找出10**100以内的汉明数
答案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=2.96s

查看全部评分

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

使用道具 举报

发表于 2017-8-12 18:09:48 | 显示全部楼层
本帖最后由 gunjang 于 2017-8-12 19:44 编辑
  1. import time
  2. from math import log,log2
  3. def gethamming4_2(n):
  4.         bmax = int(log(n,3))
  5.         cmax = int(log(n,5))
  6.         r = 0
  7.        
  8.         cp = 1
  9.         for c in range(cmax+1):
  10.                 cbp = cp
  11.                 for b in range(int(log(n/cp,3))+1):
  12.                         #2 loop times =[0..log2(n/cbp)]
  13.                         r += 1 + int(log(n/cbp,2)) #1 include a==0
  14.                         cbp *= 3
  15.                 cp *= 5
  16.         return r

  17. #Win7 x64+Python 3.62 x64 + AMD Phenom II X4 965 + DDR3*8G
  18. st = time.time()
  19. print(gethamming4_2(10**100)) #1697191
  20. print(time.time()-st) ##4.2=0.016000747680664062
复制代码

评分

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

查看全部评分

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

使用道具 举报

发表于 2017-8-12 18:34:02 | 显示全部楼层
  1. import math

  2. #判断一个数是否是质数
  3. def isprime(x):
  4.         if x == 1:
  5.             return False
  6.         k = int(math.sqrt(x))
  7.         for j in range(2,k+1):
  8.             if x % j == 0:
  9.                 return False
  10.         return True

  11. def hamming(n):
  12.     flag = True
  13.     #质因子集合
  14.     prime_list = list()
  15.     #列出所有的质因子
  16.     for i in range(2,n+1):
  17.         if isprime(i) and n % i == 0:
  18.             prime_list.append(i)
  19.     prime_list = list(set(prime_list))
  20.     #判断质因子是否小于等于5
  21.     for j in prime_list:
  22.         if j > 5:
  23.             flag = False

  24.     return flag
  25.         
  26. if __name__ == "__main__":
  27.     number = int(input('请输入您需要的数字:'))
  28.     hamming_list = []
  29.     while number:
  30.         result = hamming(number)
  31.         if result:
  32.             hamming_list.append(number)
  33.             number -= 1
  34.         else:
  35.             number -= 1
  36.     print(hamming_list)
复制代码

算得很慢,持续优化中

评分

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

查看全部评分

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

使用道具 举报

发表于 2017-8-12 20:59:56 | 显示全部楼层
  1. def hmfun(n):
  2.     data=1
  3.     count=0
  4.     i=0
  5.    
  6.     while data<n:
  7.         j=0
  8.         while data<n:
  9.             k=0      
  10.             while data<n:
  11.                 data=5**i*3**j*2**k
  12.                 if data<=n :
  13.                     count+=1
  14.                 k+=1

  15.             k=0
  16.             data=5**i*3**j*2**k
  17.             j+=1
  18.          
  19.         j=0
  20.         data=5**i*3**j*2**k
  21.         i+=1


  22.     return count

  23. if __name__=='__main__':
  24.     print('10**100以内(包含10**100)共有%d个汉明数'% hmfun(10**100))
复制代码

评分

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

查看全部评分

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

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-3-29 03:56

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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