当前位置: 代码迷 >> C语言 >> [玩笑]谁会用C程序做DNA鉴定
  详细解决方案

[玩笑]谁会用C程序做DNA鉴定

热度:179   发布时间:2007-01-29 01:59:00.0
[玩笑]谁会用C程序做DNA鉴定
任意输入两段DNA(字符串)例如
S1[]=TCGGTCAGTAGCAGACTGTCAGTCCAGTCAG~~~~~~~~~~~;
S2[]=TGACAGG GTCAGTCCAGTCAGATCGGTAAGT~~~~~~~~~~;

要求打印出两段DNA中相同的最长的一段如上则是打印出“
GTCAGTCCAGTCAG”。

这个我也不会做所以才说是玩笑。
希望各位大虾多多指教。
由于本人水平有限,如果能给出具体的程序是最好的。谢谢!
搜索更多相关的解决方案: DNA  鉴定  玩笑  

----------------解决方案--------------------------------------------------------
如果用笨办法循环,比较...做起来可能比较麻烦,帮你顶
----------------解决方案--------------------------------------------------------
给个思路,但是这样的空间复杂°最坏

定义2个一维数组&一个2维数组,2维数组的空间要足够大
设一个计数器,开始判断2个1维数组,如果相同则存入2维数组,计数器+1。如果遇到不同,指针转向2维数组的下一行,计数器清零。
最后统计比较2维数组行长度,并打印最长的行。
----------------解决方案--------------------------------------------------------
#include "stdio.h"
#include "ctype.h"
#include "string.h"
void main(void)
{
char s1[]="TCGGTCAGTAGCAGACTGTCAGTCCAGTCAG",*str1,*p;
char s2[]="TGACAGGGTCAGTCCAGTCAGATCGGTAAGT",*str2;
unsigned int i,len,b=4,t=0,max=0;
p=s1;
str1=s1;
str2=s2;
len=strlen(s2);
/*把s1,s2当成2辆火车,让s2从尾部开始与s1的头部开始比较,直到s2的头部走出s1的尾部,
这样比较的的话就只要比较对应字符相同就行了,可以用strcmp函数。*/
while(len-1-b>0)
{
str2=str2+len-1-b;//让str2先指向尾部倒数第四个,应为DNA都是3个一组的,所以前3个比较没多少意思,肯定有
while (*str2!='\0')
{
if (*str2==*str1)
{
t++;//用来记录最大长度的个数
}
else
{
t=0;
}
str1++;
str2++;
if (t>max)
{
max=t;
p=str1;//定位个指针p,方便输出
}
}
b++;//让str2指针不段的向前移动
t=0;
str1=s1;
str2=s2;
}
b=1;
while(*str1!='\0'&&strlen(str1)>max)
{
while(*str1!='\0'&&*str2!='\0')
{
if (*str2==*str1)
{
t++;
}
else
{
t=0;
}
str1++;
str2++;
if (t>max)
{
max=t;
p=str1;
}
}
t=0;
b++;
str2=s2;
str1=s1;
str1=str1+b;
}
p=p-max;
for (i=0;i<max;i++)
{
printf("%c",p[i]);
}
}
应该是行的,但是感觉比较浪费时间,
----------------解决方案--------------------------------------------------------

我是用VC6.0编译的


----------------解决方案--------------------------------------------------------

动态规划求解最长公共子串问题

算法思想

求字符串str1,str2的最长公共子串的长度。


定义二元函数函数f(m,n):分别以str1[m],str2[n]结尾的连续公共子串的长度

而对于f(m+1,n+1) 有以下两种情况

1.str1[m+1] != str2[n+1],则有f(m+1,n+1) =0

2.str1[m+1] == str2[n+1],则有f(m+1,n+1) = f(m,n) + 1

另外f(0,j) = 0(j>=0)

f(j,0) = 0 (j>=0)

按照上面这个公式,我们用容易写出这个算法的实现

算法实现

1 int commstr(char *str1, char *str2)

2 /* 返回str1,str2的最长公共之串长度*/

