第3章-常用经典算法概述(2.分治策略).ppt

*最后剩下的一格要么是真正残缺的，要么是为了和原问题相同已经覆盖上骨牌了******ChessBoard(tr,tc,dr,dc,size){ifsize=1return；t?tile+1，//L型骨牌号s?size／2；//分割棋盘//覆盖左上角子棋盘if(drtr+sdctc+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(drtr+sdc=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)}*//覆盖左下角子棋盘if(dr=tr+sdctc+S)//特殊方格在此棋盘中ChessBoard(tr+s，tc，dr，dc，s)；else{//此棋盘中无特殊方格//用t号骨牌覆盖右上角Board[tr+s][tc+s-1]=t；//覆盖其余方格Chessboard(tr+s，tc，tr+s，tc+s-1，s);}*//覆盖右下角子棋盘if(dr=tr+sdc=tc+s)//特殊方格在此棋盘中ChessBoard(tr+s，tc+s，dr，dc，s)；else{//此棋盘中无特殊方格//用t号骨牌覆盖左上角Board[tr+s][tc+s]=t；//覆盖其余方格Chessboard(tr+s，tc+s，tr+s，tc+s，s);}}*voidoutputBoard(intsize){forinti=0;isize;i++){forintj=0;jsize;j++)；coutsetw(5)board[i][j];coutendl;}}//输出覆盖情况*******一般来说，函数T(n)是平滑的；*******至多进行3?n/2?次数的比较是找出最大元和最小元的充分条件任何基于比较的找最大值和最小值的算法，其元素比较次数下界3n/2(向上取整)-2，所以分治法解是最优的，但是每次递归调用都需要保存i,j,fmax,fmin的值及返回地址*通常，在分析算法的复杂性时，加法和乘法当作基本运算，即执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处理速度的常数。?这个假定仅在硬件能对整数直接表示和处理时才合理。然而，*******O(n2),对递归算出的n/2的乘积进行合并成原问题的解需要4次加法8个规模为n/2的子问题***Hopcroft和Kerr已经证明(1971)，计算2个２×２矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算2×2矩阵的7次乘法这样的方法了。或许应当研究３×３或５×５矩阵的更好算法。***分治策略的基本思想二分查找算法寻找最大最小元素大整数乘法Strassen矩阵乘法棋盘覆盖问题（Trimino拼图）本节主要内容：2.分治策略（divide-a