没有合适的资源?快使用搜索试试~ 我知道了~
算法设计与分析答案.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 84 浏览量
2022-10-21
09:00:01
上传
评论
收藏 425KB PDF 举报
温馨提示
试读
12页
算法设计与分析答案.pdf算法设计与分析答案.pdf
资源推荐
资源详情
资源评论
算法设计与分析答案屈婉玲
【篇一:分金块问题的解决思想和算法设计】
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 use one of
the mostefficient algorithm choose the maximum and
minimum of the gold. this paper gives a more commonly used
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]
else 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];
}
else if(i==j-1)
if(a[i]a[j])
{
fmax=a[j];
fmin=a[i];
}
else
{
fmax=a[i];
fmin=a[j];
}
else
{
mid=(i+j)/2;
剩余11页未读,继续阅读
资源评论
春哥111
- 粉丝: 1w+
- 资源: 5万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功