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.

赞助商链接

分治算法

分治算法_计算机软件及应用_IT/计算机_专业资料。分治算法简单问题 1. 设 A[1..n] 是一个由 n 个整数组成的数组, x 是一个整数,给出一个分治算法,要求找...

分治算法设计

分治算法设计 - 安徽文达信息工程学院学生实验报告(计算机语言编程类适用) 2017-2018 学年第 2 学期 院部 计算机学院 班级 课程名称《 算法分析与设计 》 软件...

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

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

分治算法实验报告

《算法设计与分析》实验报告 实验 1 分治算法 姓名张成辉 学号 1307300123 班级计科 132 实验日期 2015.1.13 实验地点学院 302 一、实验目的 1、掌握分治算法的...

分治算法实验报告

算法分析与设计实验报告 第 1 次实验姓名 时间 实验名称 10.17 上午 学号 地点 四合院 102 班级 分治算法实验(用分治法查找数组元素的最大值和最小值) 。 ...

分治和倍增

分治和倍增_学科竞赛_高中教育_教育专区。一枚OI蒟蒻的算法理解 分治和倍增 DJ(纯手打,复制请标明出处与作者,谢谢! ) 分治 ? 概念 ? 例题 二分答案 ? 概念 ...

蛮力法和分治法的性能比较

蛮力法与分治法求解最近对问题 1、蛮力法 蛮力法是一种简单直接地解决问题的方法,常常直接基于问题的描述和所涉及的概念 定义,来求解问题。虽然巧妙和高效的算法...

分治算法试题

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

分治法解最接近点对问题

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

基于分治法的快速排序

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

更多相关标签