pascal的深度搜索(包括介绍,例题)
深度优先搜索一、概念深度优先搜索是在图运算中最常用的一种算法。它遵循的搜索策略是尽可能“深”地搜索图,即沿纵深方向搜索图。在深度优先搜索中,对于最新发现的节点,如果它还有以此为起点而未搜索的边,则沿此边继续搜索下去。 当节点v的所有边都已被搜索过,则回溯到与节点v相邻的上层节点,反复回溯,直到所有的节点都被遍历为止。二、图的深度优先搜索图可以分为无向图和有向图。无向图的深度优先搜索遍历过程如下:首先从图G=(V,E)中的某一顶点V0出发,访问任意一个和V0邻接的顶点W1,再从W1出发,访问和W1邻接但又没有被访问过的任意一个顶点W2,然后,从W2出发进行如上的访问。 重复这个过程,直到...全部
深度优先搜索一、概念深度优先搜索是在图运算中最常用的一种算法。它遵循的搜索策略是尽可能“深”地搜索图,即沿纵深方向搜索图。在深度优先搜索中,对于最新发现的节点,如果它还有以此为起点而未搜索的边,则沿此边继续搜索下去。
当节点v的所有边都已被搜索过,则回溯到与节点v相邻的上层节点,反复回溯,直到所有的节点都被遍历为止。二、图的深度优先搜索图可以分为无向图和有向图。无向图的深度优先搜索遍历过程如下:首先从图G=(V,E)中的某一顶点V0出发,访问任意一个和V0邻接的顶点W1,再从W1出发,访问和W1邻接但又没有被访问过的任意一个顶点W2,然后,从W2出发进行如上的访问。
重复这个过程,直到某一个顶点的所有邻接点都被访问过时,然后退回到尚未被访问过的邻接顶点,再从该顶点出发,重复上述的搜索过程,直到所有的被访问的顶点的邻接点都被访问过为止,这时搜索过程结束。图的深度优先搜索的特点是尽可能先对纵深方向进行搜索,整个搜索过程是递归定义的,它的遍历类似于树的前序遍历。
如上面图所示为一个无向图,根据深度优先搜索法遍历的过程如下:以编号为1的顶点为起点,和1邻接的顶点有2,4,5三个顶点。选其中的顶点2进行访问,而顶点2的尚未被访问过的邻接点有3,4两个,任意选其中的一个顶点4进行访问,而和顶点4相邻但尚未被访问过的邻接点有3,5两个,选其中的顶点3进行访问,而顶点3的尚未被访问过的邻接点只有顶点5,接着便访问顶点5。
在访问顶点5之后,与顶点5邻接但尚未被访问过的顶点已没有了,即此时顶点5的邻接点均已访问过,这时退回到上一顶点3,但顶点3 所有邻接点都已被访问过,所以再退回到上一顶点4,顶点4也一样,其邻接点均被访问过,故此再退回上一顶点2,而顶点2邻接点也均被访问过,所以再退回上一顶点,由于此时顶点1的所有邻接点也都被访问过,而且此时已退回到了出发点,故此整个搜索过程便结束。
上述搜索各顶点顺序为:12435,这里以深度搜索访问各顶点的顺序不是唯一的,可以有多种访问顺序,如:14235,15423等,都是由深度搜索遍历的结果。对于有向图的深度优先搜索,其方法和无向图的一样,如下图所示的有向图,对其进行深度优先搜索,其过程如下:从顶点V1出发,先选V2进行访问,和V2邻接但尚未被访问过的顶点只有V3一个,则访问V3,而和V3邻接的且又没有被访问过的顶点只有V6,访问顶点V6,到V6之后,没有顶点和V6邻接,则退回V3,而V3也没有邻接点了,再退到V2,V2也没有邻接点,则再退到尚有邻接点没有被访问过的顶点V1去。
此时和V1邻接而又没有被访问过的顶点有V4,V5两个,选V4进行访问,而V4的邻接点只有V3一个,且V3已经访问过,所以,退回V1,再选V5进行访问,V5只有一个邻接的且没有被访问过的顶点V7,即访问V7,访问V7之后,与V7邻接的有V3和V6,但这两个顶点已被访问过,所以,回退到V5,V5的邻接点均已访问过,故再退到V1,此时V1的所有邻接点都已访问过,且V1已是出发点,故搜索过程结束。
其访问各顶点的顺序为:1236457。选数(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(2)算法解析本题动态规划无从下手,也无数学公式可寻,看来只能搜索(组合的生成算法),其实1>=n>=20这个约束条件也暗示我们本题搜索是有希望的,组合的生成可用简单的DFS来实现,既搜索这k个整数在原数列中的位置,由于组合不同于排列,与这k个数的排列顺序无关,所以我们可以令a[I]>a[I 1](a[I]表示第I个数在原数列中的位置),这个组合生成算法的复杂度大约为C(n,k),下面给出递归搜索算法的框架:Proc Search(dep) Beginfor i >- a[dep - 1] 1 to N - (M - dep) do1:a[dep] >- i2:S >- S x[i]3:if dep > k then Search(dep 1) else 判断素数4:S >- S - x[i] End接下来的问题就是判断素数,判断一个整数P(P=sqrt(P))是P的约数,如果不存在,该数就为素数,由于在此题中1>=xi>=5000000,n>=20,所以要判断的数P不会超过100000000,sqrt(p)>=10000,因此,为了加快速度,我们可以用筛选法将2…10000之间的素数保存到一个数组里(共1229个),这样速度估计将提高5~6倍。
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; endend;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) endend;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]) endend;begin assign(input,'xunum。
in'); reset(input); assign(output,'xunum。
out'); rewrite(output); Readln(N, M); for i := 1 to N do Read(x[i]); ans := 0; S := 0; Get_Prime; Search(1, 0); Writeln(ans); close(input); close(output);end。收起