二分法解决金块问题精选PPT.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《二分法解决金块问题精选PPT.ppt》由会员分享,可在线阅读,更多相关《二分法解决金块问题精选PPT.ppt(17页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、二分法解决金块问题第1页,此课件共17页哦报告报告2算法设计与分析实验报告算法设计与分析实验报告分而治之算法分而治之算法 二分法解决金块问题二分法解决金块问题第2页,此课件共17页哦分治法概述分治法概述1 内容提要内容提要典型二分法典型二分法2分金块问题分金块问题3算法分析与总结算法分析与总结4第3页,此课件共17页哦分治法概述分治法概述1一一 分治法分治法 把一个难于直接解决的大问题分解为若干个“相似”的小问题,再解所有小问题,然后把小问题的解“合并”,从而得到大问题的解。即:分治法是递归设计方法的一种具体策略。二二 适合分治法策略的问题适合分治法策略的问题 当求解一个输入规模为n且取值又相
2、当大的问题时,我们可以将这n个数据分解成k个不同的可以独立求解的子问题,这些子问题与原问题具有相似的结构,利用递归递归或循环循环机制求解。三三 分治法的应用分治法的应用 折半查找,合并排序,快速排序,二叉树遍历,二叉排序树的查找等算法。第4页,此课件共17页哦典型二分法典型二分法2二分法描述:二分法描述:在算法设计中每次一个问题分解成的子问题个数一般是固定的,每个子问题的规模也是平均分配的。当每次都将问题分解为原问题规模的一半时,成为二分法。如图2-1所示:子问题二子问题二子问题一子问题一子问题三子问题三子问题四子问题四子问题五子问题五子问题六子问题六原问题原问题图图2-1 二分法示意图二分法
3、示意图第5页,此课件共17页哦分金块问题分金块问题3一一 金块问题描述:金块问题描述:老板有n个金块,希望最优秀的雇员得到其中最重的一块,最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器,如何用最少的比较次数找出最重和最轻的金块?以9以内的实例理解问题。问题:问题:1.最重的是那块?用max标记 2.最轻的是那块?用min标记 第6页,此课件共17页哦分金块问题分金块问题3二二 算法设计算法设计 蛮力法的思想蛮力法的思想:对金块逐个的进行比较查找,先拿两块比较重量,留下重的一个与下一块比较,知道全部比较完毕,就找到了最重的一块。算法描述如下:Maxmin(float a,int n)ma
4、x=a1;min=a1;for(i=2;i=n;i=i+1)if(maxai)min=ai Return(max,min)第7页,此课件共17页哦分金块问题分金块问题3 二分法思想:二分法思想:假设只有一个金块,重10克,则不需要比较轻重,最重者和最轻 者是同一个金块。即比较0次。假设有2个金块,一个重10克,另一个重16克,则需要比较1 次,可以把最重者和最轻者确定下来。当有多个金块时(假设6块),则用二分法对其分解,直到分解为(1)或(2)的情形时,问题很容易解决。第8页,此课件共17页哦假设6个金块重量如下(以找最轻金块为例):2 6 4 3 8 1 一分为二(两组):【2 6 4】【3
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二分法 解决 金块 问题 精选 PPT
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内