UVa1368 - DNA Consensus String

  

   

    

     

    
    

     

      //UVa1368 - DNA Consensus String
     
    
   

    

     

    
    

     

      //题目:给m个长度为n的DNA序列，求一个DNA序列到所有序列的总Hamming距离最小，Hamming距离为不同字符的位置的个数。
     
    
   

    

     

    
    

     

      //分析:每列找出最多重复次数。
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      #defien A1 //1,only DNA
     
    
   

    

     

    
    

     

      #defien A2 //2,已AC
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      #ifdef A1
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      int main(){
     
    
   

    

     

    
    

     
	int T;
     
    
   

    

     

    
    

     
	scanf("%d",&T);
     
    
   

    

     

    
    

     
	while(T--){
     
    
   

    

     

    
    

     
	//输入
     
    
   

    

     

    
    

     
		int m, n;
     
    
   

    

     

    
    

     
		scanf("%d %d",&m,&n);//m个n长度的
     
    
   

    

     

    
    

     
	//存储
     
    
   

    

     

    
    

     
		int s[n][4];
     
    
   

    

     

    
    

     
		memset(s,0,sizeof(s));
     
    
   

    

     

    
    

     
		char f[4]={'A','C','G','T'};
     
    
   

    

     

    
    

     
	//找个数
     
    
   

    

     

    
    

     
		for(int i = 0; i <= m; i++){//rows
     
    
   

    

     

    
    

     
			int g,count = 0;
     
    
   

    

     

    
    

     
			char ch;
     
    
   

    

     

    
    

     
			//while((ch=getchar()) != '\n'){
     
    
   

    

     

    
    

     
			while(scanf("%c",&ch) == 1){//every row
     
    
   

    

     

    
    

     
				//getchar();
     
    
   

    

     

    
    

     
				if(ch=='\n')break;
     
    
   

    

     

    
    

     
				if(ch=='A')g=0;
     
    
   

    

     

    
    

     
				if(ch=='C')g=1;	
     
    
   

    

     

    
    

     
				if(ch=='G')g=2;
     
    
   

    

     

    
    

     
				if(ch=='T')g=3;
     
    
   

    

     

    
    

     

      				s[count][g] += 1;	
     
    
   

    

     

    
    

     

      				count++;
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		//printf("%d %d %d %d %d\n",s[1][0],s[1][1],s[1][2],s[1][3],s[0][0]); 
     
    
   

    

     

    
    

     
	//输出
     
    
   

    

     

    
    

     
		for(int j = 0; j < n; j++){
     
    
   

    

     

    
    

     
			int max = 0, T = 4;
     
    
   

    

     

    
    

     
			//int *pt;
     
    
   

    

     

    
    

     
			while(T){
     
    
   

    

     

    
    

     
				//pt = &s[j][T];
     
    
   

    

     

    
    

     
				if(((s[j][T-1]) > (s[j][max])))max = T-1;
     
    
   

    

     

    
    

     

      				T--;
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     
			//printf("%d\n",s[j][T-1]);
     
    
   

    

     

    
    

     
			printf("%c",f[max]);
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		putchar('\n');
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      #endif
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      #ifdef A2
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      int main(void){
     
    
   

    

     

    
    

     
    int t;
     
    
   

    

     

    
    

     
	scanf("%d",&t);
     
    
   

    

     

    
    

     
	while(t--){
     
    
   

    

     

    
    

     
		int n,m;
     
    
   

    

     

    
    

     
		scanf("%d %d",&n,&m);
     
    
   

    

     

    
    

     
		char DNA[n][m+1];
     
    
   

    

     

    
    

     
		for(int i=0;i<n;i++) scanf("%s",DNA[i]);
     
    
   

    

     

    
    

     
		int list[4];
     
    
   

    

     

    
    

     
		int num=0,num1;
     
    
   

    

     

    
    

     
		for(int i=0;i<m;i++){
     
    
   

    

     

    
    

     
			memset(list,0,sizeof(list));
     
    
   

    

     

    
    

     
			for(int j=0;j<n;j++){
     
    
   

    

     

    
    

     
				if(DNA[j][i]=='A') list[0]++;
     
    
   

    

     

    
    

     
				else if(DNA[j][i]=='C') list[1]++;
     
    
   

    

     

    
    

     
				else if(DNA[j][i]=='G') list[2]++;
     
    
   

    

     

    
    

     
				else list[3]++;
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     
			int temp=0,ans;
     
    
   

    

     

    
    

     
			for(int k=0;k<4;k++){
     
    
   

    

     

    
    

     
				if(list[k]>temp) {
     
    
   

    

     

    
    

     

      				ans=k;
     
    
   

    

     

    
    

     

      				temp=list[k];
     
    
   

    

     

    
    

     

      				num1=n-list[k];
     
    
   

    

     

    
    

     

      			    }
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     
			if(ans==0) printf("A");
     
    
   

    

     

    
    

     
			else if(ans==1) printf("C");
     
    
   

    

     

    
    

     
			else if(ans==2) printf("G");
     
    
   

    

     

    
    

     
			else printf("T");
     
    
   

    

     

    
    

     

      			num+=num1;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		printf("\n%d\n",num);
     
    
   

    

     

    
    

     

      	}    
     
    
   

    

     

    
    

     
    return 0;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      #endif
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
  
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/54744435