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

分治算法综述.docx

需积分: 0 0 下载量 20 浏览量 2024-01-08 16:52:30 上传评论收藏 718KB DOCX 举报

温馨提示

试读

39页

该word文档包含分治算法的思想，适用于用分治算法解决的问题的特性，分治算法解题步骤，经典实例，总结与体会。经典实例（递归求累加，求阶乘、汉诺塔问题、快速排序算法、二分查找算法（折半查找算法）、归并排序算法、矩阵乘法和Strassen、大整数乘法、循环赛日程表）。 *无题目链接

资源推荐

资源详情

资源评论

分治算法的思想

适用于用分治算法解决的问题的特性

分治算法解题步骤

经典实例

总结与体会

分治算法

1. 分治算法的思想

将一个问题分解为 n 个相互独立且与原问题性质相同的子问题，通过逐个解决小问题，从

而解决整个问题。（逐个击破，分而治之）

2. 适用于用分治算法解决的问题的特性

 原问题规模大，不易解决。但原问题可缩小且到一定程度就可以容易解决。

 原问题可以分解为多个规模较小、求解方式相似的子问题。且各个子问题之间相互独

立、互不影响。

 若干子问题的解进行合并后，可以得到原问题的解。

合并子问题的解是应用分治算法的关键，能否利用分治法完全取决于问题是否满足这点。

如果仅仅具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心算法或动

态规划。

3. 分治算法解题步骤

分解(Divide): 原问题分为若个子问题，这些子问题是原问题的规模

较小的实例。

解决(Conquer): 递归地求解各子问题。若子问题足够小，则直接求

解。

合并(Combine): 将子问题的解合并成原问题的解。

4.经典实例

递归求累加，求阶乘

累加

add(int num)

{

sum = 0;

if(num <= 1)

{

sum += num;

return sum;

}

else

return sum += num + add(num-1);

}

阶乘

int fac(int n)

{

if(n==0||n==1)

return 1;

else

return n*fac(n-1);

}

递归算法=分治算法？

答：不一定。递归虽然包含分解和解决两个步骤，但是并不是每道

题都要求合并结果

汉诺塔问题

void hanoiTower(int num, char a, char b, char c)

{

if (num == 1)

{

cout << "第1个盘从" << a << "->" << c;

}

else {

//递归n－1个盘子，由a放置到b

hanoiTower(num - 1, a, c, b);

//a上剩下的一个盘子，由a拿到c，输出出来

cout << "第" << num << "个盘从" << a << "->" << c <<

endl;

//b上有n-1个盘子，将这n-1个盘子递归放到c上

hanoiTower(num - 1, b, a, c);

}

快速排序算法

void quickSort(int a[], int low, int high)

{

if (low >= high)

return;

int left = low, right = high;

int p = a[left];

while (left < right)

{

//大于p值就不动

while (left < right && a[right] >= p)

{

--right;

}

//把比基准值小的放左边

if (a[right] < p)

{

a[left] = a[right];

}

//小于p值就不动

while (left < right && a[left] <= p)

{

++left;

}

//把比基准值大的放右边

if (a[left] > p)

{

a[right] = a[left];

}

//插进中间的空位

if (left >= right)

{

a[left] = p;

//break;

}

//对左右部分进行递归

quickSort(a, low, left-1);

quickSort(a, left+1, high);

}

二分查找算法（折半查找算法）

//递归查找

int recursionBinarySearch(int a[], int low, int high, int key)

{

if(low >= high)

{

return -1;//一定是-1，若为 0，查找第一个数字的时候就

会和 index=0 冲突

}

int mid = (low + high) / 2;

if(a[mid] == key)

剩余38页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

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

做人求其滴

粉丝: 337
资源: 5

上传资源快速赚钱

我的内容管理展开

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

我的收益

登录查看自己的收益

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

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

我的收藏

我的下载

下载帮助

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

分治算法综述.docx

量子优化算法综述.docx

遗传算法综述.docx

算法设计与分析实验报告：分治算法实验.docx

圆心提取算法综述.docx

启发式优化算法综述.docx

粒子群优化算法综述.docx

模拟退火算法综述.docx

目标跟踪算法综述.docx

谱聚类算法综述.docx

图像增强算法综述.docx

粒子滤波算法综述.docx

云计算调度算法综述.docx

图嵌入模型综述.docx图嵌入模型综述.docx图嵌入模型综述.docx

最优控制-遗传算法综述.docx

数据挖掘算法综述.docx

细胞分割算法综述.docx

动态规划算法综述.docx

人工蜂群算法综述.docx

人工智能算法综述.docx

第十五届蓝桥杯大赛软件赛省赛C++B组题目

C/C++中文参考手册离线最新版

代码随想录-八股文 pdf

编译器（gcc、g++）

第十五届蓝桥杯大赛软件赛省赛-C++A组题目

Qt5.9 C++开发指南.pdf 及示例源码

Qt （高仿Visio）流程图组件开发，源码分享

mingw-w64-install.exe

Qt、QCustomPlot、实时波形绘制、实时曲线绘制

C/C++中文帮助文档

最新资源