DFS 例题讲解.ppt

《DFS 例题讲解.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、作业中的两道题1398–square和2281–wordstack1398-squareGivenasetofsticksofvariouslengths,isitpossibletojointhemend-to-endtoformasquare?ThefirstlineofinputcontainsN,thenumberoftestcases.Eachtestcasebeginswithaninteger4≤M≤20,thenumberofsticks.Mintegersfollow;eachgivesthelengthofastick-anintegerbetween1and10,0

2、00.因为M最大为20，所以，如果用DFS还是可以接受的。1398-square由所有火柴棒的长度和，我们可以求出要组成正方形的边长。我们设边长为length。在搜索前，首先可以把边长为分数的，也就是火柴棒的长度和不能被4整除的，排除掉。其实问题可以转化为从M个数中挑出4组和为length的数。首先、从M个数中搜索出和为lenth的数。如果能搜到，则接着从剩余的数中，进行同样的搜索，依此类推，一共进行4段这样的搜索。如果某一段搜索失败，则回溯到上一段搜索。如果一直回溯到第一段的搜索，仍未能找到解，则说明无解。1398-square具体的搜索过程：将长度按从大到小排序。对应正方形的4条边，

3、进行4段同样的搜索。而且这4段搜索也是递归式的，就是说，当第一段边搜索到后，便递归进行下一段的搜索。由此可见，搜索过程中要用到的信息包括：1、当前是第几段。2、当前段还剩余的长度。3、搜索的起始位置。每段搜索的过程是相同的：因为到最后，所有的火柴棒都是会被用到的，所以，每当开始一个新段的搜索时，总是把剩余的第一个数放入，在这段的搜索过程中，它始终是放入状态。然后进入堆栈的下一层，试着放入下一个剩余的数，如果放入这个数后递归到下面未回溯回来，则说明已经找到最后答案，程序结束。如果得到回溯，那么把该数取出，同理再试着放入排在它后面的数。为什么需要‘’搜索的起始位置‘’？1398-square

4、搜索的起始位置很重要，它关系到每层递归可选的状态数，和程序运行时间紧密相连。起始位置就是，在每次进入递归函数的时候，应该从哪个位置的数开始试着放入，前面说到，如果这次递归要放入的是一个段的第一个数，这个数肯定是剩余的第一个数，而且这个数是不会被取出的，也就是说，这一层的可选状态只有一个，如果放入这个数之后，后面发现无法搜索到一个完整的边，那么说明剩余的数到达最终的目标，必须回溯到上一个段。如果这次递归要放入不是一个段的第一个数，那么它的起始位置肯定是在它上一层递归放入的数的后面，但是它前面可能还存在没有被放入的数，这些数就不用再试了吗？因为是对同一个段的搜索，所以，组成这个段的数被放入的

5、顺序是没有关系的。所以，如果一个数作为一个段的第一个数放入不合适，那么它作为第二个数或第三个数放入肯定也是不合适的。1398-square根据前面所分析，我们可以得出递归函数应该包括三个参数：当前是第几段。当前段还剩余的长度。搜索的起始位置。intdfs(intduan,intstart,intleft){...}intdfs(intduan,intstart,intleft){if(left==0){//如果left为0，开始新的一段if(duan==3)return1;//如果当前段为3，则程序结束for(start=0;in[start]&&start

6、到剩余数中第一个为放入数in[start]=1;//找到后标记放入if(dfs(duan+1,start+1,length-num[start]))return1;//开始该段的递归搜索in[start]=0;//如果未找到，则反标记，return0;//回溯到上一段}inti;if(start>=n)return0;//没有可搜索数，返回for(i=start;i

7、

8、num[i]>left)//i已放入或无法放入continue;if(i>0&&!in[i-1]&&num[i]==num[i-1])continue;//剪枝

9、操作in[i]=1;if(dfs(duan,i+1,left-num[i]))return1;in[i]=0;}return0;}2281-wordstackGivenacollectionofNwords,findanarrangementofthewordsthatdividesthemamongNlines,paddingthemwithleadingspacestomaximizethenumberofnon-spacech