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

jerryxjr1220 · 发表于 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

冬雪雪冬 · 发表于 2017-8-10 23:05:00

本帖最后由冬雪雪冬于 2017-8-11 08:02 编辑

抛砖引玉吧，这个没有优化，我的机器上用时25s，希望能看到大家优秀的程序。

'''先说说思路，既然这个数是2，3，5因子组成的，那么此数必然是2的倍数乘3的倍数乘5的倍数。
2的倍数不超过2**n2 > 1e100，3和5一样。
依次做3重循环如果不大于1e100，就统计一次。'''
import math
n2 = int(math.log2(1e100)) + 1 #计算2的倍数上限，下同，
n3 = int(math.log2(1e100)/math.log2(3)) + 1 #其实用log10更方便1e100都不用算了
n5 = int(math.log2(1e100)/math.log2(5)) + 1
count = 0
for i2 in range(n2):
for i3 in range(n3):
for i5 in range(n5):
if (2 ** i2) * (3 ** i3) * (5 ** i5) <= 1e100:
count += 1
print(count)

复制代码

结果是1697191，不知对不对？

冬雪雪冬 · 发表于 2017-8-10 23:24:31

本帖最后由冬雪雪冬于 2017-8-11 08:04 编辑

优化一下，用时减少到3s多
思路与前面一样，这里用对数来计算，把乘方变成了乘法，把乘法变成了加法，所以计算效率提高。

import math
n2 = int(math.log2(1e100)) + 1
n3 = int(math.log2(1e100)/math.log2(3)) + 1
n5 = int(math.log2(1e100)/math.log2(5)) + 1
lg2 = math.log10(2)
lg3 = math.log10(3)
lg5 = math.log10(5)
count = 0
for i2 in range(n2):
for i3 in range(n3):
for i5 in range(n5):
if lg2 * i2 + lg3 * i3 + lg5 * i5 <= 100:
count += 1
print(count)

复制代码

冬雪雪冬 · 发表于 2017-8-10 23:30:27

本帖最后由冬雪雪冬于 2017-8-11 08:06 编辑

加上break语句，用时1.4s
当i5循环大于100后就停止计算，同理i3的计算也在超过后停止，为什么i2不判断，大家想一下。

import math, time
st = time.time()
n2 = int(math.log2(1e100)) + 1
n3 = int(math.log2(1e100)/math.log2(3)) + 1
n5 = int(math.log2(1e100)/math.log2(5)) + 1
lg2 = math.log10(2)
lg3 = math.log10(3)
lg5 = math.log10(5)
count = 0
for i2 in range(n2):
for i3 in range(n3):
for i5 in range(n5):
if lg2 * i2 + lg3 * i3 + lg5 * i5 <= 100:
count += 1
if lg2 * i2 + lg3 * i3 + lg5 * i5 > 100:
break
if lg2 * i2 + lg3 * i3 > 100:
break
print(count)
print(time.time() - st)

复制代码

小锟 · 发表于 2017-8-10 23:44:09

本帖最后由小锟于 2017-8-11 10:06 编辑

# 观察前几个汉明数[1，2，3，4，5，6，8，9，10，12，15],
# 开始列表为1，然后增加了1*2 ， 1*3 ，2*2 ，1*5,2*3,，4*2，3*3
# 发现由前面的已知n项我们可以推出n+1项
# 5之前的质数有[2,3,5]
# 因此只用求出前n项中的元素与[2,3,5]的乘积取最小值就是第n+1项
# 用一个列表来记录位置
n = 10 ** 100
#只有第一项的汉明数
a = [1]
#判断最小值是否重复
chongfu = {1}
#记录位置的列表
nums = [0,0,0]
count = 1
while True :
b = [a[nums[0]] * 2 , a[nums[1]] * 3 ,a[nums[2]] * 5]
min_num = min(b)
if min_num > n:break
min_num_index = b.index(min_num)
nums[min_num_index] += 1
if min_num in chongfu:continue
chongfu.add(min_num)
a.append(min_num)
count += 1
print(count)

复制代码

老甲鱼与小甲鱼 · 发表于 2017-8-11 10:31:45

嗯，那个我理解有点问题，不大于5的质数不是只有2,3,5吗，为什么可以组合出1,4这种数，数学不太好，百度定义太晦涩，求解

凤凰0620 · 发表于 2017-8-11 12:31:32

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

import time
start =time.clock()
def get_hanmings(a=[]):
start = 0
c=[]
b=[1,2,3,4,5]
for i in b[start:]:
for j in a[start:]:
c.append(i*j)
start += 1
return c
a=[1,2,3,4,5]
pre_result = [1,2,3,4,5]
while pre_result[-1]<=10**135:
b = get_hanmings(a)
a = list(set(b)-set(a))
for i in a:
pre_result.append(i)
result=[]
for i in pre_result:
if i <= 10**100:
result.append(i)
print(len(result))
end = time.clock()
print('Running time: %s Seconds'%(end-start))

复制代码

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

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

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

凤凰0620 · 发表于 2017-8-11 13:05:46

谢谢奖励，不过我后来修改了又~

hhhhhq · 发表于 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

sum = 0
for a in range(0,333):
x1 = 2**a
for b in range(0,210):
x2 = (3**b) * x1
if x2 > 10**100:
break
for c in range(0,144):
x3 = (5**c) * x2
if x3 > 10**100:
break
sum += 1
print(sum)

复制代码

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

过客1993 · 发表于 2017-8-11 17:10:38

本帖最后由过客1993 于 2017-8-11 17:46 编辑

