分享
 
 
 

关于一维模式识别的快速解决方案.

王朝java/jsp·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

问题原型:给定一个一维向量,向量的值为正数或者负数,我们假定没有0(有0也没所谓,只是没什么意义),问哪一段向量的值和为最大? array arr[0...n] 存在 sum(arr[i]...arr[j]) is max!其中i,j属于[0,n].

1.我尝试解决该问题的方法:

首先,引进两个数据结构:

a.struct Meta{ //记录可操作的某个元素

int val; //从这个位置到下一个Meta的StartPos之间的原向量的值之和

int startpos; //该值对应的原向量段的起始位置.

};

b.struct MaxRec{ //记录某个可能成为最大值的位置和值信息.

int startpos;

int endpos;

int val;

};

c.采用栈或队列的工作方式

d.采用预先格式化的数据信息:+ - + - + -......+ 即,使得可操作的数据信息成正负交替出现的 形式,这样有利于我们对数据的判断.当然第一个数据或者最后一个数据如果是负数的话,肯定是我们 舍弃的对象,这样最后出现的结果将是两端都是正数,格式化的过程就是把相连续的同号数累加在一 起,最终使得出现上面 的交替现象.

2.操作过程:

我们假设一次连续出现的三个值为o,p,q.其中o,q为正数,p为对应的负数的绝对值(相反数,因为一定是负数).

对于o,p,q的不同大小关系可以列出下列情况,采用相对应的处理方式:

a.o<p<q 或 o<q<p :留下q,舍弃o,p.即最大的值一定从q开始.进行下面的重复计算

b.p<o<q 或 p<q<o :a+b+c作为一个整体成为一个Meta进入下一个重复计算.即因为p是最小的,故他 们之和肯定比当中的任何一个正数都大,故如此处理.

c.q<o<p :保存一个可能的最大值,那就是o.然后从q开始进行下面的计算,从q开始以后有 可能出现更大的最大值.但他们已不可能捆在一起,因为o+p<0,对q以后的数据不利,故如此处理,以后 得到更大的值时对最大值进行更新即可.

d.q<p<o :同样o可能成为最大值,保存这个最大值,并且把o+p+q作为一个新的Meta,进入 下一次的计算,之所以让o+p+q进入,是因为o+p>0,他对q来说是有利的,因此这样处理.

上面的四种情况可以总结成三种情况:

一.综合b和d:如果o>p,那么肯定加和,而如果p>q那么o可能时最大值.

二.综合a和c:如果o<p,那么肯定舍弃o,p.而如果q<o,那么o可能成为最大值.

3.之所以使用栈来处理Meta(存放Meta的栈),是因为计算的过程中要合并Meta,这样的话,Meta数组就是动态的,而不是静态的,所以用栈比较合适,虽然栈也是数组,但毕竟抽象.

4.记得处理边界情况,也就是说,你应该处理栈是否已经到顶了,以下已经没有正数了

5.可以考虑算法从两端向中间计算的模式,可能会出现高效率的美事,不过仅供参考.

------------------------------------------------------------------------------

------------------------------------------------------------------------------

其中遇到的问题记录(可以不看):

1.判断两个数是否异号:a*b<0的话异号,a*b>0的话同号,但是乘法是很没效率的,可以设计以下方法:

(a^b&0x80000000) == 0同号,否则异号.

注意:&的优先级比^的要高,所以上式应该写成:(a^b)&0x8000000000 == 0

2.最大值与最小值之间:任何一个最大值加上1都会得到最小值,我们通常所说的位数包括符号位,例如4位整数能表达的范围是-8~7,区间是16为2的4次方,显然最大正数是0111为7,最大负数(绝对值)是0111+1=1000,因为第一个为符号位,因此他是-8,取一个正数的相反数,就是让符号位参加运算:取反+1,当然对于最大的正数取反的话正好是最小的负数,因此负数的绝对值最大永远都比正数最大值多1.

------------------------------------------------------------------------------

------------------------------------------------------------------------------

事实证明我的想法是对的:我用了不到O(2n)的时间解决了这个所谓的立方问题.--O(n3)

代码已经变得非常简单(Java描述):

public class Test {

int[] vec = {31,-41,59,26,-153,58,97,-93,-23,84,-43,108}; //初始数组

int startpos; //第一个正数起始位置

int endpos; //最后一个正数结束位置

/**

* 构造函数

*/

public Test() {

}

/**

* 测试函数

* @param args

*/

public static void main(String[] args) {

Test test = new Test();

Object[] arrMeta = test.prepare(test.vec);

MaxRec mres = test.excute(arrMeta);

System.out.print(mres);

}

/**

*准备数据,把连续的正数或者负数都写在一起

* @param vec

* @return

*/

public Object[] prepare(int[] vec){

ArrayList arrList = new ArrayList();

int conint = Integer.MIN_VALUE;

int sum=0; //当前累加和

/*寻找正确的位置

*/

startpos=0;

endpos=vec.length-1;

while(vec[startpos]<0) startpos++;

while(vec[endpos]<0) endpos--;

/*开始处理

*/

Meta aMeta = new Meta(startpos,0);

for(int i=startpos;i<=endpos;i++){

if(sum==0 || ((sum^vec[i])&conint) == 0) { //同号

sum += vec[i];

}else{

aMeta.value = sum;

arrList.add(aMeta);

aMeta = new Meta(i,0);

sum = 0;

i--;

}

}

aMeta.value = sum; //最后一次数据

arrList.add(aMeta);

return arrList.toArray();

}

/**

* 处理过程,找出最大值的方法

* @param arrMeta

*/

public MaxRec excute(Object[] arrMeta){

//通过我们的prepare处理之后,必然出现正-负-正的元素排列,也就是说,o>0,p<0,q>0

MaxRec mr = new MaxRec(0,0,0);

Meta o;

Meta p;

Meta q;

int i = 0;

while(i<arrMeta.length){ //直到处理完最后一个元素为止

o = (Meta)arrMeta[i];

if(i+1 >= arrMeta.length){ //数组越界处理

p = new Meta(endpos+1,0);

}else{

p = (Meta) arrMeta[i+1];

}

if(i+2 >= arrMeta.length){ //数组越界处理

q = new Meta(endpos+1,0);

}else{

q = (Meta) arrMeta[i+2];

}

// 一.如果o>p,那么肯定加和,而如果p>q那么o可能时最大值.

// 二.如果o<p,那么肯定舍弃o,p.而如果q<o,那么o可能成为最大值.

if(o.value > -p.value){

if(-p.value >= q.value && mr.value < o.value ){

mr.value = o.value;

mr.startpos = o.startpos;

mr.endpos = p.startpos;

}

q.value += o.value+p.value;

q.startpos = o.startpos;

}else{

if(q.value < o.value && mr.value < o.value){

mr.value = o.value;

mr.startpos = o.startpos;

mr.endpos = p.startpos;

}

}

i += 2;

}//while loop

return mr;

}

}

/**

*保存各个节点的类,即正负相间的各个元素.

*/

class Meta{

public int value; //单元值

public int startpos; //单元起始位置(数组中位置)

public Meta(int startpos,int value){

this.value = value;

this.startpos = startpos;

}

public String toString(){

return value+" "+startpos;

}

}

/**

* 保存最大值信息的类.

*/

class MaxRec{

public int startpos; //起始位置(数组中位置)

public int endpos; //终止位置(数组中位置)

public int value; //最大值

public MaxRec(int s,int e,int v){

this.startpos = s;

this.endpos = e;

this.value = v;

}

public String toString(){

return "from "+startpos+" to "+endpos+":max-value="+value;

}

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有