project2.cpp

最长递增序列和最长公共递增子序列的实现

#include <iostream>
#include <cstring>
#include <string>
#include <cctype>
using namespace std;
#define MAX 100

//参考<<计算机算法设计与分析>>

void printLCS(int i,int j,string x,int b[][MAX])
{
    if(i < 0 || j < 0)
        return ;
    if(b[i][j] == 1)
    {
        printLCS(i - 1,j - 1, x, b);
        cout << x[i-1];
    }
    else if(b[i][j] == 2)
        printLCS(i - 1,j,x,b);
    else printLCS(i,j-1,x,b);
}

void LCS(string x,string y)
{
      int lenx,leny;
      int i,j;
      int c[MAX][MAX];
      int  b[MAX][MAX];
      lenx = x.length();
      leny = y.length();

      for(i = 0; i <= lenx; i++)
        c[i][0] = 0;
      for(j = 0; j <= leny; j++)
        c[0][j] = 0;
        
      for(i = 1; i <= lenx; i++)
        for(j = 1; j <= leny; j++)
        {
            if(x[i-1] == y[j-1])
            {
                c[i][j] = c[i-1][j-1] + 1;
                b[i][j] = 1;
            }
            else if(c[i-1][j] >= c[i][j-1])
            {
                c[i][j] = c[i-1][j];
                b[i][j] = 2;
            }
            else
            {
                c[i][j] = c[i][j-1];
                b[i][j] = 3;
            }
        }
      cout << "The longest common length is " << c[lenx][leny] << endl;
      cout << "The longest common subsequence is: ";
      printLCS(lenx,leny,x,b);
      cout << endl;
}

void LIS()
{
    int a[MAX],b[MAX];
    int i,j,k,n;
    cout << "input your sequence length: " ;
    cin >> n;
    cout << "input the sequence: ";
    for(i = 0; i < n; i++)
        cin >> a[i];
    for(i = 1,b[0] = 1; i < n; i++)
        for(j = 0,k = 0; j < i; j++)
        {
            if(a[j] < a[i] && k < b[j])
                k = b[j];
            b[i] = k + 1;
        }
    int len = 0;
    k = 0;
    for(i = 0; i < n; i++)
        if(b[i] > len)
        {
            len = b[i];
            k = i;
        }
    cout << "The longest incresing subsequence length is: " << len << endl;
    int out[MAX],nj = k,ni;
    out[len] = a[k];
    k = len;
   // for(i = 0; i < n; i++)
    //    cout << b[i] << " "; cout << endl;
    while(len > 1)
    {
        --len;
        for(i = 0; i < nj; i++)
        {
            if(b[nj] >= b[i] && b[i] == len)
            {
                out[len] = a[i];
                ni = i;
            }
        }
        nj = ni;
    }

    cout << "The longest increasing subsequence is : " ;
    for(i = 1; i <= k; i++)
        cout << out[i] << " ";
    cout << endl;
}
void LCIS(string x,string y)
{

}
void printhelp()
{
    cout << endl;
    cout << "请输入你要运行的计算：" << endl;
    cout << "1.求最长公共子序列: " << endl;
    cout << "2.求最长递增子序列: " << endl;
    cout << "3:求最长公共递增子序列：" << endl;
    cout << "4.退出" << endl;
}
int main()
{
    char choice;
    string x,y;
    while(true)
    {
        printhelp();
        cin >> choice;
        switch(choice)
        {
            case '1':
                cout << "input the first string:";
                cin >> x ;
                cout << "input the second string:";
                cin >> y;
                LCS(x,y);
                break;
            case '2':
                LIS();
                break;
            case '3':
                cout << "input the first string:";
                cin >> x ;
                cout << "input the second string:";
                cin >> y;
                LCIS(x,y);
                break;
            case '4':
                return 0;
            default:
                break;
        }
    }

}