nbhkdz.com冰点文库

分治


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

算法分析——分治法

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

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

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

分治法:快速傅里叶变换算法

分治法:快速傅里叶变换算法_计算机软件及应用_IT/计算机_专业资料。快速傅里叶变换的java实现,附实验报告、源程序及运行示例分治法:快速傅里叶变换算法学院:网研院...

分治算法例题

分治算法例题_理学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 分治算法例题_理学_高等教育_教育专区。C语言 分治算法例题...

分治算法实验 - 棋盘覆盖问题

分治算法实验 - 棋盘覆盖问题_计算机软件及应用_IT/计算机_专业资料。算法分析与设计 分治算法 棋盘覆盖课程名称:算法设计与分析 姓名: 实验序号:一 班级: 学号: ...

分治法解最接近点对问题

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

算法设计与分析 分治算法基本思想

算法设计与分析 分治算法基本思想_IT/计算机_专业资料。算法设计与分析 算法基本思想程序 4-1-1 折半搜索 template<class T> int BinarySearch(T a[], const ...

分治算法--最大子数组完整C程序

(int *p,int low,int high); int pos_low,pos_high,val;//定义全局变量存放起始位置和和值 //分治法排序 int main() { int A[]={13,-3,-25,20,-...

分别用蛮力法、分治法、减治法实现a的N次方

分别用蛮力法、分治法、减治法实现a的N次方_计算机软件及应用_IT/计算机_专业资料。《算法设计与分析》实验报告一学 日号: 期: 2012.11.5 姓得名: 分: 一...

基于分治法的快速排序

实验2. 基于分治法的快速排序算法 实验内容本实验要求基于算法设计与分析的一般过程(即待求解问题的描述、算法设计、算法 描述、算法正确性证明、算法分析、算法实现...