没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
第
1
页 共
15
页
第九章 分治策略
当我们要求解一个数据规模为 n 且 n 取值又相当大的问题时,直接求解往往是非常困难
的。如果在将这 n 个输入分成 k 个不同子集合的情况下,能得到 k 个不同的可分别求解的子
问题,其中 1<k≤n,求出了这些子问题的解之后,还可找到适当的方法把它们合并成整个问
题的解,那么,具备上述特性的问题可考虑使用分治策略求解。
第 4 课 金块问题(gold)
【问题描述】
一个老板有一袋金块,里面有 n 块金子。每个月,老板会从袋子
中拿出两个金块奖励两名表现优秀的雇员。按规矩,最优秀的雇员将
得到袋中最重的金块,排名第二的雇员将得到袋中最轻的金块。如果
老板周期性地往袋中加入新的金块,那么每个月他都要找出最重和最
轻的金块。假设有一台比较质量的仪器,我们希望用尽量少的比较次
数找出最重和最轻的金块。
【输入格式】
第 1 行只有一个整数 n(2≤n≤100000)。
第 2 行 n 个长整型范围内的整数,每个整数之间用一个空格隔开,
表示每块金子的质量。
【输出格式】
输出两个用空格分开的整数,表示最重和最轻的金块的质量。
【输入样例】
8
10 8 2 4 5 3 9 1
【输出样例】
第
2
页 共
15
页
10 1
分析问题
明显,金块问题就是在 n 个元素中求最大值和最小值的问题。最
直接的方法就是逐个地进行比较查找,
如下面程序所示:
//program p9_01_01
/*
第 1 课 金块问题(gold)方法一
明显,金块问题就是在 n 个元素中求最大值和最小值的问题。
最直接的方法就是逐个地进行比较查找,
如下面程序所示:
*/
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int maxa,mina;
int main( void )
{
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>a[i];
}
maxa=mina=a[1];
for(int i=2;i<=n;++i)
{
//比较的次数:2*(n-1)=2*n-2
if(a[i]>maxa) maxa=a[i];
if(a[i]<mina) mina=a[i];
}
cout<<maxa<<" "<<mina<<endl;
return 0;
}
这种方法需要比较 2n-2 次。也可以采用另一种方法,先比较 n-1 次求出最重的金块,再
从剩下的 n-1 个金块中比较 n-2 次得到最轻的,这样总的比较次数为 2n-3 次(程序如下),
相差只有一次。显示,这不是我们希望求解的最少的比较次数。
//program p9_01_01
第
3
页 共
15
页
/*
第 1 课 金块问题(gold)方法二
这种方法需要比较 2n-2 次。
也可以采用另一种方法,
先比较 n-1 次求出最重的金块,
再从剩下的 n-1 个金块中比较 n-2 次得到最轻的,
这样总的比较次数为 2n-3 次(程序如下),相差只有一次。
显示,这不是我们希望求解的最少的比较次数。
*/
#include <bits/stdc++.h>
using namespace std;
int a[100005];
int maxa,mina;
int main( void )
{
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>a[i];
}
maxa=a[1];
int j;
for(int i=2;i<=n;++i) //比较的次数:n-1
{
if(a[i]>maxa) maxa=a[i];
j=i;
}
//将最大值放到 a[n]处
swap(a[j],a[n]);
mina=a[1];
for(int i=2;i<n;++i) //比较的次数:n-2
{
if(a[i]<mina) mina=a[i];
}
cout<<maxa<<" "<<mina<<endl;
return 0;
}
剩余14页未读,继续阅读
dllglvzhenfeng
- 粉丝: 9342
- 资源: 1868
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
- 1
- 2
前往页