首页 > 代码库 > POJ 1458 LCS 数组过小因编译器不同引发
POJ 1458 LCS 数组过小因编译器不同引发
按道理说LCS的问题应该讨论的很明白了,不应该出问题。昨天晚上手贱点开了暑期写的LCS滚动数组的代码。发现毫无逻辑错误。
但却是WA,用的C++,。于是随手换了个g++ 却手动把1-flag 与flag相比较输出最大,就AC
#include<stdio.h> #include <math.h> #include <string.h> #define N 2000 char str1[N]; char str2[N]; int dp[2][N]; int main() { int i,j,n,m,flag; while(scanf("%s %s",str1,str2)!=EOF) { memset(dp,0,sizeof(dp)); flag=1; for(i=1;i<=strlen(str1);i++) { for(j=1;j<=strlen(str2);j++) { if(str1[i-1] == str2[j-1]) dp[flag][j]=dp[1-flag][j-1]+1; else if(dp[flag][j-1]>dp[1-flag][j]) dp[flag][j]=dp[flag][j-1]; else dp[flag][j]=dp[1-flag][j]; } flag=1-flag; } printf("%d\n",dp[1-flag][j-1]); } return 0; }没想到是编译器的问题,依旧在纠结我的程序逻辑哪里有问题。使用了好几个方法去测试。
在这期间问了好多人,发现大家都是一个写的模板,很少思考各种不同之间的问题,包括一个大神。。。。。。总是用已经可以成功的方法套。都说这样写没错别想那个了。
1. 测试数据弄多点,每次输出两者,看什么情况下最优。//结果总是1-flag最优,说明这种思路没错。
2. 逆向分析,既然是最后两者判断输出最优,那么必然是两个数组中j-1这个位置的问题,那肯定是最后一个字符匹配成功才导致的(不成功就是复制flag的了)
但这逻辑上也是不同。。。。。
3. 在lj同学测试下,发现g++可以过
原来是数组开小了。。。。。。。。我擦,调了一晚上竟然这种结果,你要是re的话不早就好了???
C/C++不对内存越界检测,所以程序稀里糊涂越界,没被检测到。且g++ c++处理机制不同才导致。。。。
这个收获才是真多,,,,,,,
POJ 1458 LCS 数组过小因编译器不同引发
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。