小练习：20160912 给出100万以下所有十进制和二进制表示都是回文的数字之和

冬雪雪冬 · 发表于 2016-9-12 21:46:00

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

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

x

本帖最后由冬雪雪冬于 2016-9-19 11:00 编辑

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

登录/注册后可看大图

好了言归正传，我们开始做小练习。

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

----除列出程序外，请给出输出的结果。----

题目：

十进制数字

登录/注册后可看大图

(二进制),可以看出在十进制和二进制下都是回文（从左向右读和从右向左读都一样）。

求 100 万以下所有在十进制和二进制下都是回文的数字之和。

（注意在两种进制下的数字都不包括最前面的 0）

冬雪雪冬 · 发表于 2016-9-12 21:47:12

其实题目真的非常简单，我是用[::-1]算回文的。

sum1 = 0
for i in range(1, 1000000):
if str(i) == str(i)[::-1]:
b = '{:b}'.format(i)
if b == b[::-1]:
sum1 += i
print(sum1)

复制代码

bacon6581 · 发表于 2016-9-12 22:43:50

from time import time
start=time()
lst=[]
result=0
for i in range(1,1000000,2):
b_str=bin(i)[2:]
i_str=str(i)
if i_str==i_str[::-1] and b_str==b_str[::-1]:
lst.append(i)
for i in lst:
result+=i
print(lst)
print(result)
print(time()-start)

复制代码

>>> ================================ RESTART ================================
>>>
[1, 3, 5, 7, 9, 33, 99, 313, 585, 717, 7447, 9009, 15351, 32223, 39993, 53235, 53835, 73737, 585585]
872187
5.8598997592926025
>>>

复制代码

wangzhenas · 发表于 2016-9-12 23:15:50

本帖最后由 wangzhenas 于 2016-9-19 04:49 编辑

答案： 872187
耗时： 0.004s
思路是利用生成器函数生成100，000以下的所有回文数，然后用filter函数判断二进制是否为回文数并求和

