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

xiewen1235

初次发帖，请多支持

import datetime
import math
starttime = datetime.datetime.now()
Maxnum = 10**100

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

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

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

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

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

print('==================求汉明数个数========================')
import time
import numpy as np
#定义全局变量
x = input('请输入最大值中10的幂指数：')
H = [1]
x = int(x)
y = 430   #调试参数，保证2**y>10**100
T1 = list(np.logspace(1,y,y,base=2))
T2 = list(np.logspace(1,y,y,base=3))
T3 = list(np.logspace(1,y,y,base=5))  
#定义新函数f1(),判断每个列表中符合要求的数并放入列表H中
def f1(X) :
    for i in range(0,y) :
        if X[i] <=10**x :
            H.append(X[i])
        else :
            break 
#定义新函数f2(),每个列表中的元素两两相乘，将符合要求的数放入H中
def f2(X,Y):
    for a in X :
        if a > 10**x :
            break    
        for b in Y :
            if b > 10**x :
                break
            h = a*b
            if h <= 10**x :
                H.append(h)
            else :
                break 
#运行程序主体
start = time.clock() 
f1(T1)
f1(T2)
f1(T3)
f2(T1,T2)
f2(T1,T3)
f2(T2,T3)
#三三相乘，将符合要求的数放入H中        
for a in T1 :
    if a > 10**x :
        break
    for b in T2 :
        if b > 10**x :
            break
        for c in T3 :
            if c > 10**x :
                break
            h = a*b*c
            if h <=10**x :
                H.append(h)
            else :
                break
print('10**',x,'以内包含的汉明数个数:',len(H))
end = time.clock()
print ('运行时间:',end-start,'s')

运行结果：

==================求汉明数个数========================
请输入最大值中10的幂指数：8
10** 8 以内包含的汉明数个数: 1105
运行时间: 0.03742721926610512 s
>>> 
==================求汉明数个数========================
请输入最大值中10的幂指数：2
10** 2 以内包含的汉明数个数: 34
运行时间: 0.02984148582876169 s
>>> 
==================求汉明数个数========================
请输入最大值中10的幂指数：100
10** 100 以内包含的汉明数个数: 1697190
运行时间: 27.276055697650705 s

Assistant

e,f,g,count,n = 1,1,1,0,10**100
while e <= n:
    while e <= n:
        while e <= n:
            count += 1
            e *= 2
        f *= 3
        e = g * f
    g *= 5
    f = 1
    e = g
print(count)

michaelol

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

def hanmingshu(n):
    hanming=set()
    factor=[2,3,5]
    hanming_temp=set()
    hanming_tempnew=set()
    hanming_temp.add(1)
    hanming_tempmin=min(hanming_temp)
    if n==1:
        hanming.update(hanming_temp)
        return hanming
    else:
        hanming.update(hanming_temp)
        while(hanming_tempmin*2<=n):
            for i in hanming_temp:
                for j in factor:
                    if i*j<=n:
                        hanming_tempnew.add(i*j)
                    else:
                        break
            hanming.update(hanming_tempnew)
            hanming_temp.clear()
            hanming_temp.update(hanming_tempnew)
            hanming_tempmin=min(hanming_temp)
            hanming_tempnew.clear()
    return hanming

print(len(hanmingshu(10**100)))

michaelol

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

def hanmingshu(n):
    hanming=set()
    factor=[2,3,5]
    hanming_temp=set()
    hanming_tempnew=set()
    hanming_temp.add(1)
    hanming_tempmin=min(hanming_temp)
    if n==1:
        hanming.update(hanming_temp)
        return hanming
    else:
        hanming.update(hanming_temp)
        while(hanming_tempmin*2<=n):
            for i in hanming_temp:
                for j in factor:
                    if i*j<=n:
                        hanming_tempnew.add(i*j)
                    else:
                        break
            hanming.update(hanming_tempnew)
            hanming_temp.clear()
            hanming_temp.update(hanming_tempnew)
            hanming_tempmin=min(hanming_temp)
            hanming_tempnew.clear()
    return hanming

print(len(hanmingshu(10**100)))

qitan888

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

#!/bin/python
#coding=utf-8

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

def hamming(n):
    k1,k2,k3 = 0,0,0
    res = [1]
    for i in range(1,n):
        s1 = res[k1]*2
        s2 = res[k2]*3
        s3 = res[k3]*5
        min_val = min(s1,s2,s3)
        res.append(min_val)
        if res[i] == s1:
            k1 +=1
        if res[i] == s2:
            k2 += 1
        if res[i] == s3:
            k3+= 1
    return res[-1]

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

