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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程 第廿三题：
172/2返回列表上一页12
查看: 2561  |  回复: 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
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[基金申请] 在坚冰还盖着北海的时候，我看到了怒放的梅花。 +3 ziyangfang 2026-08-25 3/150 2026-08-25 13:14 by huagongfeihu
[基金申请] 如果此刻你正在为国基感到焦虑，不妨来听听这首《基金之外》 +8 scalable 2026-08-24 8/400 2026-08-25 12:52 by jnhyjjm
[基金申请] 人气不行了 +11 fansofjerry 2026-08-21 11/550 2026-08-25 11:04 by 孤独的英雄6
[教师之家] 导师吐槽：我怎么摊上了这么个极品研究生！ +3 苏东坡二世 2026-08-23 3/150 2026-08-25 10:35 by shisan1313
[基金申请] 今天基金会出结果吗？20260819 +17 kkkl_v 2026-08-19 18/900 2026-08-25 09:41 by windflowerwy
[基金申请] 我面上完蛋了 +13 且听虎啸 2026-08-20 14/700 2026-08-25 09:10 by mrkang
[基金申请] 只有每年这种时候来逛逛小木虫 +25 yaoyewhu2008 2026-08-20 27/1350 2026-08-25 08:01 by Equinoxhua
[基金申请] 明天应该可查了！？ +5 chengyan1220 2026-08-23 5/250 2026-08-24 23:28 by 我4大白菜
[基金申请] 能否退出参与的面上项目解除限项 +21 koalala 2026-08-24 24/1200 2026-08-24 19:25 by 家与远方
[基金申请] filecode，4个jtjc了 +14 ziyangfang 2026-08-19 17/850 2026-08-24 18:37 by 哈哈蛤？
[基金申请] 建议基金发布提前给出明确的时间点 +13 kulium 2026-08-21 16/800 2026-08-24 16:27 by superceng
[基金申请] 今日不放榜？网传国自然预计 8 月 27 日可查结果 +17 医学老男孩 2026-08-20 21/1050 2026-08-24 14:21 by refreshing11
[基金申请] 让我中一个面上吧！ +13 大萍1987 2026-08-20 16/800 2026-08-24 10:23 by 太傻了
[基金申请] 放榜前的不淡定 20+4 snowwithsea 2026-08-19 17/850 2026-08-24 10:20 by echo8914667
[基金申请] 科研孤儿太难了 +18 我4大白菜 2026-08-20 19/950 2026-08-24 09:47 by 凯恩广盛催化分�
[基金申请] 什么时候开奖？ +10 CrisMessi 2026-08-18 11/550 2026-08-24 06:50 by 开心的小狮子
[基金申请] 今天放榜吗？ +15 布布和一二 2026-08-19 16/800 2026-08-23 09:55 by 张春生
[基金申请] 时间戳今天，20号变了 +5 archvillain 2026-08-20 5/250 2026-08-22 06:12 by hui_daxiao
[基金申请] 看来今天不会放榜了？ +8 chengyan1220 2026-08-21 11/550 2026-08-21 17:52 by dcqxinyang
[基金申请] 时间戳又变了 +13 wuchongjun 2026-08-20 19/950 2026-08-21 17:21 by 紫杉醇
信息提示
关闭
请填处理意见
关闭