计算机算法设计与分析之不定期更新的日常+动态规划矩阵连乘+最长公共子序列

偏执的太偏执、 2022-07-16 05:13 22阅读 0赞

1.代码实现与分析如下：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    const int maxn=50;
    
    int m[maxn][maxn];
    int s[maxn][maxn];
    
    void matrixChain(int *p,int n)///自底向上计算
    {
        for(int i=1; i<=n; i++) ///处理底部
        {
            m[i][i]=0;
        }
        for(int r=2; r<=n; r++)
        {
            for(int i=1; i<=n; i++)
            {
                int j=i+r-1;///i和j之间满足的关系
                int k=i;///k表示括括号断开的位置
                m[i][j]=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                s[i][j]=k;
                for(k=i+1; k<j; k++)
                {
                    int tmp=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                    if(tmp<m[i][j])///找最小值
                    {
                        m[i][j]=tmp;
                        s[i][j]=k;
                    }
                }
            }
        }
    }
    
    void dfs(int ss[][maxn],int i,int j)
    {
        if(i==j) return;
        else
        {
            cout<<"Multiply A"<<i<<","<<ss[i][j]<<" ";
            cout<<"and A"<<s[i][j]+1<<","<<j<<endl;
            int k=ss[i][j];
            dfs(ss,i,k);
            dfs(ss,k+1,j);
        }
    }
    
    int main()
    {
        int p[maxn];///Ai:P[i-1]*P[i]
        int n;
        while(scanf("%d",&n)!=EOF)///n个矩阵，则矩阵的围数则为0-n；
        {
            memset(p,0,sizeof(p));
            memset(s,0,sizeof(s));
            memset(m,0,sizeof(m));
            for(int i=0; i<=n; i++)
            {
                scanf("%d",&p[i]);
            }
            matrixChain(p,n);
            cout<<"构造最优解："<<endl;
            dfs(s,1,n);
            /*for(int i=1; i<=n; i++)
            {
                for(int j=1; j<=n; j++)
                {
                    cout<<s[i][j]<<" ";
                }
                cout<<endl;
            }*/
        }
        return 0;
    }

2.最长公共子序列

代码实现和解析：

#include <iostream>///最长公共子序列
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    const int maxn=100;
    
    void lcslength(char *x,char *y,int m,int n,int c[][maxn],int b[][maxn])
    {///c[i][j]用来记录Xi和Yj的最长公共子序列，b数组用来构造这个最长公共子序列
        for(int i=0;i<=n;i++)
        {
            c[0][i]=0;
        }
        for(int i=0;i<=m;i++)
        {
            c[i][0]=0;
        }
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(x[i]==y[j])
                {
                    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-1];
                        b[i][j]=2;
                    }
                    else
                    {
                        c[i][j]=c[i][j-1];
                        b[i][j]=3;
                    }
                }
            }
        }
    }
    
    void LCS(int b[][maxn],char *x,int i,int j)
    {
        if(i==0 || j==0)
            return;
        else if(b[i][j]==1)
        {
            LCS(b,x,i-1,j-1);
            cout<<x[i]<<" ";
        }
        else if(b[i][j]==2)
        {
            LCS(b,x,i-1,j);
        }
        else
        {
            LCS(b,x,i,j-1);
        }
    }
    
    int main()
    {
        int m,n;
        char x[maxn],y[maxn];
        int c[maxn][maxn],b[maxn][maxn];
        while(scanf("%d%d",&m,&n)!=EOF)
        {
            memset(x,0,sizeof(x));
            memset(y,0,sizeof(y));
            memset(c,0,sizeof(c));
            memset(b,0,sizeof(b));
            for(int i=1;i<=m;i++)
            {
                scanf(" %c",&x[i]);
            }
            for(int i=1;i<=n;i++)
            {
                scanf(" %c",&y[i]);
            }
            /*for(int i=0;i<m;i++)
            {
                cout<<x[i]<<" ";
            }
            cout<<endl;
            for(int i=0;i<n;i++)
            {
                cout<<y[i]<<" ";
            }
            cout<<endl;*/
            //for(int i=0;i<)
            lcslength(x,y,m,n,c,b);
            cout<<"两个序列的最长公共子序列为："<<endl;
            LCS(b,x,m,n);
            cout<<endl;
        }
        return 0;
    }
    /*
    6 6
    A B C B D A
    B D C A B A
    7 6
    A B C B D A B
    B D C A B A
    */