《算法竞赛入门经典（第2版）》 习题3-7 DNA序列（DNA Consensus String, ACM/ICPC Seoul 2006, UVa1368）

输入m个长度均为n的DNA序列，求一个DNA序列，到所有序列的总hamming距离尽量小。两个等长字符串的hamming距离等于字符不同的位置个数，例如，ACGT和GCGA的hamming距离为2（左数第1、4个字符不同）。输入整数m和n（4<=m<=50，4<=n<=1000），以及m个长度为n的DNA序列（只包含字母A、C、G、T），输出到m个序列的hamming距离和最小的DNA序列和对应的距离，如有多解，要求为字典序最小的解。

【输入】

包含T组数据。输入数据的第1行是一个整数T，表示将会有T组数据。接下来的每一组数据第一行是两个整数m和n，m和n之间有一个空格隔开。此后会有m行DNA序列，每行的序列长度为n。

【输出】

对每一组数据都要输出两行。第一行是求出的DNA序列，第二行是这个序列与本组各行数据的hamming距离之和。

示例输入：

3
5 8
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT
4 10
ACGTACGTAC
CCGTACGTAG
GCGTACGTAT
TCGTACGTAA
6 10
ATGTTACCAT
AAGTTACGAT
AACAAAGCAA
AAGTTACCTT
AAGTTACCAA
TACTTACCAA

示例输出：

TAAGATAC
7
ACGTACGTAA
6
AAGTTACCAA
12

分析

开始的时候，对于“到所有序列的总hamming距离最小”的序列有点困惑，后来发现只要竖着看就可以了！每一列出现最多的字母，构成的就是正确的解。明白了这一点之后，余下的就是细心编程了。由于每一组数据之间并无什么关联，所以每次只需要存储、处理一组数据即可，当然，不要忘了先清零！

代码

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <time.h>char a[55][1050]; // 存储一组数据
char ans[1050]; // 一行符合要求的解
int count[4]; // 统计一列当中ACGT的数量int main()
{int t, m, n;scanf("%d", &t);for(int i=0; i<t; i++) // 处理每一组数据{memset(a, 0, 55*1050); // 清零memset(ans, 0, 1050); // 清零int tot = 0; // 各列当中与解不同的字母数量之和（即hamming距离和）scanf("%d%d", &m, &n);for(int j=0; j<m; j++) // 输入m行序列到数组ascanf("%s", a[j]);for(int j=0; j<n; j++) // 对每一列进行统计{count[0]=0; count[1]=0; count[2]=0; count[3]=0; // 清零for(int l=0; l<m; l++) // 统计一列中的每个字母{if(a[l][j]=='A') count[0]++;else if(a[l][j]=='C') count[1]++;else if(a[l][j]=='G') count[2]++;else if(a[l][j]=='T') count[3]++;}int max=0;char maxc;for(int x=1;x<4;x++) // 找出此列中出现次数最多的字母，如果相同则保留字典序较小者（从左向右比较）if(count[max]<count[x]) max = x;switch(max){ // 出现最多的字母maxccase 0:maxc = 'A'; break;case 1:maxc = 'C'; break;case 2:maxc = 'G'; break;case 3:maxc = 'T'; break;}ans[j] = maxc; // 记录最终解的一个字母for(int x=0; x<m; x++) // 累加此列当中不同字母的数量if(a[x][j] != maxc) tot++;}for(int j=0;j<n;j++) printf("%c", ans[j]); // 输出一个解printf("\n%d\n", tot);}return 0;
}