当前位置:首页 >> 学科竞赛 >>

信息学奥林匹克竞赛辅导课件:构造法


第三章 构造法

构造法:就是根据题设条件或结论所具有的特征、 性质,构造出满足条件或结论的数学模型,借助 于该数学模型解决问题的方法.

在现实世界中,有大量事物存在着许多相 似或相近的规律,存在着本质相同的东西。正 因为如此,在求解非标准题的过程中就有可能 形成一些常用的方法思路(策略),按照这些 方法思路分析和求解试题,一般可使解题

过程 变得容易一些。这些方法思路统称为构造法。
由于构造法比较综合地反映了选手的智慧、 知识基础和创造性思维的能力,因此是联赛的 考核重点。

从数学方法的分类来看,构造的数学模型属于初 等模型或优化模型。

一般地,数学模型具有三大功能: ? 1解释功能:利用数学模型说明事物发生的原因。 ? 2判断功能:利用数学模型判断原来的知识和认 识的可靠性。 ? 3预见功能:利用数学模型揭示事物的发展规律, 为人们的行为提供指导或参考。

构造法解题的思路或步骤可以 归纳为:

构造法解题的类型一般有:
1.数学建模:通过沿用经典的数学思想建立起 模型;或者提取现实世界中的有效信息,用 简明的方式表达其规律,这种规律可以是一 条代数公式、一幅几何图形、一个物理原理、 一个化学方程式等等。 2.直接构造问题解答:这是构造法运用的一种 简单类型。它只能针对问题本身,探索其独 有性质,不具备可推广性。 无论是直接构造问题解答还是数学建模, 都要通过算法来实现。

?

?

?

如何设计一个有较低编程复杂度和时空复杂度且 结构清晰的算法,十分重要。通常考虑的因素有: (1)选择的模型必须尽量多地体现问题的本质特征。但 这并不意味着模型越复杂越好、冗余的信息会影响算 法的效率。 (2)模型的建立不是一个一蹴而就的过程,而是要经过 反复地检验、修改,在实践中不断完善。 (3)数学模型通常有严格的格式,但程序编写形式可不 拘一格。

构造与建模是一个复杂的抽象过程。我们要善于描视 问题的本质,寻找突破口,进而选择适当的模型。构造 的模型可以帮助我们认识问题,不同的模型从不同的角 度反映问题,可以引发不同的思路,起到发散思维的作 用。

但认识问题的最终目的是解决问题,模型的固有性质 可帮我们建立算法,其优劣可以通过时空复杂度等指标 来衡量,但最终还是以程序的运行结果为标准。
所以模型不是一成不变的,同样要通过各种技术不 断优化。模型的产生虽然是人脑思维的产物,但它仍然 是客观事物在人脑中的反映。所以要培养良好的建模能 力,还必须依靠在平时的学习中积累丰富的知识和经验。

在建模过程中经常使用的策略有 ⑴对应策略:将问题a对应另一个便于思考或有求解方法的问题 b,化繁为简,变未知为已知。

对应经典问题 ? 对应简单问题 ? 对应数学问题 ⑵分治策略:将问题的规模逐渐减少,可明显降低解决 问题的复杂程度。算法设计的这种策略称之为分治策 略,即对问题分而治之。 ? 递推的分治策略
?

⑶归纳策略:归纳策略则是通过列举试题本身的
特殊情况,经过深入分析,最后概括出事物内在的一 般规律,并得到一种高度抽象的解题模型。 ? 递推式 ? 递归式 ? 制定目标 ? 贪心方案

在自然界或日常生活中,许多现象具有不确定的 性质,很难建立数据模型,一般采用模拟策略 ⑷模拟策略:模拟某个过程,通过改变数学模型 的各种参数,进而观察变更这些参数所引起过 程状态的变化,由此展开算法设计。模拟题没 有固定的模式,一般形式有两种:

?

随机模拟:题目给定或者隐含某一概率。设 计者利用随机函数和取整函数设定某一范围 的随机值,将符合概率的随机值作为参数。 然后根据这一模拟的数学模型展开算法设计。 由于解题过程借助了计算机的伪随机数发生 数,其随机的意义要比实际问题中真实的随 机变量稍差一些,因此模拟效果有不确定的 因素;

过程模拟:题目不给出概率,要求编程者按照 题意设计数学模型的各种参数,观察变更这些 参数所引起过程状态的变化,由此展开算法设 计。 模拟效果完全取决于过程模拟的真实性和 算法的正确性,不含任何不确定因素。由于过 程模拟的结果无二义性,因此竞赛大都采用过 程模拟。 模拟的解题方法一般有三种类型 ? 直叙式模拟 ? 筛选法模拟 ? 构造法模拟
?

第一节、对应策略
将问题a对应于另一个便于思考或有求解方 法的问题 b ,化繁为简,变未知为已知。

对应经典问题 ? 对应简单问题 ? 对应数学问题
?

一一对应技术是一种重要的策略。它的核心 是求同,通过举一反三、触类旁通地对已经解决 的类似问题和有关事实作联想,推导出事物间的 联系,从而全面、深入地认识和分析事物。“世 界上没有完全不同的东西”,相似点的普遍存在 为我们使用对应策略解题提供了基础。 但是对应并不等于等价,两个问题间的表 面相似并不等于本质的联系。对应策略不仅要分 析问题间的共同点,还要分析问题间的不同点, 是一种异中求同的思维方法.

一. 对应经典问题
经典问题及其算法的知识积累是解题的基 础,竞赛的许多试题最终都可以转化为经典问 题,因此必须尽可能多地掌握经典问题及其算 法的知识。解题时,心中经常回忆已经解决的 经典问题和有关解法,往往会收到意想不到的 效果。 当然这些试题并不直接以经典问题的原貌 出现。我们必须合理运用求同思维、求异思维 比较两者间的相同点和不同点,通过适当的方 法将试题转化为经典问题。

【例1】计算最少的公路造价 现有 n 个城市间的交通网,边上的权是公 路造价,任一对城市都是可以连通的。现在要 用公路把 n 个城市连接起来,这至少需要修筑 n-1条公路。如何设计可使得这 n 条公路的总造 价最少。 输入:顶点数 n 和边数 e ; 以下有 e 行,每行包括一条边的两个顶点。 输出: n - 1 行,每行为连接一条公路的两个城 市序号。

分析:我们以城市为顶点,公路为边,公路的造 价为边权,构造一张具有 n 个顶点的带权连通 图,这张连通图的生成树有 n - 1 条边。 问题对应为:如何在所有可能的生成树中,寻找 各边的权的总和为最小的一棵生成树。显然, 这个问题就是经典的最小生成树问题。

下图为 6 个城市间的交通网,边上的权是公路造价。 修筑 5 条公路的方案如下:

