`
hao3100590
  • 浏览: 131532 次
  • 性别: Icon_minigender_1
  • 来自: 成都
社区版块
存档分类
最新评论

关于序列的几个算法

阅读更多

1.求最小子序列的和

就是对于连续的序列,找出连续序列中和最小的

例如:int a[LEN] = {4,-1,5,-2,-1,2,6,-2,1,-3};

最小的子序列就是:-2,1,-3

对于下面的最大子序列就是:4,-1,5,-2,-1,2,6。

 

 

/**
	*最小子序列和
	*n
	*/
int subMinSum(int a[], int length){
	int thismin = 0, min = INT_MAX;
	for(int i=0; i<length; i++){
		thismin += a[i];
		if(thismin < min){
			min = thismin;
		}else if(thismin > 0){
			thismin = 0;
		}
	}
	return min;
}

 

 2.最大子序列的和,其思想和求最小是一样的

 

/**
	*最大子序列和
	*
	*/
int subMaxSum(int *a, int length){
	int thismax = a[0], max=INT_MIN;//注:此处修正了thismax = 0,因为全负数的时候返回0,这里初值设置为a[0]那么会返回最大负数
	for(int i=0; i<length; i++){
		thismax += a[i];
		if(thismax > max){
			max = thismax;
		}else if(thismax < 0){
			thismax = 0;
		}
	}
	return max;
}

 

 针对上面的两种算法,效率是比较高的,但是正确性不容易看出来,需要自己仔细的揣摩和证明,但是优点也很明显,就是对数据只需要一次的扫描,顺序读入,这对于大量数据来说是很有利的,只要全部读入数据就可以得出结果,这个在算法分析一书中叫做“联机算法(on-line algorithm)”,意思就是上面描述的,线性时间完成的联机算法基本上算法完美算法。

 

3.求最大子序列,并记录子序列位置

这里我们肯定很容易记录下最终的位置,就是不容易确定序列的起始位置,主要是由于该算法的特性,最后想了好久才想到用:减最大的值的方法,当等于0的时候就找到起始位置了,从而确定序列范围

 

#include <iostream>
using namespace std;

int maxsub(const int* a, int length, int* loc){
	//maxsum记录最大的值,thissum记录当前的值
	int maxsum=0, thissum=0, i=0;
	if(length <= 0) return 0;
	for(i=0; i<length; i++){
		thissum += a[i];
		if(maxsum < thissum){
			maxsum = thissum;
			loc[1] = i;
			//这里有一个思想就是,为负数的子序列不可能成为最优子序列的前缀,
		}else if(thissum < 0){
			thissum = 0;
		}
	}
	thissum = maxsum;
	for(i=loc[1]; i>=0; i--){
		thissum -= a[i];
		if(thissum == 0){
			 loc[0] = i;
			 break;
		}
	}
	return maxsum;
}

int main(){
	int a[] = {2, -3, 7, -4,-2,-2,6,-2};
	int loc[2]={0};
	cout<<maxsub(a, 8, loc)<<endl;
	cout<<"from:"<<loc[0]<<"---to:"<<loc[1]<<endl;
	return 0;	
}
 

 

 

4.最小正子序列和

这个是在一博客中看到的:http://blog.csdn.net/qq675927952/article/details/6790726

然后我有一个疑问就是,究竟什么是最小正子序列和?这个在网上找了也没有个好的答案(http://tengtime.com/a/gaoxingnenWEBkaifa/20120406/3217.html),如果哪位仁兄知道,不胜感激!!

对于下面求出的sum我也没搞的太清楚是为什么?然后又循环什么的?

 

struct Node  
{  
    int sum;  
    int xiabiao;  
      
};  
int cmp(const Node& t1,const Node& t2)  
{  
    return t1.sum < t2.sum;
} 

/**
	*最小正子序列和
	*n*logn
	*/
int positiveSubMinSum(int *data, int len){
	Node* temp = new Node[len];  
  temp[0].sum = data[0];  
  temp[0].xiabiao = 0;  
  for(int i=1;i<len;i++)  
  {  
    temp[i].sum = temp[i-1].sum+data[i];  
    temp[i].xiabiao = i;  
  }  
  //对temp.sum[]进行从小到大排序,sum[]中只有相邻的两个数才有可能 得到 最小正子序列和  
  sort(temp,temp+len,cmp);  
  int sum = INT_MAX;  
  for(int i=0;i<len-1;i++)  
  {  
    if(temp[i].xiabiao < temp[i+1].xiabiao)  
    {  
         if(temp[i+1].sum - temp[i].sum > 0 && temp[i+1].sum - temp[i].sum < sum)  
         sum = temp[i+1].sum - temp[i].sum;  
    }  
  }  
  delete temp;  
  temp=0;  
  return sum;  
}

  5.最大子序列的乘积

对网上的一些算法进行了下比较,发现这个算法还可以,比较简洁:http://blog.csdn.net/ztj111/article/details/1909339

对该算法的说明:

 

这个问题其实可以简化成这样:数组中找一个子序列,使得它的乘积最大;同时找一个

子序列,使得它的乘积最小(负数的情况)。虽然我们只要一个最大积,但由于负数的

存在,我们同时找这两个乘积做起来反而方便。

 

我们让maxCurrent表示当前最大乘积的candidate,minCurrent反之,表示当前最小乘积

的candidate。这里我用candidate这个词是因为只是可能成为新一轮的最大/最小乘积,

而maxProduct则记录到目前为止所有最大乘积candidates的最大值。

 

由于空集的乘积定义为1,在搜索数组前,maxCurrent,maxProduct,minCurrent都赋为1。

假设在任何时刻你已经有了maxCurrent和minCurrent这两个最大/最小乘积的candidates,

新读入数组的元素x(i)后,新的最大乘积candidate只可能是maxCurrent或者minCurrent

与x(i)的乘积中的较大者,如果x(i)<0导致maxCurrent<minCurrent,需要交换这两个

candidates的值。

 

当任何时候maxCurrent<1,由于1(空集)是比maxCurrent更好的candidate,所以更新

maxCurrent为1,类似的可以更新minCurrent。任何时候maxCurrent如果比最好的

maxProduct大,更新maxProduct。

 

 

void swap(int& a, int& b){
	 int temp = a;
	 a = b;
	 b = temp;
}

/**
	*最大子序列乘积(同时也求出了最小的子序列乘积)
	*在找最大的值得时候,必须记录最小值,因为有负数存在,最小的数可能变成最大的数
	*/
int mutiSubMax(int *a, int length){
	  int i;
    int maxProduct = 1;
    int minProduct = 1;
    int maxCurrent = 1;
    int minCurrent = 1;

    for( i=0; i<length ;i++)
    {
        maxCurrent *= a[i];
        minCurrent *= a[i];
        if(maxCurrent > maxProduct) 
            maxProduct = maxCurrent;
        if(minCurrent > maxProduct)
            maxProduct = minCurrent;
        if(maxCurrent < minProduct)
            minProduct = maxCurrent;
        if(minCurrent < minProduct)
            minProduct = minCurrent;
        //注意交换
        if(minCurrent > maxCurrent)
            swap(maxCurrent,minCurrent);
        //这个必须在最后(防止为0的时候)
        if(maxCurrent<1)
            maxCurrent = 1;
        //if(minCurrent>1)//这里不需要,因为通过交换即可,只需要一个
        //  minCurrent =1;
    }
    return maxProduct;
}
 

6.最长递增子序列
参考:

http://blog.csdn.net/hhygcy/article/details/3950158

http://www.programfan.com/blog/article.asp?id=13086

a,问题描述

L=<a1,a2,…,an>n个不同的实数的序列,L的递增子序列是这样一个子序列Lin=<aK1,ak2,…,akm>,其中k1<k2<…<kmaK1<ak2<…<akm。求最大的m

b,问题分析

最长递增子序列可以看成一个动态规划的问题,关于动态规划可以参见:

http://hi.baidu.com/hacklzt/blog/item/81e6b8fc795d251f09244de7.html

http://www.cnblogs.com/brokencode/archive/2011/06/26/2090702.html

其实质就是:将问题细化,逐步求解

当然实际的过程相对复杂些,就拿该题来说

如:子序列{1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 }这样一个字符串的的最长递增子序列就是{1,3,4,5,6,7}或者{1,3,4,5,6,19}。

首先,该问题可以抽象为:子序列为L(1..n),  A(1...i)是一个从1到i的优化的子结构,也就是最长递增子序列,求A(n)。

其次,根据上面的抽象,求的就是A(n), 那么问题就转化为求A(j)与A(1...i)(j>i)的关系(状态转移方程)。

最后,根据动态规划的概念,找的就是上面的这样一个关系,如何将A(j)与A(1...i)联系起来?从而将问题细化,L(j) = max {L(i), i<j && A(i)<A(j) } + 1

也就是说L(j)等于之前所有的L(i)中最大的的L(i)加一。这样的L(i)需要满足的条件就是A(i)<A(j).这个推断还是比较容易理解的.就是选择j之前所有的满足小于当前数组的最大值.

然后就是将上面的关系式转换为代码,这个就很简单了。

过程如下:


 

/**
	*最长递增子序列
	*
	*/
#include <iostream>
#include <cstring>
using namespace std;

//利用动态规划法O(n^2)
void longestIncreaseSub(int* a, int length, int* sub){
	int n = length;
	//利用一个辅助数列,记录子问题的值
	int *t = new int[n];//需要将t所有都初始化1,t记录子序列(子问题)的最长递增子序列长度
	int *p = new int[n];
	memset(p,0,sizeof(int));
	//初始的最大子序列长度默认为1,即自身组成一个最长递增子序列
	t[0]=1;
	for(int i=1; i<n; i++){
		t[i]=1;
		for(int j=0; j<i; j++){
			//这里面就是动态优化的状态转移方程
			if(a[j]<a[i] && t[j]>t[i]-1){
				//里面存的是(0到i)的子序列中最长递增子序列的长度
				t[i]=t[j]+1;
				//符合要求的子序列位置(就是上一个子序列中的最后一个值的位置)
				p[i]=j;
			}
		}
	}
	int m=0,k=0;
	for (int i=1;i<=n;i++)  
  {
     if (m<t[i])
     {//m存t中最大值(就是要找的最长递增子序列),i是其所在的索引
       m = t[i];  
       k = i;  
     }
  }
  while(m>=0){
  	sub[m-1] = a[k];
  	m--;
  	//p[k]中存着子序列中下一个值的下标位置
  	k = p[k];
  }
    
	for(int d=0; d<n; d++) cout<<t[d]<<" ";
	cout<<endl;
	for(int d=0; d<n; d++) cout<<p[d]<<" ";
	delete[] t;
	delete[] p;
	p = NULL;
	t = NULL;
}

int main(){
	int a[] = { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };  
	int length = sizeof(a)/sizeof(int);
	int* sub = new int[length];
	memset(sub,0,sizeof(int));//初始化sub
	
	longestIncreaseSub(a,length, sub);
	
	cout<<endl;
	for(int k=0; k<length; k++) cout<<sub[k]<<" ";
	delete[] sub;
	sub = NULL;
}
 

 

 

 

7.上面的1,2,4,5的代码全部

 

/**
	*2.17
	*求最小子序列和,最小正子序列和,最大子序列乘积
	*
	*/	
#include <iostream>
#include <algorithm>  
using namespace std;
#define INT_MIN -32768
#define INT_MAX 32767
//在里面有使用#define和const定义常量的比较,推荐使用const
//#define LEN 10
const int LEN = 10;

/**
	*最大子序列和
	*
	*/
int subMaxSum(int *a, int length){
	int thismax = 0, max=INT_MIN;
	for(int i=0; i<length; i++){
		thismax += a[i];
		if(thismax > max){
			max = thismax;
		}else if(thismax < 0){
			thismax = 0;
		}
	}
	return max;
}

/**
	*最小子序列和
	*n
	*/
int subMinSum(int a[], int length){
	int thismin = 0, min = INT_MAX;
	for(int i=0; i<length; i++){
		thismin += a[i];
		if(thismin < min){
			min = thismin;
		}else if(thismin > 0){
			thismin = 0;
		}
	}
	return min;
}

struct Node  
{  
    int sum;  
    int xiabiao;  
      
};  
int cmp(const Node& t1,const Node& t2)  
{  
    return t1.sum < t2.sum;
} 

/**
	*最小正子序列和
	*n*logn
	*/
int positiveSubMinSum(int *data, int len){
	Node* temp = new Node[len];  
  temp[0].sum = data[0];  
  temp[0].xiabiao = 0;  
  for(int i=1;i<len;i++)  
  {  
    temp[i].sum = temp[i-1].sum+data[i];  
    temp[i].xiabiao = i;  
  }  
  //对temp.sum[]进行从小到大排序,sum[]中只有相邻的两个数才有可能 得到 最小正子序列和  
  sort(temp,temp+len,cmp);  
  int sum = INT_MAX;  
  for(int i=0;i<len-1;i++)  
  {  
    if(temp[i].xiabiao < temp[i+1].xiabiao)  
    {  
         if(temp[i+1].sum - temp[i].sum > 0 && temp[i+1].sum - temp[i].sum < sum)  
         sum = temp[i+1].sum - temp[i].sum;  
    }  
  }  
  delete temp;  
  temp=0;  
  return sum;  
}

void swap(int& a, int& b){
	 int temp = a;
	 a = b;
	 b = temp;
}

/**
	*最大子序列乘积(同时也求出了最小的子序列乘积)
	*在找最大的值得时候,必须记录最小值,因为有负数存在,最小的数可能变成最大的数
	*/
int mutiSubMax(int *a, int length){
	  int i;
    int maxProduct = 1;
    int minProduct = 1;
    int maxCurrent = 1;
    int minCurrent = 1;

    for( i=0; i<length ;i++)
    {
        maxCurrent *= a[i];
        minCurrent *= a[i];
        if(maxCurrent > maxProduct) 
            maxProduct = maxCurrent;
        if(minCurrent > maxProduct)
            maxProduct = minCurrent;
        if(maxCurrent < minProduct)
            minProduct = maxCurrent;
        if(minCurrent < minProduct)
            minProduct = minCurrent;
        //注意交换
        if(minCurrent > maxCurrent)
            swap(maxCurrent,minCurrent);
        //这个必须在最后(防止为0的时候)
        if(maxCurrent<1)
            maxCurrent = 1;
        //if(minCurrent>1)//这里不需要,因为通过交换即可,只需要一个
        //  minCurrent =1;
    }
    return maxProduct;
}

int main(){
	int a[LEN] = {4,-1,5,-2,-1,2,6,-2,1,-3};
	cout<<"列表:"<<endl;
	for(int i=0; i<10; i++){
		cout<<a[i]<<" ";
	}
	cout<<endl;
	cout<<"最大子序列和:"<<subMaxSum(a, LEN)<<endl;
	cout<<"最小子序列和:"<<subMinSum(a, LEN)<<endl;
	cout<<"最小正子序列和:"<<positiveSubMinSum(a, LEN)<<endl;
	cout<<"最大子序列乘积:"<<mutiSubMax(a, LEN)<<endl;
	return 0;
}

 

 

  • 大小: 35 KB
分享到:
评论

相关推荐

    深度搜索+递归实现银行家算法安全序列全搜索算法实现代码.doc

    银行家算法的实现代码主要包括以下几个部分: 1. 资源数 resourceNumber:表示系统中可用的资源数。 2. 进程数 processNumber:表示系统中存在的进程数。 3. 可用资源数组 Available:表示系统中可用的资源数组。 4...

    生物序列分析中几个典型算法介绍

    ### 生物序列分析中几个典型算法介绍 #### 生物信息学研究背景与方向 生物信息学是一门跨学科的研究领域,它将生物学、计算机科学、数学以及统计学等多领域的知识和技术融合在一起,用于解决生物学中的复杂问题。...

    序列比对算法综述(有兴趣的看看)

    本文旨在概述几种主流的序列比对算法,并对其特点和应用场景进行深入探讨。 #### 二、双序列比对 ##### 2.1 Smith-Waterman算法 Smith-Waterman算法是一种局部比对算法,最初由Smith和Waterman在1981年提出。该...

    流聚类序列算法

    在"记录本序列中所占总位数, 即项集数*每个Itemset对象的weight值"这一描述中,我们可以解读出几个关键概念。 1. **数据流**:数据流是指源源不断地、连续到达的数据,这些数据通常无法全部存储,需要在有限的计算...

    数据挖掘之序列模式挖掘之GSP算法

    为了优化GSP算法,可以从以下几个方面着手: 1. **并行化处理**:利用多核处理器或者分布式计算框架,将GSP的各个阶段并行化,以加速计算。 2. **数据预处理**:对原始数据进行编码和降维,减少计算复杂性。 3. **...

    时间序列算法java实现

    3. **自回归模型(Autoregressive Model, AR)**:基于过去几个时刻的残差来预测未来值。 4. **滑动平均模型(Moving Average Model, MA)**:预测值为过去一段时间内的随机误差的加权和。 5. **自回归积分滑动平均...

    java序列化原理与算法

    Java序列化的基本流程可以分为以下几步: 1. **类信息描述**:首先输出子类的类信息描述。 2. **字段信息描述**:接着描述子类中的字段信息。若字段为对象类型,则暂时用字符串指针表示。 3. **父类信息描述**:...

    ARIMA时间序列算法预测完整包

    在实际应用中,ARIMA模型的构建包括以下几个步骤: 1. **数据探索**:分析时间序列的特性,如趋势、季节性和周期性。 2. **平稳性检验**:通过ADF(Augmented Dickey-Fuller)检验等方法判断序列是否平稳,如果不...

    论文研究-基于跳跃轨道的数字序列混沌加密算法 .pdf

    其核心思想在于将加密序列映射到几个不同的周期轨道上,并通过另一个非线性系统迭代周期轨道的系统参数来获取一个短序列,这个短序列则作为重建这些周期轨道的密钥。这种映射和迭代过程大大增加了私密信息的抗破译性...

    祖冲之序列密码算法.zip

    但是一般来说,这类算法会包含以下几个步骤: 1. **密钥生成**:首先,需要一个足够长的初始密钥(也称为种子)来启动算法。这个初始密钥必须是随机的,并且需要保持秘密,因为它直接关系到整个加密系统的安全性。 ...

    基于多目标决策的时间序列数据挖掘算法仿真.pdf

    基于多目标决策的时间序列数据挖掘算法主要分为以下几个步骤: 1. 数据预处理:首先,需要对时间序列进行预处理以消除噪声。噪声是时间序列数据挖掘中的一个主要障碍,它可能会掩盖真实的信号并影响结果的准确性。...

    最长公共子序列的动态规划算法

    5. 测试案例:列出几个测试用例,展示算法的正确性和效率。 6. 结果分析:对实验结果进行解读,讨论算法的优缺点,以及可能的优化方向。 7. 结论:总结实验的主要发现,强调动态规划在解决LCS问题上的有效性。 在...

    prefixspan序列模式挖掘算法的源代码

    源代码通常分为以下几个关键部分: 1. **数据结构**:设计合适的数据结构存储序列数据库,如基于前缀树的数据结构,以便高效地进行模式扩展和支持度计算。 2. **序列处理**:读取和解析输入的序列数据库,将其转化...

    基于MATLAB的混沌序列图像加密算法的研究的开题报告.pdf

    本研究的设计内容主要包括以下几个方面: 1. 混沌序列图像加密算法的原理和实现 2. MATLAB平台下的混沌序列图像加密算法的设计和实现 3. 混沌序列图像加密算法的安全性和性能分析 四、开发环境 本研究使用MATLAB...

    一种实序列FFT新算法与C语言实现

    该算法的C语言实现涉及以下几个关键步骤: 1. **初始化**:定义必要的变量和数组,包括用于存储旋转因子的数组。 2. **转换为复数序列**:根据上述转换公式,将实数序列转换为复数序列。 3. **执行FFT**:调用...

    非线性规划的序列二次规划(SQP)算法Matlab程序

    在Matlab环境中实现SQP算法,通常需要以下几个关键步骤: 1. **建立目标函数和约束条件**:首先,你需要定义非线性目标函数和约束条件。这可以通过编写Matlab函数来完成,目标函数应返回函数值,而约束条件可以是...

    算法-最长公共子序列-LCS

    总结起来,解决LCS问题的动态规划算法包括以下几个步骤: 1. 初始化二维数组c和b。 2. 填充c数组,同时记录b数组。 3. 计算c[m][n],得到LCS的长度。 4. 使用b数组回溯,构造LCS。 这种方法的时间复杂度为O(mn),...

    序列二次规划算法 matlab实现,内附例子

    MATLAB中的SQP实现,如`sqpm`,可能包含以下几个关键步骤: 1. **初始化**:算法开始时,需要设定初始解、目标函数、约束条件以及优化参数。初始解通常是问题的可行区域内的任意一点,而目标函数和约束条件则是问题...

    序列优化算法改写

    在改写这些算法时,关键要考虑以下几点: - **效率优化**:通过合理选择样本对,可以减少迭代次数,例如使用近似最近邻搜索。 - **并行计算**:如果硬件支持,可以尝试将SMO算法并行化,以利用多核处理器的优势。 - ...

Global site tag (gtag.js) - Google Analytics