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

Forpersonaluseonlyinstudyandresearch;mercialuse袁实验一分治与递归算法的应用葿羅一、(分-治-合)、技巧和效率分析方法。(基准与递归方程)。。芈二、问题描述薄金块问题肁老板有一袋金块(共n块,n是2的幂(n≥2)),最优秀的雇员得到其中最重的一块,最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器,希望用最少的比较次数找出最重和最轻的金块。并对自己的程序进行复杂性分析。芁3、问题分析莈一般思路:假设袋中有n个金块。可以用函数Max,通过n-1次比较找到最重的金块。找到最重的金块后,可以从余下的n-1个金块中用类似法通过n-2次比较找出最轻的金块。这样,比较的总次数为2n-3。羅分治法:螃如果集合中只有1个元素,则它既是最大值也是最小值;羀如果有2个元素,则一次maxnum(i,j)一次minnum(i,j)就可以得到最大值和最小值;蒈如果把集合分成两个子集合,递归的应用这个算法分别求出两个子集合的最大值和最小值,最后让子集合1的最大值跟子集合2的最大值比较得到整个集合的最大值;让子集合1的最小值跟子集合2的最小值比较得到整个集合的最小值。莆程序设计膁对金块问题的程序设计如下:蝿核心算法分析薈doubleSearch_Max(doubleg[],intleft,intright)与doubleSearch_Min(doubleg[],intleft,intright)函数分别是求最大重量与最小重量金块的被调用函数,函数体中蒃当left==right时,只有一个重量,最小和最大重量相等,分别直接返回返回g[left],g[right]。袃当right-left==1时,有两个重量,分别调用一次min(g1,g2)和max(g1,g2)函数就可得出最小与最大重量,分别返回。薈当right-left>1时,mid=(left+right)/2取中点,将数据群分为两半,分别递归调用,最后将得到的两个数据群的最值运用min()或max()函数得到最小最大重量。薈函数调用及主函数设计袄Intmain()中,首先输入要输入的数据个数n,运用for循环将数据输入到gold[0~n]数组中,然后分别调用Search_Max(gold,0,n-1)和Search_Min(gold,0,n-1)函数输出最小最大重量;莀doubleSearch_Max(doubleg[],intleft,intright)与doubleSearch_Min(doubleg[],intleft,intright)函数中,分别调用min(g1,g2)和max(g1,g2)函数实现查找最小最大值功能。薁主要算法流程图蚈芄输入n肂荿For循环输入g[0~n]螈蚅薀膈袈Main()函数分别调用用袂节袇Search_Min(gold,0,n-1)羇Search_Max(gold,0,n-1)芃蚀羀调用肇调用蚄蒂doublemin(g1,g2)虿***doublemax(g1,g2)***,知道了分治法的思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。对它的运用模型更加熟悉,相信以后会更加熟练的运用它。薂附录源程序:蒁#include<iostream>芇#include<>薃#include<algorithm>芃usingnamespacestd;艿doublemax(doubleg1,doubleg2)//比较找大值莇{羃 return(g1>g2?g1:g2);螁}肈doublemin(doubleg1,doubleg2)//比较找小值蒇{莄 return(g1<g2?g1:g2);蒃}螇doubleSearch_Max(doubleg[],intleft,intright)//用二分法递归找最大值薇{螅 if(left==right) //当只有一个数时,直接返回该值羁 {袀 doublemax;蚆 max=g[right];羂 returnmax;蚃 }蕿 if(right-left==1)螆 {莃doubleLM,RM;肁 LM=g[left];莈RM=g[right];螆return(max(LM,RM));螄 }袃 if(right-left>1)蒁 {袆doubleLM,RM;膅 intmid=(left+right)/2;//取中点芀 LM=Search_Max(g,left,mid);膀 RM=Search_Max(g,mid,right);//左半部分,右半部分的最大