nbhkdz.com冰点文库

分治

时间:2012-12-01


例:求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.

分治算法实验(用分治法实现归并排序算法)

算法分析与设计实验报告 第二 次实验姓名 时间 实验名称 10.17 上午 学号 地点 班级 工训楼 309 分治算法实验(用分治法实现归并排序算法) 实验目的 通过上机...

分治算法之平面最接近点问题

12 2 第 1 章 绪论 1.1 分治算法的知识介绍分治算法的基本思想是将一个规模为 N 的问题分解为 K 个规模较小的子问题, 这些 子问题相互独立且与原问题性质...

分治算法实验(用分治法实现快速排序算法)

算法分析与设计实验报告 第四 次附加实验姓名 时间 实验名称 12.26 上午 学号 地点 班级 工训楼 309 分治算法实验(用分治法实现快速排序算法) 实验目的 通过...

格雷码Gray的分治构造算法

算法设计与分析课程设计 题目:Gray 码的分治构造算法 专业: 班级: 学号: 姓名: 网络工程 计算机工程系 2012 年 11 月 16 日 一、算法问题描述 Gray 码是一...

c语言---分治法

分治法在计算机科学中, 分治法是一种很重要的算法。 字面上的解释是“ 在计算机科学中 , 分治法是一种很重要的算法 。 字面上的解释是 “ 分而治 就是把...

分治算法试题

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

比赛--分治算法

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

论分治算法在信息学竞赛中的应用

{由右上角推出左下角} end; left:=left+n; end; n:=n*2; end; end; 通过上例我们得出分治算法可以使用递归结构和非递归结构解决, 非递归编写的程序时 ...

贪心算法、分治算法、动态规划算法间的比较.doc

贪心算法、分治算法、动态规划算法间的比较.doc_数学_自然科学_专业资料。贪心算法、分治算法、动态规划算法间的比较 题目:贪心算法、分治算法、动态规划算法间的比较...

分治法的应用

分治法的应用_IT/计算机_专业资料。分治法的应用分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是 “分而治之” ,就是把一个复杂的问题分成...