haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 学科竞赛学科竞赛

题二: 选数

发布时间:2013-12-18 12:31:36  

题二: 选数

[问题描述]:

已知n(1<=n<=20)个整数x1,x2,…,xn(1<=xi<=5000000),以及一个整数k(k<n)。从n个整数中任选k个整数相加,可分别得到一系列的和。现在,要求你计算出和为素数共有多少种。

[问题分析]:

本题动态规划无从下手,也无数学公式可寻,看来只能搜索(组合的生成算法),其实1<=n<=20这个约束条件也暗示我们本题搜索是有希望的,组合的生成可用简单的DFS来实现,既搜索这k个整数在原数列中的位置,由于组合不同于排列,与这k个数的排列顺序无关,所以我们可以令a[I]<a[I+1](a[I]表示第I个数在原数列中的位置),这个组合生成算法的复杂度大约为C(n,k),下面给出递归搜索算法的框架:

接下来的问题就是判断素数,判断一个整数P(P>1)是否为素数最简单的方法就是看是否存在一个素数a(a<=sqrt(P))是P的约数,如果不存在,该数就为素数,由于在此题中1<=xi<=5000000,n<=20,所以要判断的数P不会超过100000000,sqrt(p)<=10000,因此,为了加快速度,我们可以用筛选法将2…10000之间的素数保存到一个数组里(共1229个),这样速度估计将提高5~6倍。

特别注意:本题是要求使和为素数的情况有多少种,并不是求有多少种素数,比赛时就有很多同学胡乱判重而丢了12分;还有1不是素数,在判素数时要对1做特殊处理。

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com