找回密码
 注册
Simdroid-非首页
楼主: waynebuaa

[欧拉习题] PrjEulr 1---求出1000以内所有的能被3或5整除的数的和

[复制链接]
发表于 2008-12-8 01:12:31 | 显示全部楼层 来自 山西太原
当然啦,Union求并集肯定要比你求和再把重复的减掉要慢很多啦
回复 不支持

使用道具 举报

发表于 2008-12-8 10:36:23 | 显示全部楼层 来自 江苏无锡
Simdroid开发平台
赫赫。大伙有没有听说过高斯算 1+ 100 的故事 ?

我在 way 最后的代码基础上

  1. Timing[Sum[i, {i, 3, n, 3}] + Sum[i, {i, 5, n, 5}]-Sum[i, {i, 15, n, 15}]]
复制代码
通过自定义函数,来改进 Sum 的效率。

  1. n = 10^6 - 1;
  2. function[k_, n_] := k (Floor[n/k]*(1 + Floor[n/k])/2);
  3. Timing[function[3, n] + function[5, n] - function[15, n]]
复制代码
短时程序运行速度估算如下


  1. reps = 100000;
  2. {time, res} =
  3. Timing[Do[
  4.    function[3, n] + function[5, n] - function[15, n], {reps}]]
  5. time/reps

复制代码
目前的运行速度,大约比 way 最后0.25 秒的代码快 10000 倍。

[ 本帖最后由 FreddyMusic 于 2008-12-8 10:40 编辑 ]
回复 不支持

使用道具 举报

 楼主| 发表于 2008-12-8 11:52:45 | 显示全部楼层 来自 北京海淀

回复 22# FreddyMusic 的帖子

我前面的Sum太多了,可以简化一下:
  1. Timing[Sum[i, {i, #, n, #}] & /@ {3, 5, 15}.{1, 1, -1}]
复制代码
这个程序的特点就是没有判断,没有乘法,用的全是基本的加法运算,可想而知,速度自然快些。



到此为止,除了楼上的FM给的方法外,以上所有的程序都有一个共性,就是面向过程的数值计算。

其实,由我给的那个sum程序,大家可以看得出来,我的那个程序有许多的单调的加法运算,这个如果从符号运算的角度出发,可以避免的,就是先把通式求出来
  1. Sum[i, {i, a, N, a}]
复制代码
于是就有了FM的算法,呵呵,其实本来我想留着以这个收尾,想做一个总结的。没想到被FM给抢了先机,不过,我没有定义Function,用的是规则代换:
  1. Timing[((k Floor[n/k]*(1 + Floor[n/k])/2) /. k -> {3, 5, 15}).{1,1, -1}]
复制代码

[ 本帖最后由 waynebuaa 于 2008-12-8 12:15 编辑 ]
回复 不支持

使用道具 举报

 楼主| 发表于 2008-12-8 13:40:55 | 显示全部楼层 来自 北京海淀

总结

做一个总结吧:
我先把大家的代码都集中在一起了,通过阅读代码,相信大家多多少少能从中得到提高。

大家也看到了,这个基本上就是我们mathematia simwe “欧拉计划” 讨论学习的大体流程。
不知道这样的计划大家有什么意见?

附注:
就这个题目而言,比较简单,但到了后面,难度系数会大大增加的,那个时候才是真正体现算法和思想的重要性的时候

[ 本帖最后由 waynebuaa 于 2008-12-8 13:52 编辑 ]

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有账号?注册

×
回复 不支持

使用道具 举报

发表于 2008-12-8 13:54:54 | 显示全部楼层 来自 山西太原
Wayne辛苦啦,那咱就开始下一道题吧
回复 不支持

使用道具 举报

发表于 2008-12-9 13:03:53 | 显示全部楼层 来自 江苏无锡
Wiki list algorithm earlier than me. We are lucky to find the same method.

http://en.wikipedia.org/wiki/Project_Euler
回复 不支持

使用道具 举报

发表于 2013-10-14 13:03:36 | 显示全部楼层 来自 北京西城
本帖最后由 chyanog 于 2013-10-14 13:13 编辑

  1. Tr@N@DeleteDuplicates[Join @@ Range[0, 1*^7 - 1, {3, 5}]] // AbsoluteTiming

  2. Tr@N@Pick[#, #~Mod~3*#~Mod~5, 0] &@Range[1*^7 - 1] // AbsoluteTiming

  3. n /. Solve[{n~Mod~3 n~Mod~5 == 0, 0 < n < 1000}, n, Integers] // Total
  4. Sum[Boole[Mod[i, 3] == 0 || Mod[i, 5] == 0] i, {i, n}]
  5. Sum[(Boole[Mod[i, 3] == 0] + Boole[Mod[i, 5] == 0] -Boole[Mod[i, 15] == 0]) i, {i, n}] // Simplify


  6. tic,n=1e7-1;sum(unique([int32(0:3:n), int32(0:5:n)])),toc

  7. tic,a=int32(1:1e7-1);sum(a(mod(a,3)==0 | mod(a,5)==0)),toc
复制代码
回复 不支持

使用道具 举报

发表于 2018-3-9 21:06:47 | 显示全部楼层 来自 江西南昌
留个脚印,就当是学习吧Total[Select[Range[1000 - 1], Mod[#, 3] == 0 || Mod[#, 5] == 0 &]]
回复 不支持

使用道具 举报

发表于 2020-4-25 18:12:19 | 显示全部楼层 来自 江西
天堂2开服服务端传奇3开服服务端英雄王座开服服务端千年开服服务端征途开服服务端
新魔界开服服务端骑士开服服务端烈焰开服服务端破天开服服务端决战开服服务端
美丽世界开服服务端乱勇OL开服服务端倚天2开服服务端完美世界开服服务端征服开服服务端
永恒之塔开服服务端仙境RO开服服务端诛仙开服服务端神泣开服服务端石器开服服务端
冒险岛开服服务端惊天动地开服服务端热血江湖开服服务端问道开服服务端密传开服服务端
火线任务(Heat Project)开服服务端飞飞OL开服服务端洛汗开服服务端天之炼狱开服服务端
丝路传说开服服务端大话西游开服服务端蜀门开服服务端机战开服服务端剑侠情缘开服服务端
绝对女神开服服务端传说OL开服服务端刀剑开服服务端弹弹堂开服服务端科洛斯开服服务端
魔力宝贝开服服务端武林外传开服服务端网页游戏开服服务端页游开服服务端希望OL开服服务端
天龙开服服务端奇迹Mu开服服务端魔兽开服服务端魔域开服服务端墨香开服服务端
天堂开服服务端传世开服服务端真封神开服服务端劲舞团开服服务端天上碑开服服务端
成吉思汗开服服务端剑侠世界开服服务端全民奇迹开服服务端挑战OL开服服务端
红月开服服务端十二之天(江湖OL)开服服务端倚天开服服务端dnf开服服务端

一条龙=服务器+商业版本+空间+域名+网站配套程序+广告+技术支持+7*24小时服务 服务器租用,品质第一,速度至上,稳定是宗旨,硬防是基础,硬件防火墙+金盾软件防火墙=软硬兼施双防护(全面防护DDOS+SYN和CC及DB等各攻击),主营业务:手游端游页游服务端版本一条龙开服+服务器租用+网站建设修改+广告宣传渠道!
回复 不支持

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|小黑屋|联系我们|仿真互动网 ( 京ICP备15048925号-7 )

GMT+8, 2024-3-29 00:52 , Processed in 0.032185 second(s), 9 queries , Gzip On, MemCache On.

Powered by Discuz! X3.5 Licensed

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表