当前位置:首页 >> 学科竞赛 >> 搜索算法pascal

搜索算法pascal


信息学奥赛培训讲稿

搜索算法讲稿
一、预备知识——树(图)的深度优先遍历(DFS)和广度优先遍历(BFS)
树的深度优先遍历(DFS)的方法实质是先序遍历这棵树:从根结点出发,沿树的纵深方向遍历,当在这个 方向上不能在继续遍历的时候,退回到上层结点,选择另外一个分枝继续遍历。 (相当于图的 DFS) 树的广度优先遍历(BFS)的方法实质是

按层来遍历这棵树:从根结点出发,访问了根结点之后访问根结点 的所有子结点,然后分别从这些子结点出发,继续按广度优先的顺序遍历这棵树。 (相当于图的 BFS) 。 例如:下面这棵树的 DFS 和 BFS 遍历顺序。 DFS 遍历顺序: V0-V1-V4-V5-V6-V2-V7-V8-V3-V9-V10-V11

BFS 遍历顺序: V0-V1-V2-V3-V4-V5-V6-V7-V8-V9-V10-V11

我们知道图的两种遍历方法,其遍历过程都有一棵生成树,所以“图”的遍历可统一到“树”的遍历。 我们还知道,图的 DFS 要用到“栈” (递归) ,图的 BFS 要用到“队列” 。这些都是我们学习搜索算法的要用 到的知识。 从结点‘A’出发两种遍历。 DFS 遍历顺序 BFS 遍历顺序

二、搜索算法概述
搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况, 从而求出问题的 解的一种方法。搜索过程实际上是根据初始条件和扩展规则构造一棵“解答树”并寻找符合目标状态的节点 的过程。所有的搜索算法从其最终的算法实现上来看,都可以划分成两个部分──控制结构(扩展结点的方式)
1

信息学奥赛培训讲稿

和产生系统(扩展结点) ,而所有的算法的优化和改进主要都是通过修改其控制结构来完成的。 常用的搜索方法有回溯法、深度优先搜索法和广度有优先搜索法(在绝大部分的信息学奥赛辅导书籍中,将 回溯算法与深度优先搜索法合在一起称为深度优先搜索算法) : 深度优先搜索算法(DFS) ,就是按深度优先的策略,并按约束条件构造问题的解答树(如果问题给出的图是 显示的,即明确地给出图中结点、边的关系,则就变成了图或树的遍历问题) ; 广度优先搜索算法(BFS) ,就是按就是按广度优先的策略,并按约束条件构造问题的“解答树” (如果问题 给出的图是显示的,即明确地给出图中结点、边的关系,则就变成了图或树的遍历问题) 。 由上面的叙述可以看出,搜索算法中的“解答树”是非常关键的,如果我们在运用搜索算法的时候,脑海里 有这棵树,能让我们的思路清晰,给优化算法带来方便,下面我们来看如何构造问题的“解答树” 。

(构造一个解) 深度优先搜索算法 可以用递归过程或者模拟递归来实现。以下是实现的两种框架:

Program 深度优先搜索算法程序; Const ?; Type ?; Var ?; Procedure try(depth:longint,?); Var i:longint; Begin If depth>目标深度 then begin 输出方案 ;exit end; For i:=depth 深度可能决策范围 do begin If 决策 i 符合展开条件 then begin 记录决策 i ; Try(depth+1); 删除决策 i ; End; End; End; Begin
2

信息学奥赛培训讲稿

主程序读入数据并初始化; Try(1); 程序终止化; End.

3

信息学奥赛培训讲稿

4

信息学奥赛培训讲稿

5

信息学奥赛培训讲稿

6

信息学奥赛培训讲稿

7

信息学奥赛培训讲稿

例 1、杯子分溶剂问题:有 2 个杯子,容量分别为 x 毫升、y 毫升,在一个实验瓶中装有 x+y 毫升的化学
溶剂,实验中需要将他精确地分为两份,没有量具,只用两个杯子,试设计一个程序能找出一种对分方法,若不 能对分,输出‘NO!’ 。 分析:假设 x=5、y=3,设瓶子为 A,则我们将每个容器中的溶剂的数量作为状态结点,从一个容器往另一个 容器中倒溶剂,表示一种状态的变化,这就是结点的“产生系统” ,我们知道,每种状态可以扩展出 6 个分枝结 点,即: ◆ A 向 X 倾倒溶剂:A->X ◆ A 向 Y 倾倒溶剂:A->Y ◆ X 向 A 倾倒溶剂:X->A ◆ X 向 Y 倾倒溶剂:X->Y ◆ Y 向 A 倾倒溶剂:Y->A ◆ Y 向 X 倾倒溶剂:Y->X 比如初始结点(8,0,0)可以扩展出的结点为: (3,5,0)(5,0,3) 、 ,后四种:X->A、X->Y、Y->A、Y->X 均无法扩展出来,因此剪掉。 按照这种思路,我们可以构造出解答树如下: (访问过的结点不应在扩展,因此也要被剪掉) 。

