启发式规则,分治法,递归,汉诺塔,排序算法_39953.ppt

通用分治递推式 问题规模为n的实例被划分为 b个规模为n/b的实例,其中a个实例需要求解,假设n是b的幂 T(n)=aT(n/b)+f(n) 主定理 如果在递推式中f(n)∈?(nd），其中d≥0 汉诺塔问题可以通过以下三个步骤实现： （1）将塔A上的n-1个碟子借助塔C先移到塔B上。 （2）把塔A上剩下的一个碟子移到塔C上。 （3）将n-1个碟子从塔B借助塔A移到塔C上。 显然，这是一个递归求解的过程 // 覆盖右上角子棋盘 if (dr tr + s dc = tc + s) // 特殊方格在右上角子棋盘中 ChessBoard(tr, tc+s, dr, dc, s); //递归处理子棋盘 else { // 用 t 号L型骨牌覆盖左下角，再递归处理子棋盘 board[tr + s - 1][tc + s] = t; ChessBoard(tr, tc+s, tr+s-1, tc+s, s); } // 覆盖左下角子棋盘 if (dr = tr + s dc tc + s) // 特殊方格在左下角子棋盘中 ChessBoard(tr+s, tc, dr, dc, s); //递归处理子棋盘 else { // 用 t 号L型骨牌覆盖右上角，再递归处理子棋盘 board[tr + s][tc + s - 1] = t; ChessBoard(tr+s, tc, tr+s, tc+s-1, s); } // 覆盖右下角子棋盘 if (dr = tr + s dc = tc + s) // 特殊方格在右下角子棋盘中 ChessBoard(tr+s, tc+s, dr, dc, s); //递归处理子棋盘 else { // 用 t 号L型骨牌覆盖左上角，再递归处理子棋盘 board[tr + s][tc + s] = t; ChessBoard(tr+s, tc+s, tr+s, tc+s, s); } } 按照分治的策略，可将所有参赛的选手分为两部分，n＝2k个选手的比赛日程表就可以通过为n/2＝2k-1个选手设计的比赛日程表来决定。递归地执行这种分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单：只要让这2个选手进行比赛就可以了。 temp=n; n=n*2; //填左下角元素 for (i=temp+1; i=n; i++ ) for (j=1; j=temp; j++) a[i][j]=a[i-temp][j]+temp; //左下角元素和左上角元素的对应关系 //填右上角元素 for (i=1; i=temp; i++) for (j=temp+1; j=n; j++) a[i][j]=a[i+temp][(j+temp)% n]; //填右下角元素 for (i=temp+1; i=n; i++) for (j=temp+1; j=n; j++) a[i][j]=a[i-temp][j-temp]; } } 用分治法解决最近对问题，很自然的想法就是将集合S分成两个子集 S1和 S2，每个子集中有n/2个点。然后在每个子集中递归地求其最接近的点对，在求出每个子集的最接近点对后，在合并步中，如果集合 S 中最接近的两个点都在子集 S1或 S2中，则问题很容易解决，如果这两个点分别在 S1和 S2中，问题就比较复杂了。 算法4.5——一次划分 int Partition(int r[ ], int first, int end) { i=first; j=end; //初始化 while (ij) { while (ij r[i]= r[j]) j--； //右侧扫描 if (ij) { r[i]←→r[j