首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > C++ >

编了个动态规划求最长公共子序列有关问题,lengthLCS函数中双重for循环中i总是不能到len1(崩了),调了一天没调出来,求编程高人指点!

2012-08-25 
编了个动态规划求最长公共子序列问题,lengthLCS函数中双重for循环中i总是不能到len1(崩了),调了一天没调出

编了个动态规划求最长公共子序列问题,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]; }
[解决办法]
耐心单步调试把

热点排行