首页 > 代码库 > Huaman Gene Functions

Huaman Gene Functions

2024-08-08 08:44:13   220人阅读

算法分析：

/*

  分析此问题可知，为最长子序列（LCS）问题的变形。
  假设两个子序列分别是X,Y;
  Xi=（x1，x2...xi），Yj=(y1,y2..yj)分别是两个子序列的前i，j个子序列
  求最长子序列;
   1、当xi=yj时，dp[i][j]=dp[i-1][j-1]+1
   2、当xi！=yj时，则dp[i][j]=max（dp[i-1][j]，dp[i][j-1]).


  对于本题来说是变种LCS.
   设dp[i][j]为取s1第i个字符，s2第j个字符时的最大分值
   则决定dp为最优的情况有三种（matrix[][]为s1[i]和s2[j]两符号的分数）：
   1、  s1取第i个字母，s2取“ - ”： dp[i-1][j]+matrix[ s1[i] ][‘-‘];
   2、  s1取“ - ”，s2取第j个字母：dp[i][j-1]+matrix[‘-‘][ s2[j] ];
   3、  s1取第i个字母，s2取第j个字母：dp[i-1][j-1]+matrix[ s1[i] ][ s2[j] ];
   即dp[i][j]=max( dp[i-1][j]+matrix[ s1[i] ][‘-‘],
   dp[i][j-1]+matrix[‘-‘][ s2[j] ],
   dp[i-1][j-1]+matrix[ s1[i] ][ s2[j] ] );

   初始化：

   1、dp[0][0]=0;

   2、dp[i][0](i属于(1，s1.length))
        dp[i][0]=matrix[s1[i]][‘-‘];
      dp[0][j](j属于（1，s2.length）)
        dp[0][j]=matrix[‘-‘][s2[j]]
   注：matrix[][]可以定义为int型的数组，此处只是为了方便描述而将数组维数值用字符来代替。

*/

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAXVALUE 101
using namespace std;
int switchint(char t)
{
        if(t=='A')
            return 0;
        if(t=='C')
            return 1;
        if(t=='G')
            return 2;
        if(t=='T')
            return 3;
        if(t=='-')
            return 4;
}
int getmaxs(int x,int y,int z)
{
    int temp;
    if(x>y)
      temp=x;
    else
      temp=y;
    return temp>z? temp:z;

}

int main()
{
     int length1,length2; //分别记录s1和s2序列长度
     int times;//循环次数
     char s1[MAXVALUE];
     char s2[MAXVALUE];
     int dp[MAXVALUE][MAXVALUE];//用来记录总长子列长度
    //首先我们先创建一个matrix二维整形数组来记录score
     int matrix[5][5]=
     {
         5,-1,-2,-1,-3,
         -1,5,-3,-2,-4,
         -2,-3,5,-2,-2,
         -1,-2,-2,5,-1,
         -3,-4,-2,-1,0
     };
     // *我们用0来表示

    //此函数用来将字符转换成整形数值，目的是方便构建matrix整形数组


    cin>>times;
    while(times--)
    {
        cin>>length1;
        for(int i=1;i<=length1;i++)
            cin>>s1[i];
        cin>>length2;
        for(int i=1;i<=length2;i++)
            cin>>s2[i];
        // #region 初始化
         memset(dp, 0, sizeof (dp));
         for(int i=1;i<=length1;i++)
         {
             int temp=switchint(s1[i]);
             dp[i][0]=dp[i-1][0]+matrix[temp][4];
         }
         for(int j=1;j<=length2;j++)
         {
             int temp=switchint(s2[j]);
             dp[0][j]=dp[0][j-1]+matrix[4][temp];
         }
         //#endregion
            for(int i=1;i<=length1;i++)
            {
                for(int j=1;j<=length2;j++)
                {
                    //dp[i][j]=max(dp[i-1][j-1]+matrix[switchint(s1[i])][switchint(s2[j])],dp[i-1][j]+matrix[switchint(s1[i])][4],dp[i][j-1]+matrix[4][switchint(s2[j])]);
                    int t1=dp[i-1][j-1]+matrix[switchint(s1[i])][switchint(s2[j])];
                    int t2=dp[i-1][j]+matrix[switchint(s1[i])][4];
                    int t3=dp[i][j-1]+matrix[4][switchint(s2[j])];
                    dp[i][j]=getmaxs(t1,t2,t3);
                }

            }
            cout<<dp[length1][length2]<<endl;
            //delete []dp;
        }

        return 0;
}



   

Huaman Gene Functions


联系
我们