小练习：20170424 考察具有有趣性质的平方数链

冬雪雪冬 · 发表于 2017-4-23 20:23:14

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

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

x

本帖最后由冬雪雪冬于 2017-5-1 15:53 编辑

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了200余题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives
这里已经有了500余题。

登录/注册后可看大图

题目要求：
以python语言完成，如果是python2请注明。
程序以代码文字格式发帖。
注重程序效率和创意。
答题在一周内完成，即5.1 10：00之前，其后将公开大家的答案，并评比成绩。
另程序和答案可以在网上搜到，希望大家独立完成。题目不难，大家看看谁的效率高。

----回帖需写明解题思路，鼓励在程序中加上注释

一些鱼油反映题目有些过难，为此略过一部分偏难的题目。

题目：

通过将一个数各位的平方不断相加，直到遇到已经出现过的数字，可以形成一个数字链。

例如：
44 → 32 → 13 → 10 → 1 → 1
85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

因此任何到达 1 或 89 的数字链都会陷入无限循环。令人惊奇的是，以任何数字开始，最终都会到达 1 或 89。

以一千万以下的数字 n 开始，有多少个 n 会到达 89？

提示：
无需每个数都算到89或1，例如20算出了89，那么42算到20就可以判断了。

lovesword · 发表于 2017-4-24 10:21:21

#!/usr/bin/env python
# coding=utf-8
# python 2.7
dict_res = {}
cnt_89 =0
dict_tmp = {}
def fact(n,n_):
if dict_res.get(n):
return dict_res[n]
if n==1:
dict_res[n_] =0
return 0
if n ==89:
dict_res[n_] =1
return 1
tmp_ = n
if dict_tmp.get(tmp_):
n = dict_tmp[tmp_]
return fact(n,n_)
tmp =map(int,str(n))
n=reduce(lambda x,y:x+y**2,tmp[1:],tmp[0]**2)
dict_tmp[tmp_]=n
return fact(n,n_)
i =1
while i<10000000:
tmp = fact(i,i)
cnt_89 += tmp
i=i+1
print cnt_89

复制代码

8581146
[Finished in 54.8s]

jerryxjr1220 · 发表于 2017-4-24 13:01:33

用了一个列表来对应键值关系，本质上还是穷举计算每一个数，所以用时要20多秒。

import time
start = time.time()
def get_sum(x):
total = 0
while x:
x, temp = divmod(x, 10)
total += temp * temp
return total
D = [0] * 600
D[1], D[89] = 1, 89
c = 0
for i in range(1, 10000000):
lst = []
i = get_sum(i)
while not D[i]:
lst.append(i)
i = get_sum(i)
for e in lst:
D[e] = D[i]
if D[i] == 89:
c += 1
print(c)
print('Time used: %.3f sec' % (time.time() - start))

复制代码

8581146
Time used: 20.694 sec

ooxx7788 · 发表于 2017-4-25 11:39:39

# import logging
def cal(interger):
temp_num = sum(map(lambda x: int(x) ** 2, interger))
# logging.debug(f'{str(temp_num)}')
return str(temp_num)
# logging.basicConfig(level=logging.INFO)
finish_useful = {'89'}
finish_useless = {'1'}
finish = finish_useless | finish_useful
for start in range(1, 568): # 9999999=9**2*7=567
start = str(start)
# logging.debug(f'{start}')
temp = {start}
while start not in finish:
start = cal(start)
temp.add(start)
if start in finish_useful:
finish_useful |= temp
finish |= temp
else:
finish_useless |= temp
finish |= temp
result = len(finish_useful)
for start in range(568, 10000000):
start = str(start)
if cal(start) in finish_useful:
result += 1
print(result)

复制代码

WelanceLee · 发表于 2017-4-25 16:08:14

import time
def compute(n):
s = 0
while n != 0:
m = n % 10
s += m**2
n = n // 10
return s
start = time.time()
a = []
for i in range(1, 570):##7个9最多只能到567
s = i
while True:
s = compute(s)
if s == 89:
a.append(1)
break
if s == 1:
a.append(0)
break
mid = time.time() ##检测构建指示数组花费的时间
n = 0
for i in range(1, 10**7):
if a[compute(i) - 1]:
n += 1
end = time.time()
t1 = mid - start
t2 = end - mid
t = end - start
print(t1, t2, t)

复制代码

用了接近30s，感觉斜率不高

余欲渔 · 发表于 2017-4-28 17:29:02

