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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程 第廿三题：
172/2返回列表上一页12
查看: 2287  |  回复: 16
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
本帖产生 4 个 程序强帖 ，点击这里进行查看

libralibra

至尊木虫 (著名写手)

骠骑将军
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
jjdg(金币+2): 辛苦了 2011-06-07 15:08:35
按上面的算法重写了下,6s多,看看python还能提高效率不

代码
CODE:
#! usr/bin/env python
# coding: cp936

from mytictoc import tic, toc
from math import sqrt

def sumdivisors(n):
    sumdiv = sum([i+n/i for i in xrange(2,int(sqrt(n))+1) if n%i==0])+1
    if int(sqrt(n))*int(sqrt(n))==n:
        sumdiv -= int(sqrt(n))
    return sumdiv

def euler23():
    n = 28123
    tic()
    abn_list = [c for c in xrange(12,n+1) if sumdivisors(c)>c] # 生成富数列表
   
    # 生成所有可表示成2个富数之和的数,并剔除重复项
    num_list = set([abn_list[i]+j for i in xrange(0,len(abn_list)) for j in abn_list[i:] if abn_list[i]+j    
    # 1-28123求和减去num_list求和即为结果
    print sum(xrange(1,n))-sum(num_list)
    toc()

if __name__=='__main__':
    euler23()

结果
CODE:
C:\WINDOWS\system32\cmd.exe /c python test.py
4179871
Elapsed time: 6.37453140 seconds

Hit any key to close this window...

[ Last edited by libralibra on 2011-6-7 at 02:08 ]
赞一下(2人) 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
11楼2011-06-07 02:05:17
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
★
jjdg(金币+1): 感谢参与 2011-06-07 15:08:22
如果两两富数的和没重复，就可以在O(n)时间里计算出来了。可惜不只有重复，而且还有很多的重复，看来怎么也在O(n^2)这个量级上了。
赞一下(1人) 回复此楼
12楼2011-06-07 09:05:18
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sudo

木虫 (正式写手)
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
jjdg(金币+2): 辛苦了 2011-06-07 15:08:04
直觉告诉我不会有比O(N^2)更快的算法了，不过仍然的我们可以空间换时间：
CODE:
#include

#define MAGIC 28124

int fsum[MAGIC];
unsigned char tag[MAGIC];

int main(){
    int sum=0;
    int i, j;

    for(i=1; i         for(j=i+i; j             fsum[j] += i;
        }
    } //计算因子和表

    for(i=1; i         if(fsum[i]<=i) continue;
        for(j=i; i+j             if(fsum[j]>j){
                tag[i+j] = 1;
            }
        }
    } //标记所有能表示为两个富数和的数

    for(i=1; i         if(!tag[i]) sum += i;
    }

    printf("%d\n", sum);

    return 0;
}

输出：
CODE:
4179871

Process returned 0 (0x0)   execution time : 0.269 s
Press any key to continue.

PS:
仔细翻了一下前面的帖子发现思想和huycwork的差不多...就当上面什么也没写吧...（咳，怎么找不到删帖的选项呢...）

[ Last edited by sudo on 2011-6-7 at 09:36 ]
赞一下(2人) 回复此楼
13楼2011-06-07 09:12:25
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
★
jjdg(金币+1): 感谢参与 2011-06-07 15:07:47
引用回帖:
Originally posted by sudo at 2011-06-07 09:12:25:
直觉告诉我不会有比O(N^2)更快的算法了，不过仍然的我们可以空间换时间：

[code]
#include <stdio.h>

#define MAGIC 28124

int fsum[MAGIC];
unsigned char tag[MAGIC];

int main(){
    in ...

没事，挂着吧。

感觉这种组合法要比那种分解法要快。
赞一下(1人) 回复此楼
14楼2011-06-07 12:08:57
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sudo

木虫 (正式写手)
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
jjdg(金币+1): 感谢参与 2011-06-07 15:07:36
引用回帖:
Originally posted by holmescn at 2011-06-07 12:08:57:
没事，挂着吧。

感觉这种组合法要比那种分解法要快。

其实应该是比huywork的稍微慢一点~因为如果生成富数表的话，规模就变小不少吧~我这个是直接暴力试

PS：咳，刚开始没理解你的意思...呃，huywork就是这种方法啊，在前面大家都没看见？这个肯定比分解法快的，因为既没有重复计算，也不涉及除法

[ Last edited by sudo on 2011-6-7 at 14:06 ]
赞一下(2人) 回复此楼
15楼2011-06-07 12:33:27
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

蓝水卫士

木虫 (著名写手)
★
jjdg(金币+1): 感谢参与 2011-06-07 15:08:44
都是高手啊！
回复此楼
16楼2011-06-07 12:56:22
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
dubo(金币+1): 欢迎讨论 2011-06-07 22:46:22
引用回帖:
Originally posted by sudo at 2011-06-07 12:33:27:
其实应该是比huywork的稍微慢一点~因为如果生成富数表的话，规模就变小不少吧~我这个是直接暴力试

PS：咳，刚开始没理解你的意思...呃，huywork就是这种方法啊，在前面大家都没看见？这个肯定比分解法 ...

兄台太过谦虚了呃~人月神话里面不是说嘛，世界上没有两个一样的软件，而且你的意见一向精炼且带文艺美的说，用前人的话说，就是前面的脖子和肩膀啊

我觉得如果把筛选出来的富数应用组合的话，时间应该还可以再优化的，我给的代码里面有一些冗余计算，比直接组合所有富数和要慢，但是比暴力穷举要快。慢的原因就在于每次都要从第一个开始试算，直接组合就没有这种失败了。
赞一下(2人) 回复此楼
漩涡的中心有一块空地，空空的。
17楼2011-06-07 16:13:48
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 holmescn 的主题更新
172/2返回列表上一页12
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 290求调剂 +5 孔志浩 2026-03-12 10/500 2026-03-16 09:01 by 余晖&
[考博] 欢迎申博同学联系 +3 天道酬勤2026686 2026-03-10 7/350 2026-03-15 19:03 by 天道酬勤2026686
[考研] 085601材料工程315分求调剂 +3 yang_0104 2026-03-15 3/150 2026-03-15 10:58 by peike
[考研] 290求调剂 +4 @将就将就看 2026-03-10 8/400 2026-03-14 14:23 by 千千运气
[考研] 一志愿安徽大学材料工程专硕313分，求调剂的学校 +8 Yu先生 2026-03-10 10/500 2026-03-14 01:04 by JourneyLucky
[考研] 一志愿华中农业大学071010，总分三百二,求调剂 +3 困困困困坤坤 2026-03-10 3/150 2026-03-14 00:35 by JourneyLucky
[考研] 327求调剂 +4 Ffff03 2026-03-10 4/200 2026-03-14 00:17 by JourneyLucky
[考研] 材料371求调剂 +9 鳄鱼? 2026-03-11 11/550 2026-03-13 22:53 by JourneyLucky
[考研] 26调剂/材料/英一数二/总分289/已过A区线 +6 步川酷紫123 2026-03-13 6/300 2026-03-13 21:59 by 星空星月
[考研] 一志愿西南交大，材料专硕317求调剂 +5 lx8568 2026-03-11 5/250 2026-03-13 21:43 by peike
[考研] 332求调剂 +3 Zz版 2026-03-13 3/150 2026-03-13 20:36 by 18595523086
[考研] 材料工程调剂 +4 咪咪空空 2026-03-11 4/200 2026-03-13 19:57 by JourneyLucky
[考研] 求调剂 +7 18880831720 2026-03-11 7/350 2026-03-13 16:10 by JourneyLucky
[考研] 307求调剂 +5 超级伊昂大王 2026-03-12 5/250 2026-03-13 15:56 by 棒棒球手
[考研] 290求调剂 +7 ADT 2026-03-12 7/350 2026-03-13 15:17 by JourneyLucky
[考研] 274求调剂 +3 S.H1 2026-03-12 3/150 2026-03-13 15:15 by JourneyLucky
[考博] 2026年博士申请 +3 QwQwQW10 2026-03-11 3/150 2026-03-12 17:58 by gxch43
[考研] 0857环境调剂 +5 熠熠_11 2026-03-10 5/250 2026-03-11 10:59 by wang_dand
[考研] 化工0817调剂 +8 灿若星晨 2026-03-10 8/400 2026-03-10 22:44 by 星空星月
[考博] 26申博求助 +3 跳跃饼干 2026-03-10 4/200 2026-03-10 21:15 by Tntcnn
信息提示
关闭
请填处理意见
关闭