小练习结果揭晓：10亿以下有多少可反数？

冬雪雪冬 · 发表于 2017-7-11 21:47:02

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

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

x

原帖子：http://bbs.fishc.com/thread-90063-1-1.html

题目：

一些正整数 n 有这样一个性质：n 与 n取“相反”之和的所有位皆为奇数。例如： 36 + 63 = 99 以及 409 + 904 = 1313。我们将这样的数成为可反数；所以，36，63，409，904 都是可反数。在 n 和 n 取相反的最前面都不允许有 0。

一千以下共有 120 个可反数。

10 亿（10⁹）以下共有多少个可反数？

正确答案是：608720

说实在的，除了暴力求解我也没有想出更好的方法，大家的解法也基本都是采用类似的方法。但达锅却巧妙的分析可能的组合秒解此题，很是佩服。
ooxx7788 也是用类似的方法秒解，但超过了最后的答题时限，很是遗憾。
由于大家的用时过长，我不好验算，就计算了1000之内的，看看结果是否正确。
回答正确的鱼油是：
lz恒
jerryxjr1220
达锅
suloman
小锟
WelanceLee
ooxx7788

最终优胜的鱼油是：达锅

达锅 · 发表于 2017-7-11 23:11:46

我的目标是拿得一次MVP就去学numpy，终于可以开始了

jerryxjr1220 · 发表于 2017-7-12 14:40:56

本帖最后由 jerryxjr1220 于 2017-7-12 14:45 编辑

我知道现在再回复答案已经晚了，不过我刚才用numba神器重写一下。
纯数值运算：

from numba import jit, autojit
from math import log10
from time import process_time
@jit("int32(int32)")
def reverse_add(n):
m = n
l = int(log10(n))
s = 0
for i in range(l+1):
s = s*10 + n%10
n //= 10
return s+m
@jit("boolean(int32)")
def judge_odd(n):
while n > 0:
if n % 2 == 0:
return False
n //= 10
return True
@jit("int32(int32)")
def solve(limit):
c, i = 0, 11
while i < limit:
if (i // (10**int(log10(i)))) % 2:
i += 10**int(log10(i))
if judge_odd(reverse_add(i)):
c += 2
i += 2
return c
print(solve(1000000000))
print(process_time())

复制代码

608720
20.4673312
同样的算法，不用神器跑了将近13分钟，用了神器后20秒

@冬雪雪冬

冬雪雪冬 · 发表于 2017-7-12 15:57:23

jerryxjr1220 发表于 2017-7-12 14:40
我知道现在再回复答案已经晚了，不过我刚才用numba神器重写一下。
纯数值运算：

棒！再不能说python的速度慢了。

jerryxjr1220 · 发表于 2017-7-12 16:06:10

冬雪雪冬发表于 2017-7-12 15:57
棒！再不能说python的速度慢了。

不过我也发现“神器”也有局限性，就是它只对纯数值运算进行了优化，所以速度很快。

如果程序中还穿插其他类型的数据，比如转换了“字符串”什么的，那速度就和原来差不多了。

ooxx7788 · 发表于 2017-7-12 16:46:13

jerryxjr1220 发表于 2017-7-12 16:06
不过我也发现“神器”也有局限性，就是它只对纯数值运算进行了优化，所以速度很快。

如果程序中还穿插 ...

http://python.jobbole.com/84432/

不知道这个文章你们看过没有。合理的使用方法，其实python也不会很慢。（当然，前提是得会。）
numpy和numba这样可以加快速度，很大原因就是以为只要把数据类型统一固定以后，python速度就会明显提升了。

我就是我520小莉 · 发表于 2017-7-12 21:00:19

啊啊啊

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

[技术交流] 小练习结果揭晓：10亿以下有多少可反数？

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

点评

评分