2、递归和分治策略.pptVIP

分治算法;将要求解的较大规模的问题分割成k个更小规模的子问题。;对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。;将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。;递归的概念;例1 阶乘函数 阶乘函数可递归地定义为：;递归地计算如下： int factorial(int n) { if (n == 0) return 1; return n*factorial(n-1); };例2 Fibonacci数列 无穷数列1，1，2，3，5，8，13，21，34，55，…，被称为Fibonacci数列。它可以递归地定义为： ;;前2例中的函数都可以找到相应的非递归方式定义：;例3 Ackerman函数 当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。 Ackerman函数A(n，m)定义如下： ; A(n，m)的自变量m的每一个值都定义了一个单变量函数： M=0时，A(n,0)=n+2 M=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*n M=2时，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)= 2^n 。 M=3时，类似的可以推出A(n,3)= M=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。 ;例4 Hanoi塔问题 设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。;在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题。 ;例4 Hanoi塔问题;递归小结;递归小结;分治法的适用条件;二分有哪些信誉好的足球投注网站技术;二分有哪些信誉好的足球投注网站技术;棋盘覆盖;当k0时，将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘(a)所示。 特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。 ; 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-1, s);} // 覆盖右上角子棋盘 if (dr tr + s dc = tc + s) // 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else {// 此棋盘中无特殊方格 // 用 t 号L型骨牌覆盖左下角 ;上述算法中，数组board表示棋盘。board[0][0] 是棋盘左上角方格。Title是全局变量，用来表示 L型骨牌的编号，初始值为0，其它参数： tr:棋盘左上角方格的行号 tc:棋盘左上角方格的列号 dr:特殊方格所在的行号 dc:特殊方格所在的列号 size:棋盘规格2k*2k ;循环赛日程表; void table(int k, int a[][]) { int n=1; for (int i=1;i=k;i++) n=n*2; for (int i=1;i=n;i++) a[1][i]=i; int m=1; for(int s=1;s=k;