大家可以按照这种思路完成上面的解答树,看能否找到可能的解。 如果问题要求找到所有可能的分法,我们可以采用深度优先的策略来构造这棵树,如果要找最快的分法,可 以采用广度优先的策略来构造这棵树。

三、深度优先搜索算法
深度优先搜索算法与我们学习过的树的先序遍历思路是一样的,在问题的“解答树”中,按照深度优先的策 略,从根结点出发搜索“解答树”的每个结点,直至找到问题的解为止。 深度搜索算法在搜索“解答树”的任一结点时,总是先判断该结点是否符合问题的“约束条件” (显式的或 隐式) 。如果肯定不符合,则跳过对以该结点为根的子树的搜索,逐层向其上层结点回溯。否则,进入该子树, 继续按深度优先的策略进行搜索。 如上面例题 1 分溶剂问题,我们用程序语言描述深度优先生成解答树的过程描述为:
8

信息学奥赛培训讲稿

注意:记录结点状态的数据结构定义如下: Const Maxd=100; Type node=Record a,x,y:Integer; End; Var f:Array[1..Maxd] of node; 存储已纵深方向上已经扩展出的结点(栈) 。 每个结点的状态,a:瓶容器,x:x 杯,y:y 杯 树的最大深度

深度优先扩展结点过程 Procedure dfs(dep:Integer); Var c:Integer; Begin If (f[dep].a=(x+y)div 2) and (f[dep].x=(x+y)div 2) then Begin outans(dep); exit End; For c:=1 to 6 do If expandok(f[dep].a,f[dep].x,f[dep].y,dep,c) then dfs(dep+1) End; 每个结点可扩展出 6 个子结点 如果第 dep 层的第 c 个子结点能扩展,则扩 展,并以该结点为新的待扩展结点,继续扩 展。 如果已经找到目标结点,则输出一个解 扩展结点(f[dep].a,f[de].x,f[dep].y)

解释:上面的过程是一个典型的深度优先搜索程序,函数 expandok(f[dep].a,f[dep].x,f[dep].y,dep,c) 是扩展结点的约束条件,我们有问题不难分析出约束条件为: 1、某个容器里溶剂量为 0,则不能向其他容器倾倒液体; 2、某个容器已经装满,则不能向这个容器倾倒液体; 3、前面已经存在的结点不能继续扩展。

所以,约束条件函数 expandok(sa,sx,sy,d,c:Integer):Boolean;如下:

Function expandok(sa,sx,sy,d,c:Integer):Boolean;——>判断第 d 层的第 c 个分支结点能否被扩展 Var i,tmp:Integer; Begin expandok:=True; case c of 1: If (sa=0)or(sx=x) then Begin expandok:=false;exit End; A->X 时如果 A 为 0 或 X 已满,则不能扩展 2: If (sa=0)or(sy=y) then Begin expandok:=false;exit End; A->y 时如果 A 为 0 或 y 已满,则不能扩展 3: If (sx=0) then Begin expandok:=false;exit End; X->A 时如果 X 为 0,则不能扩展 4: If (sx=0)or(sy=y) then Begin expandok:=false;exit End; X->Y 时如果 X 为 0 或 Y 已满,则不能扩展 5: If (sy=0) then Begin expandok:=false;exit End; Y->A 时如果 Y 为 0,则不能扩展 6: If (sy=0)or(sx=x) then Begin expandok:=false;exit End; Y->X 时如果 Y 为 0 或 X 已满,则不能扩展
9

信息学奥赛培训讲稿

