编了个动态规划求最长公共子序列问题,lengthLCS函数中双重for循环中i总是不能到len1(崩了),调了一天没调出来,求编程高人指点!!!
#include<iostream>
#include<cstdlib>
#include<cstring>
using namespace std;
//seeking the longest commen subsequence
int lengthLCS(string &s1, int len1, string &s2, int len2, int **b);
//print the longest commen subsequence
void printLCS(string &s1, int len1, int len2, int **b );
int main()
{
//define to string to input
string s1,s2;
//the length of the strings
int len1,len2;
//the length of the longst commen subsequence
int length = 0;
while(cin >> s1 >> s2)
{
len1 = s1.length();
len2 = s2.length();
//create dynamic two-dimentional array
//to sign the searching direction
int **b = new int *[len1 + 1];
for(int i = 0; i < len1; i ++)
{
b[i] = new int[len2 + 1];
}
length = lengthLCS(s1, len1, s2, len2, b);
cout << "the length of the longest commen sunsequence: " << length;
cout << endl;
cout << "the longest commen subsequence: ";
printLCS(s1, len1, len2, b);
cout << endl;
//release the dynamic two-dimentional array
for(int i = 0; i < len1 + 1; i ++)
{
delete[] b[i];
}
delete[] b;
}
system("pause");
return 0;
}
int lengthLCS(string &s1, int len1, string &s2, int len2, int **b)
{
//to store the length of the LCS
int length = 0;
//create a dynamic two-dimentional array
//to sign the length of the LCS
int **c = new int*[len1 + 1];
for(int i = 0; i < len1 + 1; i ++)
{
c[i] = new int[len2 + 1];
}
//initialize the zero line and low of two-dimentional array c by zero
for(int i = 0; i < len1 + 1; i ++)
{
c[i][0] = 0;
}
for(int j = 0; j < len2 + 1; j ++)
{
c[0][j] = 0;
}
//calculate the length of the LCS c[][]
//sign the searching diretion b[][]:
//0 present that s1[i] = s2[j]
//1 present that s1 != s2 and we should search between s1(1~i-1) and s2(1~j)
//2 present that s1 != s2 and we should search between s1(1~i) and s2(1~j-1)
for(int i = 1; i <= len1; i ++)
{
for(int j = 1; j <= len2; j ++)
{
if(s1[i - 1] == s2[j - 1])
{
c[i][j] = c[i - 1][j - 1] + 1;
b[i][j] = 0;
}
else if(c[i][j - 1] > c[i - 1][j])
{
c[i][j] = c[i][j - 1];
b[i][j] = 2;
}
else
{
c[i][j] = c[i - 1][j];
b[i][j] = 1;
}
}
}
length = c[len1][len2];
//release the dynamic two-dimentional array
for(int i = 0; i <= len1; i ++)
{
delete[] c[i];
}
delete[] c;
return length;
}
//recursion thoughts (递归思想)
void printLCS(string &s1, int len1, int len2, int **b)
{
if(len1 == 0 || len2 == 0)
{
return;
}
//sign the searching diretion b[][]:
//0 present that s1[i] = s2[j]
//1 present that s1 != s2 and we should search between s1(1~i-1) and s2(1~j)
//2 present that s1 != s2 and we should search between s1(1~i) and s2(1~j-1)
if(b[len1][len2] == 0)
{
//需要先输出前面的字符,所以先递归然后再输出
printLCS(s1, len1 - 1, len2 - 1, b);
cout << s1[len1 - 1];
}
else if(b[len1][len2] == 1)
{
printLCS(s1, len1 - 1, len2, b);
}
else
{
printLCS(s1, len1, len2 - 1, b);
}
}
[解决办法]
还没学动态规划,如果用Lingo可不可以。
[解决办法]
数组越界,b数组创建的时候应该是
- C/C++ code
int **b = new int *[len1 + 1];for(int i = 0; i < len1[color=#FF0000] + 1[/color]; i ++){b[i] = new int[len2 + 1]; }
[解决办法]
耐心单步调试把