没有合适的资源？快使用搜索试试~ 我知道了~

文库首页开发技术其它C++递归与分治算法解的Red and Black，分形（Fractal）以及Rank the Languages问题详解

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

Black问题

Fractal问题

Rank

5星 · 超过95%的资源需积分: 10 16 下载量 42 浏览量 2010-09-08 17:45:25 上传评论收藏 2.09MB PPT 举报

温馨提示

试读

47页

这是用C++递归与分治算法编写的关于Red and Black问题 Fractal问题 Rank the Languages问题的文档（包括详解和完整代码）

资源推荐

资源详情

资源评论



1 ．递归



递归：一个函数直接或者间接的调用自己。采用递归求解

问题的步骤：



（ 1 ）建立问题的递归关系（原先的问题是否能分解成性

质相同、规模较小的子问题），



（ 2 ）确定递归边界，也就是递归的出口（在问题分解到

一定小的规模时，有已知解），



（ 3 ）设计递推函数，



（ 4 ）编程实现并调试。



曾经学过的实例：整数划分问题、 Hanoi 塔问题。



2 ．分治



分治法的基本思想是将一个规模为 n 的问题分解为 k 个规

模较小的子问题，这些子问题互相独立且与原问题相同。

递归地解这些子问题，然后将各个子问题的解合并得到原

问题的解。能采用分治法求解的问题，一般具有如下特征：



（ 1 ）当问题规模小到一定程序时，可以很容易解决；



（ 2 ）分解之后的若干个子问题都是互相独立的，和原问

题性质相同，只是规模小了；



（ 3 ）分解所得的各个子问题的解能够合并成原问题的解。



采用分治法解题的基本步骤如下：



（ 1 ）分解：将原问题分解成若干个规模较小、互相独立

且与原问题形式相同的子问题；



（ 2 ）求解：若子问题规模较小而容易求解则对其求解，

否则递归求解各个子问题；



（ 3 ）合并：将各个子问题的解合并成原问题的解。



曾经学过的实例：归并排序、快速排序、 L 型骨牌的棋盘

覆盖问题、线性时间选择问题、平面最接近点对问题、循

环赛日程安排问题。



分治法的一般的算法设计模式如下：



divide_and_conquer(P)



{



if(|P|<=n0) adhoc(P); /* 表示当问题 P 的规模不超

过 n0 时，问题已容易解出 */



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) 子问题的思

想。

剩余46页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

攻城狮7号

2013-05-18

例子分析到位，不错
hbhcliou

2012-12-01

分形算法的思想体现得很明确，有一定借鉴作用。

woailuo626

粉丝: 5
资源: 11

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

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

递归与分治算法

算法课程中的递归与分治算法程序

递归与分治 算法分析

计算机算法设计与分析的递归与分治策略

C++递归与分治法实现报告

递归与分治实验(二)

c++递归c++递归c++递归

算法思想——递归与分治

递归与分治算法解题报告.ppt

递归与分治算法的设计

算法分析与设计实验-实验一 递归与分治算法设计

NOIP普及讲座1-递归与分治(C++版).pdf

递归算法详解递归算法详解

c语言分治法求众数重数-五大常见算法策略之——递归与分治策略，算法数据结构

算法递归与分治

递归与分治策略 递归与分治策略

分形递归算法实现分叉树

递归与分治策略

递归和分治策略算法实现

win10环境下vscode运行opencv(C++)(解压即用)-1号包

虹软3.0人脸识别客户端（追踪，活体检测，人脸特征存储，人脸识别，人脸注册，人脸匹配）可离线断网部署 5000个免费key/年

c++入门，核心，提高讲义笔记

仿照Visionmaster，用C++、Qt编写的视觉软件

C++STL库常用库函数总结

c++小游戏 c++小游戏

mingw-w64-install.exe

C/C++中文帮助文档

我的世界简易版（C++编写，源代码+程序）

cmu 15445 2023spring project0

最新资源

递归与分治算法分析

算法分析与设计实验-实验一递归与分治算法设计

递归与分治策略递归与分治策略