您好,欢迎来到小奈知识网。
搜索
您的当前位置:首页分金块问题的两种算法实验报告

分金块问题的两种算法实验报告

来源:小奈知识网


分金块问题的解决思想和算法设计

王雕 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)时间复杂性和空间复杂性。

分析该算法可以看出,比较操作 max6算法的正确性分析

算法的正确性分析包含两方面的含义:1)算法是可终止的。2)算法是有效的。

在上述算法中,由于n是有限数,所以算法在有限次执行之后必然终止,这是显然的。

算法的有效性是指当算法正常终止时,最重、最轻的金块能够被找到(没有遗漏现象)。由于算法是从第一个金块开始逐一寻找,直到和第n个金块比较之后才结束,所以最后得到的必然是最重(max)、最轻(min)的金块.综合1)和2),算法是正确的。 7实验结果:

算法思想二 用分治法解决金块问题

1典型二分法思想:一种简单的分治法。即当每次将比较大的一个问题一分为二,形成两个较小的问题,再把每个较小问题一分为二,变

为更小的两个问题,……,直到得到容易解决的小问题为止,再解决所有小问题,然后把小问题的解逐层合并,得到原来大问题的解。

原问题 子问题一 子问题二

子问题三 子问题四 子问题五 子问题六

………..

典型二分法用二叉树表示:

……………….

2 用二分法如何解决金块问题? 从两个简单实例谈起:

(1) 假设只有一个金块,重10克,则不需要比较轻重,最重者和最轻者是同一个金块。即比较0次。

(2) 假设有2个金块,一个重10克,另一个重16克,则 需要比较1次,可以把最重者和最轻者确定下来。

(3) 当有多个金块时(假设6块),则用二分法对其分 解,直到分解为(1)或(2)的情形时,问题很

容易解决。

假设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用二分法解决金块问题算法设计:

问题抽象、简化为:在n个元素的集合中寻找最大和最小值元素。

(1)将集合一分为二,变为两个集合,目的是在较小的两个集合中分别找最大、最小元素。

(2)递归分解较小集合,直到每个集合中的元素个数≤2,然后找出小集合的最大、最小元素。

(3)合并(回溯):自低向上把子问题的解合并,大元素中取最大者,小元素中取最小者,最后得到元问题的解。

4 用二分法解决金块问题算法描述:

void maxmin(int i,int j,float &fmax,float &fmin) {

int mid;

float lmax,lmin,rmax,rmin; if(i==j) { }

else if(i==j-1)

if(a[i]fmax=a[j]; fmin=a[i]; fmax=a[i]; fmin=a[i];

}

} else { } else { }

mid=(i+j)/2;

maxmin(i,mid,lmax,lmin); maxmin(mid+1,j,rmax,rmin); if(lmax>rmax)

fmax=lmax; fmax=a[i]; fmin=a[j];

else

fmax=rmax;

if(lmin>rmin)

fmin=rmin;

else

fmin=lmin;

5用二分法解决金块问题算法分析:

以元素比较总次数作为maxmin算法的时间复杂度度量指标,用T(n)表示比较总次数,则可以推导出递归关系:

0 n=1 T(n)= 1 n=2 T(n/2)+T(n/2) n>2

T(n)下界为(3n/2)-2

6实验结果对应数据:

7 两种算法的比较

比较项目 算法名称 时间复杂度 算法特点 占用空间较小 适合数量较少的问题

蛮力法 O(n) 二分法 O(n) 内存消耗较大 对于无规则的比较有优势

8 结束语

本文给出了两种关于金块问题的算法,分别是蛮力法和二分法。分析了其时间复杂度和占用空间等。总结了两种算法的特点及适用性。一般情况下,选择二分法较为快速,但内存消耗较大。

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- huatuo3.com 版权所有 蜀ICP备2023022190号-1

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务