分治算法实验

中原工学院信息商务学院

算法设计与分析 实验报告

系 别： 计算机科学系 专 业： 网络工程 班 级： 网络132 学 号： 201301024225 学生姓名： 齐冬生 指导教师： 邬 迎

2014年11月9日

实验二 分治算法的应用

一、实验目的

1．掌握分治算法的基本思想（分-治-合）、技巧和效率分析方法。 2．熟练掌握用递归设计分治算法的基本步骤（基准与递归方程）。 3．学会利用分治算法解决实际问题。

二、实验内容

1.问题描述：

题目二：金块问题

老板有一袋金块（共n块，n是2的幂（n≥2））,最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块。并对自己的程序进行复杂性分析。

【输入输出样例】

题目三：求最大两个数和最小两个数

利用分治法求一组数据中最大的两个数和最小的两个数。

三．算法设计

数据结构与核心算法的设计描述，函数调用及主函数设计主要算法流程图等.

题目二:1）将数据等分为两组（两组数据可能差1），目的是分别选取其中的最大和最小值。

2）递归分解直到每组元素发的个数<=2,可简单的找到最大（小）值。

3）回溯时合并子问题的解，在两个子问题的解中大者取大，小者取小，即合并为金块问题的解。

题目三:对一组数进行比较大小，求出其中的最大值和最小值，利用分治法的原

理来实现。先对数组中元素个数进行判断，只有一个元素时，最大值max和最小值min都是它本身；当有两个元素时，比较两个数的大小，大者为最大值max，小者为最小值min；当数组中元素多于两个时，里用分治法原理，求出划分出的每组中的最值与另外一组最值比较，最后的得出最大值max和最小值min。

四.程序调试及运行结果分析 题目二:

题目三：

五.实验总结 题目二:

#include #define Max 100

void maxmin(int i,int j,float a[],float &max,float &min); void main() {

int n;

float max,min; float a[Max];

cout<<\"请输入金块的个数：\"; cin>>n;

cout<<\"请输入对应金块的重量:\"; for(int i=0;i>a[i];

maxmin(0,n-1,a,max,min);

cout<<\"最重的金块重量为：\"<void maxmin(int i,int j,float a[],float &max,float &min) {

if(i==j) {

max=a[i]; min=a[i]; }

else if(i==j-1) {

if(a[i]>a[j]) {

max=a[i]; min=a[j]; }

else {

max=a[j]; min=a[i]; } }

else {

int mid;

float lmax,lmin,rmax,rmin; mid=(i+j)/2;

maxmin(i,mid,a,lmax,lmin); maxmin(mid+1,j,a,rmax,rmin); if(lmax>rmax) max=lmax; else max=rmax; if(lmin题目三：

#include int main()

{ int a[10]={7,13,15,17,29,10,18,6,14,2}; int i,max1=0,max2=0,min1=0,min2=0; for(i=0;i<10;i++) {

if(a[max1]max1=i;

if(a[min1]>a[i])

min1=i;

}

if(max1==0)

max2=1;

if(min1==0)

min2=1;

for(i=0;i<10;i++) {

printf(\"max1=%d\\nmax2=%d\\nmin1=%d\\nmin2=%d\\n\,a[min2]); } 实验心得

通过这次实验，我对算法的意义又多了一些认识，一个好的算法真的很重要，特别是当数据量很大的时候。就比如本题中的金块问题，如果用蛮力法，对金块逐个进行比较，平均比较次数是3（n-1）/2.但是如果用分治法的话，平均比较次数为1.5n-2,比前者要好一点，这也恰恰体现了分治法的含义，最重要的是递归算法的空间效率和运行效率都是比较低的。这也提醒我们，实际应用中不能仅仅根据时间复杂性选择算法，也要根据实际问题来解决，不能只钻牛角尖，也要学会变通，这样会大大节省的时间。

if(i==max1||i==min1)

continue;

if(a[max2]max2=i;

if(a[min2]>a[i])

min2=i; }