procedure prime(s:longint);{判断K个数的和是否为素数} var
i:integer; begin i:=2;
while (sqr(i)<=s)and(s mod i<>0) do inc(i); if sqr(i)>s then inc(ans){若为素数则总数加1} end;
procedure dfs(i,m:byte);{搜索第i个数， } var
j:byte;{j表示第i个数的位置 begin
for j:=m to n-k+i do{枚举第i个数} begin
inc(s,a[j]);{入栈}
if i=k then prime(s)
else dfs(i+1,j+1);{继续搜第i+1个数} dec(s,a[j]){出栈} end end; begin
readln(n,k);
for i:=1 to n do read(a[i]);
ans:=0; s:=0; dfs(1,1);
writeln(ans); end.
从上面的两个例子我们可以看出，用递归实现深度优先搜索比非递归更加方便。
在使用深度搜索法解题时，搜索的效率并不高，所以要重视对算法的优化，尽可能的减少搜索范围，提高程序的速度。
在下一篇中将继续介绍另一种搜索方法——广度优先搜索法。
算法在信息学奥赛中的应用（搜索法二） 在深度优先搜索算法中，深度越大的结点越先得到扩展，若把它改为深度越小的结点越先得到扩展，就是广度优先搜索法。
广度优先搜索基本算法： program bfs;
初始化；建立队列data;
设队列首指针closed:=0;队列尾指针open:=1; repeat
closed 增1，取出closed所指结点进行扩展； for i:=1 to r do begin if 子结点符合条件then begin
open增1，并把新结点存入数据库队尾；
if新结点与原有结点有重复 then 删于该结点(open减1) else if 新结点即目标 then 输出并退出 ;
end{if}; end{for};
until closed>=open;{队列为空}
使用广度优先搜索时，离根结点最近的结点先扩展，所以广度优先搜索法比较适合求步数最少的解，由于深度优先使用了标志法，使得存储空间大大减少，而广度优先要保留所有搜索过的节点，随着搜索程度的加深，所需的存储空间成指数增加。因此在必要时我们采用双向搜索来减少搜索空间和存储空间，如下面的例子。
例 字串变换（NOIP2002tg）
[问题描述]:已知有两个字串 A$, B$ 及一组字串变换的规则（至多6个规则）: A1$ -> B1$ A2$ -> B2$ 规则的含义为：在 A$中的子串 A1$ 可以变换为 B1$、A2$ 可以变换为 B2$ ?。例如：A$＝'abcd' B$＝'xyz' 变换规则为：‘abc’->‘xu’ ‘ud’->‘y’ ‘y’->‘yz’ 则此时，A$ 可以经过一系列的变换变为 B$，其变换的过程为：‘abcd’->‘xud’->‘xy’->‘xyz’ 共进行了三次变换，使得 A$ 变换为B$。 [输入]:键盘输人文件名。文件格式如下： A$ B$
A1$ B1$ \\
A2$ B2$ |-> 变换规则 ... ... /
所有字符串长度的上限为 20。
[输出]:输出至屏幕。格式如下： 若在 10 步（包含 10步）以内能将 A$ 变换为 B$ ，则输出最少的变换步数；否则输出\[输入输出样例] b.in: abcd xyz abc xu ud y y yz 屏幕显示：3
算法分析：此题是求变换的最少步数，很显然可以使用广度优先搜索法，如果直接从初状态搜到目标状态，最坏情况下存储的结点数超过6的10次方幂，搜索空间过大，因此我们考虑使双向搜索，同时从初始状态和目标状态向中间状态搜索，当相遇时搜索结束。采用双向搜索，存储的结点数还有可能超限，我们在前向搜索队列中存储5步内变换的结点，在后向搜索队列中，由于第5步产生的结点只是用来与前向队列中的结点比较，所以可以不存储在队列中，后向搜索队列只需存储4步内的结点，这样就解决了存储空间问题。
为了使用方便，在程序设计中用一个数组a[1..max]存储两个队列，前向搜索队列为a[1..mid]，后向搜索队列为a[mid..max]，用st存储搜索方向，st=0表示前向搜索，st=1表示后向搜索，用op[st]和cl[st]分别表示队列尾指针和首指针，用be表示队列起始位置，循环产生每一个结点，若在10内无解退出循环，若在10内找到解则输出解并退出程序。
源程序：
const mid=12000;max=16000; type
node=record s:string;x:byte;end; var
i,mark:integer;
a:array [1..max]of ^node;
x:array[0..6,0..1]of string[20]; d,fil:string;
op,cl:array [0..1] of integer; procedure Init;{读取数据，初始化} var f:text;t:string; begin
readln(fil);
assign(f,fil);reset(f);i:=0;
while not eof(f) do begin readln(f,t);
x[i,0]:=copy(t,1,pos(' ',t)-1);
x[i,1]:=copy(t,pos(' ',t)+1,length(t)); inc(i); end;{while}
mark:=i-1;close(f); end;
{判断是否到达目标状态}
procedure bool(be,st:integer); begin
for i:=mid-be+1 to cl[1-st] do
if a[cl[st]]^.s=a[i]^.s then begin writeln(a[cl[st]]^.x+a[i]^.x); halt; end;{if} end;
{判断节点是否与前面的结点重复} procedure check(be,st:integer); begin
for i:=be+1 to cl[st]-1 do
if a[i]^.s=a[cl[st]]^.s then begin dec(cl[st]);exit; end; bool(be,st); end;
{扩展产生新节点}
procedure expand(be,st:integer); var i,j,k,lx,ld:integer; begin
inc(op[st]);d:=a[op[st]]^.s; k:=a[op[st]]^.x;ld:=length(d); for i:=1 to mark do begin lx:=length(x[i,st]); for j:=1 to ld do begin
if (copy(d,j,lx)=x[i,st]) then begin if (st<>1)or(k<>4)then begin inc(cl[st]); new(a[cl[st]]); end;{if}
a[cl[st]]^.s:= copy(d,1,j-1)+ x[i,1-st]+ copy(d,j+lx,ld); a[cl[st]]^.x:=k+1;
check(be,st);{检查是否重复} end;{if} end;{for} end;{for} end;
procedure bfs;
var be,k,st:integer; Begin
for st:=0 to 1 do begin
if st=0 then be:=0 else be:=mid; op[st]:=be+0;cl[st]:=be+1; new(a[cl[st]]);
a[cl[st]]^.s:=x[0,st]; a[cl[st]]^.x:=0; end;{for} repeat
if (op[0]
init;bfs;writeln('NO ANSWER!') END.
两种搜索算法的比较： 搜索方式 扩展方式 深度优先 后产生先扩展 广度优先 先产生先扩展 数据结构 适合求解的问题 栈 队列 可行解或所有解 最优解 在选择搜索方式时，并不是完全遵循以上原则，具体还是要根据题目的要求而定。在求最优解时，如果搜索的深度不大，我们也可以考虑使用深度优先搜索；在求解可行解时，如果搜索的深度没有限制，或者搜索的代价与搜索的深度成正比,我们也应该使用广度优先搜索。
算法在信息学奥赛中的应用（动态规划法）
在学习动态规划法之前，我们先来了解动态规划的几个概念