/**
* 区间覆盖问题: 要求给定一组已经排好序数字,每个数字代表一个以其为起点的单位区间。
* 然后给定一个区间长度L, 要求能够覆盖到最多的单位区间,并且整个长度不超过L。
* 同时给出覆盖了哪些区间。比如L=5,{1,2,7,10,11,12,14,20,22,23},
* 能够覆盖最多10,11,12,14四个区间,覆盖长度长度为5 <= L。
*/
#include <stdio.h>
#define M 10 //单位区间数目
#define L 5 //区间长度
int a[M] = {1,2,7,10,11,12,14,20,22,23}; //排好序的数字(单位区间)
/**
* 返回最大能够括住的区间数目,要求括住的长度不超过L
*/
int find_maxLeval(){
int begin,end;
int gap_num,gap_v;
int max_leval_num = 0;
int l,r;
//使用两个指针,分别指向括住的区间的首尾
begin = end = 0;
while(end < M){
gap_num = end - begin + 1; //括住的区间数目
gap_v = a[end] - a[begin] + 1; //括住的区间长度
if(gap_v > L){ //如果长度超过了L,则向前移动begin指针
while(gap_v > L){
begin++;
gap_num = end - begin + 1;
gap_v = a[end] - a[begin] + 1;
}
}
else{ //如果长度未超过L,则看是否需要更新括住的区间数目
if(gap_num > max_leval_num){
max_leval_num = gap_num; //更新括住的区间数目
l = begin; //更新首指针
r = end; //更新尾指针
}
}
end++;
}
printf("l=%d,r=%d\n",l,r);
return max_leval_num;
}
int main(){
int max;
max = find_maxLeval();
printf("max=%d\n",max);
return 0;
}
运行结果:
分享到:
相关推荐
用Matlab进行最小二乘法线性拟合求传感器非线性误差灵敏度.pdf用Matlab进行最小二乘法线性拟合求传感器非线性误差灵敏度.pdf用Matlab进行最小二乘法线性拟合求传感器非线性误差灵敏度.pdf用Matlab进行最小二乘法线性...
线性时间选择,中位数算法,利用按每5个元素分组,分别找出其中位数,再递归找出
用c++实现的平均O(n)时间和最坏O(n)时间求数组中第i大的数
给定一个包含n个元素的一维线性序列a[p:r],从这n个元素中找出第k小的元素,1。设a[0:14]={2,9,11,3,14,7,10,8,15,4,13,1,6,5,12},k = 8,采用线性时间选择算法解决该问题。 1)写出算法实现代码并截屏程序运行结果...
山东科技大学计算方法实验二 非线性方程求根实验报告完整版,C语言编程+流程图+运行结果 进一步熟练掌握求解非线性方程的二分法与Newton迭代法。 掌握二分法与Newton迭代法的算法,能运用程序设计语言和此方法编制...
线性时间选择问题,采用不生成随机数的算法
算法之线性时间选择 文档包括详细的算法分析与代码示例
姚琦伟、范剑青编写的《非线性时间序列——建模、预报及应用》不仅对这些技术在时间序列状态空间、频域和时域等方面的应用给出了详细的介绍,同时,为了体现参数和非参数方法在时间序列分析中的整合性,还系统地阐述...
非线性方程的一般形式: f(x)=0 代数方程: f(x)=a0+a1x+……+...(1)找出有根区间;(只含一个实根的区间称隔根区间) (2)近似根的精确化。从隔根区间内的一个或多个点出发,逐次逼近,寻求满足精度的根的近似值。
Matlab非线性方程求根
排序算法的讲述。有关线性排序算法的讲述。
区间分析,又称区间数学,是一门用区间变量代替点变量进行运算的数学分支,本书主要介绍了用区间分析方法求解非线性方程的方法
非线性时间序列_范剑青_中文..................................................................................................................................
论文研究-区间数线性规划及其满意解.pdf, 针对目标函数和约束条件均为区间数的线性规划问题,通过对目标函数和约束条件分别处理,提出了一种基于模糊约束满意度的求解...
它基于KS二维检验统计量提出KS2D距离度量,是一种非参数的鲁棒性强的距离度量方式,它将时间序列的非线性相关结构放到距离度量之中,能够粗糙地识别时间序列形状和动态相关结构的相似性。与理论研究结果相一致,模拟...
对于区间[a,b]上连续不断且f(a)·f(b)的函数y=f(x),通过不断地把函数f(x)的零点所在的区间一分为二,使区间的两个端点逐步逼近零点,进而得到零点近似值的方法叫二分法。 算法:当数据量很大适宜采用该...
java 解决计算方法问题:非线性方程求根
分治策略 线性时间选择 分治策略 线性时间选择
算法分析与设计,,,,,,线性时间选择问题实验报告
分治策略 线性时间选择 分治策略 线性时间选择