神马品牌网魔兽世界蓝色幼龙坐骑:一道PASCAL题目求教
来源：百度文库 编辑：神马品牌网 时间：2024/05/05 04:08:12
【问题描述】
众所周知，人类基因可以被简单认为是一个字符串，包含四种分别用A,C,T,G表示的核苷酸。生物学家对鉴别人类基因核确定他们的功能很感兴趣。因为这对诊断人类疾病和开发新药很有用。 人类基因可以用一堆特别的快速的试验来鉴别，而且通常要借助电脑的帮助一旦基因序列测定了，下一步就可以确定它的功能了。生物学家确定一个新鉴定了的基因的功能的方法之一是在在基因数据库里和其他基因对照。要搜索的数据库里储存了很多的基因和它们的功能－－很多研究人员提交了他们的研究基因和功能到数据库，而数据库是在互联网上公开的。
数据库会返回一堆最相近基因。生物学家们假设类似的基因表示类似的功能。所以新基因的功能也包含在列表里的基因里。所以严格确定最相近的一个对生物试验非常必要。
你的任务是写一个程序来按一下规则比较两个基因和决定他们的相似程度。给出两个基因 AGTGATG 和 GTTAG，他们有多相似呢？一个测量两个基因相似程度的方法就叫做alignment。在alignment里, 如果必要是可以在基因的适当位置插进空格以令他们的长度相等。例如，一个空格插进了AGTGATG以后就得到AGTGAT-G，三个空格插进了GTTAG就得到–GT--TAG。空格用减号(-)表示。现在两个串的长度就相等了。现在排在一齐就成了：
AGTGAT-G
-GT--TAG
在这个alignment里，有四个基因是相配的：第二位的G，第三位的 T，第六位的T，和第八位的G。每对排列的字母用以下的矩阵分配了不同的分值。
* 表示空格对空格是不允许的。所以以上这个alignment的分值是(-3)+5+5+(-2)+(-3)+5+(-3)+5=9 。
当然，其他alignments也是有可能的。一下有另一种排列 (不同数目的空格插进不同的位置)：
AGTGATG
-GTTA-G
这个alignment 给出了的分值是 (-3)+5+5+(-2)+5+(-1) +5=14。 所以这一个比前一个要好。没有其他的alignment有更高的分值了，所以说这两个基因的相似程度是14。
【输入文件】
输入文件gene.in有两行：每行有一个表示基因长度的整数和一个基因序列。每个基因的长度都不超过3000。
【输出文件】
输出文件gene.out只要输出基因的相似程度。
【样例输入】
7 AGTGATG
5 GTTAG
【样例输出】
14
【时间】
2秒
最好能够又详细的思考过程
const d:array[1..5,1..5]of longint=
((5,-1,-2,-1,-3),
(-1,5,-3,-2,-4),
(-2,-3,5,-2,-2),
(-1,-2,-2,5,-1),
(-3,-4,-2,-1,0));
var l1,l2,i,j:longint;
kong:char;
a,b:ansistring;
f:array[0..100,0..100]of longint;
z:array['-'..'T']of longint;
begin
assign(input,'gene.in'); reset(input);
assign(output,'gene.out'); rewrite(output);
z['A']:=1; z['C']:=2; z['G']:=3; z['T']:=4; z['-']:=5;
readln(l1,kong,a);
readln(l2,kong,b);
fillchar(f,sizeof(f),0);
for i:=1 to l1 do f[i,0]:=f[i-1,0]+d[z[a[i]],5];
for j:=1 to l2 do f[0,j]:=f[0,j-1]+d[5,z[b[j]]];
for i:=1 to l1 do
for j:=1 to l2 do begin
f[i,j]:=f[i-1,j-1]+d[z[a[i]],z[b[j]]];
if f[i-1,j]+d[z[a[i]],5]>f[i,j] then f[i,j]:=f[i-1,j]+d[z[a[i]],5];
if f[i,j-1]+d[5,z[b[j]]]>f[i,j] then f[i,j]:=f[i,j-1]+d[5,z[b[j]]];
end;
writeln(f[l1,l2]);
close(input); close(output);
end.
来完善一下，字符串不够，应该用ansistring，否则的话会访问内存错误，崩溃掉...我可怜的没改之前只得了40分
...好复杂的样子 至少贫我现在的实力是想不出来了
过几天帮你问问同学 ^_^