递归与分治法.ppt

减常量因子 假币问题 折半查找 插值查找 二叉查找树的查找和插入 递归与分治法 void InOrder（BiTree root）/* 中序遍历二叉树的非递归算法 */ { InitStack (S);  p=root; while(p! =NULL || !IsEmpty(S)) { if (p! =NULL) /* 根指针进栈， 遍历左子树 */ Push(S, p);  p=p-LChild;  } else { /*根指针退栈， 访问根结点， 遍历右子树*/ Pop(S, p); Visit(p-data);  p=p-RChild;  } } } 假设n= 8。这个袋子被平分为各有4个金块的两个袋子A和B。为了在A中找出最重和最轻的金块，A中的4个金块被分成两组A1和A2。每一组有两个金块，可以用一次比较在A中找出较重的金块HA1和较轻的金块LA1。经过另外一次比较，又能找出HA 2和LA 2。现在通过比较HA1和HA2，能找出HA；通过LA 1和LA2的比较找出LA。这样，通过4次比较可以找到HA 和LA。同样需要另外4次比较来确定HB 和LB。通过比较HA 和HB（LA 和LB），就能找出所有金块中最重和最轻的。因此，当n= 8时，这种分而治之的方法需要1 0次比较。 为了简便，假设n是2的幂。当n= 2时，c(n) = 1。对于较大的n，c(n) = 2c(n/ 2 ) + 2。 Example: Find 9 3 5 7 8 9 12 15 Example: Find 9 3 5 7 8 9 12 15 Example: Find 9 3 5 7 8 9 12 15 Example: Find 9 3 5 7 8 9 12 15 Strassen矩阵乘法 棋盘覆盖 合并排序 Solve T(n) = 2T(n/2) + cn, where c 0 is constant. cn cn cn/2 cn/2 cn h = lg n T(n/4) T(n/4) T(n/4) T(n/4) cn Θ(n) Θ(1) Θ(n lg n) 线性时间选择 最接近点对问题 public void chessBoard(int tr, int tc, int dr, int dc, int size) {//tr棋盘左上角方格的行号，tc棋盘左上角方格的列号 //dr特殊方格所在的行号；dc特殊方格所在的列号 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-1, s);} // 覆盖右上角子棋盘 if (dr tr + s dc = tc + s) // 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else {// 此棋盘中无特殊方格 // 用 t 号L型骨牌覆盖左下角 board[tr + s - 1][tc + s] = t; //