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

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程 第廿三题：
172/2返回列表上一页12
查看: 2213  |  回复: 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
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
信息提示
关闭
请填处理意见
关闭