仓库问题——2003年第7期题解

问题描述见2003年第7期杂志。算法分析这又是一道计算费用最少问题。也就是最优化问题。通过题目我们知道有些仓库之间是可以相望的。这就给出了为啥可以在没有足够看守人的情况下可以看守整个仓库。所以,我们可以通过在树上取某些适当的节点,使得他的总费用为最少。在下面我们用根结点的标号来表示一棵树,树T就是根结点标号为T的树。     

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

问题描述见2003年第5期杂志。算法分析通过解读招聘问题我们不难发现它是一道简单的关于有条件的分类或划分问题,解这种问题的方法有很多。在这里我们介绍用图的着色和集合划分来解它。 1.图的着色在本问题中,我们把每一个部门作为顶点,如有应聘者同时应聘几个部门时,在这些部门之间相互连一条边,这样就得到一个图。我们对图的顶点进行着色,同色顶点安排在同一场面试,这样得到的着色数即为需要安排的最少场次。这样招聘     

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

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

WWW搜索问题——2003年第8期题解

问题描述见杂志2003年第8期算法分析 WWW搜索问题的本质是在给定的字符串中找到包含关键字符集合中所有关键字符串的最短子串,对本题所涉及的部分概念理解如下 (1)符合条件的短子串这是只包含所有关键字符但不包含多余字符的子串。例原子串:ECBWCZACBA;关键字符集:ABC,则子串为“BWCZA”、“ACB”、“CBA”,这些是符合条件的短子串。     

蓄水池问题——2003年第1期题解

算法分析蓄水池这个问题对于会一些数学计算的人来说并不难做,但要把它变成可以在计算机上执行的算法甚至程序还是有点难度。之所以这样,主要是对这种看似简单又不知从何着手的问题的算法设计不太了解。在这里我们将介绍一种从特殊到一般的思维方法,通过这种分析设计出问题的算法。为了使问题简化,我们不妨用一个矩形框来代表一个蓄     

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

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

简单表达式问题—2002年第6期题解

问题描述见2002年第6期杂志。问题分析本题要求比较两个简单表达式的异问,看上去似乎比较麻烦,但实际上只需要模拟手工化简的过程就可以解决。在初等代数中我们曾经学过化简多项式的方法,即按照普通的四则混合运算法则进行去括号运算,得到“积之和”的形式,然后合并同类项,最后按照字典顺序排列多项式中的各项。比较两个表达式是否相等的方法与之类似,只要先对表达式进行化简,然后比较化简后的两个表达式是否相等即可。下面我们具体讨论这个问题的解决方法。     

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

算法描述见《程序员》杂志2004年第1期。问题分析一、轮廓定义在描述算法前,我们先明确一下“轮廓”的定义: 1、轮廓由有限条线段组成,线段是矩形边或者矩形边的一部分。 2、组成矩形边的线段不应被任何矩形遮盖。图1与图2分别是遮盖的两种情况。     

文件系统问题题解——2004年第4期题解

问题描述见《程序员》2004年第4期。算法分析1.算法介绍本题具有实际的背景,它源于现实中操作系统的使用。我们从问题的提出不难看出这是一道使用非最优化算法求解的问题。在没有有效算法的情况下,要解决这些问题,只能用一些非最优化算法在可接受的时间复杂度内求得一些近似解。下面我们先简单介绍几种非最优化算法:     

窗体框架问题—2002年第3期题解

问题描述见2002年第3期杂志。算法分析本题是一个有实际应用背景的问题。在Delphi、VB等可视化开发工具中,容器类控件(例如Panel、Image、Toolbar等)有一个Align属性,该属性的取值可以为top、left、right、bottom、client和none之一,这个属性表明了该控件在其父容器内停靠的位置。如果一个控件的Align属性不是none,则当该控件的父容器大小发生变化的时候,该控件的大小和位置也会相应地发生     

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

首先、抓住问题的两个关键因素：“特征”和“特征串”，一个“特征”是由两个有序整数组成的，例如有“特征”（2，3），那么，在对应的“特征串”中必然存在连续的两个数a1=2和ai+1=3。现在我们不妨把每个自然数抽象成一个顶点，i对应的顶点是Vi;把     

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

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

密码分析问题——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点出发,画出一条路径,每条边经过且只经过一次。     

搜寻恐怖分子题解——2002年第11期题解

问题描述见2002年第11期杂志。问题分析构造数学模型我们把ID和真实姓名看作图中的顶点,如果某个ID可以对应于某个真实姓名,则在这两个点之间连接一条边,这样构造了一个二部图。此二部图G共有2n个顶点,设X表示ID对应的顶点集合,Y表示真实姓名对应的顶点集合。初始的时候X中的每个点到Y中的每个点都有边相连,因为开     

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

由于是求必胜状态，因此在搜索过程中，先假设甲方(x)在第k步已经处于必胜状态，那么，乙方(o)的第k步无论下在哪儿，甲方下第k+1步的时候，至少能够找到一个位置保持这个状态，即要么甲方已经赢了，要么继续保持这个必胜状态。因为甲方一直都能够保持这个必胜状态，所以甲方最后一定能够赢棋，因此甲方的第k步就是本题的解。     

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

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

飞弹问题的算法分析——2003年第10期题解

问题描述: 见《程序员》杂志2003年第10期。算法分析: 我们不妨先将原问题描述用几何语言转化一下: 已知两个点集合R和W,各包含N个点,R U W中任三点不共线。求一种匹配,R集合中的每个点与W集合中的一点相连,满足所有N条连线段不相交。     

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串的长度的增加进行