数据结构-刘大有-第六章-递归1013教案资料.ppt

《数据结构-刘大有-第六章-递归1013教案资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构-刘大有-第六章-递归1013委员会问题的递归算法算法COMM(n,k)COMM1[递归出口]IFk>nTHENRETURN(0).ELSEIF(n=kORk=0)THENRETURN(1).COMM2[递归调用]RETURN(COMM(n-1,k)+COMM(n-1,k-1))▐递归的应用－－回溯(backtracking)寻找特定问题解的一种比较可靠的方法是首先列出所有候选解，然后依次检查每一个候选解，在检查完所有或部分候选解后，即可找到所需要的解。理论上，当候选解的数量有限并且通过检查

2、所有或部分候选解能够得到所需要的解的时候，上述方法是可行的。对候选解进行系统检查的方法有多种，其中回溯和分枝限界法是比较常用的两种。6.4.2回溯回溯法试图通过建立部分的解决方法来得到整个问题的解决方案。该算法可将一个局部的解决方法扩展到整个问题。如果从局部的解决方法肯定不能得到整个问题的解决方案，也就是说局部的解将导致走进死胡同，这时就要通过移除最近加入的部分将算法回退，并且尝试其他的方法。回溯的基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，

3、就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。回溯法解决的问题：货船装箱、背包、最大完备子图、旅行商和电路板排列迷宫老鼠问题2,12,22,31,11,21,33,13,23,3000011000111011000(1,1)(1,2)(1,3)失败，回溯到(1,2)(1,1)(2,1)(3,1)(3,2)(3,3)迷宫问题小型迷宫路口动作结果1(入口)正向走进到22左拐弯进到33右拐弯进到44(堵死)回溯退到33(堵死)回溯退到22正向走进到55(堵死)回溯退到2

4、2右拐弯进到66左拐弯进到7(出口)7643521例：n-皇后问题在国际象棋中，最强大的棋子是皇后，因为她能攻击她所在行、所在列内或沿对角方向的任何一个棋子。n-皇后问题要求在棋盘上放置n个皇后，使得没有哪个皇后能攻击其他的皇后。在回溯中，由于每个皇后都必须放置在不同的行中，所以n-皇后问题的解决方案可以表示为一个n元组(x1,…,xn)，这里的xi是把第i个皇后放在第i行的列数且1≤xi≤n.由于任何两个皇后都不能出现在同一列中，因此n元组(x1,…,xn)中没有两个元素是相同的。那么，应该如何判

5、断两个皇后是否在同一斜角线上呢？如果设想棋盘的方格像二维数组A(1:n,1:n)的下标那样标记，对于在同一条斜角线上的由左上方到右下方的每一个元素都有相同的“行列”值，同样，在同一条上的由右上方到左下方的每一个元素则有相同的“行+列”值。假设有两个皇后被放置在(i,j)和(k,l)位置上，那么根据以上所述，仅当ij＝kl或i+j＝k+l时，它们才在同一条斜角线上。将这两个等式分别变换成jl＝ik或jl＝ki因此，当且仅当

6、jl

7、＝

8、ik

9、时，两个皇后在同一条斜角线上，这里的

10、jl

11、

12、为jl的绝对值。n-皇后问题的解为一个n元组，使用一个大小为n的数组queenInRow来存储。其中queenInRow[k]表示第k行的第k个皇后所在列的位置。例如queenInRow[1]=7表示第一个皇后被放在第1行、第7列。假设已经将第k-1个皇后放入第k-1行中，接下来尝试将第k个皇后放入第k行的某一列。编写算法PLACE(k,i.result)，当第k个皇后能放置于第k行第i列则返回true；否则返回false。算法PLACE要测试两种情况，即queenInRow[k]是否不同于前面

13、queenInRow[1]，…，queenInRow[k1]的值以及在同一条斜角线上是否有别的皇后。算法PLACE(k,i.result)/*如果一个皇后能放在第k行第i列则返回true；否则返回false，结果保存在result中*/PLACE1[初始化]j←1.PLACE2[判定能否放置]WHILEj

14、RETURN(result).)j←j+1.)result←true.RETURN(result).▐算法NQUEENS(k)/*此算法使用递归算法求出在一个n×n的棋盘上放置n个皇后，使其不能互相攻击的所有可能位置*/NQUEENS1FORi=1TOnDO(PLACE(k,i.canPlace)./*此处能放这个皇后吗*/IFcanPlace=trueTHEN/*能放置*/(queenInRow[k]←i.IFk=nTHENPRINT(queenInRow)./*找