题目
输入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序列和对应的距离。
如有多解，要求为字典序最小的解。例如，对于下面5个DNA序列，最优解为TAAGATACC。
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT
分析
求一个DNA序列到所有序列的Hamming距离尽量小。
所以找出每列出现频率最多的，如果频率相同，用字典序较小的。
c实现
#include<stdio.h> #include<string.h> const char a[]="ACGT"; int main() { int m,n; scanf("%d%d",&m,&n); //用来存储输入的DNA序列和答案 char s[m+1][n]; //用来标记每列中ACGT出现的次数 int count[4]; //输入DNA序列 for(int i=0;i<m;i++) { scanf("%s",s[i]); } //存储距离 int sum=0; //按列遍历 for(int j=0;j<n;j++){ //对每个列都需要重置count数组为0 memset(count,0,sizeof(count)); //统计每列中的ACGT的个数 for(int i=0;i<m;i++){ int k=0; for(;k<4;k++) { if(s[i][j]==a[k]) { break; } } count[k]++; } //找出每列中ACGT出现最多的 int max=0; for(int l=0;l<4;l++){ if(count[max]<count[l]){ max=l; } sum += count[l]; } //把出现频率最多的存入答案 s[m+1][j]=a[max]; sum -= count[max]; } //打印出答案 for(int j=0;j<n;j++){ printf("%c ",s[m+1][j]); } printf("\n"); printf("%d",sum); printf("\n"); return 0; }
原文：https://www.cnblogs.com/Vincent-yuan/p/12969574.html