《二分法解决金块问题PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《二分法解决金块问题PPT讲稿.ppt（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、二分法解决金块问题第1页，共17页，编辑于2022年，星期四报告报告2算法设计与分析实验报告算法设计与分析实验报告分而治之算法分而治之算法 二分法解决金块问题二分法解决金块问题第2页，共17页，编辑于2022年，星期四分治法概述分治法概述1 内容提要内容提要典型二分法典型二分法2分金块问题分金块问题3算法分析与总结算法分析与总结4第3页，共17页，编辑于2022年，星期四分治法概述分治法概述1一一 分治法分治法 把一个难于直接解决的大问题分解为若干个“相似”的小问题，再解所有小问题，然后把小问题的解“合并”，从而得到大问题的解。即：分治法是递归设计方法的一种具体策略。二二 适合分治法策略的问题
2、适合分治法策略的问题 当求解一个输入规模为n且取值又相当大的问题时，我们可以将这n个数据分解成k个不同的可以独立求解的子问题，这些子问题与原问题具有相似的结构，利用递归递归或循环循环机制求解。三三 分治法的应用分治法的应用 折半查找，合并排序，快速排序，二叉树遍历，二叉排序树的查找等算法。第4页，共17页，编辑于2022年，星期四典型二分法典型二分法2二分法描述：二分法描述：在算法设计中每次一个问题分解成的子问题个数一般是固定的，每个子问题的规模也是平均分配的。当每次都将问题分解为原问题规模的一半时，成为二分法。如图2-1所示：子问题二子问题二子问题一子问题一子问题三子问题三子问题四子问题四子
3、问题五子问题五子问题六子问题六原问题原问题图图2-1 二分法示意图二分法示意图第5页，共17页，编辑于2022年，星期四分金块问题分金块问题3一一 金块问题描述：金块问题描述：老板有n个金块，希望最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，如何用最少的比较次数找出最重和最轻的金块？以9以内的实例理解问题。问题：问题：1.最重的是那块？用max标记 2.最轻的是那块？用min标记 第6页，共17页，编辑于2022年，星期四分金块问题分金块问题3二二 算法设计算法设计 蛮力法的思想蛮力法的思想：对金块逐个的进行比较查找，先拿两块比较重量，留下重的一个与下
4、一块比较，知道全部比较完毕，就找到了最重的一块。算法描述如下：Maxmin(float a,int n)max=a1;min=a1;for(i=2;i=n;i=i+1)if(maxai)min=ai Return(max,min)第7页，共17页，编辑于2022年，星期四分金块问题分金块问题3 二分法思想：二分法思想：假设只有一个金块，重10克，则不需要比较轻重,最重者和最轻 者是同一个金块。即比较0次。假设有2个金块，一个重10克，另一个重16克，则需要比较1 次，可以把最重者和最轻者确定下来。当有多个金块时（假设6块），则用二分法对其分解，直到分解为（1）或（2）的情形时，问题很容易解决。
5、第8页，共17页，编辑于2022年，星期四假设6个金块重量如下(以找最轻金块为例)：2 6 4 3 8 1 一分为二（两组）：【2 6 4】【3 8 1】一分为二（四组）：【2 6】【4】【3 8】【1】解较小子问题：2 4 3 1合并子问题解：2 1 lmin rmin?分金块问题分金块问题3第9页，共17页，编辑于2022年，星期四分金块问题分金块问题3 用二分法解决金块问题算法设计步骤：用二分法解决金块问题算法设计步骤：问题抽象、简化为：在n个元素的集合中寻找最大和最小值元素。(1)将集合一分为二，变为两个集合，目的是在较小的两个集合中分别找最大、最小元素。(2)递归分解较小集合，直到每
6、个集合中的元素个数2，然后找出小集合的最大、最小元素。(3)合并（回溯）：自低向上把子问题的解合并，大元素中取最大者，小元素中取最小者，最后得到元问题的解。第10页，共17页，编辑于2022年，星期四用二分法解决金块问题算法描述：用二分法解决金块问题算法描述：Float an;Maxmin(int I,int j,float&fmax,float&fmin)int mid;float lmax,lmin,rmax,rmin;if(i=j)fmax=ai;fmin=ai;分金块问题分金块问题3i j第11页，共17页，编辑于2022年，星期四分金块问题分金块问题3用二分法解决金块问题算法描述用二
7、分法解决金块问题算法描述(续续)：else if(i=j-1)if（aiaj）fmax=aj;fmin=ai;else fmax=aj;fmin=ai;else/ij-1 mid=(i+j)/2;/x表示取整数 maxmin(i,mid,lmax,lmin);iji jmid第12页，共17页，编辑于2022年，星期四用二分法解决金块问题算法描述用二分法解决金块问题算法描述(续续)：maxmin(mid+1,j,rmax,rmin);if(lmaxrmax)fmax=lmax;else fmax=rmax;if(lminrmin)fmin=rmin;else fmin=lmin;解合并：解合并
8、：大者取大，大者取大，小者取小小者取小分金块问题分金块问题3第13页，共17页，编辑于2022年，星期四算法分析与总结算法分析与总结4二分法的算法分析：二分法的算法分析：以元素比较总次数作为maxmin算法的时间复杂度度量指标，用T(n)表示比较总次数，则可以推导出递归关系：T（n）=0 n=11 n=2T(n/2)+T(n/2)n2T(n)下界为(3n/2)-2第14页，共17页，编辑于2022年，星期四算法分析与总结算法分析与总结4两种算法的比两种算法的比较较 比较项目 算法名称时间复杂度算法特点蛮力法O(n)占用空间较小适合数量较少的问题二分法O(n)内存消耗较大对于无规则的比较有优势第15页，共17页，编辑于2022年，星期四算法分析与总结算法分析与总结4算法总结：算法总结：以上给出了两种关于求解金块问题的算法，分别是蛮力法和二分法。分别分析了他们的时间复杂度和占用空间等。分治法的思想就是把大问题逐步分解为小问题，直到可解的小问题，最后把小问题的解逐层合并，得到大问题的解。二分法是最简单的分治法，每次把问题一分为二。第16页，共17页，编辑于2022年，星期四第17页，共17页，编辑于2022年，星期四