logo资料库

C++递归与分治算法解的Red and Black，分形（Fractal）以及Rank the Languages问题详解.ppt

发布时间：2022-05-29 发布人：admin 分类：说明书 资料大小：2.09M 资料格式：ppt 举报 版权申诉
第1页 / 共47页
第2页 / 共47页
第3页 / 共47页
第4页 / 共47页
第5页 / 共47页
第6页 / 共47页
第7页 / 共47页
第8页 / 共47页
资料共47页，剩余部分请下载后查看
     1．递归  递归：一个函数直接或者间接的调用自己。采用递归求解 问题的步骤：  （1）建立问题的递归关系（原先的问题是否能分解成性 质相同、规模较小的子问题），  （2）确定递归边界，也就是递归的出口（在问题分解到 一定小的规模时，有已知解），  （3）设计递推函数，  （4）编程实现并调试。  曾经学过的实例：整数划分问题、Hanoi塔问题。
     2．分治  分治法的基本思想是将一个规模为n的问题分解为k个规模 较小的子问题，这些子问题互相独立且与原问题相同。递 归地解这些子问题，然后将各个子问题的解合并得到原问 题的解。能采用分治法求解的问题，一般具有如下特征：  （1）当问题规模小到一定程序时，可以很容易解决；  （2）分解之后的若干个子问题都是互相独立的，和原问 题性质相同，只是规模小了；  （3）分解所得的各个子问题的解能够合并成原问题的解。
     采用分治法解题的基本步骤如下：  （1）分解：将原问题分解成若干个规模较小、互相独立 且与原问题形式相同的子问题；  （2）求解：若子问题规模较小而容易求解则对其求解， 否则递归求解各个子问题；  （3）合并：将各个子问题的解合并成原问题的解。  曾经学过的实例：归并排序、快速排序、L型骨牌的棋盘 覆盖问题、线性时间选择问题、平面最接近点对问题、循 环赛日程安排问题。
    过n0时，问题已容易解出*/  分治法的一般的算法设计模式如下：  divide_and_conquer(P)  {  if(|P|<=n0) adhoc(P); /*表示当问题P的规模不超  divide P into smaller subinstances P1,P2,...,Pk;  for(i=1; i<=k; i++)  yi=divide_and_conquer(Pi);  return merge(y1,...,yk); //合并子算法  }
     其中，|P|表示问题P的规模。n0为一阀值，表示当问题P 的规模不超过n0时，问题已容易解出，不必再继续分解。 adhoc(P)是该分治法中的基本子算法，用于直接解小规 模的问题P。当P的规模不超过n0时，直接算法adhoc(P) 求解。算法merge(y1,y2,...,yk)是该分治法中的合并子 算法，用于将P的子问题P1,P2,...,Pk的解y1,y2,...,yk合 并为P的解。  在用分治法设计算法时，最好使子问题的规模大致相同。 即将一个问题分成大小相等的k个子问题的处理方法是行 之有效的。许多问题可以取k=2。这种使子问题规模大致 相等的做法是出自一种平衡(banlancing)子问题的思想。
     从分治法的一般设计模式可以看出，用它设计出的算法一 般是递归算法。因此，分治法的计算效率通常可以用递归 方程来进行分析。一个分治法将规模为n的问题分成m个 规模为n/m的子问题，其中k(k<=m)个子问题需要求解。 为方便起见，设分解阀值n0=1，且adhoc解规模为1的 问题耗费1个单位时间。另外再设将原问题分解为k个问 题，用merge将k个子问题的解合并为原问题的解需用f(n) 个单位时间。如果用T(n)表示该分治法 divide_and_conquer(P)解规模为|P|=n的问题所需的计 算时间，则有： )( nT  O / )( nfmn )1( )  n n   1 1 kT (   
     通常可以用展开递归式的方法来解这类递归方程，反复代 入求解得： )( nT  n log km  1  mnfk ( / j j ) log nm  j  0  递归方程及其解只给出n等于m的方幂时T(n)的值，但是 如果T(n)足够平滑，由n等于m的方幂时T(n)的值估计 T(n)的增长速度。通常，可以假定T(n)单调上升。另一个 需要注意的问题是，在分析分治法的计算效率是，通常得 到的是递归不等式：    O / mn )1( )  )( nT )( nf   n n n n kT (  0 0  在讨论最坏情况下的计算时间复杂度，用等号(=)还是用 小于等于号(<=)是没有本质区别的。
     一个大小为W*H的矩形房间内，地上铺了红色与黑色两 种正方形的瓷砖，瓷砖大小为1*1，初始时刻，你站在一 个黑色瓷砖上，只能向上下左右四个方向相邻的黑色瓷砖 移动。给出房间的描述和你的初始位置，用“#”表示红 色瓷砖，用“.”表示黑色瓷砖块数，用字符“@”表示初 始时你所在的黑色瓷砖，求出你所能到达的黑色瓷砖块数。  输入：第一行给出两个整数W和H分别表示地面的长度和 宽度，接下来有W行，每一行有H列，其中“#”表示红 色瓷砖，“.”表示黑色瓷砖块数， “@”表示初始时你 所在的黑色瓷砖。最后一行0 0表示输入结束。  输出：一个整数，表示你所能到达的黑色瓷砖块数。
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料