当前位置:首页 >> 学科竞赛 >> 分治

分治


例:求n(n是2的幂(n>=2))个元素中的最大元与最小元。

[分析]用分治法解决这个问题就是把集合a分成a1,a2两个子集,每个子集有n/2个元素,应用递归结构找出两个子集的最大元和最小元,比较得到的两个最大元和最小元即可得到整个集合a中的最大元和最小元。

[参考程序]
program fenzhi;
const n=10;
type atype=array[1..n]of integer;
var max,min,I:integer;
a:atype;
procedure maxmin(r1,r2:integer;var max,min:integer);
var d,max1,min1,max2,min2:integer;
begin
if r2=r1+1 then
begin
if a[r2]>a[r1] then begin
max:=a[r2];
min:=a[r1];
end
else begin
min:=a[r2];
max:=a[r1];
end
end
else
begin
d:=(r1+r2)div 2;
maxmin(r1,d,max1,min1);
maxmin(d,r2,max2,min2);
if max1>max2 then max:=max1 else max:=max2;
if min1>min2 then min:=min2 else min:=min1;
end;
begin
writeln(‘input a:’);
for I:=1 to n do read(a[i]);
maxmin(1,n,max,min);
writeln(‘the max number is:’,max,’min number is:’,min);
end.

赞助商链接
更多相关文档:

实验1++递归与分治算法

淮海工学院计算机工程学院 实验报告书课 程名:题目: 《算法分析与设计》 递归与分治算法 实验 1 班学姓 级: 号: 名: 评语: 成绩: 指导教师: 批阅时间: 年...

分治算法试题

分治算法试题_理学_高等教育_教育专区。分治算法当我们求解某些问题时,由于这些问题要处理的数据相当多,或求解过程相当复杂,使得直接求解法 在时间上相当长,或者根本...

作业3 分治法

作业3 分治法_财会/金融考试_资格考试/认证_教育专区。2012 级算法设计与分析分治法 1. 作业题 作业 3 (1) 求 n 个元素的数组中最大元素的位置。 请用分治...

分治法求最大最小值

一. 实验目的及实验环境 实验目的:加深对分治算法原理及实现过程的理解。 实验环境:VC++6.0 二. 实验内容 用分治法求数组中最大元素和最小元素。 三.方案设计...

分治法解最接近点对问题

算法分析与设计实验报告 2014-2015 第一学期 实验一:用分治法解最接近点对问题 指导教师:cccc 实验时间:2014 年 10 月 28 日 实验地点:计算中心二楼 班级: ...

实验2 分治法算法设计

实验2 分治法算法设计_计算机软件及应用_IT/计算机_专业资料。算法分析与设计,实验二,分治法算法设计二分检索算法,归并排序算法,快速排序算法《...

比赛--分治算法

8页 10财富值 分治算法 9页 2财富值 分治算法 12页 1财富值如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...

算法分析——分治法

算法分析——分治法_IT/计算机_专业资料。分治算法小组的汇报内容: 小组的汇报内容:一、分治算法的基本概念………第 2 页 分治算法的基本概念………第 基本概念...

从《Cash》谈一类分治算法的应用

从《Cash》谈一类分治算法的应用_电脑基础知识_IT/计算机_专业资料。陈丹琦2008年信息学国家集训队作业 2008 年信息学国家集训队作业 雅礼中学 陈丹琦 从《Cash》谈...

分治算法

分治算法_计算机软件及应用_IT/计算机_专业资料。分治算法一、基本概念 在计算机科学中,分治法是一种很重要的算法。字面上的解释是 “分而治之”,就是把一个...

更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com