ACM算法设计--DFS&&BFS

2020/4/171DFS&&BFSACM算法设计之搜索篇2020/4/1722DFS算法HALIFBCDEJGKS2020/4/173深度优先搜索VS回溯BACEDGFABDEGCF先序遍历序列：ABDEGCF调用返回（回溯）2020/4/174二叉树的先序遍历算法voidPreorder(BiTreeroot){if(root==NULL)return；else{访问root指向的根结点；Preorder(root-Lchild);Preorder(root-Rchild);}}BACEDGFABDEGCF2020/4/175回溯法在程序设计中，有一类问题，其要求是求解一组解、求全部解或求最优解，这种问题的求解不是按照确定的计算法则进行，而是利用试探和回溯的搜索技术求解。回溯法的求解过程实质上是先序遍历一棵“状态树”的过程，只是这棵树不是预先建立的，而是隐含在遍历的过程中。2020/4/176回溯基本结构判断是否到了底层，是则返回上一层;否则对各种可能情况进行循环：ifpossible加入标记;进入下一层;//递归调用清除标记;elseif所有情况列举完毕，则返回上一层这个结构是普遍适用的。任何递归的DFS程序都能套进去。2020/4/177例1:求幂集例：求含有n个元素的集合的幂集如：A={1,2,3}如：{}}},3{},2{},3,2{},1{},3,1{},2,1{},3,2,1{{)A(8{1,2,3}{1,2}{1,3}{1}{2}{2,3}{}}},3{},2{},3,2{},1{},3,1{},2,1{},3,2,1{{)A(元素1元素2元素2取舍取舍取舍元素3元素3元素3元素3{}{3}取舍取舍取舍取舍{1}{}{1,2}{1}{2}{}2020/4/179求解算法voidPowerSet(inti,intn){//求含有n个元素的集合A的幂集。进入函数时已对A中的前i-1个元素作了取舍处理，现从第i个元素起进行取舍处理。//若in，则求得幂集的一个元素。//初始调用:PowerSet(1,n)if(in)输出幂集的一个元素；else{取第i个元素；PowerSet(i+1,n);舍第i个元素；PowerSet(i+1,n);}//if}//PowerSet2020/4/1710程序代码#includeiostream.hconstintMaxn=32;boolflag[Maxn];voidPowerSet(inti,intn){intj;if(in){//输出幂集的一个元素；for(j=1;j=n;j++)if(flag[j]==true)coutj;coutendl;}else{flag[i]=true;//取第i个元素；PowerSet(i+1,n);flag[i]=false;//不取第i个元素；PowerSet(i+1,n);}}//PowerSetvoidmain(){inti;for(i=0;iMaxn;i++)flag[i]=false;PowerSet(1,5);}2020/4/1711例2：n皇后问题●●●●将n个皇后放在n×n的棋盘中，要求皇后间不能相互攻击。所谓攻击是指两个皇后在同一行、同一列或在同一条斜线上，求所有的合法布局。合法●●●●非法布局2020/4/1712四皇后问题●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●2020/4/1713求解算法voidTrial(inti,intn){//进入本函数时，在n*n棋盘的前i-1行已经放置了互不攻击的i-1个皇后。//现从第i行起继续为后续棋子选择合适的位置if(in)输出棋盘的当前布局;elsefor(j=1;j=n;j++){//在第i行的每一列上进行试探在第i行、第j列上放一个皇后；if(当前布局合法)Trial(i+1,n);移走第i行、第j列上的皇后；}//for}//Tiral2020/4/1714N皇后问题•给n*n的棋盘，问皇后的摆放方法(方法不唯一)，输出的第i个数字表示第i行皇后放在第几列。一、当nmod6!=2且nmod6!=3时，有一个解为：2,4,6,8,...,n,1,3,5,7,...,n-1(n为偶数)2,4,6,8,...,n-1,1,3,5,7,...,n(n为奇数)(上面序列第i个数为ai，表示在第i行ai列放一个皇后)2020/4/1715N皇后问题二、当nmod6==2或nmod6==3时，(当n为偶数,k=n/2；当n为奇数,k=(n-1)/2)k,k+2,k+4,...,n,2,4,...,k-2,k+3,k+5,...,n-1,1,3,5,...,k+1（k偶n偶）k,k+2,k+4,...,n-1,2,4,...,k-2,k+3,k+5,...,n-2,1,3,5,...,k+1,n(k偶,n奇)k,k+2,k+4,...,n-1,1,3,5,...,k-2,k+3,...,n,2,4,...,k+1(k奇,n偶)k,k+2,k+4,...,n-2,1,3,5,...,k-2,k+3,...,n-1,2,4,...,k+1,n(k奇,n奇)2020/4/1716例3：PrimeRingProblem•n个数排成一个圆环，要求相邻两个数的和为素数。输入：68输出：Case1:143256165234Case2:123856741258347614765832167438522020/4/1717PrimeRingProblem位置11位置2位置3位置4位置5位置62020/4/1718PrimeRingProblem位置112位置2位置3位置4位置5位置62020/4/1719PrimeRingProblem位置1123位置2位置3位置4位置5位置62020/4/1720PrimeRingProblem位置11234位置2位置3位置4位置5位置62020/4/1721PrimeRingProblem位置112345位置2位置3位置4位置5位置62020/4/1722PrimeRingProblem位置112346位置2位置3位置4位置5位置62020/4/1723PrimeRingProblem位置11234位置2位置3位置4位置5位置62020/4/1724PrimeRingProblem位置11235位置2位置3位置4位置5位置62020/4/1725PrimeRingProblem位置11236位置2位置3位置4位置5位置62020/4/1726PrimeRingProblem位置1123位置2位置3位置4位置5位置62020/4/1727PrimeRingProblem位置1124位置2位置3位置4位置5位置62020/4/1728PrimeRingProblem位置1125位置2位置3位置4位置5位置62020/4/1729PrimeRingProblem位置1125位置2位置3位置4位置5位置62020/4/1730PrimeRingProblem位置1125位置2位置3位置4位置5位置662020/4/1731PrimeRingProblem位置11253位置2位置3位置4位置5位置662020/4/1732PrimeRingProblem位置11253位置2位置3位置4位置5位置662020/4/1733PrimeRingProblem位置11254位置2位置3位置4位置5位置66下一步：回溯2020/4/1734PrimeRingProblem位置1125位置2位置3位置4位置5位置662020/4/1735PrimeRingProblem位置1125位置2位置3位置4位置5位置62020/4/1736PrimeRingProblem位置1126位置2位置3位置4位置5位置62020/4/1737PrimeRingProblem位置112位置2位置3位置4位置5位置62020/4/1738PrimeRingProblem位置113位置2位置3位置4位置5位置62020/4/1739PrimeRingProblem位置114位置2位置3位置4位置5位置62020/4/1740PrimeRingProblem位置114位置2位置3位置4位置5位置62020/4/1741PrimeRingProblem位置1143位置2位置3位置4位置5位置62020/4/1742PrimeRingProblem位置1143位置2位置3位置4位置5位置62020/4/1743PrimeRingProblem位置1143位置2位置3位置4位置5位置622020/4/1744PrimeRingProblem位置1143位置2位置3位置4位置5位置622020/4/1745PrimeRingProblem位置11435位置2位置3位置4位置5位置622020/4/1746PrimeRingProblem位置11435位置2位置3位置4位置5位置622020/4/1747PrimeRingProblem位置114365位置2位置3位置4位置5位置622020/4/1748PrimeRingProblem位置114365位置2位置3位置4位置5位置622020/4/1749•环的第1个位置固定放1，其余的n-1个位置放数2~n。•boolplay(位置k){if(kn){输出;returntrue;}for(inti=2;i=n;i++){if(i还没放进去，且(i+第(k-1)个数)是素数){将i放在位置k;标记i已放进去;if(play(位置”k+1”))returntrue;去除i已放进去的标记;//将i取出}//if}//forreturnfalse;}//play2020/4/1750程序代码intmain(){intn=0;inti;initial();//初始化in[1]=true;//放入数1result[1]=1;//位置0固定放1for(;cinN;){coutCase++n:\n;for(i=2;i=N;i++)in[i]=false;if(N%2==0)play(2);//从位置1开始，放入其余的数coutendl;}return0;}#definetrue1#definefalse0#includeiostream.hshortcan[21][21];shortin[21];//环中最多20个位置shortresult[21];//存放放入环中的数shortN;//环中实际位置数=202020/4/1751shortis_prime(intn){//判断n是否是素数，是则返回trueinti;for(i=2;in;i++)if(n%i==0)returnfalse;returntrue;}//is_primevoidinitial(){//判断1~20中任意一对数之和是否为素数，并保存结果inti,j;for(i=1;i21;i++){for(j=i;j21;j++)can[j][i]=can[i][j]=is_prime(i+j);}//for}//initialvoidoutput(){//按逆时针方向输出环中的数inti=1;for(;iN;i++)coutresult[i]'';coutresult[i]endl;}//output2020/4/1752voidplay(intk){//需要在位置k放入一个数inti;if(kN){//所有位置已经填充if(can[result[1]][result[N]])output();return;}for(i=2;i=N;i++){if(in[i])continue;//数i已经放入if(can[result[k-1]][i]){result[k]=i;//将数i放入位置kin[i]=true;//数字i已放入play(k