备战noip2010提高组初赛复习——算法篇之算法设计的常用策略

《备战noip2010提高组初赛复习——算法篇之算法设计的常用策略》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、备战NOIP2010提高组初赛复习——算法篇之算法设计的常用策略程序设计主要包括两个方面l结构特性的设计（数据结构的设计）；l行为特性的设计（算法设计）；第一篇主要阐述了结构特性的设计，即如何为解题选择合适的数据结构。但这只是问题的一个方面。接下来的问题是如何将解题过程的每一个细节准确地加以定义，并用某种语言完整地描述出来。这一过程既所谓行为特性的设计，亦称算法设计。第二篇将围绕这个主题展开讨论。算法是一组(有限个)规则，它为某个特定问题提供了解决问题的运算序列。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实

2、现的算法。计算机解题的核心是算法设计。一个算法应该具有以下五个重要特征:(1)有穷性一个算法必须保证执行有限步之后结束；(2)确切性算法的每一步骤必须确切定义；(3)输入一个算法有0个或多个输入，以刻划运算对象的初始情况。所谓0个输入是指算法本身定出了初始条件；(4)输出一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；(5)能行性算法原则上能够精确地进行，而且人们用笔和纸做有穷次即可完成；下面，我们对构成算法所依据的一些基本方法和思路展开分析。对于读者来说，为了获得一个即有效又优美的算法，必须了解一些基本的常用的算法设计思路。现实世界的事物多姿多彩，千变万化

3、。我们不可能规定一些简单的条条框框和套用现成的模式去解决所有的问题。然而，现实世界也有大量事物存在着许多相似或相近的规律，存在本质相同的东西。正因为如此，就有可能形成一些常用的方法思路（策略），按照这些方法思路分析和求解试题，一般可使解题过程变得容易一些。本章将介绍几种典型的算法策略，这些策略常用于那些需要独立思考、见解独创和有所创新的非标准题。当然面对实际试题，究竟使用哪种方法，怎样用，需要“具体问题具体分析”，需要机智灵活，不宜死记成规、生搬硬套，得靠自己想方设法。所谓“阵而后战，兵法之常，运用之妙，存乎一心”是也。§5．1对应的策略将问题A对应另一个便于思考或有求解方法的问题B，化繁为简

4、，变未知为已知。一一对应技术是一种重要的策略。它的思维核心是求同，通过举一反三、触类旁通地对已经解决的类似问题和有关事实作联想，外推出事物间的联系，从而全面、深入地认识和分析事物。“世界上没有完全不同的东西”，相似点的普遍存在为我们使用对应策略解题提供了基础。但是对应并不等于等价，它不仅要分析问题间的共同点，还要分析问题间的不同点，是一种异中求同的思维方法。一、对应精典问题“客观世界物质第一性，思维第二性”。经典问题及其算法的知识积累是解题的基础。竞赛的许多试题最终都可以转化为经典问题，因此必须尽可能多地掌握经典问题及其算法的知识。解题时，心中经常要回忆已经解决的经典问题和有关解法，往往会收到

5、意想不到的效果。当然这些试题并不直接以经典问题的原貌出现。我们必须合理运用求同思维、求异思维比较两者间的相同点和不同点，通过适当的方法将试题转化为经典问题。【例题廿】换车问题一个城市有n个车站，已知m条连接这些车站的公共汽车单向路线。求站1至站n的最少换车数。输入：nm以下m行依次列出每条线路的车站序号。输出：最少换车次数。算法分析这个问题对我们来讲并非陌生。如果将问题要求改为“求站1到站n最少经过多少站”，就变为我们相当熟悉的最短路径的典型应用。即令有向图G=，

6、V

7、=n。若vi，vj∈V且(Vi，Vj)∈E当且仅当i站、j站在某条线路上相邻，(Vi，Vj)的权Wij设为1。显然，

8、汽车线路经过的站数=路径顶点数=路径边数+1=路径的权和+1。为使总站数最少，只要使路径的权和最小，即只要求出图G中Vi至Vj的最短路径即可。但现在的问题是求最少换车次数，虽然它与求经过最少站数的总是有共同背景，但要求不同。我们化异为同，重新对原图G作了修正：若Vi，Vj∈V且（Vi，Vj）∈E当且仅当站i与站j依次在同一条公共汽车线路上(Vi可直达Vj)，Wij仍为1。然后运用求最短路径方法计算V1至Vn的最短路径长度，其长度-1即为最少换车次数。设t—当前线路的车站数；oneline—当前线路的车站序列；g—有向图的相邻矩阵；我们按照下述算法计算最少换车次数：fillchar(g，size

9、of(g)，0)；{有向图初始化}fori：=1tomdo{读入每条线路的信息，构造g图}begint←0；fillchar(oneline，sizeof(oneline)，0)；{第i条线路初始化}whilenoteolndobegint←t+1；读第i条线路的第t个车站序号oneline[t]；forj：=1tot-1dog[oneline[j]，oneline[t]]←1；end；{whil