a = b = c = 0
num_list = [1]
x = 10 ** 100
minnum = 0
while minnum < x:
minnum = min(num_list[a] * 2, num_list[b] * 3, num_list[c] * 5)
num_list.append(minnum)
if minnum == num_list[a] * 2:
a += 1
if minnum == num_list[b] * 3:
b += 1
if minnum == num_list[c] * 5:
c += 1
print len(num_list)

复制代码

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

qq910819 · 发表于 2017-8-11 23:47:55

import datetime
def test(limit):
a=0
b=0
c=0
number=0
count=0
while number<=limit:
while number<=limit:
while number<=limit:
count+=1
c+=1
number=(2**a)*(3**b)*(5**c)
b+=1
c=0
number=(2**a)*(3**b)*(5**c)
a+=1
b=0
number=(2**a)*(3**b)*(5**c)
print(count)
a= datetime.datetime.now()
test(10**100)
b= datetime.datetime.now()
print("运行时间为：%s"%(b-a))

复制代码

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

小Q学Python · 发表于 2017-8-12 00:12:32

m = 10**100
counts = 0
for i in range(1000):
if 2**i > m:
break
for j in range(1000):
if 3**j > m:
break
for k in range(1000):
if 2**i*3**j*5**k > m:
break
counts += 1
print(counts)

复制代码

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

意外惊喜sad · 发表于 2017-8-12 10:04:02

本帖最后由意外惊喜sad 于 2017-8-13 13:01 编辑

代码已修改

小剑剑 · 发表于 2017-8-12 11:21:12

def binary_find_index(array,n,l=334):
begin=0
end=l-1
while True:
mid=(begin+end)//2
if array[mid]<=n:
if n<array[mid+1]:
return mid
begin=mid
else:
end=mid
x=1
fiveAndThree=[1]
for i in range(144):
x*=5
fiveAndThree.append(x)
two=[1]
x=1
for i in range(333):
x=x<<1
two.append(x)
result=0
for i in range(210):
j=0
while fiveAndThree[j]<=10**100:
x=fiveAndThree[j]
index=binary_find_index(two,x)
if x<<(332-index)<=10**100:
result+=333-index
else:
result+=332-index
fiveAndThree[j]=x*3
j+=1
print(result)

复制代码

1697191

zhang1862899 · 发表于 2017-8-12 16:07:17

number = []
for a in range(2,10**100):
if a%2!=0 and a%3!=0 and a%5!=0:
number.append(a)
count=0
for i in range(1,(10**100)+1):
for b in number:
if i%b==0:
count+=1
break
print('共有%d个汉明数' % (10**100-count))

复制代码

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

lalalaoh · 发表于 2017-8-12 16:31:35

def Ham(num):
count = 0
han_list=[]
for each in range(num+1):
han_list.append(0)
if each==1 or each==2 or each==3 or each==5:
count +=1
han_list[each]=1
elif each%2 == 0 and han_list[int(each/2)]:
count +=1
han_list[each]=1
elif each%3 ==0 and han_list[int(each/3)]:
count +=1
han_list[each]=1
elif each%5 ==0 and han_list[int(each/5)]:
count +=1
han_list[each]=1
return count

复制代码

michaelol · 发表于 2017-8-12 16:56:25

本帖最后由 michaelol 于 2017-8-13 15:58 编辑

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

复制代码

gunjang · 发表于 2017-8-12 18:09:48

本帖最后由 gunjang 于 2017-8-12 19:44 编辑

import time
from math import log,log2
def gethamming4_2(n):
bmax = int(log(n,3))
cmax = int(log(n,5))
r = 0
cp = 1
for c in range(cmax+1):
cbp = cp
for b in range(int(log(n/cp,3))+1):
#2 loop times =[0..log2(n/cbp)]
r += 1 + int(log(n/cbp,2)) #1 include a==0
cbp *= 3
cp *= 5
return r
#Win7 x64+Python 3.62 x64 + AMD Phenom II X4 965 + DDR3*8G
st = time.time()
print(gethamming4_2(10**100)) #1697191
print(time.time()-st) ##4.2=0.016000747680664062

复制代码

小冰冰偶哈哈 · 发表于 2017-8-12 18:34:02

import math
#判断一个数是否是质数
def isprime(x):
if x == 1:
return False
k = int(math.sqrt(x))
for j in range(2,k+1):
if x % j == 0:
return False
return True
def hamming(n):
flag = True
#质因子集合
prime_list = list()
#列出所有的质因子
for i in range(2,n+1):
if isprime(i) and n % i == 0:
prime_list.append(i)
prime_list = list(set(prime_list))
#判断质因子是否小于等于5
for j in prime_list:
if j > 5:
flag = False
return flag
if __name__ == "__main__":
number = int(input('请输入您需要的数字：'))
hamming_list = []
while number:
result = hamming(number)
if result:
hamming_list.append(number)
number -= 1
else:
number -= 1
print(hamming_list)

复制代码

算得很慢，持续优化中

小火木 · 发表于 2017-8-12 20:59:56

def hmfun(n):
data=1
count=0
i=0
while data<n:
j=0
while data<n:
k=0
while data<n:
data=5**i*3**j*2**k
if data<=n :
count+=1
k+=1
k=0
data=5**i*3**j*2**k
j+=1
j=0
data=5**i*3**j*2**k
i+=1
return count
if __name__=='__main__':
print('10**100以内（包含10**100）共有%d个汉明数'% hmfun(10**100))

复制代码

账号		自动登录	找回密码
密码			立即注册

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

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

评分

本帖被以下淘专辑推荐:

评分

已优化

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分

评分