UVa1368：DNA序列（DNA Consensus String）

题目：

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

TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT

Sample Input：

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

Sample Output：
TAAGATAC 
7 
ACGTACGTAA 
6 
AAGTTACCAA 
12

注意事项：

1.C/C++语言可以使用#define和const创建符号常量；而使用enum枚举类型不仅能够创建符号常量，还能定义新的数据类型。使用enum枚举类型的步骤如下：
（1）枚举量的声明和定义

enum enumType {Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday};

这句话有两个作用：

第一：声明enumType为新的数据类型，称为枚举(enumeration);

第二：声明Monday、Tuesday等为符号常量，通常称之为枚举量，其值默认分别为0-6。

对于枚举，只定义了赋值运算符，没有为枚举定义算术运算。
（2）自定义枚举量的值
显式的设置枚举量的值：但指定的值必须是整数

enum enumType {Monday=1, Tuesday=2, Wednesday=3, Thursday=4, Friday=5, Saturday=6, Sunday=7};

也可以只显示的定义一部分枚举量的值：

enum enumType {Monday=1, Tuesday, Wednesday=1, Thursday, Friday, Saturday, Sunday};

其中，Tuesday，Thursday、Friday、Saturday、Sunday的默认值分别设置为2、2、3、4、5。
未被初始化的枚举值的值默认将比其前面的枚举值大1。

编程总结：

1.思路：找出每列中重复次序最多的字符，同时注意字典序；每找一列，统计海明码距离。
2.在设计寻找每列中出现的最大值，同时保持字典序时，先将DNA按字典序排序（A、C、G、T），然后相当于求第一次出现的最大值。
3.在用于switch时，‘A’、’C‘、’G‘、’T’；应该使用单引号来表示单个字符；而在string直接用+相连接时，应该注意使用“A”表示字符串进行连接。

程序代码：

#include<iostream>
#include<string>
using namespace std;

char dna[50][1000];
enum dnaType {A,C,G,T};//分别默认值为0，1，2，3；方便统计H数组

int findMax(int a[], int size) {
	int result = 0;
	for (int i = 1; i < size; i++) {
		if (a[i] > a[result]) {
			result = i;
		}
	}
	return result;
}


int main()
{
	int m,n;
	int H[4];//每一列各字符出现的次数
	int sum = 0;//海明距离
	string result = " ";//结果串：就是每列中 出现频率最高的字符。
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		cin >> dna[i];
	}

	char val;
	for (int j = 0; j < n; j++) {
		memset(H, 0, sizeof(int)*4);//每统计一列，就重新初始化H数组

		for (int i = 0; i < m; i++) {
			val = dna[i][j];

			switch (val)
			{
			case 'A':
				H[0]++;
				break;
			case 'C':
				H[1]++;
				break;
			case 'G':
				H[2]++;
				break;
			case 'T':
				H[3]++;
				break;
			default:
				break;
			}
		}
		//寻找H数组中的最大值，统计结果
		int num = findMax(H, 4);
		
		switch (num)
		{
		case 0:
			result += "A";
			sum += (m - H[0]);
			break;
		case 1:
			result += "C";
			sum += (m - H[1]);
			break;
		case 2:
			result +="G";
			sum += (m - H[2]);
			break;
		case 3:
			result += "T";
			sum += (m - H[3]);
			break;
		default:
			break;
		}
	}
	cout << result << endl;
	cout << sum << endl;
	system("pause");
	return  0;
}