分金块问题的解决思想和算法设计
王雕 40912127 2009级计算机科学与技术三班
摘要:在日常生活中,分金块问题是一个常见的问题,人们总是会面 临怎样比较大小。本文给出了较为常用的两种算法—蛮力法和分治 法。
关键词:分金块问题;蛮力法(非递归);分治法; 1 问题概述
老板有n个金块,希望最优秀的雇员得到其中最重要的一块,最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器,如何用最少的比较次数找出最重和最轻的金块? 2 理解金块问题:以9以内的实例理解问题
金块示例
问题:1.最重的是那块?用max标记 2.最轻的是那块?用max标记 3 求解金块问题的常用算法一蛮力法
蛮力法的设计思想:蛮力法,也称穷举法,是一种简单而直接地解决问题的方法,常常直接基于问题的描述,因此,也是最容易应用的方法。但是,用蛮力法设计的算法其时间性能往往是最低的,典型的指数时间算法一般都是通过蛮力搜索而得到的。即从第一块开始查找,查找哪块最重,哪块最轻。
a[0] a[1] a[2] a[3] max min ?< max
4算法设计:
Maxmin(float a[],int n) {max=a[1];min=a[1]; for(i=2;i<=n;i=i+1) {if(maxmax=a[i] else if(min>a[i]) min=a[i] } Return(max, min) } Step1 将所有金块重量存于数组 Step2 将第一个金块同时标记为最重和最轻的金块 Step3 将第一个与后一个进行重量的比较,将更重的标记为max,同时如果现阶段最轻的比后者轻,那么将后者标记为min。 Step4 依次进行比较,最重得到最重的和最轻的max min. 5算法分析:(1)时间复杂性和空间复杂性。
Copyright © 2019- huatuo3.com 版权所有 蜀ICP备2023022190号-1
违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务