3 {

4 int len1=strlen(str1),len2=strlen(str2),row,col,max=0;

5 int **pf = new int*[len1+1];//动态分配一个二维数组作为辅助空间

6 for (row=0; row<len1+1; row++)

7 pf[row] = new int[len2+1];

8

9 //数组赋初值

10 for (row=0; row<len1+1; row++)

11 pf[row][0] = 0;

12 for (col=0; col<len2+1; col++)

13 pf[0][col] = 0;

14

15 for (row=1; row<=len1; row++)

16 for (col=1;col<=len2; col++)

17 {

18 if (str1[row-1] == str2[col-1])

19 {

20 pf[row][col] = pf[row-1][col-1] + 1;

21 max = pf[row][col] > max ? pf[row][col] : max;

22 }

23 else

24 pf[row][col] = 0;

25 }

26 //空间回收

27 for (row=0; row<len1+1; row++)

28 delete[] pf[row];

29 delete[] pf;

30

31 return max;

32 }


程序的输出

字符串"blog.csdn.net"和"csdn.blog"求公共子串时的输出结果

String:

1. blog.csdn.net

2. csdn.blog

c s d n . b l o g

0 0 0 0 0 0 0 0 0 0

b 0 0 0 0 0 0 1 0 0 0

l 0 0 0 0 0 0 0 2 0 0

o 0 0 0 0 0 0 0 0 3 0

g 0 0 0 0 0 0 0 0 0 4

. 0 0 0 0 0 1 0 0 0 0

c 0 1 0 0 0 0 0 0 0 0

s 0 0 2 0 0 0 0 0 0 0

d 0 0 0 3 0 0 0 0 0 0

n 0 0 0 0 4 0 0 0 0 0

. 0 0 0 0 0 5 0 0 0 0

n 0 0 0 0 1 0 0 0 0 0

e 0 0 0 0 0 0 0 0 0 0

t 0 0 0 0 0 0 0 0 0 0


max substr length:5

这是程序的输出结果,请注意红色字体


时间空间复杂度分析

如果用n,m表示两个字符串的长度的话,那么算法的

时间复杂度为O(n*m),空间复杂度也为O(n*m)

附:完整的源程序g++编译通过

#include <stdio.h>

#include <string.h>

void print_table(char *str1,char *str2,int **pf)

{

int i,j,row,col;

row = strlen(str1);

col = strlen(str2);

printf("\t\t");

for (i=0; i<col; i++)

printf("%c\t",str2[i]);

for (i=0; i<=row; i++)

{

for (j=0; j<=col; j++)

{

if (j == 0)

{

printf("\n");

if (i)

printf("%c\t",str1[i-1]);

else

printf("\t");

}

printf("%d\t",pf[i][j]);

}

}

}

int commstr(char *str1, char *str2)

/* 返回str1,str2的最长公共之串长度*/

{

int len1=strlen(str1),len2=strlen(str2),row,col,max=0;

int **pf = new int*[len1+1];//动态分配一个二维数组作为辅助空间

for (row=0; row<len1+1; row++)

pf[row] = new int[len2+1];

//数组赋初值

for (row=0; row<len1+1; row++)

pf[row][0] = 0;

for (col=0; col<len2+1; col++)

pf[0][col] = 0;

for (row=1; row<=len1; row++)

for (col=1;col<=len2; col++)

{

if (str1[row-1] == str2[col-1])

{

pf[row][col] = pf[row-1][col-1] + 1;

max = pf[row][col] > max ? pf[row][col] : max;

}

else

pf[row][col] = 0;

}

print_table(str1,str2,pf);

//空间回收

for (row=0; row<len1+1; row++)

delete[] pf[row];

delete[] pf;

return max;

}

int main(int argc,char **argv)

{

if (argc >= 3)

{

printf("String:\n\t1. %s\n\t2. %s\n",argv[1],argv[2]);

printf("\nmax substr length:%d\n",commstr(argv[1],argv[2]));

}

return 0;

}


----------------解决方案--------------------------------------------------------
以上的算法是最快的
----------------解决方案--------------------------------------------------------
非常感谢各位的帮助,我学C只有半年,有些还看不懂,甚至都没听说过,例如:“二元函数函数f(m,n):”,“时间空间复杂度分析”,“int **pf = new int*[len1+1];//动态分配一个二维数组作为辅助空间”。~~~~~~~有些顾名思义,仔细一想有的也可以理解,不过有的还是搞不定。也许往后深入可能会理解的。blackbrod的解法我比较容易理解。
在这里还是只能说声谢谢,我受益匪浅!

----------------解决方案--------------------------------------------------------
  相关解决方案