End; case c of 1:Begin tmp:=sa+sx; If tmp>x then sx:=x else sx:=tmp; sa:=tmp-sx End; 2:Begin tmp:=sa+sy; If tmp>y then sy:=y else sy:=tmp; sa:=tmp-sy End; 3:Begin sa:=sa+sx; sx:=0 End; 4:Begin tmp:=sx+sy; If tmp>y then sy:=y else sy:=tmp; sx:=tmp-sy End; 5:Begin sa:=sa+sy; sy:=0 End; 6:Begin tmp:=sx+sy; If tmp>x then sx:=x else sx:=tmp; sy:=tmp-sx End; End; For i:=1 to d do If (sa=f[i].a) and (sx=f[i].x) and (sy=f[i].y) then Begin expandok:=False; exit End; f[d+1].a:=sa;f[d+1].x:=sx; f[d+1].y:=sy; End; 生成新的结点 查找结点(sa,sx,sy)是否已访问过 Y 向 X 倾倒后 Y 和 X 的实际液体量; Y 向 A 倾倒后 Y 和 A 的实际液体量; X 向 Y 倾倒后 X 和 Y 的实际液体量; X 向 A 倾倒后 X 和 A 的实际液体量; A 向 Y 倾倒后 A 和 Y 的实际液体量; A 向 X 倾倒后 A 和 X 的实际液体量;

过程 outans(dep);输出一个解: Var i:Integer; Begin ans:=ans+1; write(ans,':'); For i:=1 to d-1 do 路径长为 d write('(',f[i].a,',',f[i].x,',',f[i].y,')','->');输出这跳路径上的所有结点 writeln(f[d].a,',',f[d].x,',',f[d].y); writeln; End; 完整的程序,请同学们自己补充完整。 由上面的分析,我们可以归纳以下深度优先搜索的步骤: 1、 确定问题的解空间(数据规模,解答树的最大分支) ,并画出小范围的解答树。 2、 分析约束条件(充分挖掘题目的隐含条件) 3、 写出深度优先搜索的核心程序,一般核心程序的递归程序框架如下: 输出目标结点

10

信息学奥赛培训讲稿

procedure DFS(dep:integer); { i 是递归深度;} var begin if 找到解 then begin 输出结果; exit End; { n 是深度控制,即解答树的的高度;} for j:=下界 to 上界 do begin x[i]:=h[j]; if 可行{满足剪枝函数和约束条件} then begin 置值; DFS(dep+1); {继续向下搜索} 恢复全局变量的数据; end; end; end; 4、 调试程序(充分分析边界条件) 。 至于搜索算法的的优化,我们常常在解答树的基础上做以下工作: 1、 充分分析问题的约束条件; 2、 分析搜索的“上界”和“下界” ,使分枝尽量减少; 3、 搜索前预处理一些数据,达到简化搜索的目的; 4、 加强剪枝(着就是能力和水平的问题了) 。

下面来看几个简单例子!

11

信息学奥赛培训讲稿

例 2、编程列举出 1、2、?、n 的全排列。 编程列举出 1、2、?、n 的全排列。 分析:深度优先搜索算发的本质是:按照深度优先的策略搜索问题的解答树。 因此要使用它解决问题, 应该先画出问题小范围的解答树。
具体到本题,我们假设 n=3 时,如下图:位置 1 可以放置数字 1、2、3;位置 2 可以放置数字 1、2、3;位 置 3 可以放置数字 1、2、3,但是当位置 1 放了数字 1 后位置 2 和位置 3 都不能在放 1,因此画树的约束条件是:

各位置的数字不能相同。

我们画“解答树”时,根结点一般是一个空结点,根结点下面的第 1、2、3 三层分别对应位置 1、

位置 2、位置 3,用“╳”标示的分支表示该结点不满足约束条件,不能被扩展出来:

我们用递归过程来描述 “解答树”的深度优先搜索 Pascal 过程 procedure DFS(i:integer); Var c:integer; Begin If i>3 then Begin 输出一种排列; exit End; For c:=1 to 3 do If used(c)=false Then Begin used[c]:=true; a[i]:=c; DFS(i+1); used[c]:=false; End; End; 汉语解释 搜索第 i 层结点(向第 i 个位置放数)

如果搜索到一条路径,则输出一种解; 每一个结点可以分解出 3 个子结点; 如果能生成第 i 层的第 c 个结点; 数字 c 已用,将这个结点存储; 扩展第 i 层的第 c 个结点(向第 i+1 个位置放数) 向上回溯,并恢复数据

请同学自己将这个程序完善,并在机器上调试通过。

12

信息学奥赛培训讲稿

例 3:素数环: 把从 1 到 n 这 n 个数摆成一个环,要求相邻的两个数的和是一个素数。 〖问题分析〗 非常明显,这是一道搜索的题目。从位置 1 开始,每个空位有 n 个可以填的数字,只要填进 去的数合法:

〖算法设计〗

步骤 1、画解答树(n=3) :

步骤 2、确定约束条件和剪枝函数
约束条件:已用过的数字不能再用并且在 a[i]中要填的数字 c 与左边 a[i-1]和是素数 (used[c]=false) If used[i]=false then 数字 i 未使用; If used[i]=True then 数字 i 已使用; ok(i-1,c)

