新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚
   XML论坛     W3CHINA.ORG讨论区     计算机科学论坛     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
    		•   Add to Google

    >> We choose to study algorithmic problems,  not because they are easy,  but because they are hard.
    [返回] 计算机科学论坛 → 计算机理论与工程 → 『 算法理论与分析 』 → 两个算法问题，想了很久，一直找不到好点的解决方法 ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 7063 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： 两个算法问题，想了很久，一直找不到好点的解决方法 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     czihong 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：3
      积分：63
      门派：GOOGLEBBS.NET
      注册：2008/6/6

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给czihong发送一个短消息 把czihong加入好友 查看czihong的个人资料 搜索czihong在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看czihong的博客楼主
    发贴心情 两个算法问题，想了很久，一直找不到好点的解决方法

    问题1：
    找出满足以下条件的最小素数：
    a.3个连续素数的和
    b.17个连续素数的和
    c.45个连续素数的和
    d.979个连续素数的和
    e.本身为素数

    例如：41为满足以下条件的最小素数：
    a.3个连续素数的和（11 ＋ 13 ＋ 17 ＝ 41）
    b.6个连续素数的和（2 ＋ 3 ＋ 5 ＋ 7 ＋ 11 ＋ 13 ＝ 41）

    问题2：
    一个30 * 35 的表格，左上角为起点，右下角为终点，
    问： 从起点出发，只能向右或向下移动，到终点有几种可能。


       收藏   分享  
    顶(0)
      




    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/6/6 22:12:00
     
     liuyujyyz 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：7
      积分：79
      门派：IEEE.ORG.CN
      注册：2008/6/3

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给liuyujyyz发送一个短消息 把liuyujyyz加入好友 查看liuyujyyz的个人资料 搜索liuyujyyz在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看liuyujyyz的博客第2楼
    发贴心情 
    问题2是数学问题，应该是75C30

    ----------------------------------------------
    我是新手，多多帮助

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/6/8 15:58:00
     
     czihong 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：3
      积分：63
      门派：GOOGLEBBS.NET
      注册：2008/6/6

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给czihong发送一个短消息 把czihong加入好友 查看czihong的个人资料 搜索czihong在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看czihong的博客第3楼
    发贴心情 
    问题2已经解决了。只是问题1还不知道怎么解决。想不出一个比较好的算法
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/6/8 19:51:00
     
     netjian 帅哥哟，离线，有人找我吗？白羊座1986-4-16
      
      
      头衔：智能入门者
      等级：大四(GRE考了1600分!)
      文章：198
      积分：1332
      门派：IEEE.ORG.CN
      注册：2007/5/5

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给netjian发送一个短消息 把netjian加入好友 查看netjian的个人资料 搜索netjian在『 算法理论与分析 』的所有贴子 点击这里发送电邮给netjian  引用回复这个贴子 回复这个贴子 查看netjian的博客第4楼
    发贴心情 
    对于算法1，应该会给出这个素数的相关范围吧，
    不管是ACM还是其他的比赛，一般都会给出input的数值范围的。

    因为当这个输入的素数非常大，其分解成为几个连续的素数，但是这几个连续的素数之差也是非常大的。
    无穷大。证明如下：
    任取一个正整数n，计算N=1*2*3*……*n，则N+2、N+3、……、N+n都不是素数，因为N是1至n的所有数的公倍数，N+2是2的倍数，N+3是3的倍数，……，N+n是n的倍数。于是得到连续n-1个数不是素数。而n值可任取，因此连续的两个素数的差可以大于任何正数。

    因此，这个算法就得相当考虑剪枝以及相关的效率提高了。

    如果是数据不大的话，还可以考虑暴力+剪枝优化来处理，但是对于大型的数据，我觉得这个程序肯定超时……

    ----------------------------------------------
    长江后浪，无坚不摧。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/6/12 13:14:00
     
     czihong 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：3
      积分：63
      门派：GOOGLEBBS.NET
      注册：2008/6/6

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给czihong发送一个短消息 把czihong加入好友 查看czihong的个人资料 搜索czihong在『 算法理论与分析 』的所有贴子 引用回复这个贴子 回复这个贴子 查看czihong的博客第5楼
    发贴心情 
    这是我在google treasure hunt 2008做的题目。用bash脚本的话，我可以得出结果，而且答案是正确的，但是不关算法什么事。方法是将素数存在文件中，然后进行比较，得出结果。
    不过我想用java实现，一直找不到高效的算法，计算时间长，而且得不出结果。
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2008/6/12 21:37:00
     
     GoogleAdSense
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 算法理论与分析 』的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2024/11/30 10:15:57

    本主题贴数5，分页： [1]

    管理选项： 修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    		 62.500ms