本文实例展示了C语言实现最大间隙问题的方法,对于算法的设计有一定的借鉴价值。分享给大家供大家参考。具体如下:
问题描述如下:
给定n个实数x1,x2,...,xn,求这n个实数在实轴上相邻2个数之间的最大差值,要求设计线性的时间算法。
解决思路:
注意题中要求设计线性时间算法。如果没有这个要求,就可以先排序,找出来就很方便。但我们知道排序最优良的算法的时间效率也是nlogn的。所以不可行。
采用一种区间算法。具体步骤就不说了,给出C语言代码,有注释加以说明。
具体实现代码如下:
#include "stdio.h" #include "stdlib.h" #define MAX 10000 float findmin(float data[],int n){/*寻找数据序列中的最小值*/ int index,i; float min,temp; temp=data[0]; for(i=1;i<n;i++){ if(data[i]<temp){ temp=data[i]; index=i; } } min=data[index]; return min; } float findmax(float data[],int n){/*寻找数据序列中的最大值*/ int index,i; float max,temp; temp=data[0]; for(i=1;i<n;i++){ if(data[i]>temp){ temp=data[i]; index=i; } } max=data[index]; return max; } void initial(int n,int count[],float low[],float high[],float min,float max){/*初始化区间*/ int i; for(i=0;i<n;i++){ count[i]=0; //区间是否有数据存入 low[i]=max; //将区间的左端赋值最大值 high[i]=min; //将区间的右端复制最小值 } } void dataIn(float m,int count[],float low[],float high[],int n,float data[],float min){/*将数据序列依次放入对应区间*/ int i,location; for(i=0;i<n;i++){ location=int((data[i]-min)/m)+1; //判断数据进入哪个区间:按照等分区间,数据与最小值的差与区间大小的比值+1就是区间编号 if(location==n) location--; count[location]++; //有数据存入,计数值加1 if(data[i]<low[location]) //如果数据比左端值小,则作为左端值 low[location]=data[i]; if(data[i]>high[location]) //如果数据比右端值大,则作为右端值 high[location]=data[i]; } } float findMaxGap(int n,float low[],float high[],int count[]){ /*找出最大间隙,整个问题的核心*/ /*函数说明*/ /*上面已经把对应数据放入相应的区间,在之前可以知道,总共有n-1区间,相应的只有n-2个值,那么就一定有一个区间不会有数据*/ /*因为最大值与最小值已经分别被设为最小区间的左端值和最大区间的右端值,所以中间的n-1区间只有n-2个值*/ /*那么可以想象,最大间隙肯定不会是在一个区间中,而一定是在空区间的两端, 最大间隙为空区间右边相邻区间的左端值空区间左边相邻区间的右端值;有可能有多个这种情况,找出最大就行了*/ int i; float maxgap,dhigh,temp; dhigh=high[1]; for(i=2;i<n;i++){ if(count[i]){ temp=low[i]-dhigh; if(maxgap<temp) maxgap=temp; dhigh=high[i]; } } return maxgap; } int main(){ float data[MAX]; int n,i=0; float min,max; float m,maxgap; float low[MAX],high[MAX]; int count[MAX]; scanf("%d",&n); for(i=0;i<n;i++) scanf("%f",&data[i]); min=findmin(data,n); max=findmax(data,n); m=(max-min)/(n-1); initial(n,count,low,high,min,max); dataIn(m,count,low,high,n,data,min); maxgap=findMaxGap(n,low,high,count); printf("%.1f",maxgap); system("pause"); return 0; }
感兴趣的朋友可以测试运行本文实例以加深理解。相信本文所述对大家C程序算法设计的学习有一定的借鉴价值。
本文向大家介绍C语言实现简单飞机大战,包括了C语言实现简单飞机大战的使用技巧和注意事项,需要的朋友参考一下 本文实例为大家分享了C语言实现飞机大战的具体代码,供大家参考,具体内容如下 定义四个函数实现飞机大战 作者的另一段代码:C语言实现空战游戏,也很棒,分享给大家: 以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持呐喊教程。
本文向大家介绍C语言实现最长递增子序列问题的解决方法,包括了C语言实现最长递增子序列问题的解决方法的使用技巧和注意事项,需要的朋友参考一下 本文实例展示了C语言实现最长递增子序列问题的解决方法。分享给大家供大家参考。具体方法如下: 问题描述: 给定一个序列,找出其最长递增子序列长度。 比如 输入 1 3 7 5 输出 3 算法解决思路: 利用动态规划的思想,以序列的每个点最为最右端,找出每个点作为
本文向大家介绍c语言来实现贪心算法之装箱问题,包括了c语言来实现贪心算法之装箱问题的使用技巧和注意事项,需要的朋友参考一下 装箱问题,贪心算法求近似最优解 以上就是本文的全部内容了,希望大家能够喜欢。
本文向大家介绍C语言 makefile学习及实现实例,包括了C语言 makefile学习及实现实例的使用技巧和注意事项,需要的朋友参考一下 C语言 makefile学习及实现实例 俗话说,不会写makefile的程序员不是好的程序员。 看了很多人写的makefile教程,感觉太难懂,还不如韦东山老师视频里讲的好理解。 先记下这几个符号,以后看到就不会忘记这是什么东西了。 先来看一个例子: 其中:
本文向大家介绍C语言实现九大排序算法的实例代码,包括了C语言实现九大排序算法的实例代码的使用技巧和注意事项,需要的朋友参考一下 直接插入排序 将数组分为两个部分,一个是有序部分,一个是无序部分。从无序部分中依次取出元素插入到有序部分中。过程就是遍历有序部分,实现起来比较简单。 折半插入排序 折半插入再直接插入上有改进,用折半搜索替换遍历数组,在数组长度大时能够提升查找性能。其本质还是从无序部分取出
本文向大家介绍C语言实现密码本,包括了C语言实现密码本的使用技巧和注意事项,需要的朋友参考一下 本文实例为大家分享了C语言实现密码本的具体代码,供大家参考,具体内容如下 功能简述: 1.账号登陆(密码验证,三次锁定账号) 2.功能选择:1、查看所有密码 2、新增密码 3、删除密码 4、修改密码 5、查询密码 6、解除锁定 7、退出登陆 3.保存密码,文件加密 4.流程图: 数据定义部分 界面与用户