这里我们用数组 used[i]来表示数字 i 是否已经使用过:

函数 Ok(i,j)是判断 a[i-1]+a[i]是否是素数(其中 j 是待填入 a[I]的数):
Function ok(i,j:Integer):boolean; Var c ,s:integer; P:boolean; Begin If i=0 then begin ok:=true; exit End; P:=true; s:=a[i]+j; For c:=2 to truncc(sqrt(s)) do If s mod c=0 then Begin p:=false; break End; If i=n-1 then Begin S:=a[1]+j; For c:=2 to truncc(sqrt(s)) do If s mod c=0 then Begin p:=false; break End; End; Ok:=p; End; 由于是环,因此当 j 是第 n 个数时,应与 a[1]的和也是素数

步骤 3、写核心搜索程序(与上例一样) :
13

信息学奥赛培训讲稿

Procedure try(i:integer);{试着给 a[i]填数} Var c:integer; Begin If i>n then Begin outans; exit End; {如果找到一种填法,则输出} For c:=1 to n do {a[i]中可以填入数字 1、2、3、?、n} If (used[c]=false) and ok(i-1,c) then {如果符合约束条件则填入} Begin a[i]:=c; used[c]:=true; {在 a[i]中填入数字 c,并且标示数字 c 已用过} try(i+1); {试着给 a[i+1]填数} a[i]:=0;used[c]:=False {回溯到上层,并将 a[i]清 0,数字 c 可用} End; End;

请同学们自己将该程序完善

14

信息学奥赛培训讲稿

例 4、数的划分 将整数 n 分成 k 份,且每份不能为空,任意两份不能相同(不考虑顺序)。 例如:n=7,k=3,下面三种分法被认为是相同的。 1,1,5; 1,5,1; 5,1,1; 问有多少种不同的分法。 输入:n,k (6<n<=200,2<=k<=6) 输出:一个整数,即不同的分法。 样例 输入: 7 3 输出:4 {四种分法为:1,1,5;1,2,4;1,3,3;2,2,3;} 算法设计: 这是个计数问题,计数的题目一般不用搜索,因为搜索必须遍历完整个“解答树”才能得到最终答案,时间 复杂度高;但由于本题的数据规模比较小,如果控制好扩展结点的“上界”和“下界” ,也是能够很快得出解的。 1、画出问题的解答树 n=3,m=2 时。

2、约束条件: ①由于分解数不考虑顺序,因此我们设定分解数依次递增;所以我们扩展结点时的“下界”应是不小于待扩 展结点的值; ②假设我们将 n 已经分解成了 a[1]+a[2]+?+a[i],则 a[I+1]的最大值为: 设 k= a[1]+a[2]+?+a[i];则 a[I+1]<=(n-k) div (m-i) 所以扩展结点时的“上界”是(n-k) div (m-i)