Prim算法
设G=(V,E)是连通带权图V={0,1,?,n-1},用邻接 矩阵c[i][j]表示图G中顶点i和顶点j之间的邻接关系 及边的权,若i,j不相连,则c[i][j]置为最大值99。 构造G的最小生成树的Prim算法的基本思想是:首 先置S={0},然后,只要S是V的真子集,就作如下的贪 心选择:选取满足条件i?S,j?{V-S},且c[i][j]最 小的边,将顶点j添加到S中。这个过程一直进行到S=V 时为止。 在这个过程中选取到的所有边恰好构成G的一棵最 小生成树。

带权图,按Prim算法选取边 的过程

在上述Prim算法中,还应当考虑如何有效 地找出满足条件i?S,j?V-S,且权c[i][j]最小 的边(i,j)。实现这个目的的较简单的办法是设 置两个数组closest和lowcost。 在Prim算法执行过程中,先找出V-S中使 lowcost值最小的顶点j,然后根据数组closest 选取边(j,closest[j]),最后将j添加到S中, 并对closest和lowcost作必要的修改。 用这个办法实现的Prim算法所需的计算时间 为W(n2)

#include <iostream> using namespace std; const int MAXINT=1000; const int INF=99; const int N=6; void main() { int c[N][N]={ {99,10,99,99,19,21}, {10,99, 5, 6,99,11}, {99, 5,99, 6,99,99}, {99, 6, 6,99,18,14}, {19,99,99,18,99,33}, {21,11,99,14,33,99}}; Prim(c); }