from time import time
t = time()
def produce_10(maxi = 1000):
for i in range(maxi):
for n in (i,i//10):
result = i
while n > 0:
result *= 10
result += n % 10
n //= 10
yield result
print(sum(filter(lambda n:bin(n)[2:] == bin(n)[2:][::-1], produce_10())),time()-t)

复制代码

jerryxjr1220 · 发表于 2016-9-13 11:20:13

本帖最后由 jerryxjr1220 于 2016-9-15 00:41 编辑

手机上写的，回去后把程序补上。
结果应该是872187

换了一种算法，只需比较一半字符串，优化运算速度。

import time
start = time.time()
#def isCycle1(strnum):
# lennum = len (strnum)
# n = lennum - 1
# str1 = strnum[n] + strnum[:n]
# for i in range(1,n):
# str1 = str1[:i] + str1[n] + str1[i:n]
# # return str1
# if strnum == str1:
# return 1
# else:
# return 0
#def isCycle2(strnum):
# lennum = len (strnum)
# n = lennum - 1
# m = int(lennum/2-0.5)
# str1 = strnum[:m+1]
# str2 = strnum[n] + strnum[int(lennum/2):n]
#
# for i in range(1,m):
# str2 = str2[:i] + str2[m] + str2[i:m]
#
# if str1 == str2:
# return 1
# else:
# return 0
def isCycle3(strnum):
lennum = len (strnum)
n = lennum - 1
flag = 1
for i in range(int(lennum/2)):
if strnum[i] != strnum[n-i]:
flag = 0
break
return flag
# oddlist, cycodd, blist
oddlist = [3,5,7,9,11,33,55,77,99]
for a in range(101,1000000):
if a % 2:
oddlist.append (a)
# print (oddlist)
cycodd = []
blist = []
for each in oddlist:
if isCycle3(str(each)):
cycodd.append (each)
blist.append (bin(each)[2:])
# print (blist)
# finallist
finallist = [1]
for eachb in blist:
if isCycle3(eachb):
finallist.append (cycodd[blist.index(eachb)])
print ("解答：")
print (sum(finallist))
# print (finallist)
end = time.time()
print ("用时 %.3f秒" % (end - start))

复制代码

飘飞的白杨 · 发表于 2016-9-14 13:45:01

def shu(n):
n = str(n)
s1 = int(n+n[::-1])
s2 = int(n+n[:-1][::-1])
return s1,s2
sum = 0
for i in range(1,999):
x1,x2 = shu(i)
if bin(x1)[2:] == bin(x1)[2:][::-1]:
sum = sum+x1
if bin(x2)[2:] == bin(x2)[2:][::-1]:
sum = sum+x2
print(sum)

复制代码

答案：872187

光头铁卫 · 发表于 2016-9-14 17:28:33

想问一下这个一百万是十进制还是二进制？

Spicebush · 发表于 2016-9-15 09:16:58

#答案为872187
def hws(n):
n2s = str(n)
l = (len(n2s)+1)//2
for i in range(l):
if n2s[i] != n2s[-i-1]:
return False
return True
s = 0
for num in range(1000000):
if hws(num) and hws(int(bin(num)[2:])):
s += num
print(s)

复制代码

小剑剑 · 发表于 2016-9-15 16:06:18

本帖最后由小剑剑于 2016-9-21 10:07 编辑

from time import clock
time,su=clock(),0
def palindromic_number():
for i in range(1,10,2):
yield i
for i in range(1,1000,2):
reve=''.join(reversed(list(str(i))))
yield reve+str(i)
for ii in range(10):
yield reve+str(ii)+str(i)
def is_binary_pal(decnum):
dereve=0
copy_num=decnum
while decnum>0:
dereve=dereve*2+decnum%2
decnum//=2
return copy_num==dereve
for i in palindromic_number():
if is_binary_pal(int(i)):
su+=int(i)
print(su,clock()-time)

复制代码

25837859 0.09252274984565001

复制代码

感动的一B，范围错了，版主都发鱼币
修改后

from time import clock
time,su=clock(),0
def palindromic_number():
for i in range(1,10,2):
yield i
for i in range(1,1000,2):
reve=''.join(reversed(list(str(i))))
yield reve+str(i)
if i<100:
for ii in range(10):
yield reve+str(ii)+str(i)
for i in range(10,1000,20):
reve=''.join(reversed(list(str(i))))
yield str(i)+reve
def is_binary_pal(decnum):
dereve=0
copy_num=decnum
while decnum>0:
dereve=dereve*2+decnum%2
decnum//=2
return copy_num==dereve
for i in palindromic_number():
if is_binary_pal(int(i)):
su+=int(i)
print(su,clock()-time)
872187
0.015596389770507812

复制代码

老忘 · 发表于 2016-9-18 09:03:56

# -*- coding:Utf-8 -*-
import time
start = time.clock()
def ishw(m):
if str(m)==str(m)[::-1]:
return 1
else:
return 0
sum_hw=0
for i in range(1,1000000):
if ishw(i):
if ishw(bin(i)[2:]):
sum_hw+=i
print(sum_hw)
end = time.clock()
print ("read: %f s" % (end - start))

复制代码

计算结果：

872187
read: 1.067628 s

复制代码

寒园 · 发表于 2016-9-19 20:59:28

wangzhenas 发表于 2016-9-12 23:15
答案： 872187
耗时： 0.004s
思路是利用生成器函数生成100，000以下的所有回文数，然后用filter函数判断 ...

能将这段程序都一句都注疏下不

wangzhenas · 发表于 2016-9-20 03:47:23

寒园发表于 2016-9-19 20:59
能将这段程序都一句都注疏下不

我就简单说下思路吧
首先函数的作用是生成一百万以下的回文数
比如：从123可以得到123321，12321两个回文数，因此只需迭代到1000，因为999最大可以生成999999
然后用yield语句将函数包装为生成器，即一个可迭代对象（在这里相当于返回了一个所有回文数的列表）
然后用filter过滤出二进制为回文数的情况
最后用sum求和

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

[技术交流] 小练习：20160912 给出100万以下所有十进制和二进制表示都是回文的数字之和

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

本帖被以下淘专辑推荐:

评分

评分

评分

评分

评分

评分

评分