请同学们画出 n=7 m=3 时,加上约束条件的解答树。
3、核心搜索过程: Procedure solve(k,dep:Integer); {k=n-a[1]+a[2]+?+a[dep-1];dep 表示要得到第 dep 个分解数 Var c:Integer; Begin If (dep=m) and (k>=a[dep-1]) Then Begin Inc(ans); exit; End; For c:=a[dep-1] to k div (m-dep) do Begin a[dep]:=c; solve(k-c,dep+1) End; End;

15

信息学奥赛培训讲稿

例 5 单词的划分。

16

信息学奥赛培训讲稿

17

信息学奥赛培训讲稿

18

信息学奥赛培训讲稿

19

信息学奥赛培训讲稿

例 6:单词接龙 单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母, 要求出以这个字母开头的最长的“龙” (每个单词都最多在“龙”中出现两次) ,在两个单词相连时,其重合部分 合为一部分,例如 beast 和 astonish,如果接成一条龙则变为 beastonish,另外相邻的两部分不能存在包含关系, 例如 at 和 atide 间不能相连。 输入的第一行为一个单独的整数 n (n<=20)表示单词数,以下 n 行每行有一个单词,输入的最后一行为一个 单个字符,表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在. 只需输出以此字母开头的最长的“龙”的长度 样 例 : 输入 5 at touch cheat choose tact a 输出 23 (连成的“龙”为 atoucheatactactouchoose)
20

信息学奥赛培训讲稿

算法分析: 1、 这是一个典型的搜索题目,简单解答树可以很容易画出;(相当于排列,但每个单词可用两次) 我们将样例中的 5 个单词分别编号为 1、 3、 2、 4、5、解答树: 约束条件: ①、当前龙与待接单词是否能够相接; ②、每个单词最多使用两次

2、我们知道解答树扩展结点的约束条件之一是:当前龙与待接单词是否能够相接; 我们用一个二维表 link[I,j]:如果第 I 个单词与第 j 个单词能够相接,则 link[I,j]等于增加的长度,否则 为-1; 例如样例构成的二维表为:

龙长度=Length(s[1])+link[1,2]+link[2,3]+link[3,5]+link[5,5]+link[5,2]+link[2,3] = 2 + 4 + 3 + 3 + 3 + 4 + 4 =23

21

信息学奥赛培训讲稿

生成 link[0..n,1..n]的程序 Function len(i,j:Integer):Integer; 第 I 个单词与第 j 个单词相接的长度。 Var L1,L2,L:Integer; s1,s2:string; Begin L1:=Length(s[i]); L2:=Length(s[j]); len:=-1; L:=1; While (L<l1) and (L<l2) do Begin s1:=copy(s[i],L1-l+1,l); s2:=copy(s[j],1,l); If s1=s2 then Begin len:=length(s[j])-l; exit End; L:=L+1; end; End; Procedure linktable; Var i,j:Integer; Begin For i:=1 to n do 生成二维表 For j:=1 to n do link[i,j]:=len(i,j) End;

约束条件之二是:每个单词最多使用 2 次,因此我们设置一个 used[1..Maxn] of 0..2,来记录每个单词的使用 情况。 4、写算法核心程序: Procedure solove(i,ans:Integer); I 为搜索深度,ans 为当前龙长度 Var c,b:Integer; Begin If best<ans then best:=ans; For c:=1 to n do 每个结点可以扩展出 n 个分支 For b:=1 to 2 do 每个单词可以使用两次 If (used[c]>0) and (link[i,c]>0) Then Begin used[c]:=used[c]-1; ans:=ans+link[i,c]; solove(c,ans); 扩展当前结点 used[c]:=used[c]+1; ans:=ans-link[i,c]; 恢复数据 End; End;

主程序调用: For i:=1 to n do If c=s[i][1] then solove(i,length(s[i]));
22

信息学奥赛培训讲稿

例 6、虫食算 所谓虫食算,就是原先的算式中有一部分被虫子啃掉了,需要我们根据剩下的数字来判定被啃掉的字母。来 看一个简单的例子: 43#98650#45 + 8468#6633 44445506978 其中#号代表被虫子啃掉的数字。根据算式,我们很容易判断:第一行的两个数字分别是 5 和 3,第二行的 数字是 5。 现在,我们对问题做两个限制: 首先,我们只考虑加法的虫食算。这里的加法是 N 进制加法,算式中三个数都有 N 位,允许有前导的 0。 其次,虫子把所有的数都啃光了,我们只知道哪些数字是相同的。我们将相同的数字用相同的字母表示,不 同的数字用不同的字母表示。如果这个算式是 N 进制的,我们就取英文字母表中的前 N 个大写字母来表示这个 算式中的 0 到 N-1 这 N 个不同的数字 (但是这 N 个字母并不一定顺序地代表 0 到 N-1) 输入数据保证 N 个字母 。 分别至少出现一次。 BADC + CBDA DCCC 上面的算式是一个 4 进制的算式。很显然,我们只要让 ABCD 分别代表 0123,便可以让这个式子成立了。 你的任务是,对于给定的 N 进制加法算式,求出 N 个不同的字母分别代表的数字,使得该加法算式成立。输入 数据保证有且仅有一组解。 【输入文件】 输入文件 alpha.in 包含 4 行。第一行有一个正整数 N(N <= 26) ,后面的 3 行每行有一个由大写字母组成的 字符串,分别代表两个加数以及和。这 3 个字符串左右两端都没有空格,从高位到低位,并且恰好有 N 位。 【输出文件】 输出文件 alpha.out 包含一行。在这一行中,应当包含唯一的那组解。解是这样表示的:输出 N 个数字,分 别表示 A,B,C……所代表的数字,相邻的两个数字用一个空格隔开,不能有多余的空格。 【样例输入】 5 ABCED BDACE EBBAA 【样例输出】 10342 【数据规模】 对于 30%的数据,保证有 N <= 10; 对于 50%的数据,保证有 N <= 15; 对于全部的数据,保证有 N <= 26。 算法分析: 1、 这个问题的实质是求出 0、1、2、?、n-1 的一个排列,使之符合问题的条件,因此用搜索算法。 数据定义: Const Maxn=26; Var used:Array[0..Maxn-1] of integer; ans:Array['A'..'Z'] of Integer; a,b,c:string[26]; n:Integer;

23

信息学奥赛培训讲稿

核心搜索程序: Procedure try(dep:Integer); 求排列程序 Var k:Integer; Begin If dep>n-1 Then If check Then Begin outans; halt End; For k:=0 to n-1 do Begin If used[k]=0 then Begin used[k]:=1;ans[chr(dep+65)]:=k; try(dep+1); used[k]:=0; End; End; End; 函数 check 判断是否是解,程序如下: Function check:Boolean; Var g,m,k:Integer; cc:Array[1..Maxn] Of Integer; Begin g:=0; check:=True; For k:=n downto 1 do Begin m:=ans[a[k]]+ans[b[k]]+g; 高精度加法 cc[k]:=m mod n; g:=m div n; End; If g>0 then Begin check:=False; exit End; 如果和的位数超过了 n,则不是解 For k:=1 to n do If ans[c[k]]<>cc[k] Then Begin check:=False; exit End; End;

2、但问题的规模较大,上面的程序能通过 3 个数据就非常不错,因此搜索的顺序和高效率的剪枝就成为关键: ①搜索顺序:我们可以根据加法式子中出现的字母顺序(从右向左)来搜索; 比如样例中按上面的搜索则其搜索顺序为:A、B、C、D、E 如果加以变化,则搜索顺序变成:D、E、A、C、B 这一点非常重要! ! ②剪枝:我们知道加法中任意同位数字相加 a+b=c,那么 a、b、c 必须符合条件: ●已知 a、b、c 的值,则应满足:(c=(a+b) mod n ) or (c=(a+b+1) mod n) ●已知 a、b 的值,则 c 值应满足:(c=(a+b) mod n ) or (c=(a+b+1) mod n) ●已知 b、c 的值,则 a 值应满足:(a=(c-b+n) mod n) or (a=(c-b+n+1) mod n) ●已知 a、c 的值,则 b 值应满足: (b=(c-a+n) mod n) or (b=(c-a+n+1) mod n) 这四个条件就成了强有力的剪枝条件 3、剪枝函数:
24

信息学奥赛培训讲稿

按上面的分析,剪枝函数如下: Function check1(i:Integer):Boolean; Var k,l,pp1,pp2:Integer; Begin check1:=True; For k:=n downto 1 do if (ans[a[k]]>=0) and (ans[b[k]]>=0) and (ans[c[k]]>=0) then Begin pp1:=(ans[a[k]]+ans[b[k]]) mod n; pp2:=(pp1+1) mod n; If not((ans[c[k]]=pp1)or(ans[c[k]]=pp2)) then Begin check1:=False; exit End; End; For k:=n downto 1 do if (ans[a[k]]>=0) and (ans[b[k]]>=0) and (ans[c[k]]=-1) then Begin pp1:=(ans[a[k]]+ans[b[k]]) mod n; pp2:=(pp1+1) mod n; If (used[pp1]=1) and (used[pp2]=1) then Begin check1:=False; exit End; End; For k:=n downto 1 do if (ans[a[k]]>=0) and (ans[b[k]]=-1) and (ans[c[k]]>=0) then Begin pp1:=(ans[c[k]]-ans[a[k]]+n) mod n; pp2:=ans[c[k]]-ans[a[k]]-1; If pp2<0 then pp2:=pp2+n; If (used[pp1]=1) and (used[pp2]=1) then Begin check1:=False; exit End; End; For k:=n downto 1 do if (ans[a[k]]=-1) and (ans[b[k]]>=0) and (ans[c[k]]>=0) then Begin pp1:=(ans[c[k]]-ans[b[k]]+n) mod n; pp2:=ans[c[k]]-ans[b[k]]-1; If pp2<0 then pp2:=pp2+n; If (used[pp1]=1) and (used[pp2]=1) then Begin check1:=False; exit End; End; End;

a+b=c

a+b=?

a+?=c

?+b=c

请同学们完善上面的程序,并在机器上通过!
25

信息学奥赛培训讲稿

四、广度优先搜索算法:
广度优先搜索算法类似树的按层遍历,从初始结点出发,扩展出第一层结点,检查目标结点是否在这些后 继结点中,若没有,在将地一层结点逐一扩展,得到第 2 层结点,并检查是否包含目标结点,若没有继续扩展第 2 层??,如此检查下去,直到找到目标结点为止。 按上面的叙述,我们知道先扩展出来的结点,必然要先扩展,这正好符合队列“先进先出”的特征,因此 广度优先搜索算法用队列来存储被扩展的结点,程序不需要使用“递归” 。 我们先来看看例 1 的分溶剂问题,假设需要找出最快的分法,我们采用广度优先搜索的过程描述如下: Const Maxd=100; Type node=Record a,x,y,parent:Integer; 每个结点的状态,a:瓶容器,x:x 杯,y:y 杯,parent:双亲结点 树的最大节点数

End; Var f:Array[1..Maxd] of node; 存储按层已经扩展出的结点。 (队列) 深度优先扩展结点过程 Procedure bfs; Var h,r,c:Integer; Begin h:=1; r:=1; While (r<Maxn-6) and (h<=r) do Begin For c:=1 to 6 do Begin If expandok(f[h].a,f[h].x,f[h].y,r,c) Then Begin r:=r+1; f[r].parent:=h End; If (f[r].a=(x+y) div 2) and (f[r].x=(x+y) div 2) Then Begin outans(r); halt End; End; h:=h+1; End; If (h>Maxn-6) or (h>r) Then writeln('No answer!'); End; 我们可以手工模拟上面程序的搜索过程。 剪枝函数 expandok(f[h].a,f[h].x,f[h].y,r,c)与前面深度优先搜索一样; 函数 outans(r)用递归;书写如下: Procedure outans(r:Integer); Begin If f[r].parent>0 Then outans(f[r].parent); write(f[r].a,',',f[r].x,',',f[r].y,'->'); End; 请同学写出完整程序,并在机器上调试通过。
26

广度优先搜索 h:队首,r:队尾;c 每个结点的分支枚举变 量 当未超过队列的容量并且对立队列不为空 时循环做下面的操作 f[h]可以扩展出 6 个子结点 如果第 c 个分支结点可以扩展出来 新扩展结点加如队尾 如果新扩展出来的结点是目标结点,则输出 解 对首 f[h]结点扩展完毕,则 h 下移一个 没有找到解的情况;

信息学奥赛培训讲稿

我们再来看两个例子: 例 7:在一个 n*m 的棋盘上,马的位置在 P 点,马在棋盘中只能向右跳,编程求出马从 P 点跳到 Q 点的最短步数。 (n 和 m 由键盘输入) 。

分析:要求最少的步数,用广度搜索算法(这是广度搜索相对于深度搜索的优点) ; (1)解答树:由于马只能向右跳,所以马有 4 个种跳法,因此解答树结点的分支数最大为 4,如下图: 马从初始结点(1,1)可以跳到(2,3) 和(3,2)两个位置,这里结点状态有马 的坐标构成。

束条件:马不能跳出棋盘。 (2)数据结构: Const Maxn=1000; 队列最大长度 mov:Array[1..4,1..2] of integer=((-2,1),(-1,2),(1,2),(2,1)); 四个移动方向的坐标变化 Type node=Record x,y,parent:Integer; 队列结点状态 End; Var q:Array[1..Maxn] of node; 队列 (3)算法的核心程序:

27

信息学奥赛培训讲稿

Procedure bfs; Var h,r,c,x,y:Integer; h:队首、r 队尾 find:boolean; Begin h:=1; r:=1; find:=false; While not(find) and (h<=r) do Begin For c:=1 to 4 do Begin x:=q[h].x+mov[c,1]; y:=q[h].y+mov[c,2]; 马跳后的坐标变化 如果没有跳出棋盘 入队尾 If(x>0) and (y>0) and (x<=n) and (y<=m)Then Begin r:=r+1; q[r].x:=x; q[r].y:=y; q[r].parent:=h End; If (q[r].x=n) and (q[r].y=m) then Begin outans(r); find:=true End; End; h:=h+1; End; End; 如果找到目标结点,输出解 每个结点可扩展出 4 个分支结点 当没找到目标结点且队列不为空

请同学们完善上面的程序,并在机器上调试通过。 请你用深度优先搜索算法解答这个问题,然后比较两种算法的不同。 至此,我们对两种基本的搜索算法讲述完毕,至于很多信息学奥赛辅导书中提到的分枝限界、双向搜索以及 A*算法, 他们都是建立在这两种搜索算法基础上的, 为提高搜索效率和加强剪枝功能而来得, 只要你心中有棵 “解 答树” ,理解这些算法是非常容易的事情。 “分枝限界”算法:顾名思义就是在扩展解答树结点的时候,通过对问题的深入分析,将结点的分枝数目尽 量减少,例如例题 4——数的划分,通过对分枝“上界”和“下界”的分析,从而达到缩小解空间——“解答树” 的规模的目的。这种算法还常常用于求最优问题,我们可以预先定义一个问题的最小(大)值不能超过(不小于) 每个值来达到剪枝的目的,例如习题 3(辅导书 209 页上的第一题) 。 “双向搜索”算法:顾名思义就是沿“初始结点向后”和 “目标结点向前”两个方向同时搜索,直到找到 一个“交会点”为止,这种算法适用于从初始结点到目标结点的搜索,常见于宽度搜索算法中。 “A*”算法:是一种带有某种智能的搜索算法,通常要设计一个估价函数(最有可能达到目标值的估价) , 在扩展结点的过程中, 常常依据估价函数的值选用最大的进行扩展, 同时在搜索过程中要不断地修改估价函数的 值。 估价函数的设计没有固定的之法, 根据不同的问题, 有不同的估价函数, 这必须建立在对问题的深入理解 (可 能解的预期和推断)和深厚的数学功底上。

28

信息学奥赛培训讲稿

---------------------------------------练习题---------------------------------------------题 1: [问题描述] 我们要求找出具有下列性质数的个数(包含输入的自然数 n): 先输入一个自然数 n(n≤1000), 然后对此自然数按照如下方法进行处理: 1.不作任何处理; 2.在它的左边加上一个自然数,但该自然数不能超过原数的一半; 3.加上数后,继续按此规则进行处理,直到不能再加自然数为止。 [样例]: 输入: 6 满足条件的数为 6 16 26 126 36 136 输出: 6 题 2: 1、选数 已知 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

(此部分不必输出)

题 3、见辅导书 209 页上的第一题

29

信息学奥赛培训讲稿

题 4、棋子移动问题: 有 n 个黑子和 n 个白子,初始状态摆成如下样子(图中 n=3):

按一定规则移动后可以走,要求成如下样子:

一定规则: 1、与空格邻近的棋子可走一步移入空格; 2、黑子可一跨过一个白子跳如空格,或白子可以跨过一个黑子跳如空格; 3、黑子不能跨过黑子,白子不能跨过白子进入空格。 请编写程序显示最快的移动步骤。

30


更多相关文档:

pascal算法合集

pascal算法合集_学科竞赛_高中教育_教育专区。pascal语言编写手打整理 NOIP free ...2 树形查找 二叉排序树:每个结点的值都大于其左子树任一结点的 值而小于其右...

必背经典算法(pascal)

必背经典算法(pascal)_电脑基础知识_IT/计算机_专业资料。一、数论算法 1.求...查找算法 1 折半查找 function binsearch(k:keytype):integer; var low,hig,...

pascal 基本算法

Pascal基础算法 8页 1下载券p​a​s​c​a​l​ ​基​本​...[t]:=time; end; 3. 广度优先搜索——BFS procedure BFS(t:longint); ...

基本算法(pascal版本)

Pascal算法与问题解决举... 72页 免费基​本​算​法​(​p​a​...在 C++中 可以用一个函数实现,不难,就是查找,不过 s 集合就要自己构建,可以...

pascal常用算法

pascal常用算法 隐藏>> 一、数论算法 1.求两数的最大公约数 function gcd(a,b:integer):integer; begin if b=0 then gcd:=a else gcd:=gcd (b,a mod...

NOIP(pascal)典型算法题集

NOIP(pascal)典型算法设计题集 NOIP(pascal)典型算法设计题集 典型第一章 算法...第二章 算法应用一、穷举搜索法穷举搜索法是穷举所有可能情形,并从中找出符合...

常用搜索算法

(本文所采用的算法描述语言为类 Pascal。) 第一部分 基本搜索算法 一、回溯算法 回溯算法是所有搜索算法中最为基本的一种算法, 其采用了一种“走不通就掉头”...

pascal-基本算法模块

pascal-基本算法模块_计算机软件及应用_IT/计算机_专业资料。基本算法模块 For ...(u,v,w); end; 2. 深度优先搜索——DFS var time:longint;——时间 ...

pascal贪心算法

pascal贪心算法_计算机软件及应用_IT/计算机_专业资料。pascal语言贪心算法详解 ...但是贪心算法并不是对所有的问题都能得到整体最 优解或最理想的近似解,与搜索...

pascal入门算法.doc

(ab+cd)=abcd 【算法搜索问题:1000—9999 关键是边枚举边分离高位、低位,...二、字符串的常用内部函数和过程 Turbo Pascal 提供了八个标准函数和标准过程,...
更多相关标签:
贪心算法 pascal | pascal算法 | spfa算法pascal | dijkstra算法pascal | kmp算法pascal | pascal语言与基础算法 | 迪杰斯特拉算法pascal | pascal高精度算法 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com