輸入m個長度為n的DNA序列,求一個DNA序列,到所有序列的總的Hamming距離盡量小,兩個等長字元串的Hamming距離等于字元不同的位置個數,例如,ACGT和GCGA的Hamming距離為2(左數第1,4個字元不同)。
輸入整數m和n(4<=m<=50,4<=n<=1000),以及m個長度為m的DNA序列(隻包含字母A,C,G,T),輸出到m個序列的Hamming距離和最小的DNA序列和對應的距離。如有多解,要求為字典序最小的解。例如,對于下面5個DNA序列,最優解為TAAGCTAC。
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT
#include<stdio.h>
#include<string.h>
//數組太大,定義在主函數外面可以防止程式異常退出
int a[55][55];
int main() {
int n,m;
char s[55][1005];
memset(a,0,sizeof(a));
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++){
scanf("%s",s[i]);
}
//計算Hamming值,
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++){
//j<i時,可以直接取行列互換的後數組的值,
//(比如1和3比 and 3和1比是一個結果)這樣可以達到優化的目的
if(j < i){
a[i][j] = a[j][i];
}else if(j > i){
for(int k = 0;s[i][k] != '\0';k++){
if(s[i][k] != s[j][k]) a[i][j]++;
}
}
}
}
//統計Hamming
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
a[i][n+1] += a[i][j];
//找到Hamming最小值的那個DNA序列
int min = 1;
for(int i = 2;i <= n;i++){
if(a[i][n+1] < a[min][n+1]){//值小則替換更新
min = i;
}else if(a[i][n+1] == a[min][n+1]){//如果值相等則取字典序小的
if(strcmp(s[i],s[min]) < 0) min = i;
}
}
//輸出結果
printf("%s\n",s[min]);
return 0;
}