第一单元 算法概述.pptVIP

算法设计与分析 void ChessBoard(int tr, int tc, int dr, int dc, int size) { if (size==1) return； int t=tile++，// L型骨牌号 s=size／2； // 分割棋盘 //覆盖左上角子棋盘 if (dr tr +s dc tc +S) //特殊方格在此棋盘中 ChessBoard(tr，tc，dr，dc，S)； else{//此棋盘中无特殊方格 //用t号L型骨牌覆盖右下角 Board[tr+s-1][tc+s-1]=t； //覆盖其余方格 Chessboard(tr，tc，tr+s-1，tc+s-l，s)；} 算法设计与分析 //覆盖右上角子棋盘 if (dr = tr +s dc = tc +S) //特殊方格在此棋盘中 ChessBoard(tr，tc +s ，dr，dc，S)； else{//此棋盘中无特殊方格 //用t号骨牌覆盖左下角 Board[tr+s-1][tc+s]=t； //覆盖其余方格 Chessboard(tr，tc+s，tr+s-1，tc+s，s)；} ...... void outputBoard( int size) { for int i=0 ;isize ;i++){ for int j=0 ;jsize ;j++)； coutsetw(5)board [i][j]; coutendl ;}} 2.7 合并(merge)排序 算法思路:若n为1,算法终止;否则,将n个待排元素分割成k(k=2)个大致相等子集合A,B,对每一个子集合分别递归排序,再将排好序的子集归并为一个集合. 算法设计与分析 递归与分治 初始序列a [8] [4] [5] [6] [2] [1] [7] [3] 归并到b [4 8] [5 6] [1 2] [3 7] 复制到a [4 8] [5 6] [1 2] [3 7] 归并到b [4 5 6 8] [1 2 3 7] 复制到a [4 5 6 8] [1 2 3 7] 归并到b [1 2 3 4 5 6 7 8] 复制到a [1 2 3 4 5 6 7 8] 归并 [4，5，6，8] [1，2，3，7] 从两个序列的头部开始归并： 4与1比较，1被移到结果序列；4与2比较，2被移入结果序列 4与3比较，3被放入结果序列；4和7比较，4被放入结果序列, 5和7比较...， 例如 二路归并 问题:将n个元素排成非递减顺序。 temlplate class type void MergeSort(Type a[], int left, int right) { if (1eft right) //至少有2个元素 int i = (left + right ) /2; //取中点 MergeSort(a, 1eft, i)； MergeSort(a, i+1, right)； Merge(a, b, 1eft, i, right)；//从a合并到数组b copy(a, b, left, right);//复制回数组a } } T(n)= d n=1 T(n)= 2T(n/2)+cn 得: T(n)=?(nlogn) 分析: 算法设计与分析 递归与分治 合并排序 算法如下 templateclass T void merge