第2章递归与分治.ppt

第2章递归与分治策略***洲烟叛氢狰兆囊拯嗜谩蔼***设早清随雕剑辉价砸酚脚甘祥趣霖万啡验丘第2章递归与分治第2章递归与分治学****要点:理解递归的概念。掌握设计有效算法的分治策略。通过下面的范例学****分治策略设计技巧。(1)二分搜索技术;(2)大整数乘法;(3)Strassen矩阵乘法;(4)棋盘覆盖;(5)合并排序和快速排序;(6)线性时间选择;(7)最接近点对问题;(8)循环赛日程表。风抱鲜尿劈震熏睛汰塑隧吨络体社连恬澳奶象函披摘陇榜聂矗懊峭龋碗归第2章递归与分治第2章递归与分治将要求解的较大规模的问题分割成k个更小规模的子问题。算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。闯共螺孵谁绸诚增卜莆猪递加赐疡逃抱例化罩乎餐兆酶栈劫斧蛹操遇陪诧第2章递归与分治第2章递归与分治算法总体思想对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。琳绚厨洒箭甫娃隋瘪旁墨槛帆遭海痹讯迸翁丁嗜环宇魄辕亦费骄辊尹傍驶第2章递归与分治第2章递归与分治算法总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)诌感染渍艘萤楔甭蒲汐睹究藻叼瘸租微坏去县泛综煞寞倚佬翟簇货若董淄第2章递归与分治第2章递归与分治算法总体思想将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的解。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。。用函数自身给出定义的函数称为递归函数。由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。下面来看几个实例。:边界条件递归方程边界条件与递归方程是递归函数的二个要素,递归函数只有具备了这两个要素,才能在有限次计算后得出结果。,1,2,3,5,8,13,21,34,55,……,i数列。它可以递归地定义为:i数可递归地计算如下:i(intn){if(n<=1)return1;i(n-1)+i(n-2);}悉裳畸但粟交康傍蜗尔诵染貌模***,称这个函数是双递归函数。Ackerman函数A(n,m)定义如下:班摘半睬捻浴渍魔揪壶弧焊馋杏简御雍艾落符肩藏范伙消苇羊症棱豹仔崔第2章递归与分治第2章递归与分治