pascal程序：选数

已知 n 个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k＝3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：
　　3＋7＋12=22　　3＋7＋19＝29　　7＋12＋19＝38　　3＋12＋19＝34。
　　现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：3＋7＋19＝29）。
输入说明
n , k （1<=n<=20，k＜n）
x1,x2，…,xn （1<=xi<=5000000
输出说明
一个整数（满足条件的种数）。

输入样例：
4 3
3 7 12 19
输出样例：
1

noip2002普及组第二题

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

Proc Search(dep)
Begin
for i <- a[dep - 1] + 1 to N - (M - dep) do
1：a[dep] <- i
2：S <- S + x[i]
3：if dep < k then Search(dep + 1) else 判断素数
4：S <- S - x[i]
End

接下来的问题就是判断素数，判断一个整数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做特殊处理。

标程：PASCAL

{$R-,S-,I-,Q-}

program c2;

const
MaxN = 20;

var
N, M, i: Byte;
ans, s: Longint;
x: array[1 .. MaxN] of Longint;
f: array[1 .. 10000] of Byte;
p: array[1 .. 1229] of Integer;

procedure Get_Prime;
var
i, j, s: Integer;
begin
s := 0;
f[1] := 0;
for i := 2 to 10000 do f[i] := 1;
for i := 2 to 10000 do
if f[i] = 1 then
begin
Inc(s); p[s] := i;
j := 2 * i;
while j <= 10000 do begin f[j] := 0; Inc(j, i) end;
end
end;

procedure Work(S: Longint);
var
i: Integer;
begin
if S <= 10000 then Inc(ans, f[S])
else
begin
i := 1;
while sqr(longint(p[i])) <= S do
begin
if S mod p[i] = 0 then Exit;
Inc(i)
end;
Inc(ans)
end
end;

procedure Search(d, pre: Byte);
var
i: Byte;
begin
for i := pre + 1 to N - (M - d) do
begin
Inc(S, x[i]);
if d = M then Work(S)
else Search(d + 1, i);
Dec(S, x[i])
end
end;

begin
Readln(N, M);
for i := 1 to N do Read(x[i]);
ans := 0; S := 0;
Get_Prime;
Search(1, 0);
Writeln(ans)
end.

一个神牛的题解.......

不会就暴力

时间不够 先简单给你写下 你自己改改 就是直接dfs(深度优先搜索) k层，复杂度为C（n，k）。具体的实现见 run（s,i,p）//s：到目前为止的和 i:整数选自a[1--i] p:现在已经选了几个数 procedure init; var i:longint; begin assign(input,name+'.in');reset(input); read(n,k); for i:=1 to n do read(a[i]); close(input); ans:=0; end; function ok(x:longint):boolean; var i:longint; begin ok:=true; for i:=2 to trunc(sqrt(x))do if x mod i=0 then begin ok:=false;break;end; end; procedure run(s,i,p:longint); var j:longint; begin if p=k+1 then begin if ok(s)then inc(ans); exit; end; for j:=i+1 to n do run(s+a[j],j,p+1); end; begin assign(output,name+'.out');rewrite(output); init; run(0,0,1); writeln(ans); close(output); end.

选数是noip2002普及的第二题，附我的程序，我们学校的题库：http://pingce.ayyz.cn:9000 望采纳！！！ var x:array[1..20]of longint; n,k,i,j,total:integer; y:array[1..500]of boolean; procedure find(left,now,all:integer); begin if left&gt;n-now+1 then exit; if (left=0)and(now&gt;n) then begin if y[all] then inc(total); exit; end; find(left,now+1,all); if left&gt;0 then find(left-1,now+1,all+x[now]); end; begin readln(n,k); for i:=1 to n do read(x[i]); fillchar(y,sizeof(y),true); y[1]:=false; for i:=2 to 500 do if y[i] then for j:=2 to 500 div i do y[i*j]:=false; find(k,1,0); writeln(total); end.