应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程 第廿九题：有多少不同的项?
311/4返回列表1234下一页
查看: 2029  |  回复: 30
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看

holmescn

金虫 (正式写手)

[交流] Euler 工程 第廿九题：有多少不同的项? 已有4人参与

第廿八题是个数学题, 除了生成矩阵的算法外, 好像没什么太多的思考.  所以再来个题吧.

取指数函数a^b, 其中a和b都取遍[2,5]间的所有整数, 所有可能的组合可以得到:

2^2=4, 2^3=8, 2^4=16, 2^5=32
3^2=9, 3^3=27, 3^4=81, 3^5=243
4^2=16, 4^3=64, 4^4=256, 4^5=1024
5^2=25, 5^3=125, 5^4=625, 5^5=3125

把结果从小到大排列, 并去掉重复的数:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

一共15个数

如果a和b取遍[2,100]间所有的整数, 那可以得到多少个不同的数?

[ Last edited by holmescn on 2011-6-17 at 10:00 ]
回复此楼

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:
1楼 2011-06-17 09:58:49
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
好像又是个关于质数的题, 难怪"1+2=3"这么重要呢.
赞一下 回复此楼
2楼2011-06-17 10:07:50
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
dubo(金币+1): 欢迎常来程序语言版讨论 2011-06-17 18:21:22
引用回帖:
Originally posted by holmescn at 2011-06-17 10:07:50:
好像又是个关于质数的题, 难怪"1+2=3"这么重要呢.

没办法咯，所有的数都是质数生成的。
这题好像要筛数，前面的4*4个数中，只筛掉了1个数，原因是2^4和4^2=2^4
更大规模的时候，看起来需要把2~100内的所有素数和合数标记下都表示成指数的形式，筛掉那些指数落在2~100之间的合数。
赞一下(2人) 回复此楼
漩涡的中心有一块空地，空空的。
3楼2011-06-17 11:41:10
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
dubo(金币+1): 欢迎常来程序语言版讨论 2011-06-17 18:21:33
python
CODE:
print len([_x for _x in [a**b for a in xrange(2,101) for b in xrange(2,101)] if not _x in locals()['_[1]']])

结果
CODE:
9183
Elapsed time: 1.91284227 seconds
赞一下(2人) 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
4楼2011-06-17 15:16:03
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
dubo(金币+1): 欢迎常来程序语言版讨论 2011-06-17 18:21:41
引用回帖:
Originally posted by libralibra at 2011-06-17 15:16:03:
python
CODE:
print len([_x for _x in [a**b for a in xrange(2,101) for b in xrange(2,101)] if not _x in locals()['_[1]']])

结果
CODE:
9183
Elapsed time: 1.91284227 seconds




这样看来，用Perl的Hash没准还快一些。
C++的Set也不错。
赞一下(2人) 回复此楼
漩涡的中心有一块空地，空空的。
5楼2011-06-17 16:17:12
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
dubo(金币+1): 欢迎常来程序语言版讨论 2011-06-17 18:21:47
引用回帖:
Originally posted by huycwork at 2011-06-17 16:17:12:


这样看来，用Perl的Hash没准还快一些。
C++的Set也不错。

怪我写一行了,分开写很快
CODE:
from mytictoc import tic, toc

tic()
a = [_x for _x in [a**b for a in xrange(2,101) for b in xrange(2,101)]]
b = set(a)
print len(b)
toc()

结果
CODE:
9183
Elapsed time: 0.03940473 seconds

赞一下(2人) 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
6楼2011-06-17 16:53:34
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
dubo(金币+1): 欢迎常来程序语言版讨论 2011-06-17 18:21:56
引用回帖:
Originally posted by libralibra at 2011-06-17 16:53:34:
怪我写一行了,分开写很快
CODE:
from mytictoc import tic, toc

tic()
a = [_x for _x in [a**b for a in xrange(2,101) for b in xrange(2,101)]]
b = set(a)
print len(b)
toc()

结果
...

不带你这样扫盲的。
你的第一个实现明明是搜索，时间都浪费在搜索上了
第二个实现偷偷换成set了，嗯，这点俺还能看出来
赞一下(2人) 回复此楼
漩涡的中心有一块空地，空空的。
7楼2011-06-17 17:01:12
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
写一行也行啊.
CODE:
print len(set([a**b for a in xrange(2,101) for b in xrange(2,101)]))

这个算法太无聊了.

想想质因数分解法.
赞一下 回复此楼
8楼2011-06-18 09:19:04
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

qinghuoly

木虫 (正式写手)
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
dubo(金币+1): 欢迎常来程序语言版讨论 2011-06-18 11:41:41
我上个J语言版本的

p=:2+i.99  NB.
q=:99 1$p  NB.
m=:q^/p    NB.乘法表
n=:,m      NB.展开为列表
]g=: /: n  NB.取得索引
l=:g{n     NB.按大小排序
uni=:~.l   NB.移除重复项
#uni       NB.计数

NB. make it simpler
p=: 2+i.99  NB.
q=: 99 1$p  NB.
#~.,q^/p    NB. 得到答案9183

[ Last edited by qinghuoly on 2011-6-18 at 10:16 ]
赞一下(2人) 回复此楼
天地为帐，日月为灯，风雷为号角，云虹为旗令，山川为阵图，草木为兵卒。运阴阳五行为谋，策古今兴替为略。
9楼2011-06-18 10:09:54
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
★
dubo(金币+1): 欢迎常来程序语言版讨论 2011-06-18 11:41:50
OK, 完成 Python版的质数分解法, 不过不是很快,大概要3秒左右吧
CODE:
# coding: utf-8

factorsOfA = []

for a in xrange(2, 101):
    u = 2
    n = 0
    x = a
    factors = []
    while u <= a:
        if x % u == 0:
            n += 1
            x /= u
        elif n != 0:
            factors.append([u, n])
            n = 0
        else:
            u += 1
    factorsOfA.append(factors)

result = []
for a in factorsOfA:
    for b in xrange(2, 101):
        s = "*".join(["%d**%d" % (x[0],x[1]*b) for x in a])
        if s not in result:
            result.append(s)
print len(result)

话说LS的代码是什么东东啊.
赞一下(1人) 回复此楼
10楼2011-06-18 10:23:25
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 holmescn 的主题更新
311/4返回列表1234下一页
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
信息提示
关闭
请填处理意见
关闭