资源描述：
《深度优先搜索算法_pascal》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、深度优先搜索算法深度优先搜索法有两大基本特点:1．对已产生的结点按深度排序，深度大的先得到扩展，即先产生它的子结点； 2．深度大的结点是后产生的，但先得到扩展，即“后产生先扩展”。因此用堆栈作为该算法的主要数据结构，存储产生的结点，先把产生的数入栈，产生栈顶（即深度最大的元素）子结点，子结点产生以后，出栈，再产生栈顶子结点。一．递归算法： 递归过程为：procedureTRY(i); Forr:=1tomaxrdo(maxr是产生式规则数)beginIf子结点MR符合条件THENbegin产生的子结点MR压入栈；IF子结点MR是目标结点THEN输出ELSETRY（I+1）;栈顶元素出栈（删去M
2、R）；end;end;{**********main**********} programDFS;初始栈；TRY（1）；Forr:=1tomaxrdo子结点mr符合条件Y产生的子结点mr入栈输出Try(I+1)栈顶元素出栈（删去mr）N子结点mr是目标结点NYTry(I)二．非递归算法programDFS(dep);dep:=0; repeatdep:=dep+1;j:=0;p:=false;repeatj:=j+1;if子结点mr符合条件then产生子结点mr并将其记录if子结点是目标then输出并出栈(更新j) elsep:=true;else ifj>maxjthen回溯elsep:=f
3、alse; untilp=true; untildep=0;其中回溯过程如下：procedurebacktracking;dep:=dep-1; ifdep>0then取回栈顶元素elsep:=true;Dep:=0Dep:=dep+1j:=0;p:=false;j:=j+1;产生子节点MR并记录回溯P:=false输出并出栈P:=trueUntilp=falseUntildep=0YNMr符合条件子节点是目标YNYNJ>=maxj如图：A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如图的C点），该马所在的点和所有串跳跃一步可达的点称
4、为对方马的控制点。例如图中C点上的马可以控制9个点（图中的P1，P2，…，P8和C）。卒不能通过对方马的控制点。棋盘用坐标表示，A点（0，0）、B点（n,m）（n,m为不超过20的整数，并由键盘输入），同样马的位置坐标是需要给出的（约定：C<>A,同时C<>B）。现在要求你计算出卒从A点能够到达B点的路径的条数。A12345678Y1P5P42P6P33马4P7P2XP8P1B(4,8)数据结构：卒移动方向mov[1..2,1..2]12马控制范围move[0..8,1..2]0123456780110002112-12-21-2-1-1-21-22-1现有n个数字(n<=200),要求把这n
5、个数字划分成K（K能整除N，设M＝N/K)个集合S1，S2，S3…Sk,，每个集合均有M个数字，集合Si中的数字按某种次序串接，构成一个正整数Li（i=1,2,3,…,k),问怎样划分和排列集合S1，S2，S3…Sk,，使得L1：L2：L3：…：Lk＝,1：2：3：…：k.INPUT.TXT1234567893OUTPUT.TXT192384576219438657273546819327654981用数组B[0..9]来存储N个数字存储规则：B[0]存储N个数字中0的个数B[1]存储N个数字中1的个数B[2]存储N个数字中2的个数……………………B[8]存储N个数字中8的个数B[9]存储N个
6、数字中9的个数Input.txtB[I]n个数据K值havetrueMade(1)YNhave输出无解信息ii0to9B[i]>0B[I]:=B[I]-1YNS0YNexit输出结果到OUTPUTHave:=falsePass检验第2组－－第K组数是否合格，如合格则输出其中bb是b的拷贝将Z[1]—Z[m]中数字计算出值赋给Ei2tokjMdownto1gmod10ggdiv10bb[h]:=bb[h]-1Ifg>0thenexit骑士游历问题
7、：在6*6的国际象棋上的某一位置上放置一“马”，然后采用象棋中“马走日字”的规则，要求该“马”能不重复地走完36个格子，试编写程序解决这个问题。3241X,Y5867-1-2-2-1122121-1-2-2-112数组A设置8个方向变化Board[1,1]1try(1,1,2,q)YNq输出无解信息初始化board输出结果Try(x,y,i,q)表示对（x,y）位置作为第i步向前试探的过程。若试探
