DNA测序问题——2003年第3期题解

问题分析这是一道典型的分类问题,我们知道该问题的关键是要从已知的分好类的20个字母序列中提取用于分类的特征。知道了这些特征,我们就可以比较容易的对那些未表明类型的序列进行分类。分类标准:(1)所取特征必须可以标志A组和B组,也就是说,我们利用这些特征应该可以很好的区分已经表示分类的20序列。这是一个比较显然的理由。(2)所取特征必须是有一定的实际意义的。这一点是绝不能被忽视的。比如,不考虑模型的实际意义,我们可以以序列的开头字母为分类标准:已知在B类中的十个序列都是以gt开始的,而在A类中十个没有以gt开始的,甚至以g开始的都没有。显然这个条件满足第一个条件的。如果仅因此就认为这种特征是主要的,并简单的利用这个特征将所有待分类的序列分成两类,显然是不合理的。基于上述分类标准,我们利用DNA序列的局部性和全局性的特征,从频率角度和周期性角度出发来综合分析这道分类问题。     

空中交通控制问题——2003年第4期题解

问题描述见2003年第4期程序员杂志。算法分析我们对问题中的飞机可以抽象为一个点,这样,本问题的求解就变成了:找出给定平面上n个点中哪一对点的距离最小。我们很容易理解该问题,似乎也不难解决它。因为我们可以用穷举法将每一点与其它n-1个点的距离算出,找出达     

01串问题题解——2004年第3期题解

问题描述见《程序员》杂志2004年第3期。算法设计对于本问题,最直观的也最容易想到的算法是穷举法。我们可以通过计算长度为N的01字符串的所有排列组合,由于该01串的元素只有两种:‘0’和‘1’,可知长度为N的01串共有2~N种排列组合形式。如N=2,则有2~2=4种,“00”,“01”,“10”,“11”。对每一种长度为N的01串的排列组合形式,判断是否完全满足题目条件。如果能找到一个满足的01串,将该01串输出。显然,这种做法的时间复杂度随着01串的长度的增加进行     

病毒问题——2003年第9期题解

问题描述见杂志2003年第9期算法分析本期问题可以描述为:给定某一串集,试判断是否存在一条无限长的不含有该集合中任一串的串。该问题由于使用了“无限长“这种概念,故无法从整体上考虑该题的解答。我们应该从该题的一个部分或类似的问题入手。先考虑判断某一段有限代码ala2…ak是否安全的方法。最直接的方法就是对于每个病毒串,判断代码串中是否含有该病毒串。不过这种方法很明显包括了大量的重复判断。通常情     

车辆移动问题——2004年第2期题解

问题描述见《程序员》杂志2004年第2期。算法分析建立数学模型我们先来分析一下这道题。如果令 x_i 为车道 i 的初始车辆数,则(x_1,x_2,x_3,...,x_n)为所给的初始车辆序列。如果令=/n 为每车道最后要达到的平均值,则最后要达到的目标序列为(,,,...,)。本题是求从初始序列到最后的目标序列的一个最少移动(i,m)集合。在这里我们先要抓住一个隐含的相对不变量,这个相对不变量就是每个车道在完成任务的过程中向外移动的总车辆数,     

密码分析问题——2003年第12期题解

问题描述见杂志2003年第12期。算法分析首先,抓住问题的两个关键因素:“特征”和“特征串”。一个“特征”是由两个有序整数组成的,例如有“特征”(2,3),那么,在对应的“特征串”中必然存在连续的两个数 a_i=2和 a_(i+1)=3。现在我们不妨把每个自然数抽象成一个顶点,i 对应的顶点是 V_i;把每个特征抽象成一条弧,〈l,r〉对应的弧就是〈V_i,V_j〉。如图一所示,假设特征串是(1,2,3.4,3,5,6.2,5)。那么,图一中,每一条有向边所表示的正是特征串的一个“特征”。而对“特征串”来说,可以从图一中的1点出发,画出一条路径,每条边经过且只经过一次。     

棋子问题的算法分析——2003年第11期题解

问题描述见《程序员》杂志2003年第11期。算法分析 1.题目分析由于是求必胜状态,因此在搜索过程中,先假设甲方(x)在第k步已经处于必胜状态,那么,乙方(o)的第k步无论下在哪儿,甲方下第k+1步的时候,至少能够找到一个位置保持这个状态,即要么甲方已经赢了,要么继续保持这个必胜状态。因为甲方一直都能够保持这个必胜状态,所以甲方最后一定能够赢棋,因此甲方的第k步就是本题的解。本题给出每人至少已经下了2步,这样剩下的12个格子都     

高性能计算机问题——2002年第12期题解

问题描述见2002年第12期杂志。算法分析本题是一个有实际应用背景的问题。第一步,我们不妨把题目中的多个节点简化成一个节点的特殊情况。在这样的情况下,我们已确定此节点的任务是《n_A,n_B)(n_A表示有n_A个A类子任务,n_B表示有n_B个B类子任务),那么,此节点所需的最短时间也就确定了,设这个最短时间为f_1(n_A,n_B)。下面我们把这种特殊情况推广到一般情况。在一般情况下,假设某一个节点i已分配的任务是(a_i,b_i)(a_i表示有a_i个A类子任务,b_i表示有b_i个B类子任务),那么,这第i个节点所确定的最短时间是f_i(a_i,     

文件时间问题——2003年第6期题解

问题描述见杂志2003第6期问题描述。算法分析对于这道关于求执行完所有文件的最短时间的题,我们寻找问题的解的一种可靠的方法是首先列出所有候选解,即穷举所有可能分组的情况,然后依次检查每一个,在检查完所有或部分候选解后,即可找到所需要的解。理论上,当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时,上述方法是可行的。不过,在实际应用中,很少使用这种方法,因为候选解的数量通常都非常大(比如指数级,