发布时间 : 星期六 文章NOIP初赛复习 - 算法1更新完毕开始阅读
OK备战NOIP2010提高组初赛复习 ——算法篇之算法设计的常用策略
程序设计主要包括两个方面
? 结构特性的设计（数据结构的设计）； ? 行为特性的设计（算法设计）； 第一篇主要阐述了结构特性的设计，即如何为解题选择合适的数据结构。但这只是问题的一个方面。接下来的问题是如何将解题过程的每一个细节准确地加以定义，并用某种语言完整地描述出来。这一过程既所谓行为特性的设计，亦称算法设计。第二篇将围绕这个主题展开讨论。
算法是一组(有限个)规则，它为某个特定问题提供了解决问题的运算序列。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。计算机解题的核心是算法设计。一个算法应该具有以下五个重要特征:
(1)有穷性 一个算法必须保证执行有限步之后结束； (2)确切性 算法的每一步骤必须确切定义；
(3)输入 一个算法有0个或多个输入，以刻划运算对象的初始情况。所谓0个输
入是 指算法本身定出了初始条件；
(4)输出 一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出
的算法是毫无意义的；
(5)能行性 算法原则上能够精确地进行，而且人们用笔和纸做有穷次即可完成；
下面，我们对构成算法所依据的一些基本方法和思路展开分析。对于读者来说，为了获得一个即有效又优美的算法，必须了解一些基本的常用的算法设计思路。
现实世界的事物多姿多彩，千变万化。我们不可能规定一些简单的条条框框和套用现成的模式去解决所有的问题。然而，现实世界也有大量事物存在着许多相似或相近的规律，存在本质相同的东西。正因为如此，就有可能形成一些常用的方法思路（策略），按照这些方法思路分析和求解试题，一般可使解题过程变得容易一些。 本章将介绍几种典型的算法策略，这些策略常用于那些需要独立思考、见解独创和有所创新的非标准题。当然面对实际试题，究竟使用哪种方法，怎样用，需要“具体问题具体分析”，需要机智灵活，不宜死记成规、生搬硬套，得靠自己想方设法。所谓“阵而后战，兵法之常，运用之妙，存乎一心”是也。
§5．1对应的策略
将问题A对应另一个便于思考或有求解方法的问题B，化繁为简，变未知为已知。
一 一对应技术是一种重要的策略。它的思维核心是求同，通过举一反三、触类旁通地对已经解决的类似问题和有关事实作联想，外推出事物间的联系，从而全面、深入地认识和分析事物。“世界上没有完全不同的东西”，相似点的普遍存在为我们使用对应策略解题提供了基础。但是对应并不等于等价，它不仅要分析问题间的共同点，还要分析问题间的不同点，是
一种异中求同的思维方法。 一、对应精典问题
“客观世界物质第一性，思维第二性”。经典问题及其算法的知识积累是解题的基础。竞赛的许多试题最终都可以转化为经典问题，因此必须尽可能多地掌握经典问题及其算法的知识。解题时，心中经常要回忆已经解决的经典问题和有关解法，往往会收到意想不到的效果。当然这些试题并不直接以经典问题的原貌出现。我们必须合理运用求同思维、求异思维比较两者间的相同点和不同点，通过适当的方法将试题转化为经典问题。 【例题廿】换车问题
一个城市有n个车站，已知m条连接这些车站的公共汽车单向路线。求站1至站n的最少换车数。 输入：
n m
以下m行依次列出每条线路的车站序号。 输出：
最少换车次数。
算法分析
这个问题对我们来讲并非陌生。如果将问题要求改为“求站1到站n最少经过多少站”，就变为我们相当熟悉的最短路径的典型应用。即
令有向图G=
但现在的问题是求最少换车次数，虽然它与求经过最少站数的总是有共同背景，但要求不同。我们化异为同，重新对原图G作了修正：
若Vi，Vj∈V且（Vi，Vj）∈E当且仅当站i与站j依次在同一条公共汽车线路上(Vi可直达Vj)，Wij仍为1。然后运用求最短路径方法计算V1至Vn的最短路径长度，其长度-1即为最少换车次数。设
t—当前线路的车站数；
oneline—当前线路的车站序列； g—有向图的相邻矩阵；
我们按照下述算法计算最少换车次数：
fillchar (g， sizeof (g)，0)； {有向图初始化}
for i：=1 to m do {读入每条线路的信息，构造g图}
begin
t←0； fillchar(oneline，sizeof(oneline)，0)； {第i条线路初始化}
while not eoln do begin
t←t+1；读第i条线路的第t个车站序号oneline[t]；
for j：=1 to t-1 do g[oneline[j]，oneline[t]]←1； end；{while} end；{for}
求g图中V1至Vn的最短路径长度dist[n]； 输出站1至站n的最少换车次数dist[n]-1；
由上可见，对应策略使用得如何，即与其掌握经典算法的多少和理解的透彻程度有关，也与其应用经典算法于实际的实践能力有关，更与其拓延经典算法应用范围的创造力息息相关。下例的解题过程将更清楚地说明这一点。 【例题廿一】寻找数列
寻找一个由整数组成的数列，其中任意连续p个整数之和为正，任意连续q个整数之和为负。若不存在这样的整数数列，则输出NO；否则输出其中一个数列。
算法分析
本题算法设计的关键在于连续之和的表示。如果我们就事论事，直接将第i+1个整数ai+1开始的k个整数之和描述成多项式ai+1+ai+2+?+ai+k的话，算法就很难建立了。为此，我们暂且撇去每一项数究竟为何值的具体细节，而将注意力集中至连续性这一特点上。设 si—数列前i个整数之和，即si=a1+a2+?+ai。其中s0=0 (0≤i≤n)。显然根据题意 si 由上述两组不等式引出有向图g，图中共有n+1个顶点，分别为s0?sn。若si>sj(0≤i，j≤n)，则从si往sj引出一条有向边。如图（n=6，p=5，q=3） 构造有向图g的过程如下： fillchar(g，sizeof(g)，0)； {有向图g的相邻矩阵初始化} fillchar(d，sizeof(d)，0)； {各顶点的入度序列初始化} for i：=0 to n do {根据两组不等式构造有向图g} begin if i+p≤n then begin g[i+p，i]←1；d[i]←d[i]+1；end；{then} if i+q≤n then begin g[i，i+q]←1；d[i+q]←d[i+q]+1；end；{then} end；{for} 显然按照上述定义，如果图g可以拓扑排序，其顶点的拓扑序列可以对应满足条件的整数数列；反之，不存在这样的整数数列： 对图g进行拓扑排序； if 图g有回路 then 无解退出 else 生成拓扑序列order[0]?order[n]； 如果图g可以拓扑排序，则按照下述方法将拓扑order转换成s数组： 拓扑序列中顶点对应的s值是递减的，其中s0=0。如果order[i]=0，则依次设定 sorder[0]=i， sorder[1]=i-1，??， sorder[i-1]=1，sorder[i]=0， sorder[i+1]=-1，??， sorder[n]=i-n 例如，对于(图5．1—2)中的有向图g，可以计算出拓扑序列 i： 0 1 2 3 4 5 6 i order[i] sorder[i] 0 2 2 1 5 1 2 0 0 3 3 -1 4 6 -2 5 1 -3 6 4 -4 即s0=0， s1=-3， s2=2， s3=-1， s4=-4， s5=1， s6=-2 根据s的定义，可得出 ai=(a0+a1+?+ai-1+ai) - (a0+a1+?＋ai-1)=si-si-1 即 a1=s1-s0=-3 a2=s2-s1=5 a3=s3-s2=-3 a4=s4-s3=-3 a5=s5-s4=5 a6=s6-s5=-3 显然，在这个整数数列中，任意连续５个整数之和为正，任意连续３个整数之和为负。 由拓扑序列构造整数数列的方法如下： fillchar(s，sizeof(s)，0)； for i：=0 to n do if order[i]<>0 then for j：= i downto 0 do s[order[j]]←s[order[j]]+1 else break； for j：=i+1 to n do s[order[j]]←i-j； for i：=1 to n do a[i]←s[i]-s[i-1]； 从形式上看，这道数列计算题似乎与图论风马牛不相干，题中即未出现图论中常见的“车站”，“城市”等顶点，也未出现“公路”，“铁路”等边，更未出现“长度”，“传输时间”等到权，但算法设计者却明白“它山之石可以攻玉”的道理，使用图论中的经典算法—拓扑排序漂漂亮亮地解决了该题。他独辟蹊径，把si作为顶点，s的大小关系作为边，并按照其递减顺序设定边的权值，其构思的巧妙令人叹服。正是这种创造力在解题过程中起了关键性的作用。 二、对应简单问题 有些试题的求解方法原本很简单，但由于其表现形式陌生，因此窄看感到棘手。但只要你果断地抓住主要矛盾，舍弃与目标无关的次要信息，去粗存精，去伪存真，由此及彼，由表及里，便可以返朴归真，将试题与一个简单的问题对应起来。 【例题廿二】删数问题 键盘输入一个高精度的正整数，去掉其中任意s个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s，寻找一种方案，使得剩下的数字组成的新数最小。 输入： n s