def hamno(n):
    m = hamming(n)
    i = 0
    while m <= 10**100:
        i += 1
        n = n*2
        m = hamming(n)
        print("正在进行第{}次初步计算".format(i))
    print("初步计算结束，锁定范围为：({},{})".format(int(n/2),n))
    return int(n/2)

# 精确查找，使用二分法查找方式

def binary(n):
    i = 0
    n = hamno(n)
    a=range(n,n*2)
    x = 0 
    z = len(a) - 1
    while x < z:
        i += 1
        print("正在进行第{}次精确计算".format(i))
        y = int((x+z)/2)
        if hamming(a[y]) < 10**100:
            x = y+1
        elif hamming(a[y]) > 10**100:
            z = y
        else:
            return a[y]
    return a[z]

if __name__ == "__main__":
    n = 1
    print("精确计算结束，10**100（包含）内汉明数的个数为：{}".format(binary(n)))

ba21

def hamming(n):
    hm=[1,2,3]
    while(1):
        m2=True
        m3=True
        m5=True       
        hmTemp=[]
        lastHm=hm[-1]
        
        if lastHm % 5 == 0:
            firstHmindex=hm.index(lastHm//5)            
        else:
            firstHmindex=0
            
        for m in hm[firstHmindex:]:
            if m*2>lastHm and m2:
                m2=False
                hmTemp.append(m*2)
                break #如果*2都已经比最大的丑数大了，则退出
                
            if m*3>lastHm and m3:
                m3=False
                hmTemp.append(m*3)
            
            if m*5>lastHm and m5:
                m5=False
                hmTemp.append(m*5)
                
      
        cm=min(hmTemp)
        hm.append(cm)
        if cm>=n:
            break  
    return len(hm)

guoxike

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

凤凰0620

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

古堡主人。

Allprime=[7]
Allham=[1,2,3,4,5,6]
hamcount=0
for i in range(7,10**6+1):
    hamorprime=True
    juestham=False
    for j in Allprime:
        if i%j==0:
            hamorprime=False
            break
    if hamorprime:#判断是不是质数
        for p in range(2,i-1):
            if i%p==0:#是汉明数不是质数
                #hamcount+=1
                #print(hamcount,end=' ')
                print(i,end=' ')
                Allham.append(i)
                juestham=True
                break
        if not juestham:#是质数不是汉明数 
            Allprime.append(i)
    
print('All down')
print(Allprime)

amanionly

chunchun2017

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

def daiming(n):
    list0 = [1,2,3,4,5]
    index1 = 2 #T2
    index2 = 1 #T3
    index3 = 1 #T5
    min0 = 5
    while (min0<n) :
        x = 2*list0[index1]
        y = 3*list0[index2]
        z = 5*list0[index3]
        min0 = ((x if x<y else y ) if (x if x<y else y)<z else z)
        if (min0 == x):
             index1+=1
        if (min0 == y):
             index2+=1
        if (min0 == z):
             index3+=1
        list0.append(min0)
    print(len(list0))
import time
tt=time.time()
daiming(10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000)
print('time used:{}'.format(time.time()-tt))

运行结果：
1697191

人间四月尽

import time
#创建汉明数数组
ugly = [1]
#设定更新下标值
a = b = c = 0
#获取时间
t1 = time.time()
while ugly[-1] < 10**100:
        #下一个汉明数必然产生于其中
        next = min(2 * ugly[a], 3 * ugly[b], 5 * ugly[c])
        ugly.append(next)
        #更新下标值
        while 2 * ugly[a] <= ugly[-1]:
                a += 1
        while 3 * ugly[b] <= ugly[-1]:
                b += 1
        while 5 * ugly[c] <= ugly[-1]:
                c += 1
#获取时间
t2 = time.time()
#打印程序运行时间
print(t2 - t1)
print(len(ugly))

古堡主人。

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

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


    #*******************************这里是关键*************************************

bozhen

import math

nu = 10**100
xx = int(math.log(nu, 2)) + 1
yy = int(math.log(nu, 3)) + 1
zz = int(math.log(nu, 5)) + 1
nu_list = []
n = 1
for x in range(0, xx):
        for y in range(0, yy):
                for z in range(0, zz):
                        n = (2**x) * (3**y) * (5**z)
                        if n < nu + 1:
                                nu_list.append(n)
                        if n  > nu:
                                break
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入完门后应该再去看看算法