实验一 分治与递归算法的应用

实验一 分治与递归算法的应用

一、实验目的

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

金块问题

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

一般思路：假设袋中有n 个金块。可以用函数M a x，通过n-1次比较找到最重的金块。找到最重的金块后，可以从余下的n-1个金块中用类似法通过n-2次比较找出最轻的金块。这样，比较的总次数为2n-3。 分治法：

如果集合中只有1个元素，则它既是最大值也是最小值； 如果有2个元素，则一次maxnum(i,j) 一次minnum(i,j)就可以得到最大值和最小值；

如果把集合分成两个子集合，递归的应用这个算法分别求出两

个子集合的最大值和最小值，最后让子集合1的最大值跟子集合2的最大值比较得到整个集合的最大值；让子集合1的最小值跟子集合2的最小值比较得到整个集合的最小值。 四、程序设计

对金块问题的程序设计如下： （1）核心算法分析

double Search_Max(double g[],int left,int right）与

double

Search_Min(double g[],int left,int right)函数分别是求最大重量与最小重量金块的被调用函数，函数体中

当left==right时，只有一个重量，最小和最大重量相等，分别直接返回返回g[left],g[right]。

当right-left==1时，有两个重量，分别调用一次min（g1,g2）和max（g1,g2）函数就可得出最小与最大重量，分别返回。

当right-left>1时，mid=(left+right)/2取中点，将数据群分为两半，分别递归调用，最后将得到的两个数据群的最值运用min（）或max（）函数得到最小最大重量。 (2)函数调用及主函数设计

Int main（）中，首先输入要输入的数据个数n，运用for循环将数据输入到gold[0~n]数组中，然后分别调用Search_Max(gold,0,n-1)和Search_Min(gold,0,n-1)函数输出最小最大重量；

double Search_Max(double g[],int left,int right）与double

Search_Min(double g[],int left,int right)函数中，分别调用min（g1,g2）和max（g1,g2）函数实现查找最小最大值功能。 （3）主要算法流程图

输入n

For循环输入

调用

double max(g1, g2) Search_Max(gold,0,n-1) g[0~n] Main（）函数分别调用Search_Min(gold,0,n-1) 调用 double min(g1, g2) 四.程序调试及运行结果分析

五.实验总结

这次实验我又更深层次的了解了分治算法，知道了分治法的思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。对它的运用模型更加熟悉，相信以后会更加熟练的运用它。

附录源程序： #include #include #include using namespace std;

double max(double g1,double g2)//比较找大值 { }

double min(double g1,double g2)//比较找小值 { }

double Search_Max(double g[],int left,int right)//用二分法递归找最大值 {

if(left==right) { }

double max; max=g[right]; return max;

//当只有一个数时，直接返回该值

return(g1g2?g1:g2);

if(right-left==1) {

double LM,RM;

LM=g[left];

RM=g[right]; return(max(LM,RM)); }

if(right-left>1) {

double LM,RM;

int mid=(left+right)/2;//取中点 LM=Search_Max(g,left,mid);

RM=Search_Max(g,mid,right);//左半部分，右半部分的最大值比

较找最大 }

double Search_Min(double g[],int left,int right)//用二分法递归找最小值 {

if(left==right) { }

return(max(LM,RM));

double min;

本文来源：https://www.bwwdw.com/article/037d.html