- 1、本文档共58页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
2章节 递归与分治策略
第2章 递归与分治策略;将要求解的较大规模的问题分割成k个更小规模的子问题。;算法总体思想;算法总体思想;算法总体思想;2.1 递归的概念;2.1 递归的概念;2.1 递归的概念;2.1 递归的概念;2.1 递归的概念;2.1 递归的概念;2.1 递归的概念;2.1 递归的概念;2.1 递归的概念;2.1 递归的概念;(2) q(n,m)=q(n,n),m?n;
最大加数n1实际上不能大于n。因此,q(1,m)=1。
;2.1 递归的概念;2.1 递归的概念;;2.1 递归的概念;在问题规模较大时,较难找到一般的方法,因此我们尝试用递归技术来解决这个问题。
;递归算法的实现;递归算法的实现;递归小结;递归小结;分治法的适用条件;分治法的基本步骤;分治法的复杂性分析;分治法的复杂性分析;二分有哪些信誉好的足球投注网站技术;二分有哪些信誉好的足球投注网站技术;;大整数的乘法;大整数的乘法;Strassen矩阵乘法;Strassen矩阵乘法;Strassen矩阵乘法;Strassen矩阵乘法;棋盘覆盖;棋盘覆盖;棋盘覆盖;合并排序;合并排序;合并排序;快速排序;private static int randomizedPartition (Type a[], int p, int r)
{
int i = random(p,r);
MyMath.swap(a, i, p);
return partition (a, p, r);
};线性时间选择;线性时间选择;将n个输入元素划分成?n/5?个组,每组5个元素,只可能有一个组不是5个元素。用任意一种排序算法,将每组中的元素排好序,并取出每组的中位数,共?n/5?个。
递归调用select来找出这?n/5?个元素的中位数。如果?n/5?是偶数,就找它的2个中位数中较大的一个。以这个元素作为划分基准。;private static Comparable select (int p, int r, int k)
{
if (r-p75) {
//用某个简单排序算法对数组a[p:r]排序;
bubbleSort(p,r);
return a[p+k-1];
}
//将a[p+5*i]至a[p+5*i+4]的第3小元素
//与a[p+i]交换位置;
//找中位数的中位数,r-p-4即上面所说的n-5
for ( int i = 0; i=(r-p-4)/5; i++ )
{
int s=p+5*i,
t=s+4;
for (int j=0;j3;j++) bubble(s,t-j);
MyMath.swap(a, p+i, s+2);
}
Comparable x = select(p, p+(r-p-4)/5, (r-p+6)/10);
int i=partition(p,r,x),
j=i-p+1;
if (k=j) return select(p,i,k);
else return select(i+1,r,k-j);
};最接近点对问题;最接近点对问题;最接近点对问题;最接近点对问??;为了确切地知道要检查哪6个点,可以将p和P2中所有S2的点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中,所以它们在直线l上的投影点距p在l上投影点的距离小于d。由上面的分析可知,这种投影点最多只有6个。
因此,若将P1和P2中所有S中点按其y坐标排好序,则对P1中所有点,对排好序的点列作一次扫描,就可以找出所有最接近点对的候选者。对P1中每一点最多只要检查P2中排好序的相继6个点。;最接近点对问题;;循环赛日程表
您可能关注的文档
- 2014年国家公派研究生项目宣章节会.ppt
- 2014届高考生物一轮复习金榜章节件(知识概览+主干回顾+核心归纳):实验案例探究(二)评价改进类实验(共13张PPT)【更多关注@高中学习资料库 加微信:gzxxzlk做每日一练】.ppt
- 2014年奥地利暑期学校项目宣章节会.ppt
- 2014年9月华北地区高校图协二十八届学术年会.ppt
- 2014年基金资助政策调整.ppt
- 2014年安徽省公务员选调生考试YY章节座.ppt
- 2014年安徽省公务员选调生考试公开章节.ppt
- 2014年安徽省农信社考试模拟试卷章节解.ppt
- 2014年幼儿园教师远程研修章节程简报.ppt
- 2014年度扶贫开发“双到”工作考核明确强调几个问题.ppt
文档评论(0)