试用最小费用流算法解中国邮路问题.

A、平衡微分方程

B、几何方程

C、应力边界条件

D、位移边界条件

问题描述:基因序列是用字符串表示的携带基因信息的DNA分子的一级结构.基因序

列的字符集是Σ={A,C,G,T}.其中字符分别代表组成DNA的4种核苷酸:腺嘌呤、胞嘧啶、鸟嘌呤、胸腺嘧啶.许多疾病往往是由基因突变引起的.这种基因突变是从一个正常的基因序列通过几代人的遗传而产生的.对于基因片段的分析有助于了解基因突变导致的遗传疾病.例如,如果一个基因序列中含有基因片段ATG,则可能含有某种遗传疾病.生物科学家们已经发现许多这类基因片段.对于已知的不安全的基因片段集合P,如果一个基因序列中含有P中基因片段,则称该基因序列为不安全的基因序列,否则称该基因序列为安全的基因序列.

算法设计:对于给定的不安全的基因片段集合P和一个正整数n,计算长度为n的安全的基因序列个数.

数据输入:由文件input.txt提供输入数据.文件的第1行有两个正整数n(1≤n≤2x10⁹)和m(0≤m≤10).n是基因序列长度,m是不安全的基因片段个数.接下来的m行中,每行是一个长度不超过10的不安全的基因片段.每个文件可能有多个测试数据.

结果输出:将计算出的长度为n的安全的基因序列个数mod100000,输出到文件output.txt中.

问题描述:最长公共子序列问题是生物信息学中序列比对问题的一个特例.这类问题在分子生物学和模式识别中有广泛应用.其中最主要的应用是测量基因序列的相似性.在演化分子生物学的研究中发现,某个重要的DNA序列片段常出现在不同的物种中.在测量基因序列的相似性时,如果需要特别关注一个具体的DNA序列片段,就要考察带有子串排斥约束的最长公共子序列问题.这个问题可以具体表述如下.

给定两个长度分别为n和m的序列x[0...n-1|]和y[0...m-1],以及一个长度为p的约束字符串s[0...p-1].带有子串排斥约束的最长公共子序列问题就是要找出x和y的不包含s为其子串的最长公共子序列.例如,如果给定的序列x和y分别为AATGCCTAGGC和CGATCTGGAC.字符串s=TG时,子序列ATCTGGC是x和y的一个无约束的最长公共子序列,而不包含s为其子串的最长公共子序列是ATCGGC.

算法设计:设计一个算法,找出给定序列x和y的不包含s为其子串的最长公共子序列.

数据输入:由文件input.txt提供输入数据.文件的第1行中给出正整数,分别表示给定序列x和y及约束字符串s的长度.接下来的3行分别给出序列x、y和约束字符串s.

结果输出:将计算出的x和y的不包含s为其子串的最长公共子序列的长度输出到文件output.txt中.

设字符串t的后缀数组和最长公共前缀数组分别为sa和lcp.对于非负整数0≤I≤r,t的后缀S_t和S_r的最长前缀的长度为lce(l,r).设x=sa^-1[l],z=sa^-1[r],则sa[x]=I,sa[z]=r.不失一般性,可设x<z.试证明lce(l,r)具有如下性质.

问题描述:设是n个互不相同的符号组成的符号集.1≤i≤k}是Σ中字符组成的长度为k的字符串至体.是L_k的1个无分隔符字典是指对任意和.

无分隔符字典问题要求对给定的n和Σ及正整数k,计算Lk的最大无分隔符字典.

算法设计:设计一个算法,对于给定的正整数n和k,计算Lk的最大无分隔符字典.

数据输入:由文件input.txt给出输入数据.文件第1行有2个正整数n和k.

结果输出:将计算的Lk的最大无分隔符字典的元素个数输出到文件output.txt.