从1到9999999，最大就是7个数都是9，那每位数平方求和就是7*81就是567。所以我就先把567以内的数都划分到1组和89组，之后大于567的数只需要求出平方之和，找处在那个组就行，不过最终花费的时间还是比较长的，为了节约求平方的时间，直接用了字典把0~9和其平方数对应起来。

one=[]
nine=[]
zd={0:0,1:1,2:4,3:9,4:16,5:25,6:36,7:49,8:64,9:81}
def jc1(i=1):
a=[int(x) for x in list(str(i))]
he=sum([zd[x] for x in a])
if he in one:
return 1
elif he in nine:
return 0
elif he==1:
return 1
elif he==89:
return 0
else:
return jc1(he)
oo=0
nn=0
for i in range(1,568):
if jc1(i):
one.append (i)
oo+=1
else :
nine.append(i)
nn+=1
for i in range(568,10000000):
if jc1(i):
oo+=1
else:
nn+=1
print('有%d个结果是1，有%d个结果是89。'%(oo,nn))

复制代码

RESTART: C:\Users\Administrator\AppData\Local\Programs\Python\Python35-32\test.py
有1418853个结果是1，有8581146个结果是89。
>>>

复制代码

maple_7 · 发表于 2017-4-28 22:23:51

##10^7里各个位数平方和最大的是486（999,999 81*6）
##分两部分讨论，1-486和486-10^7之间的数
#设立两个列表，分别存放1-486最后结果1和89的数据
set1=set([1])
set89=set([89])
for i in range(1,487):
num=i
flag=True
while flag:
num=sum(map(lambda x:int(x)**2,list(str(num))))
if num in set1:
set1.add(i)
flag=False
elif num in set89:
set89.add(i)
flag=False
n=len(set89)
#大于486的数，其各个位数的平方和一定在1-486之间，判断是否在set89即可。
for i in range(487,10**7+1):
num=sum(map(lambda x :int(x)**2,list(str(i))))
if num in set89:
n+=1
print(n)

复制代码

新人尝试，运行时间有点长。。。还望见谅

老甲鱼与小甲鱼 · 发表于 2017-5-1 16:22:03

n = []
al =[]#最终平方和是89的平方和列表
for i in range(1,10000001):
iii = i
al2 = []
while True:
a = 0#a表示平方和
ii = str(i)
for each in ii:
a += int(each)**2
al2.append(a)
if a == 89 or a in al:
n.append(iii)
al.extend(set(al2))
al = list(set(al))#把重复的平方和去掉，提高一点效率
break
elif a == 1:
break
else:
i = a
continue

复制代码

脑子都要炸了，按我的逻辑来说应该没错，10万个数一秒不到就算完了，但是再加个零变成100万就好像陷入无限循环，算不出。。。

达锅 · 发表于 2017-7-4 21:11:44

'''不分段，用时稍久
def sl(n):#递归并记录所有计算过程，字典用于保存一个数对应的最终计算数值
if n in jh:return jh[n]#返回最终的值
ls=sl(sum(pf[i] for i in str(n)))#递归开始，计算下一个数
#ls=sl(sum(map(lambda x:pf[x],list(str(n)))))#用时4.3，循环比lambda快？
if n<800 :jh[n]=ls#设置n的条件，减少对字典操作
return ls
import time
tt=time.time()
n=10**7
#jh={i:0 for i in range(600)}
jh={}
jh[1],jh[89]=1,89
pf={str(i):i*i for i in range(10)}#字典比列表快
print(sum(1 for i in range(1,n) if sl(i)==89))#列表推导比循环快
print(time.time()-tt)
'''
#分段式
def sl(n):#递归
if n in jh:
return jh[n]#返回最终的值
return sl(sum(pf[i] for i in str(n)))#递归
def sl2(n):#递归并记录所有计算过程，字典用于保存一个数对应的最终计算数值
if n in jh:return jh[n]#返回最终的值
ls=sl(sum(pf[i] for i in str(n)))#递归开始，计算下一个数
jh[n]=ls #生成集合
return ls
import time
tt=time.time()
n=10**7
jh={}
jh[1],jh[89]=1,89
pf={str(i):i*i for i in range(10)}#读取字典比列表快？
print(sum(1 for i in range(1,811) if sl2(i)==89)+sum(1 for i in range(811,n) if sl(i)==89))#列表推导比循环快
print(time.time()-tt)

复制代码

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

[技术交流] 小练习：20170424 考察具有有趣性质的平方数链

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

评分

评分

评分

评分

评分

评分