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; }