2001年第3期编程擂台题目：艺术品出售

D&D Corporation是一家专门从事艺术品买卖业务的公司。最近,D&D以低价收购了AT&T,Bell,Cisco,Dell,Epson公司的一些艺术品。这些艺术品可分为五类,不妨称其为A类,B类,C类,D类和E类。     

星图问题——2002年第4期题解

问题描述见2002年第4期杂志。问题分析这个问题比较简单,只需要对每个星座做几何变换并在星图中穷举其位置即可。下面我们分三步来解决这个问题。匹配星座设q_0,q_1,L,q_(m-1)为星座中的m个点,P_0,P_0,L,p_(m-1)为星图中与之匹配的m个点.且q_i对应的点为p_i,其中0 i m。我们称这样的一个匹配为该星座基于的匹配,称为该匹配的基。根据题意,每个q_i都是相对于q_0旋转同一个角度、缩放相同的比例、平移同样的位移得到的。     

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

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

骆驼商队问题——2001年11期编程擂台题解

问题描述见2001年第11期杂志。问题分析去除题目中的实际背景,本题可以用数学语言描述成:在一个带权无向图G中找出一生成子图G’,使得G’的每个顶点出度不超过1,并且G’所有边的权值之和最大。首先,如果这个图是不连通的,那么它的各个连通分量之间是没有任何联系的。对这些连通分量中的问题可以分别独立     

DEL命令问题——2001年12期编程擂台题解

问题描述见2001年第12期杂志。算法分析本题的基本思路是搜索出所有可能的含通配符的字符串,然后一一检查其是否满足题意。但是盲目搜索的运算量大得惊人,所以关键在于如何进行剪枝优化。为了更好地说明本题的算法,我们首先定义一些术语。·字母表达式:是指不含通配符?或*的字符串。例如abc是字母表达式,而a?b不是;     

三角形问题——2002年第1期编程擂台题解

问题描述见2002年第1期杂志。问题分析这次的题目很简单,参赛者也较多,但可惜的是大多数参赛者的程序都无法通过所有的测试数据。本题的关键之处在于思路要清楚,且必须非常细心。具体算法如下:     

正方形问题——2001年第1期程序擂台题解

(一)问题 在直角坐标平面中有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串的长度的增加进行     

Cantor表问题——2001年第4期程序擂台题解

每期收到读者的解答,总能看到很多欣喜的解答,这些解答偏离传统的思路,常常使问题本身更加引人入胜。我想这也是杂志开辟这个栏目让大家互相探讨算法的原因吧。我们真诚希望一切勇于创新的程序员加入到我们行列,提供新颖的解答或是提供具有挑战性的问题。     

勾股数问题——2001年第2期程序擂台题解

定义：如果直角三角形三条边长均为整数，这三个整数组成的数组就称为勾股数组，对于勾股数组(a、b、c)，根据定理有关系式：a^2+b^2=c^2。     

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

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

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

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

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

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

该出手时就出手——2001年配件市场趋势

也许,在上世纪,我们曾经用着486或奔腾机,或者我们只是眼巴巴地看了看商店橱窗里那台修饰得漂漂亮亮的电脑。我们熬过了一个世纪,已经没有再等待的理由了!电脑已经不再是一台高档打字机或者游戏机,也不是我们家里同神龛一样被供奉着的灵物。我们要用它设计、创意、上网,用它做我们喜欢做的所有事情。     

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

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

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

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