void Prim(int c[N][N]) { int lowcost[MAXINT]; //存放当前结点相连的权值 int closest[MAXINT]; //存放最近结节 bool s[MAXINT]; s[0]=true; //放入起始结点 for(int i=1;i<N;i++) { lowcost[i]=c[0][i];closest[i]=0;s[i]=false;} for(i=1;i<N;i++) { int min=INF; int j=0; for(int k=0;k<N;k++) if((lowcost[k]<min)&&(!s[k])) { min=lowcost[k];j=k;} cout<<j<<' '<<closest[j]<<endl; s[j]=true; for(k=1;k<N;k++) if((c[j][k]<lowcost[k])&&(!s[k])) {lowcost[k]=c[j][k];closest[k]=j;} } }

Kruskal算法
Kruskal算法构造G的最小生成树的基本思想是,首 先将G的n个顶点看成n个孤立的连通分支。将所有的边 按权从小到大排序。然后从第一条边开始,依边权递 增的顺序查看每一条边,并按下述方法连接2个不同的 连通分支:当查看到第k条边(v,w)时,如果端点v和w 分别是当前2个不同的连通分支T1和T2中的顶点时,就 用边(v,w)将T1和T2连接成一个连通分支,然后继续查 看第k+1条边;如果端点v和w在当前的同一个连通分支 中,就直接再查看第k+1条边。这个过程一直进行到只 剩下一个连通分支时为止。

对前面的连通带权图,按 Kruskal算法顺序得到的最小 生成树上的边如下图所示。

【例2】 换车问题
一个城市有 n 个车站,已知 m 条连接这些车站 的公共汽车单向路线。求站1至站n的最少换车 数。 输入: n m 以下 m 行依次列出每条线路的车站序号。 输出:最少换车次数。

分析:这个问题对我们来讲并不陌生。如果将问题要求改 为“求站 1 到站 n 最少经过多少站”,就变为我们相 当熟悉的最短路径的典型应用。

即令有向图G=<V,E>,|V|=n,若vi, vj属于E当且 仅当i站,j站在某条线路上相邻,(Vi ,Vj)的权Wij设为1。 显然,汽车线路经过的站数=路径顶点数=路径边数 +1=路径的权和+1。为使总站数最少,只要使路径的 权和最小,即只要求出图G中Vi至Vj间的最短路径即可。

但现在的问题是求最少换车次数,虽然它与求经 过最少站数总是有共同背景,但要求不同。我们化异为 同,重新对原图G作了修正。若 Vi,Vj属于E当且仅当站 i 与站 j 依次在同一条公共汽车线路上(Vi可直达Vj), Wij仍为1。然后运用求最短路径方法计算V1 至Vn的最 短路径长度,其长度减1即为最少换车次数。

【 例 3 】挖地雷 在一个地图上有n个地窖(n<=20),每个地窖中埋有 一定数量的地雷,同时,给出地窖之间的联系路径。 当地窖及其连接的数据给出之后,某人可以从任一 处开始挖地雷,然后可以沿着连接路径往下挖(仅能 选择一条路径),挖的过程中允许某人重复经过地窖。 当无连接时,挖地雷工作结束。设计一个挖地雷的方 案,使某人能挖到最多的地雷。

输入格式: n (表示地窖的个数) w1,w2,w3,…wn a(1,2)…a(1,n) a(2,3)…a(2,n) …… a(n-1,n) 表示地窖之间连接路径(其中aij表示地窖 i 和地窖 j 之间是否有通路:如果通,则 aij=1,不通 aij=0) 输出格式: r1-r2 … rk (挖地雷的顺序) max (为挖地雷的数量)

例如: V1,V2, V3, … V6表示地窖。 下图给出了一个示例:

?

分析:我们将地窖设为顶点,地窖之间的通路设为边, 每个地窖中的地雷数设为顶点的权,使得问题对应一个 顶点带权的无向图,解题的目的是要在这张图中寻找一 条路径,该条路径途经的地窖所含的地雷数最多。但是, 是否允许某人重复经过地窖是问题的关键。

如果不允许某人重复经过地窖,则最佳路径为 1-2-3 ,挖 到的地雷数为 13 ;如果允许某人重复经过地窖,则最佳 路径为 1 -2 -3 -2 -4 ,挖到的地雷数为 14 。

?

不允许重复的求解方法带有明显的阶段特征,允许重复 则不具备阶段特征。允许重复与不允许重复对应两种不 同的解决方法。
允许某人重复经过地窖实际上是允许挖地雷的顺序中出 现回路。无论该人怎样挖,其经过的路径必然在一个连 通子图中。我们采用计算无向图传递闭包的方法找出所 有的连通子图,并计算出其中顶点权(即地雷数)和最 大的一个连通子图。最后,从该连通子图的任一个顶点 出发,通过深度优先搜索输出挖地雷的顺序。

?

由上可见,对应策略使用得如何,既与其掌 握经典算法的多少和理解的透彻程度有关,也 与其应用经典算法于实践的能力有关,更与其 拓展经典算法应用范围的创造力息息相关。

二、对应简单问题
有些试题的求解方法原本很简单,但由 于其表现形式陌生,因此乍看感到棘手。 但只要你果断地抓住主要矛盾,舍弃与目 标无关的次要信息,去粗取精,去伪存真, 由此及彼,由表及里,便可以返朴归真, 将试题与一个简单的问题对应起来

【例5】密码锁 (lock)

凭借你多年的开锁经验,你马上断定眼前这扇门 用的是密码锁。只见锁身上有 n 行数字,在每行 数字末尾都有好几个数字拨盘。看着这一行行多 少不一的数字和数字末尾留下的空格,你忽然想 起了小时候经常玩的一个游戏:找规律。这个游 戏就是给你一个数列的前几项,让你填出后一项, 例如: 2 4 6 ( 8 ) 1 4 9 ( 16 )

在玩游戏的过程中,你发现了一个窍门,所 有这类问题,都可以用这种方法解决: 对于一个已知前 m 项的数列 a1 , a2 , a3 , … ,am,一定可以找到惟一一个不超过 m-1次的多项式f(x),使得 f(1) = a1 , f (2) = a2 … f (m)=am ,那么 f(m+1)就是要找的下一 项。 现在你决定用这种方法试着打开眼前这把密 码锁。

输入:第一行是一个整数 n,代表门上共有n行数 字,n<=100。 以下 n 行,每行对应门上的一行数字,每 行的数字不超过 1000 个。 输入的数字之间用空格隔开,每行末尾没 有多余的空格。 输入的数字都是绝对值小于108的整数。 输出:输出应该包括 n 行,每一行是根据输入数 据的规律推出的下一个数字,顺序与输入数据 相对应。结果的绝对值都小于 108 。

分析: (1)构造数列的通项公式: 这是最直接的方法。

对于已知m项的数列,构造出的通项公式共有m项, 当i<=m时,有且仅有一项不为零,而且等于 ai . 例如数列前 3 项为1,3,5, 通项公式为:

这种方法的缺点是运算过程中数的规模比 较大,如果用高精度计算,时空效率可能无法接 受。如果不用高精度,恐怕得不到准确解。 (2)求数列的 r 阶差数列 定理:如果一个数列的通项公式是关于自然数 n 的 r 次多项式,那么这个数列是r阶等差数列。 这个定理的证明很简单,只要反复进行以 g(n)=f(n)-f(n-1)的运算,求数列的差数列,就会 发现通项公式的次数每迭带一次都会降低一次, 最终原数列的 r 阶差数列就是一个常数列。也就 是说原数列是一个 r 阶等差数列。

数列 原数列 1阶差数列
2阶差数列 (常数列)

第1项 1 3
2

第2项 4 5
2

第3项 9 7

第4项 16

在这道题里,已知这个数列的通项公式有m-1 项,那么这个数列就是一个m-1阶的等差数列.于 是就可以借助等差数列求出数列的第m+1项,例 如表所示的数列 1 , 4 , 9 方法二比较简捷,要计算的数据不是很大, 而且计算量较小。算法的时间复杂度为w(m2/2), {m*(m+1)/2} 由于计算过程中有许多数据不需要 保存,所以空间需求是w(1)。

long r_cal(long num[],int m) { long result=0; //存放结果 for(int j=m-1;j>0;j--) //计算m-1阶等差数列的等差值 for(int k=0;k<=j-1;k++) num[k]=num[k+1]-num[k]; for(j=0;j<m;j++) result=result+num[j]; //计算第j行的最后一项 return result; }

【例6】 空中都市

在一个未来的空中都市中,有很多个小岛(城区)。 现在要求在这些岛之间架一些桥梁(桥是架在两 个岛之间的)。 要求:首先,如果A与B之间有桥,B与C之间有桥, 则A与C之间就不能再架桥了,即对于城市中的 任意三个岛,不能在其中两两都架上桥。 在这样的前提下,要求架的桥数最多(不考虑具体 的空间结构问题),并计算其中的一个可行方案。

输入文件只包含一行,该行为一个非负整数 n( 0<=n<=1000 ) ,即城市中有n个小岛。 输出文件:桥数的最大值 k,以下为 k 行,每行为一座桥 相邻的两个小岛序号(a , b) 输入示例: 6 输出示例: 9 (1,4) (1,5) (1,6) (2,4) (2,5) (2,6) (3,4) (3,5) (3,6)

分析:按照题意,如果小岛A与小岛B之间、小岛B 与小岛C之间和小岛A 与小岛C 之间都有桥的话, 则说明A, B, C三个小岛之间存在传递性。试题要 求构造一个含n个顶点且满足下述条件的图: (1)任三个顶点间不含传递性; (2)图中所含边数最多。

我们通过下述方法将空中都市问题对应一个简单 问题:把n个小岛分为尽量平均的两部分,第一 组为n/2或(n-1)/2个顶点,第二组为n/2 或(n + 1)/2 个顶点。然后第一组的每一个顶点分别向 第二组的所有顶点引出,如图所示:

?

由此得出桥的数目是:

?

下面,我们来证明这个构造方法的正确性。 由于两组的任一对顶点之间都有边相连,因 此如果再架桥的话,只能在同组的一对顶点之间 进行。如果在某一组的顶点 i 和顶点 j 间架桥, 则由于顶点 i 和顶点 j 与另一组的任一个顶点 k 相连,使得顶点 i 、顶点 j 和顶点 k 之间存在传 递关系,这是不允许的。而一个数拆分成两个数 的积,两个数的值愈接近,积愈大。由此可见, 按照上述方法得出的图所含边数最多。

#include <iostream> using namespace std; int main() { int n; //n为岛数 cin>>n; if (n%2==0) cout<<n*n/4<<endl; else cout<<(n-1)*(n+1)/4<<endl; for(int i=1;i<=n/2;i++) //枚举第一组岛屿 for(int j=n/2+1;j<=n;j++) //枚举第二组岛屿 cout<<'('<<i<<','<<j<<')'<<endl; //输出方案 return 0; }

三、对应数学问题 运用己学到的数学知识,对试题给出的 各个对象及其关系进行分析、演绎、归纳, 从而建立一个清晰简练的解析式,使得试题 与某个数学问题对应。当然,这个数学问题 的计算量非人工演算所能及,必须译成算法 语言,通过计算机运算方可完成。对应数学 问题的方式有两种: ? (1) 机理分析法 ? (2) 统计分析法

1.机理分析法 根据客观事物的特性,分析其内部的机理, 弄清关系,在适当抽象的条件下,得到可以描述 事物属性的数学工具。我们在联赛中可以用这种 方法建立数学模型,然后根据所对应的算法求出 解。

通过抽象建模得出对应信息原型的数学模型;然后 将数学模型理论对应到算法,并编程实现;最后 通过算法的执行得到问题的解。

【例7】国际象棋( knight )
?

国际象棋是我们休息娱乐时常玩的游戏。在各个棋子中, 马的行进方式最为特殊,也为人们所津津乐道。我们都 知道:马走的是“日”字,也就是说每次都是向水平或 竖直方向移动1格,而向另一个方向移动2格,所以也可 称作是 1x2 的马(走法如图所示)。在图中我们看到一 个马有 8 种跳的方向。

?

小明是一个数学爱好者,他将马的走法重新定 义了一下,重新定义后的广义马成为 nxm 的马。 为了研究广义马,小明让马从(0 , 0 )出发,随 意地在一张足够大的棋盘上移动。他发现,有 时候广义马总是无法跳入某些格子中,比如 2x2 的马永远不可能跳到(1, 1),这令他非常感 兴趣。他希望知道对于给定的 n , m , nx m的 广义马是否能够跳到所有的格子。由于 n , m 可以非常大,这令小明花了许多功夫在尝试上, 但仍不能得出肯定的结论。于是他就来找你这 个计算机专家帮忙了。

输入:在输入文件knight.in 中包含了多组测试数据,每 组测试数据占一行。每组测试数据由 2 个数 n , m (1 < = n <=108 , 1 <=m <=108)组成,表示广义马的 类型。文件最后一行由2个0 表示文件结束。 输出:将答案输出到文件 knight.out 中,每组测试数据 占一行。如果马能跳到指定的位置输出 YES ,否则输 出 Impossible 。 分析:通常,马的遍历问题都是用搜索解决的。但本题 中有一些特殊的地方:棋盘是无穷大的,马也是广义 的。另外,更重要的是问题规模相当大(1<=n <=108 , 1 <=m <=108) ,所以需要深入地研究这个问题。由 于计算哪些类型的马可以遍历整个棋盘似乎有些困难, 于是我们就先来研究对于给定的广义马,存在哪些到 不了的特殊位置。

首先从最简单的 1Xn 的广义马开始分析: ? (1)当 n 为奇数时,将棋盘染成黑白相间。若(0 , 0)为白色,因为每跳一步,马在竖直和水平方向 前进的步数之和(1+n)为偶数。所以自(0 , 0)出 发的马始终在白格子上跳跃,黑色的格子是马永 远到不了的。

(2)当 n 为偶数时,我们有这样的移动方案 (如图 ( b )所示),使得马从(0 , 0)开始经过一 系列的跳步后,到(1 , 0 )的位置,也就是说可 以让马到达相邻的格子,所以马可以遍历整个 棋盘。

?

?

?

下面我们分析一般的广义马。我们能否将 nxm 的广义马对应 1xn 的广义马呢?分析三种情况: 第 1 种情况:若n,m 有最大公约数 p ( p > 1 ) , 则马只能跳到形似(pxs , pxt)的格子上,其他的 格子都到不了。 第 2 种情况:若 n+m 是偶数,类似于 1xn 马 的情况,马只能在同色的格子内跳动,不能遍 历棋盘。

第3种情况:若 n +m 为奇数,且 n , m 互质。不妨设 n 为奇数,那么 m 为偶数。因为 1xn 马的问题已经 被彻底解决,所以很自然的想将 nxm 经过一系列变 换转化成 1xn 马的问题。我们可以看到马的跳法本质 上是 4 种(另 4 种可以看成是以下 4 种跳法反跳一 步) : ① ( m , n ) ② ( m ,-n) ③ ( n , m ) ④ ( n ,-m) 马经过跳 p 次 ①,q 次 ② ,r次 ③ ,s次 ④ 后 水平方向的位移为(p+q ) m +(r+s) n 竖直方向的位移为(p-q)n + (r-s) m 为了利用 1xn 马的结论,解不定方程 (p+q) m + (r+s)n=1 因为n, m 互质。该方程一定有解(p0, q0, r0, s0).

因为m 是偶数, n 是奇数,所以( r0 + s0)是奇数。 因为马要遍历整个棋盘,其竖直和水平方向前进的步 数之和(p0+q0)m+(r0+s0)n+(p0-q0)n+(r0s0)m 为奇数, 所以( p0-q0)是偶数。(p0-q0 ) n + ( r0-s0) m是偶 数。 也就是马通过一系列的跳动所得到的效果相当于 1xlen 的马跳一步的效果( len =(p0-q0 ) n + ( r0-s0 ) m)。根据前面的结论, 1 xlen 的马可以遍历整个棋 盘,所以当 n+m 为奇数且 n , m 互质时, nxm 的 马可以遍历整个棋盘。 算法的时间复杂度为W( 1 ) ,空间需求为W( 1 )。

#include <iostream.h> long gcd(long a,long b) //计算n和m的最大公约数 { if (b==0) return a; else return gcd(b,a%b); } void main() { long n,m; //n,m为广义马的类型 cin>>n>>m; //若n+m为偶数,无解 if ((n+m)%2==0) cout<<"Impossible"; else { if (n<m) //求gcd时,要求n>m { long temp; temp=n; m=n; n=temp;} //若n,m互质,输出成功,否则失败 if (gcd(n,m)==1) cout<<"YES"; else cout<<"Impossible"; } }

1657【例8】棋盘上的距离
国际象棋 的棋盘是黑白 相间的8 * 8的 方格,棋子放 在格子中间。 如下图所示:

王、后、车、象的走子规则如下: 王:横、直、斜都可以走,但每步限走一格。 后:横、直、斜都可以走,每步格数不受限制。 车:横、竖均可以走,不能斜走,格数不限。 象:只能斜走,格数不限。 写一个程序,给定起始位置和目标位置, 计算王、后、车、象从起始位置走到目标位置 所需的最少步数

Input 第一行是测试数据的组数t(0 <= t <= 20)。以下每行 是一组测试数据,每组包括棋盘上的两个位置,第一个 是起始位置,第二个是目标位置。位置用"字母-数字" 的形式表示,字母从"a"到"h",数字从"1"到"8"。 Output 对输入的每组测试数据,输出王、后、车、象所需的最少 步数。如果无法到达,就输出"Inf". Sample Input 2 a1 c3 f5 f8 Sample Output 2 1 2 1 3 1 1 Inf

解题思路
首先,王、后、车、象彼此独立,应分别考虑。 我们假设起始位置与终止位置在水平方向上的距离是x, 在竖直方向上的距离是y 王:所需要最小步数是min(x,y)+abs(x-y) 后:1步:当x==y或x==0或y==0 2步:当x!=y 车:1,当x==0或y==0 2,x!=0且y!=0 象:只能斜走,因此横纵坐标增减的数值相等,所以横纵 坐标之间的奇偶性无论如何都保持不变。横纵坐标之差 为奇数的点和为偶数的点不能相互到达。当它们属于同 一类点时, 1步,当|x|==|y|时 2步,当|x|!=|y|时

#include <cmath> using namespace std; int main() {int n,i; cin>>n; //n是测试数据组数 for(i=0;i<n;i++){ char begin[3],end[3]; cin>>begin>>end; int x=abs(begin[0]-end[0]); int y=abs(begin[1]-end[1]); if (x==0 && y==0) cout<<"0 0 0 0"; //在起始位置 else {if (x<y) cout<<y<<' '; else cout<<x<<' '; //王 if (x==y||x==0||y==0) cout<<1<<' '; else cout<<2<<' '; if (x==0||y==0) cout<<1<<' '; else cout<<2<<' '; if (abs(x-y)%2!=0) cout<<"Inf"; else if (x==y) cout<<1; else cout<<2; } cout<<endl; } return 0; }

2.统计分析法
我们在一时得不到事物的特征机理的情况 下,可通过某种方法测试得到一些数据(即问 题的部分解),再利用数理统计知识对数据进 行处理,从而得到最终的数学模型。统计分析 法是相对于机理分析法的逆向思维。这种方法 在实验性学科中应用十分广泛。例如在研究 f(x)= sinx 的图像时,我们先取一些特殊点,再 根据其大致走向作出函数图像。在联赛中,我 们亦可以用手工或简单的程序求出问题的部分 解,然后分析出其中的规律,得到数学模型。

先从信息原型出发,通过手工或简单的程序得 到问题的部分解。然后通过对部分解的分析, 运用数理统计得到信息原型的主要属性(这里 的属性大部分是某些规律),从而建立数学模型, 然后通过算法得出问题的全部解。

【 例9 】 极值问题
m , n 为整数,且满足下列两个条件: ① m ,n属于 1,2,3,… , k (1<=k<=109 ); ② (n2-mn-m2)2=1. 由键盘输入 k ,求一组满足上述两个条件的 m , n 并且 使 m2+ n2 的值最大。 分析:本题是一道数学性很强的试题。信息原型本身就具 有很强的抽象性。如果一开始就在抽象中分析,是很难 理清思路的。面对(n2-mn-m2)2=1这本来就十分抽象 的关系式,由于缺乏继续抽象的线索,自然也就无法通 过机理分析法得到对应的数学模型。这时统计分析法就 有了用武之地

首先,通过手工测试,我们得出了如表所示的 一些小的数据结果: 当m=1时, 可求出n=2; 当m=2时, 可求出n=3; 当m=3时, 可求出n=5; 当m=4时, n无整数解; 当m=5时, 可求出n=8; 我们将整理出的m,n排列在一起,有1 2 3 5 8

k

2

3

4

8

16

32

64

n
m

2
1

3
2

3
2

8
5

13
8

21
13

55
34

令人惊奇的是: n , m 随着 k 的增长以斐波纳契数列形 式增长!我们于是猜测:问题的解就是小于等于 k 的 最大的相临两个斐波纳契数。有了问题的研究方向, 我们就朝这个方向去设法证明自己的猜想。

如果我们的猜想正确,那么当(m,n)是方程(n2mn-m2)2=1的一组解时,根据斐波纳契数列关系, ( n,n+m)也一定是方程的一组解。 即((n+m)2-(n+m)n-n2)2=1 则: (n2+2mn+m2-n2-mn-n2)2=1 (mn+m2 -n2)2=1 若(n2-mn-m2)2=1 成立,则:以上各步可逆,所以 当(n,m)是方程的一组解时,(n,n+m)一定是方 程的另一组解。

#include <iostream> using namespace std; int main() { //m,n,next是斐波纳契数列的头三项 long m=1,n=1,next=2,k=0; //读入一个范围中的K while(k<1||k>1000000000) cin>>k; while(next<=k) //找出m,n的最大值 { m=n; n=next; next=m+n; } cout<<m<<' '<<n; return 0; }

【例10】取石子问题

有两堆石子,数量可能不同。有两个人轮流 取。每次有两种不同的取法。一是在任意一堆中 取走任意多的石子;二是在两堆中同时取走相同 数量的石子。最后把石子全部取完的是胜者。现 在给出初始的两堆石子的数目,如果轮到你来取, 又假设双方都采取最好的策略,问最后你是胜者 还是败者。

输入文件只有一行,包含两个非负整数 a 和 b , 表示两堆石子的数目。(a<=109 ,b<=109 )。 输出文件也只有一行,包含一个数字。如果最后你 是胜者,则输出 1 。反之,则输出0。 输入示例: 6 10 输出示例: 0

分析:我们无法直接从两堆石子的取法中找到规律。 在这种情况下,只能在测试得到的部分解答中寻 找出路。 (1)分析失败的情况 测试结果有两种可能 : ① 失败的情况: ( 1 , 2 ) ( 3 , 5 ) ( 4 , 7 ) ( 6 , 10 ) ( 8 , 13 ) ( 9 , 15 ) ( 11 , 18 ) ( 12 , 20 ) ( 14 , 23 ) ( 16 , 26 ) ( 17 , 28 ) ( 19 , 31 ) ( 21 , 34 ) … ② 胜利的情况: ( 1, 1 ) ( 1 , 3 ) ( 1 , 4 ) … 。胜 利的情况比失败的情况多得多。

在上述两种情况,我们选择相对容易得出的失败情 况展开分析,寻找规律。 ① 从 1 开始的每一个数字,在这些数字对中都会 出现一次且仅会出现一次; ② 数对的差成等差数列 1 , 2 , 3 , 4 . ③ 有些数对的数字排列(例如( 1 , 2 ) ( 3 , 5 ) ( 8 , 13 ) … )来自斐波纳契数列(例如 1 , 2 , 3 , 5 , 8 , 13 , 21… ) ; ④ 有些数对(例如( 4 , 7 )和( 11 , 18 ) … ),虽然 不是标准斐波纳契数列中的数字,但还是符合斐 波纳契数列的规则的;

⑤ 如果数对(a,b)出现在其中,则(a+b,a+2b)也必 然出现在数对中(相反的结论是不对的) ; ⑥ 数对中两个数之比都非常接近于0.618 ,即著 名的黄金分割数。 (2)判别 a , b 的输赢 由于从 1 开始的每一个自然数,按照斐波纳 契数列的规则不重复地出现在失败的数对中,因 此,可以得出如下结论:

若数对按照递增顺序排列成( a , b ),且满足

则确定 ( a , b )失败。由此得出算法:

#include <iostream.h> Void main() { long x,y,temp; cin>>x>>y; //按照递增顺序排列 x 和 y if (x>y) { temp=x;x=y;y=temp;} //若 x 和 y 接近黄金分割数,则失败; 否则胜利 if (x==y/1.618) cout<<0; else cout<<1; }

本节作业
简要回答如下问题: 1.什么是构造法?设计构造法模型通常要考虑哪 些因素? 2.在构造法建模过程中经常使用的策略有哪些? 3.对应策略通常分为哪几种类型? 4.对应数学问题有几种方式,其基本思想分别是 什么?

写出算法思想
例1 例5 例6 例8 例9

第二节、分治策略
将问题的规模逐渐减少,可明显降低解决问题 的复杂程度。算法设计的这种策略称之为分治策 略,即对问题分而治之。用分治策略求解一个问 题,所需的时间是由子问题的个数、大小以及把 这个问题分解为子问题所需的工作总量来确定。 一般来说,把任意大小的问题尽可能地等分成两 个子问题较为有效。竞赛中常用的分治策略有: ( 1 )递推的分治策略 ( 2 )递归的分治策略

? ?

一、分治算法总体思想
将要求解的较大规模的问题分割成k个更小规模的子 问题。

对这k个子问题分别求解。如果子问题的规模仍然不够小, 则再划分为k个子问题,如此递归的进行下去,直到问 题规模足够小,很容易求出其解为止。

将求出的小规模的问题的解合并为一个更大规模的问题 的解,自底向上逐步求出原来问题的解。

因此:分治法的设计思想是,将一个难以直 接解决的大问题,分割成一些规模较小的相同问 题,以便各个击破,分而治之。 当n=2时,分治法又称为二分法。 分治算法在每一层递归或递推分为三个步骤: ① 分:将原问题分解成一系列的子问题; ② 治:递归或递推地解各子问题,若子问题足够 小,则直接解之; ③ 合:将子问题的结果合并成原问题的解。 可以看到,决定算法时间效率的关键在于合并过程。

二、递归的概念
直接或间接地调用自身的算法称为递归算法。 用函数自身给出定义的函数称为递归函数。 由分治法产生的子问题往往是原问题的较小模式, 这就为使用递归技术提供了方便。在这种情况下,反 复应用分治手段,可以使子问题与原问题类型一致而 其规模却不断缩小,最终使子问题缩小到很容易直接 求出其解。这自然导致递归过程的产生。 分治与递归像一对孪生兄弟,经常同时应用在算 法设计之中,并由此产生许多高效算法。 下面来看几个实例。

例1 阶乘函数
阶乘函数可递归地定义为:

n?0 ? 1 n!? ? ?n(n ? 1)! n ? 0

边界条件

递归方程

边界条件与递归方程是递归函数的二个要素, 递归函数只有具备了这两个要素,才能在有限次计 算后得出结果。

例2 Fibonacci数列
无穷数列1,1,2,3,5,8,13,21,34, 55,……,称为Fibonacci数列。
1 n?0 ? ? F ( n) ? ? 1 n ?1 ? F ( n ? 1) ? F ( n ? 2) n ? 1 ?
边界条件

递归方程

第n个Fibonacci数可递归地计算如下:

int fibonacci(int n) { if (n <= 1) return 1; return fibonacci(n-1)+fibonacci(n-2); }

例3 Ackerman函数
A(1,0) ? 2 ? ? A(0, m) ? 1 m?0 ? ? A(n,0) ? n ? 2 n?2 ? ? ? A(n, m) ? A( A(n ? 1, m), m ? 1) n, m ? 1

当一个函数及它的一个变量是由函数 自身定义时,称这个函数是双递归函 数。

前2例中的函数都可以找到相应的非递归方式定义:

n!? 1? 2 ? 3 ??? (n ? 1) ? n
n ?1 n ?1 ? ? ? ? ? ? 1 ? 1? 5 1? 5 ? ? ?? ? ? F (n) ? ? ? 2 ? ? 2 5 ?? ? ? ? ? ??

本例中的Ackerman函数却无法找到非递归的定义

A(n,m)的自变量m的每一个值都定义了一个单变量函数: m=0时,A(n,0)=n+2 m=1时,A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2,和 A(1,1)=2故A(n,1)=2*n m=2时,A(n,2)=A(A(n-1,2),1)=2A(n-1,2),和 A(1,2)=A(A(0,2),1)=A(1,1)=2,故A(n,2)= 2^n 。 m=3时,类似的可以推出

n m=4时,A(n,4)的增长速度非常快,以至于没有适当的数 学式子来表示这一函数。

2 ?

2

2 ? 2

例4 排列问题
设计一个递归算法生成n个元素{r1,r2,…,rn}的 全排列。设R={r1,r2,…,rn}是要进行排列的n 个元素,Ri=R-{ri}。集合x中元素的全排列记 为perm(x)。 (ri)perm(x)表示在全排列perm(x)的每一个排列 前加上前缀得到的排列。R的全排列可归纳定义 如下:当n=1时,perm(R)=(r),其中r是集合 R中唯一的元素; 当n>1时,perm(R)由(r1)perm(R1), (r2)perm(R2),…,(rn)perm(Rn)构成。

template <class Type> void perm(Type list[],int k,int m) { //产生list[k:m]的所有排列 if (k==m) { //单元素排列 for(int i=0;i<=m;i++) cout<<list[i]; cout<<endl; } else //多元素序列,递归产生排列 for(int i=k;i<=m;i++) { swap(list[k],list[i]); perm(list,k+1,m); swap(list[k],list[i]); } }

template <class Type> inline void swap(Type &a,Type &b) { Type temp=a;a=b;b=temp; } #include <iostream.h> int main() { //示例0到4的全排列。 int a[5]={0,1,2,3,4}; perm(a,0,4); //示例’a’到’d’的全排列 char b[5]="abcd"; perm(b,0,3); return 0; }

例5 整数划分问题
将正整数n表示成一系列正整数之和。 n=n1+n2+…+nk, 其中n1≥n2≥…≥nk≥1,k≥1. 正整数n的这种表示称为正整数n的划分。求正整数n的不 同划分个数。 例如正整数6有如下11种不同的划分: 6; 5+1; 4+2,4+1+1; 3+3,3+2+1,3+1+1+1; 2+2+2,2+2+1+1,2+1+1+1+1; 1+1+1+1+1+1。

?

?

前面的几个例子中,问题本身都具有比较明显 的递归关系,因而容易用递归函数直接求解。 在本例中,如果设p(n)为正整数n的划分数, 则难以找到递归关系,因此考虑增加一个自变 量:将最大加数n1不大于m的划分个数记作 q(n,m)。可以建立q(n,m)的如下递归关系。

(1) q(n,1)=1,n≥1; 当最大加数n1不大于1时,任何正整数n只有一种 划分形式,即n=1+1+1+…+1 (2) q(n,m)=q(n,n),m ≥ n; 最大加数n1实际上不能大于n。因此,q(1,m)=1。 (3) q(n,n)=1+q(n,n-1); 正整数n的划分由n1=n的划分和n1≤n-1的划分组成。 (4) q(n,m)=q(n,m-1)+q(n-m,m),n>m>1; 正整数n的最大加数n1不大于m的划分由n1=m的 划分和n1≤m-1 的划分组成。 正整数n的划分数p(n)=q(n,n)。

1 n ? 1, m ? 1 ? ? q(n, n) n?m ? q(n, m) ? ? 1 ? q ( n , n ? 1 ) n ? m ? ? ?q(n, m ? 1) ? q(n ? m, m) n ? m ? 1

#include <iostream> using namespace std; int q(int n,int m) { if((n<1)||(m<1)) return 0; if((n==1)||(m==1)) return 1; if(n<m) return q(n,n); if(n==m) return q(n,m-1)+1; return q(n,m-1)+q(n-m,m); } void main() { cout<<q(6,6); }

例6 Hanoi塔问题
?

? ?

?

设a,b,c是3个塔座。开始时,在塔座a上有一叠共n个 圆盘,这些圆盘自下而上,由大到小地叠在一起。各 圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这 一叠圆盘移到塔座b上,并仍按同样顺序叠置。在移 动圆盘时应遵守以下移动规则: 规则1:每次只能移动1个圆盘; 规则2:任何时刻都不允许将较大的圆盘压在较小的 圆盘之上; 规则3:在满足移动规则1和2的前提下,可将圆盘移 至a,b,c中任一塔座上。

#include <iostream> using namespace std; void hanoi(int n, char a, char b, char c) { if (n > 0) { hanoi(n-1, a, c, b); move(a,c); hanoi(n-1, b, a, c); } }

void move(char x,char y) { cout<<x<<"-->"<<y<<endl; } int main() { int m; //盘子数 cin>>m; hanoi(m,'a','b','c'); return 0; }

【例7】排序工量(sequence quantity)
SORT 公司是一个专门为人们提供排序服 务的公司,该公司的宗旨是:“顺序是最美 丽的”。他们的工作是通过一系列移动,将 某些物品按顺序摆好。他们的服务是通过工 作量来计算的,即移动东西的次数。所以, 在工作前必须先考察工作量,以便向用户提 出收费数目。

用户并不需要知道精确的移动次数,实 质上,大多数人都是凭感觉来认定这一列物 品的混乱程度. 根据 SORT 公司的经验,人们一般是根 据“逆序对”的数目多少来称呼这一序列的 混乱程度的。假设我们将序列中第i物品的参 数定义为 ai,那么排序就是指将 a1 , … , an由小到大排列。若i<j 且 ai>aj ,则 <i,j>就为一个“逆序对”。

?

例如,数组( 3 , 1 , 4 , 5 , 2 )的“逆序对” 有<3 , 1 > , < 3 , 2 > , < 4 , 2 > , < 5 , 2 > , 共 4 个。

?

?

?

SORT 公司请你写一个程序,在尽量短的时间 内,统计出“逆序对”的数目。 输入:n, a1 , … , an,其中n<10000,ai为 小于 1000 的正整数 输出:数列 a1 , … ,an的“逆序对”数目, 即“逆序数”

分析:( 1 )简单搜索法 要单纯地计算出结果并不难,最直接,最简易的方 法就是使用两重循环,依次枚举数列中 i < j 的所有数 对(ai , aj),判断 ai 是否大于aj,大于则统计“逆序对” 的数目。 int n,a[10000],c=0; //c是逆序对个数 cin>>n; //n是数据个数 for(int i=0;i<n;i++) cin>>a[i]; //使用两重循环依次列举所有数对 for(i=0;i<n-1;i++) for(int j=i+1;j<n;j++) if(a[i]>a[j]) c++; //判断是否为逆序对,是则计数

我们可以看到这种算法虽然简捷,但两重 循环中循环体共执行了n*(n-1)/2,即时间复杂 度为W(n2) ,当n很大时,程序出解速度非常慢, 运行效率较低。那么有没有什么更好的算法可 以降低程序的时间复杂度,提高程序的运行效 率呢?

( 2 )分治算法(Divide and Conquer) 我们用数组 a[lo.. hi]存放当前子数列,用d(lo, hi) 记录该子数列中的所有逆序对。 ? 分:令med=[(lo+hi)/2],将子数列a[lo.. hi]分成 元素个数尽量相等的两部分:左子数列a[lo.. med]和右子数列a[med+1,hi],两个子数列已按 由小到大的顺序排序。继续划分子数列,直至 lo=hi 为止。

?

?

治:若逆序对的两个数分别取自子数列 a[lo.. med] 和 a[med+1.. hi] 的话,则将该逆序对存入 f(lo, med, hi)。 合:显然 a[lo.. hi]中的逆序对数d(lo,hi) =其子数列a[lo .. med] 中的逆序对数d(lo, med) +a[med+1..hi]中逆序对数d(med+1, hi) +当前数列新得逆序对数f(lo, med , hi) ,

即 d(lo, hi)=d(lo, med)+d(med+1 ,hi)+f(lo, med , hi )

最后得到的d(lo,hi)中的逆序对个数就是我们所求的结 果。而计算当前子数列的f(lo,med,hi )的快慢是算法时 效的瓶颈。如果摆脱不了“搜索思想”的影响,依然用两 重循环来算的话,其时效不会提高。
?

设指针i, j分别指向左子数列 a[lo..med]和右子数列 a[med+1..hi]中的某个数,即 lo<=i<=med , med+1<=j<=hi。
?

?

显然 i < j ,如果a[i]>=a[j],即a[i],a[j]为一对逆序 对时,则继续向下比较,直至 a[j]>=a[i]。因为子数 列 a[lo.. med]和 a[med+1 ..hi] 己按由小到大的顺 序排序,可知 a[med+1] ,…, a[j-1]均小于 a[i],计算 可得a[med+1..hi]中比 a[i] 小的数共有j-med-1个, 如图所示。将j-med-1 计入 f(lo , med , hi)。

由于 a[lo..med]和 a[med+1.. hi]均已排序,因此 只要顺序移动 i , j 就能保持以上条件,这是合并 的时间复杂度为线性时间的根本原因。例如由图 (a)的状态到图 (b)的状态只需将 i 顺序移动一个位 置,将 j 顺序移动三个位置。可见分治算法成功地 将时间复杂度降为W(nlogn),并且在求逆序数的同 时将数列排序。

int sorting(int lo,int hi) { int med,i,j,k,c=0; //中间指针,左指针,右指针,排序指针,逆序对 if (lo<hi) { med=(lo+hi)/2; c=c+sorting(lo,med); c=c+sorting(med+1,hi); i=lo; k=lo; j=med+1; while((i<=med)||(j<=hi)) { if((i<=med)&&((j>hi)||(a[i]<=a[j]))) { b[k]=a[i]; i++; c=c+(j-med-1);} else { b[k]=a[j]; j++;} k++; } for(i=lo;i<=hi;i++) a[i]=b[i]; }return c; }

主程序如下: #include <iostream> using namespace std; int a[10000]; //存放数列 int b[10000]; int main() { int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; cout<<sorting(1,n); return 0; }

【例8】棋盘覆盖

在一个2k×2k 个方格组成的棋盘中,恰有一 个方格与其它方格不同,称该方格为一特殊方格, 且称该棋盘为一特殊棋盘。

?

在棋盘覆盖问题中,要用图示的4种不同形态 的L型骨牌覆盖给定的特殊棋盘上除特殊方格 以外的所有方格,且任何2个L型骨牌不得重叠 覆盖。

当k>0时,将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘(a)所 示。 dc

?

dr 特殊方格必位于4个较小子棋盘之一中,其余3个子棋盘 中无特殊方格.为了将这3个无特殊方格的子棋盘转化为 特殊棋盘,可以用一个L型骨牌覆盖这3个较小棋盘的会 合处,如 (b)所示,从而将原问题转化为4个较小规模的 棋盘覆盖问题.递归地使用这种分割,直至棋盘简化为 棋盘1×1。

用一个二维数组Board表示棋盘,Board[0][0]是棋盘的左上角方格 tile是表示骨牌的编号,其初始值为0。 void chessBoard(int tr, int tc, int dr, int dc, int size) //棋盘左上角行号,列号,特殊方格所在的行号,列号,size=2k. { if (size == 1) return; int t = tile++, // L型骨牌号 s = size/2; // 分割棋盘 // 覆盖左上角子棋盘 if (dr < tr + s && dc < tc + s) // 特殊方格在此棋盘中 chessBoard(tr, tc, dr, dc, s); else {// 此棋盘中无特殊方格 // 用 t 号L型骨牌覆盖右下角 board[tr + s - 1][tc + s - 1] = t; // 覆盖其余方格 chessBoard(tr, tc, tr+s-1, tc+s-1, s);}

// 覆盖右上角子棋盘 if (dr < tr + s && dc >= tc + s) // 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else {// 此棋盘中无特殊方格 // 用 t 号L型骨牌覆盖左下角 board[tr + s - 1][tc + s] = t; // 覆盖其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s);} // 覆盖左下角子棋盘 if (dr >= tr + s && dc < tc + s) // 特殊方格在此棋盘中 chessBoard(tr+s, tc, dr, dc, s); else {// 用 t 号L型骨牌覆盖右上角 board[tr + s][tc + s - 1] = t; // 覆盖其余方格 chessBoard(tr+s, tc, tr+s, tc+s-1, s);}

// 覆盖右下角子棋盘 if (dr >= tr + s && dc >= tc + s) // 特殊方格在此棋盘中 chessBoard(tr+s, tc+s, dr, dc, s); else {// 用 t 号L型骨牌覆盖左上角 board[tr + s][tc + s] = t; // 覆盖其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s);} }

分治法的适用条件
分治法所能解决的问题一般具有以下几个特征:
? ?

该问题的规模缩小到一定的程度就可以容易地解决; 该问题可以分解为若干个规模较小的相同问题,即该问 题具有最优子结构性质(问题的最优解包含其子问题的 最优解) 该问题所分解出的各个子问题是相互独立的,即子问题 之间不包含公共的子问题。

? ?

利用该问题分解出的子问题的解可以合并为该问题的解;

上述的第一条特征是绝大多数问题都可以满足的, 因为问题的计算复杂性一般是随着问题规模的增加而增 加; 第二条特征是应用分治法的前提,它也是大多数问 题可以满足的,此特征反映了递归思想的应用; 第三条特征是关键,能否利用分治法完全取决于问 题是否具有第三条特征,如果具备了第一条和第二条特 征,而不具备第三条特征,则可以考虑贪心法或动态规 划法。 第四条特征涉及到分治法的效率,如果各子问题是 不独立的,则分治法要做许多不必要的工作,重复地解 公共的子问题,此时虽然可用分治法,但一般用动态规 划法较好。

分治法的基本步骤
divide-and-conquer(P) { if (|P|<=n0) adhoc(P); //解决小规模的问题 divide P into smaller subinstances P1,P2,...,Pk; //分解问题 for(i=1;i<=k;i++) //递归的解各子问题 yi=divide-and-conquer(Pi); return merge(y1,...,yk); //将各子问题的解合并为原问题的解 }

人们从大量实践中发现,在用分治法设计算法时, 最好使子问题的规模大致相同。即将一个问题分成大 小相等的k个子问题的处理方法是行之有效的。这种 使子问题规模大致相等的做法是出自一种平衡 (balancing)子问题的思想,它几乎总是比子问题规 模不等的做法要好。 从分治法的一般设计模式可以看出,用它设计的程 序一般是一个递归算法。

本节作业
1.分治算法总体思想是什么? 2.分治策略可以分为哪几种类型? 3.分治法的适用条件 4.分治法的基本步骤 例4 例5 例7


相关文章:
信息学奥林匹克竞赛培训教案
信息学奥林匹克竞赛培训教案_学习计划_计划/解决方案...计算机由美国宾夕法尼亚大学的物理学家约翰·莫 克...利用循环结构程序设计, 使得我 们有可能只编写少量...
信息学奥林匹克竞赛培训教案(校本课程)
信息学奥林匹克竞赛培训教案(校本课程)_学科竞赛_高中...计算机由美国宾夕法尼亚大学的物理学家约翰 · ...第 3 课 选择结构程序设计(20071224) 请参阅《...
信息学奥林匹克竞赛辅导Pascal语言
搜试试 3 帮助 全部 DOC PPT TXT PDF XLS ...顺序结构程序设计 第四章 选择结构程序设计 第五章...界法 第三章 A*算法 信息学奥林匹克竞赛辅导 ...
信息学奥赛辅导
迈出起跑线 ——信息学奥辅导手记“更快、更高、更强”奥林匹克精神几乎尽...开发脑智力的好方法,也是素质教育的重要内容。程序设计竞赛活动同素质教育没有矛盾...
信息学奥赛(初赛)辅导教材
数据表的结构 3.表结构 7 7 8 8 9 12 13 13 15 16 16 17 19 19 22 23 23 23 23 24 24 24 24 II 金华一中信息学(计算机)奥林匹克竞赛辅导教程 ...
信息学奥林匹克竞赛程序设计快速入门篇
190379824.doc 1、 实验一、 顺序结构程序设计 编写...信息学奥林匹克竞赛程序设计快速入门篇(C 语言) s...[·方法 1·] #include "stdio.h" main() { ...
程序设计竞赛辅导
搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...信息学奥林匹克竞赛培训... 80页 免费 小学生Pascal...使用递推(迭代)法构造算法的基本方法是:首先确定一...
怎样做好信息学奥赛培训辅导
信息学奥林匹克竞赛是智力与计算机应用的比赛,是推动...共同提高辅导水平,我将自己的培训经历、方法、思路...数据结构的应用(共需课时十二次课) 第一章 线性表...
(信息学奥赛辅导)程序设计试题汇编(答案)
搜试试 7 帮助 全部 DOC PPT TXT PDF XLS ...程序结构 第 页共 75 页信息学奥林匹克竞赛辅导—...闰年的计 算方法如下:若(( year mod 4 =0)and...
全国信息学奥赛NOI培训教程(Pascal 2016)
界法 第三章 A*算法 第 3 页共 230 页 全国信息学奥赛 NOI 培训教程 青少年信息学奥林匹克竞赛情况简介信息学奥林匹克竞赛是一项旨在推动计算机普及的学科竞赛...
更多相关标签: