算法设计与分析答案屈婉玲
【篇一：分金块问题的解决思想和算法设计】
s=txt>摘 要：在日常生活中，分金块问题是一个常见的问题，人们总是会面临怎样比较大小。才能利用一种最 高效的算法选出其中最大和最小的金块。本文给出了较为常用的两种算法—蛮力法和分治法。
关键词：分金块问题；蛮力法(非递归)；分治法；
points gold bullion problem solving thought and algorithm design
abstract: in daily life, points gold bullion is a common problem, people will always face how to compare size. can u one of the mostefficient algorithm choo the maximum and minimum of the gold. this paper gives a more commonly ud two kinds of algorithm, brute force method and partition method.
天蝎座的日期 keywords: points gold bullion problem; brute force method(non recursive); partition method;
1引言
递归调用是一种特殊的嵌套调用，是某个函数调用自己，而不是另外一个函数。递归调用一种解决方案，一种是逻辑思想，将一个大工作分为逐渐减小的小工作，比如说一个和尚要搬50块石头，他想，只要先搬走49块，那剩下的一块就能搬完了，然后考虑那49块，只要先搬走48块，那剩下的一块就能搬完了……，递归是一种思想，只不过在程序中，就是依靠函数嵌套这个特性来实现了。
由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法
2问题概述
老板有n个金块，希望最优秀的雇员得到其中最重要的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，如何用最少的比较次数找出最重和最轻的金块？
酸甜
理解金块问题：以9以内的实例理解问题。
金块示例
问题：1.最重的是那块？用max标记。
2.最轻的是那块？用min标记。
3 求解分金块问题的常用算法
3.1蛮力法
蛮力法，也称穷举法，是一种简单而直接地解决问题的方法，常常直接基于问题的描述，因此，也是最容易应用的方法。但是，用蛮力法设计的算法其时间性能往往是最低的，典型的指数时间算法一般都是通过蛮力搜索而得到的。即从第一块开始查找，查找哪块最重，哪块最轻。
算法设计：
maxmin(float a[],int n)
{max=a[1];min=a[1];
for(i=2;i=n;i=i+1)
{if(maxa[i])
max=a[i]
el if(mina[i])
min=a[i]
}
return(max, min)
}
step1 将所有金块重量存于数组
step2 将第一个金块同时标记为最重和最轻的金块
step3 将第一个与后一个进行重量的比较，将更重的标记为max，同时如果现阶段最轻的比后者轻，那么
将后者标记为min。
step4 依次进行比较，最重得到最重的和最轻的max min.
3.2分治法
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】
解较小子问题： 24 3 1
合并子问题解： 2 1
最终的解： 1
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)
{
fmax=a[i];
招聘英语 fmin=a[i];
}
el if(i==j-1)
if(a[i]a[j])
入座打一数学名词 {武夷水仙茶
fmax=a[j];
fmin=a[i];
}
el
{
fmax=a[i];
fmin=a[j];
}
el
{
mid=(i+j)/2;
maxmin(i,mid,lmax,lmin);
脸为什么会出油 maxmin(mid+1,j,rmax,rmin);
if(lmaxrmax)
fmax=lmax;
el
fmax=rmax;
if(lminrmin)
fmin=rmin;
el
fmin=lmin;
}
}
4 仿真实验及其结果：
在eclip3.5环境下测试brute force method，随机输入n= 8 ;num={23,43,3,5,6,23,9,6}验证,
验证结果max=43; min=3结果正确。
输入n=6; num={3,7,8,9,0,15} 验证;
验证结果 max=15;min=0结果正确。
表-1 brute force method实验输入输出参数设置
由于蛮力算法是从第一个金块开始逐一寻找，直到和第n个金块比较之后才结束，所以最后得到的必然是最重(max)、最轻(min)的金块.
表-2 partition method实验输入输出参数设置
表-2 贪心算法的时间复杂度分析
分析蛮力法可以看出，比较操作 maxa[i]和mixa[i]是执行频次最高的关键语句。因此以这两个语句执行的总次数作为该算法执行所需要的时间。最好情况下，金块由轻到重排列，不需要进行mina[i]比较，而 maxa[i]比较共需进行n-1次,即可得到max和min; 最坏情况下，金块由重到轻排列，还需要进行n-1次mina[i]比较，才能得到最终的min，因此共进行
2(n-1)次比较。在平均情况下(概率平均)，a[i]将有一半的时间比max大，因此平均比较次数是3(n-1)/2。所以算法时间复杂度为o(n).
分析分治法可以看出，元素比较总次数作为maxmin算法的时间复杂度度量指标，用t(n)表示比较总次数，则可以推导出递归关系：
t(n)下界为(3n/2)-2
格力遥控器
5 结束语
本文给出了两种关于金块问题的算法，分别是蛮力法和二分法。分析了其时间复杂度和占用空间等。总结了两种算法的特点及适用性。一般情况下，选择二分法较为快速，但内存消耗较大。
参考文献
[1] 《算法设计与分析》 王红梅 清华大学出版社 (2006-07出版)
恨相知晚 [2] 《算法设计与分析》 屈婉玲、刘田、张立昂 清华大学出版社 (2011-05出版)
[3] 《java核心技术(卷1):基础知识(原书第8版) 》 昊斯特曼 (horstmann gay s.)、gary cornell、叶乃
