- 浏览: 128789 次
- 性别:
- 来自: 成都
最新评论
-
yi_chao_jiang:
你好,多谢分享,问个问题,在上传数据的时候判断文件是否有上传记 ...
断点续传和下载原理分析 -
a41606709:
为什么我的tabhost显示不出来? 怎么设置在全部页面中让他 ...
TabActivity中的Tab标签详细设置 -
Zero颴:
大神篇,思路,配图都很清晰,perfect!
Android事件模型之interceptTouchEvnet ,onTouchEvent关系正解 -
QAZ503602501:
牛死人了!!!
B-树 -
mengsina:
很牛的文档。数学功底好啊
Android Matrix理论与应用详解
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<…<km且aK1<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; }
发表评论
-
排序方法总结
2012-08-12 11:34 1133这里面包含了所有常见的排序操作 1.性能等比较分析 2 ... -
常见字符串操作大全
2012-08-12 11:34 14221.常见的字符串操作 如计算长度,求子串等都是考验基本功的, ... -
KMP算法解析
2012-08-12 11:35 2775一.理论基础 1.什么 ... -
二叉堆的实现
2012-08-12 11:35 11741.堆的概念 这里只需要注意两点: a.堆的存储方式:就是 ... -
set和map的简单实现
2012-08-10 11:35 12791.Set的简单实现 set是利用二叉查找树来实现的,而且为 ... -
红黑树的插入总结
2012-08-10 11:25 9161.红黑树 这个在july的博客中有详尽的说明,我就不在赘述 ... -
B-树实现
2012-08-10 11:03 15901.什么是B-树? 这个在我的前一篇博客中已经详细的阐释过: ... -
平衡二叉树
2012-08-10 10:39 27961.问题描述 什么是平衡 ... -
二叉排序树
2012-08-10 10:25 14201.基本概念 二叉排 ... -
B-树
2012-07-04 22:48 56181.B-树的概念 是一种多 ... -
构造哈夫曼树
2012-07-04 10:40 11891.算法说明 就是建造哈夫曼树树,从而使得构造出的树带权路径 ... -
线索二叉树
2012-07-04 09:20 12391.算法描述 就是简单的线索二叉树的建立,遍历,查找等基本操 ... -
二叉树基本操作大全
2012-07-03 18:22 25581.二叉树的基本操作 这里我有一个疑问: 在使用构造 ... -
多种队列的实现
2012-06-29 10:09 14951.算法描述 a.数据结构与算法(Mark Allen We ... -
栈的各种实现
2012-06-28 16:34 10781.算法描述 a.实现二个栈,在一个数组里面,除非没有任何空 ... -
中缀表达式转换为后缀
2012-06-28 11:10 17551.算法描述 例如a+b*c这是常见的中缀表达式,但是 ... -
后缀表达式的值
2012-06-27 16:33 12901.算法描述 计算后缀表达式的值 2.事例 如:( ... -
Josephus问题
2012-06-21 15:30 9561.算法描述 简单的游戏:有N个人坐成一圈,编号1-N、从编 ... -
关于最长递增子序列的实际应用--动态规划
2012-06-07 11:35 1791参考链接: a.http://www.programfan. ... -
线性查找二维数组
2012-06-05 17:23 10031.算法描述 有序(行有序,列有序,且每行从左至右递增 ...
相关推荐
生物序列分析中几个典型算法介绍
基于跳跃轨道的数字序列混沌加密算法,宋静华,,本文提出一种利用混沌轨道跳跃特性的加密算法,加强私密信息的抗破译性。该方法将加密序列映射至几个不同的周期轨道,然后通过另
对于不确定数据的频繁序列模式挖掘,会导致可能频繁模式数量的指数级出现,其中有些无用的挖掘结果...为了减少搜索空间与避免冗余的计算,应用了几个剪枝与边界技术。U-FCSM算法的有效性与效率通过大量的实验得以表明。
1、常见排序算法实现(1-6选择几个算法练习) 1)问题描述:输入一组关键字序列分别实现下列排序。 (1)实现简单选择排序、直接插入排序和冒泡排序。 (2)实现希尔排序算法。 (3)实现折半插入排序。 ...
AntroPy 是一个 Python 3 包,提供了几种用于计算时间序列复杂度的高效算法。例如,它可以用于从 EEG 信号中提取特征。 更多详情、使用方法,请下载后阅读README.md文件
由于这个问题能运用学过的基本的算法分析和设计的方法与思想,能够锻炼设计较复杂算法的思维,我对这个问题进行了较深入的分析思考,得出了几种复杂度不同算法,并给出了分析和证明。 最长递增子序列问题的描述 设...
实验1 最大公约数(包括连续整除、欧几里得、分解质因数算法) 实验2 最近对问题(包括蛮力算法和分治算法) 实验3 最长公共子序列(包括动态规划法)...以上几个实验基本上都是采用不同的算法实现,所有代码均为原创。
掌握内存管理的页面淘汰算法 输入可用内存页面数和一个作业访问逻辑页号的序列,分别给存FIFO、LRU算法的缺页中断率 LRU OPT FIFO
银行家算法是从当前状态出发,逐个按...若这个时候操作系统还有3个资源,无论P这一次申请几个资源,操作系统都可以满足他,因为操作系统可以保证P不死锁,只要他不把剩余的资源分配给别人,进程P就一定能顺利完成任务。
每个变量只需要几个字节的内存,提供最先进的压缩率,并且可以在单个线程中以多 GB/s 的速度解压缩。 有关详细信息,请参阅。复制结果要重现论文中的任何结果,您可以执行以下操作。安装依赖项 - 用于缓存函数输出 ...
压缩包包含几十个文档,几十种常用的算法,还有数据建模,非常详细 压缩包pdf文档如下: 十大算法讲义.pdf 排队模型.pdf 数学建模算法全收录.pdf 数学建模算法大全.pdf 算法大全第01章__线性规划.pdf 算法大全第02章...
第6章到第9章分别给出了几个领域的算法,如序列和集合的算法(排序、序列比较、匹配等)、几何算法(凸包和交集问题等)、代数和数值算法(矩阵乘法、快速傅里叶变换等);第10章涉及归约或约简,也是第11章的序幕,...
(2)对下列就绪进程序列分别使用上面的几种算法进行调度,计算每种算法下的平均周转时间和平均带权周转时间。 进程号 到达时间 要求执行时间 0 0 1 1 1 35 2 2 10 3 3 5 4 6 9 5 7 21 6 9 35 7 11 23 8 12 42 9 13 ...
第6章到第9章分别给出了几个领域的算法,如序列和集合的算法(排序、序列比较、匹配等)、几何算法(凸包和交集问题等)、代数和数值算法(矩阵乘法、快速傅里叶变换等);第10章涉及归约或约简,也是第11章的序幕,...
1、插入、冒泡、选择、堆、快速、基数排序算法;2、使用C++写的;3、欢迎大家下载。
搜索网上这两个任务相关的项目,发现一个痛点:项目太单一,不够系统化,这里的系统化是说涵盖理论介绍,高效的算法实现,到工程化的 server 以及可视化 web 界面(通常一个算法从研究到落地必经的几个环节)。
这是一次上机作业,是算法导论上机,涵盖几个比较重要的算法
★算法领域的标准教材,全球多所知名大学选用 ★MIT名师联手铸就,被誉为“计算机算法的圣经” ★编写上采用了“五个一”,即一章介绍一个算法、一种设计技术、一个应用领域和一个相关话题。 以相当的深度介绍...
第6章到第9章分别给出了4个领域的算法,如序列和集合的算法、图算法、几何算法、代数和数值算法;第10章涉及归约,也是第11章的序幕,而后者涉及NP完全问题;第12章则介绍了并行算法;最后是部分习题的答案及参考...
1.ICEEMDAN用于数据分解,SMA是近几年较为新颖的黏菌优化算法,具有收敛速度快、寻优能力强等优点,用于优化SVM的两个参数sig和gamma,效果非常好。附赠未分解的SMA-SVM进行对比,对比效果明显,显著优于未分解的...