求最长公共子序列的长度,递归法,求找错

C++语言 码拜 8年前 (2016-04-21) 870次浏览
#include<iostream>
#include<string>
using namespace std;
string s,s1;
int lens,lens1;
int LCS(int i,int j)
{
if(i>=lens||j>=lens1)
return 0;
if(s[i]==s1[j])
return 1+LCS(i+1,j+1);
else
return LCS(i+1,j)>LCS(i,j+1)?LCS(i+1,j):LCS(i,j+1);
}
int main()
{
int N;
cin>>N;
if(0<N&&N<100)
{
for(int i=0;i<N;i++)
{
cin>>s;
if(s.length()<=1000)
{
for(int j=0,k=s.length()-1;j<s.length();j++,k–)
s1[j]=s[k];
lens=s.length();
lens1=s1.length();
int l=LCS(0,0);
cout<<lens-l<<endl;
}
}
}
}
解决方案

80

“给定一个小点的输入,完整单步跟踪(同时按Alt+7键查看Call Stack里面从上到下列出的对应从里层到外层的函数调用历史)一遍。”是理解递归函数工作原理的不二法门!
递归函数关注以下几个因素
·退出条件
·参数有哪些
·返回值是什么
·局部变量有哪些
·全局变量有哪些
·何时输出
·会不会导致堆栈溢出

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明求最长公共子序列的长度,递归法,求找错
喜欢 (0)
[1034331897@qq.com]
分享 (0)