以文本方式查看主题

-  计算机科学论坛  (http://bbs.xml.org.cn/index.asp)
--  『 算法理论与分析 』  (http://bbs.xml.org.cn/list.asp?boardid=60)
----  两个算法问题,想了很久,一直找不到好点的解决方法  (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=63547)


--  作者:czihong
--  发布时间:6/6/2008 10:12:00 PM

--  两个算法问题,想了很久,一直找不到好点的解决方法
问题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 的表格,左上角为起点,右下角为终点,
问: 从起点出发,只能向右或向下移动,到终点有几种可能。


--  作者:liuyujyyz
--  发布时间:6/8/2008 3:58:00 PM

--  
问题2是数学问题,应该是75C30
--  作者:czihong
--  发布时间:6/8/2008 7:51:00 PM

--  
问题2已经解决了。只是问题1还不知道怎么解决。想不出一个比较好的算法
--  作者:netjian
--  发布时间:6/12/2008 1:14:00 PM

--  
对于算法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值可任取,因此连续的两个素数的差可以大于任何正数。

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

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


--  作者:czihong
--  发布时间:6/12/2008 9:37:00 PM

--  
这是我在google treasure hunt 2008做的题目。用bash脚本的话,我可以得出结果,而且答案是正确的,但是不关算法什么事。方法是将素数存在文件中,然后进行比较,得出结果。
不过我想用java实现,一直找不到高效的算法,计算时间长,而且得不出结果。
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
50.781ms