admin 管理员组

文章数量: 887006

给定数组a[0:n

给定数组a[0:n-1]试设计一个算法，在最坏情况下用[3n/2 -2 ] 次比较找出a[0:n-1]中元素的最大值和最小值；

解：要求对于数组用小于【3n/2-2】的比较次数找到两个最值

可以用数组第一个元素来初始化max，min

然后遍历数组，分别和max，min比较，一遍就可以找出

int a[n];
cin>>n
int max,min;
max=min=a[0]
for(int i=1;i<n;i++)
{
if(a[i]>max) max=a[i];
else if (a[i]<min)
min=a[i];
}
cout<<max<<" "<<min<<endl;

这样比较次数最坏就是数列递减排列，需要比较2（n-1）次

最好的情况就是数列递增排列，需要比较n-1次

平均次数为（3n-3）/2

所以为所求

本文标签： 给定数组a0n

版权声明：本文标题：给定数组a[0:n 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732351402h1533171.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。