C语言实现最大间隙问题实例

作者:无名 - C 语言 -

本文实例展示了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;
   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程序算法设计的学习有一定的借鉴价值。

IT人知识库 该篇知识地址:http://www.itpeo.net/12818/432987.html





C语言实现图的遍历之深度优先搜索实例

DFS(Depth-First-Search)深度优先搜索算法是图的遍历算法中非常常见的一类算法。分享给大家供大家参考。... ...

贪吃蛇游戏C++命令行版实例代码

本文实例讲述了贪吃蛇游戏C++命令行版的实现代码,是非常经典的游戏。分享给大家供大家参考。具体实现方法如下: 众所周知,... ...

C语言连续子向量的最大和及时间度量实例

本文实例分析了C语言连续子向量的最大和及时间度量,分享给大家供大家参考之用。具体方法如下: #include <... ...

C语言二叉树的非递归遍历实例分析

本文以实例形式讲述了C语言实现二叉树的非递归遍历方法。是数据结构与算法设计中常用的技巧。分享给大家供大家参考。具体方法如... ...

C语言的递归思想实例分析

本文实例分析C语言的递归思想,分享给大家供大家参考之用。具体方法如下: 通俗点来说,递归就是自己调用自己。 递归的难点一... ...

C语言创建链表错误之通过指针参数申请动态内存实例分析

本文实例讲述了C语言创建链表中经典错误的通过指针参数申请动态内存,分享给大家供大家参考之用。具体实例如下: #inc... ...

C语言实现带头结点的链表的创建、查找、插入、删除操作

本文实例讲述了C语言实现带头结点的链表的创建、查找、插入、删除操作。是数据结构中链表部分的基础操作。分享给大家供大家参考... ...

C程序读取键盘码的方法

本文以一个简单实例讲述了C程序读取键盘码的方法,分享给大家供大家参考。具体分析如下: 一般来说,键盘码在底层开发中经常会... ...

C语言中char*和char[]用法区别分析

本文实例分析了C语言中char* 和 char []的区别。分享给大家供大家参考之用。具体分析如下: 一般来说,很多人会... ...

rfedfre

Cocos2d-x中CCEditBox文本输入框的使用实例

文本输入框这个东西相信大家不论做什么游戏总会用到吧,今天我们就来看看这个东西如何使用。文本输入框同样属于扩展库中的内容,... ...

C语言实现最长递增子序列问题的解决方法

本文实例展示了C语言实现最长递增子序列问题的解决方法。分享给大家供大家参考。具体方法如下: 问题描述: 给定一个序列,找... ...

C语言金币阵列问题解决方法

本文实例详细讲述了C语言实现金币阵列问题的解决方法,分享给大家供大家参考。具体方法如下: 问题描述: 有m*n(1 ≤ ... ...

C语言实现计算树的深度的方法

本文实例讲述了C语言实现计算树的深度的方法。是算法设计中常用的技巧。分享给大家供大家参考。具体方法如下: /* *... ...

C语言实现找出二叉树中某个值的所有路径的方法

本文实例讲述了C语言实现找出二叉树中某个值的所有路径的方法,是非常常用的一个实用算法技巧。分享给大家供大家参考。 具体实... ...

C语言实现输入一个字符串后打印出该字符串中字符的所有排列

本文实例讲述了C语言实现输入一个字符串后打印出该字符串中字符的所有排列的方法,属于数学里的排列问题。是一个很实用的算法技... ...

C语言实现输入一颗二元查找树并将该树转换为它的镜像

本文实例讲述了C语言实现输入一颗二元查找树并将该树转换为它的镜像的方法,分享给大家供大家参考。具体实现方法如下: 采用递... ...

C语言实现输出链表中倒数第k个节点

本文实例展示了C++实现输出链表中倒数第k个节点的方法,分享给大家供大家参考之用。 运行本文所述实例可实现输入一个单向链... ...

Mac OS X 10.8 中编译APUE(Unix环境高级编程)的源代码过程

最近在温习APUE(《unix环境高级编程》),以前都是在linux下搞,现在打算在自己机器弄下,于是google了下,... ...

rfedfre

C程序实现整数的素数和分解问题

本文以实例形式讲述了C程序实现整数的素数和分解问题,分享给大家供大家参考之用。具体方法如下: 要求:对于一个给定的整数,... ...

C语言字符串原地压缩实现方法

本文实例讲述了C语言字符串原地压缩的实现方法,对于学习字符串操作的算法设计有不错的借鉴价值。分享给大家供大家参考。具体方... ...