程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva - 1368 - DNA Consensus String(字符串)

uva - 1368 - DNA Consensus String(字符串)

編輯:C++入門知識

題意:給你幾個字符串,找到一個字符串,使其到所有字符串的總Hamming的距離盡量小,Hamming就是字符不同的位置個數。如有多解輸出字典序最小的。和題目有關的就是序列只有 AGCT,,高中生物學過。。uva總是把題目說的天花亂墜。

方法:找每一列最多的那個。別怕麻煩。

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   

using namespace std;

char dna[50][1010], ans[1010];
int c[5], h;

void Input(int m, int n)
{
	int i = 0, j = 0;
	for (i = 0; i < m; i++)
		for (j = 0; j < n; j++)
			cin >> dna[i][j];
}

void Judge(int j, int i)
{
	switch(dna[j][i])
	{
	case 'A': 
		c[0]++; break;
	case 'C': 
		c[1]++; break;
	case 'G':
		c[2]++; break;
	case 'T':
		c[3]++; break;
	}
}

void Count_H(int m, int n)
{
	int i = 0, j = 0;
	for (i = 0; i < m; i++)
		for (j = 0; j < n; j++)
			if (dna[i][j] != ans[j])
				h++;
}

int main()  
{  
#ifdef Local    
	freopen("a.in", "r", stdin);    
#endif
	int t = 0;
	cin >> t;
	while (t--)
	{
		h = 0;
		memset(dna, '\0', sizeof(dna));
		memset(ans, '\0', sizeof(ans));
		int m, n, i = 0, j = 0;
		cin >> m >> n;
		Input(m, n);
		for (i = 0; i < n; i++)
		{
			memset(c, 0, sizeof(c));
			for (j = 0; j < m; j++)
				Judge(j, i);
			int max = 0, pos = 0;
			for (j = 0; j < 4; j++)
			{
				if (c[j] > max)
				{
					pos = j, max = c[j];
				}
			}
			switch(pos)
			{
			case 0:
				ans[i] = 'A'; break;
			case 1:
				ans[i] = 'C'; break;
			case 2:
				ans[i] = 'G'; break;
			case 3:
				ans[i] = 'T'; break;
			}
		}
		Count_H(m, n);
		cout << ans << endl;
		cout << h << endl;
	}
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved