博客

题目描述：


输入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个序列，最优为：TAAGATAC。

T A T G A T A C

T A A G C T A C

A A A G A T C C

T G A G A T A C

T A A G A T G T

思路：


用二维数组保存输入，求总hamming距离最小，其实就是求最接近于每列元素的那个字母。例如第一列：

T T T A T T

显然T是最接近的，因为这组里T出现次数最多。

使用整型数组a[4]保存每列中四个元素各出现了多少次，那么出现最多的也就是最接近的，直接输出即可。

代码：

#include<iostream>
#include<string>
#include<cstring>
#include<ctype.h>
#define LOCAL
using namespace std;
void count(int mark[],char ch)
{
	switch(ch)
	{
		case 'A':mark[0]++;break;
		case 'C':mark[1]++;break;
		case 'G':mark[2]++;break;
		default: mark[3]++;break;
	}
}
int main()
{
	char a[52][1002],ans[4]={'A','C','G','T'};
	int i,j,mark[5],max,pos,m,n,sum=0;
	cin>>m>>n;
#ifndef LOCAL
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
#endif
	for(i=0;i<m;i++)
		scanf("%s",a[i]);
	for(j=0;j<n;j++)
	{
		memset(mark,0,sizeof(mark));
		max=-1;
		for(i=0;i<m;i++)
			count(mark,a[i][j]);
		for(i=0;i<4;i++)
			if(mark[i]>max){
				max=mark[i];
				pos=i;
			}
		sum+=m-max;
		cout<<ans[pos];
	}
	cout<<endl<<sum;
	return 0;
}