当前位置:首页 >> 学科竞赛 >> 信息学奥赛数据结构辅导资料

信息学奥赛数据结构辅导资料






1、数据结构基础知识……………………2 2、动态规划………………………………17 3、分支限界………………………………19 4、分治策略………………………………21 5、排序算法………………………………28 6、贪心算法………………………………45 7、计算机基础知识练习题………………51 8、附录——基础知识练习题参考答案…7

8

数据结构
数据结构是计算机专业基础课程之一, 是十分重要的核心课程。 计算机的所有系统软件 和应用软件都要用到各种类型的数据结构。 要想更好地运用计算机来解决实际问题, 仅仅学 习计算机语言而缺乏数据结构知识是远远不够的,而打好“数据结构”这门课程的扎实基 础,对于学习计算机机专业的其他课程都是十分重要的。 随着计算机应用领域不断扩大,非数值计算问题占据了当今计算机应用的绝大多数, 简单的数据类型已经远远不能满足需要, 各数据元素之间的复杂联系已经不是普通数学方程 所能表达的。因此,掌握好数据结构方面的知识,对于提高我们解决实际问题的能力将会有 莫大的帮助。 实际上一个好的程序无非是选择一个合适的数据结构和好的算法, 而好的算法 的选择很大程度上取决于描述实际问题的数据结构的选取。所以,学好数据结构,将是进一 步提高我们程序设计的关键之一。所以通常我们在程序设计时,所遇到的首要问题就是:选 择什么样的数据结构才合适呢?这个问题十分关键。下面我们就各种数据结构作一些引导。

线 性 表
数据表是最常用且比较简单的一种数据结构, 它是由有限个元素组成的有序集合, 每个 元素由一个或多个数据项组成。 线性表具有如下的结构特点: ①均匀性:虽然不同数据表的数据元素可以是各种各样的,但对于同一线性表的各数 据必定具有相同的数据类型和长度。 ②有序性:各数据元素在线性表中的位置只取决于它们的序号,数据元素之间的相对 位置是线性的, 即存在唯一的“第一个”和“最后一个”的数据元素, 除第一个和最后一个 外,其他的元素前都只有一个数据元素(直接前趋)和后面只有一个数据元素(直接后继)。

队列 2.4.1 抽象数据类型队列的定义
和栈相反, 队列(Queue)是一种先进先出(First In First Out,缩写为 FIFO)的线性表。 队列 它只允许在表的一端进行插入, 而在另一端删除元素。 这和我们日常生活中的排队是一致的,

1

最早进入队列的元素 最早离开。在队列中,允许插入的一端叫做队尾 队尾(rear),允许删除的 队尾 一端则称为队头 队头(front)。 队头 假设队列为 q=(a1,a2,...an),那么,a1 是队头元素,an 则是队尾元素。队列中的 元素是按照 a1,a2,...an 的顺序进入 的,推出队列也只能按照这个次序依次推出,也就是 说,只有在 a1,a2,...an-1 都离开队列之后,an 才能 推出队列。 如图所示:

堆栈 2.2 表达式求值
表达式求值是程序设计语言编译中的一个最基本问题. 表达式求值是程序设计语言编译中的一个最基本问题.它的实现 是栈应用的一个典型例子. 介绍一种简单直观,广为使用的算法, 是栈应用的一个典型例子.这里 介绍一种简单直观,广为使用的算法, 通常成为"算符优先法". 通常成为"算符优先法".
要把一个表达式翻译成正确求值的一个机器指令序列,或直接对表达式求值,首先要能 够正确 解释表达式.要对表达式求值,首先要了解算术四则运算的规则.即: ? 1) 先乘除,后加减; ? 2) 从左算到右; ? 3) 先括号内,后括号外. 算符优先法就是根据这个运算优先关系的规定来实现对表达式的编译或解释执行 的. 任何一个表达式都是由数,运算符和界限符组成的,我们称它们为单词.为了叙述的 简洁,我们 仅讨论简单算术表达式的求值问题.这种表达式只含加,减,乘,除等四种运算符. 读者不难将它推 广到一般的表达式上. 我们把运算符和界限符统称为算符,它们构成的集合命名为 OP.根据上述三条运 算规则,在运算 的每一步中,任意两个相继出现的算符 θ1 和 θ2 之间的优先关系至多是下

2

面三种关系之一; θ1<θ2θ1 的优先权低于 θ2 θ1="θ2θ1 的优先权等于 θ2" θ1>θ2θ1 的优先权高于 θ2 表 3.1 定义了算符之间的这种优先关系.

为实现算符优先算法,可以使用两个工作栈.一个称作 OPTR,用以寄存运算符;另一 个称作 POND ,用以寄存操作数或运算结果.算法的基本思想是: ? 1)首先置操作数栈为空,表达式起始符"#"为运算栈的栈底元素; ? 2)依此读入表达式中每个字符,若是操作数则进 OPND 栈,若是运算符,则和 OPTR 栈的栈顶 运算符比较优先权后 作相应操作,直至整个表达式求值完毕(即 OPTR 栈 的栈顶元素和当前读入的字符均为"#"). 以下算法描述了这个求值过程. FUNC exp_reduce:operandfype; {算术表达式求值的算符优先算法.假定从终端输入的表达式无语法错误,以"#"作结束 符. 设 OPTR 和 OPND 分别为运算符栈和操作数栈,OP 为运算符的集合} INISTACK(OPTR);PUSH(OPTR,'#');INISTACK(OPND); {栈初始化,并在运算符栈的栈底压入表达式左端的虚设字符'#'} read(w);{从终端接受一个字符} WHILE NOT ((w='#')AND(GETTOP(OPTR)='#'))DO IF w NOT IN op THEN PUSH(OPND,w) ELSE CASE precde(GETTOP(OPTR),w)OF '<':[PUSH(OPTR,w);read(w)];{栈顶元素优先权低} '=":[x:=POP(OPTR);read(w)]; {脱括弧并接受下一字符} ">':[theta:=POP(OPTR); b:=POP(OPND); a:=POP(OPND); PUSH(OPND,operate(a,theta,b))]{退栈并将运算结果入栈} ENDC; RETURN(GETTOP(OPND)) ENDF;{exp_reducde} 算法中还调用了两个函数。其中 precede 是判定运算符栈的栈顶运算符 θ1 与读入的 运算符 θ2 之间优先关系的函数;orerate 为进行二元运算 aθb 的函数,如果是编译表达 式, 则产生这个运算的一组相应指令并返回存放结果的中间变量名; 如果是解释执行表达式, 则直接进行该运算,并返回运算结果。

3

例 3-2 利用算法 exp_reducde 对算术表达式 3*(7-2)求值,操作过程如下所示。

2.3.1 递归过程及其实现
栈的另一个重要应用是在程序设计语言中实现递归过程。一个直接调用自己或通 递归过程。 递归过程 过一系列的过程语句间接地调用自己的过程,称做递归过程 递归过程。 递归过程 例如, PROCEDURE A; BEGIN · · · A; · · · END; 过程 A 中的语句 A 直接调 用了过程 A 本身,这叫做直接递归调用 直接递归调用。又如: PROCEDURE B; PROCEDURE C; BEGIN 直接递归调用 BEGIN · · · · · · C; C; · · · · · · END; END; 在过程 B 中调用了过程 C,而过程 C 又调用了过程 B.这两个过程都通过另一个过程调用了它们自己, 这就叫做间接 间接 调用。 调用 递归是程序设计中一个强有力的工具。 ? 其一,有很多数学函数是递归定义的,如大家熟悉的阶乘函数 Fact(n)=1 若 n = 1 Fact(n)= n·Fact(n-1) 若 n >1 2 阶 Fibonacci 数列 Fib(n)=0 若 n=0 Fib(n)=1 若 n=1 Fib(n)=Fib(n-1)+Fib(n-2) 其它情形 和 Ackerman 函数 Ack(m,n)=n+1 m=0 Ack(m,n)=Ack(m-1,1) n=0 Ack(m,n)=Ack(m-1,Ack(m,n-1)) 其 它情形等; ? 其二,有的数据结构,如二叉树,广义表等,由于结构本身固有的递归特性, 则它们的操作可递归地描述; 其三,还有一类问题,虽则问题本身没有明显的递归结构,但用递归求解比迭代 求解更简单,如八皇后问题,Hanio 塔问题等.


5.1 树的结构定义和基本操作
树(Tree)是 n(n>=0)个结点的有限集。在一棵非空树中: (1) 有且仅有一个特定的称为根的结点; (2) 当 n>1 时其余结点可分为 m(m>0)个互不相交的有限集 T1,T2...Tm,其中,每一个集

4

合 本身 又是一棵树, 并且称为根的子树(subtree)例如,在图 6.1 中,(a)是只有一个根 结点的树;(b)是有 13 个结点的树,其中 A 是根,其余结点分成三个互不相交的子树:

树是一种数据结构 : Tree=(D,R) 其中:D 是具有相同特性的数据元素的集合;若 D 只含一 个数据元素,则 R 为空集,否则 R 是 D 上 个二元关系的集合, R={H}。 为如下描述二元关 即 H 系: ? (1) 在 D 中存在发唯一的称为根的数据元素,它在关系 H 下无前驱; ? (2) 若 D-{root}≠φ,则存在 D-{root}的一个划分 D1,D2,...Dm(m>0),对任意一对 j≠k (l<=j,k<=m)有 Dj∩Dk=φ,且对任意的 i(l<=i<=m),唯一存在数据元素 Xi∈Di,有 ∈H; ? (3) 对应于 D-{root}的划分,H-{ ,..., }有唯一的一个划分 H1,H2,...,Hm(m>0), 对任意一对 j≠k(l<=j,K<=m)有,Hj∩Hk=φ,且对任意的 i(l<=i<=m)Hi 是 Di 上的 二元关系,(Di,{Hi})是一棵符合本定义的树,称为根 root 的子树。 树结构中的一些基本术语: ? 结点的度:结点拥有的子树数。 ? 叶子(终端结点):度为零的结点。 ? 非终端结点(分支结点):度不为零的结点。 ? 树的度:树内各结点的度的最大值。 树的基本操作: (1) INITIATE(T) 初始化操作,置 T 为空树。 (2) ROOT(T)\ROOT(X) 求根函数。求数 T 的根或求结点 x 所在的树的根结点。若 T 是空树或 X 不在任何一棵树上,则函数值为“空”。 (3) RARENT(T,x) 求双亲函数。求树 T 中结点 x 的双亲结点。若结点 x 是树 T 的根结点或结 点 x 不在 T 中,则函数值为“空”。 (4) CHILD(T,x,i) 求孩子结点函数。求数 T 中结点 x 的第 i 个孩子结点。若结点 x 是树 T 的叶子或无第 i 个孩子或结点 x 不在树 T 中,则函数值为“空”。 (5) RIGHT_SINLING(T,x)求右兄弟函数。求树 T 中结点 x 右边的兄弟。若结点 x 是其双亲的 最右边的孩子结点或结点 x 不在树 T 中,则函树值为“空”。 (6) CRT_TREE(x,F) 建树操作。生成一棵以 X 结点为根,以森 F 为子树森林的树。 (7) INS_CHILD(y,i,x) 插入子树操作。置以结点 x 为根的树为结点 y 的第 i 棵子树。若原 树中无结点 y 或结点 y 的子树个数&gti-1,则空操作。 (8) DEL_CHILD(x,i) 删除子树操作。删除结点 x 的第 i 棵子树。若无结点 x 或结点 x 的子 树个数&gti,则空操作。

5

(9) TRAVERSE(T) 遍历操作。按某个次序依此访问树中各个结点,并使每个结点只被访问一 次。 (10) CLEAR(T) 清除结构操作。将树 T 置为空树。

5.2.1 二叉树定义与基本操作
二叉树(binary tree)是另一种树型结构,它的特点是每个结点至多只有二棵子 二叉树 树(即二叉树中不存在度大于 2 的结点),并且,二叉树的子树有左右之分,其次序不能任意 颠倒. 二叉树是一种数据结构 : Binary_tree=(D,R) 其中:D 是具有相同特性的数据元素的集合;若 D 等于空,则 R 等于空称为空的二叉树;若 D 等于空则 R 是 D 上某个二元关系 H 的集合,即 R={H},且 (1) D 中存在唯一的称为根的元素 r,它的关系 H 下无前驱; (2) 若 D-{r}不等于空,则 D-{r}={Dl,Dr},且 Dl 交 Dr 等于空; (3) 若 Dl 不等于空,则在 Dl 中存在唯一的元素 xl,〈r,xl〉属于 H,且存在 Dl 上的关系 Hl 属于 H;若 Dr 不等于空,则在 Dr 中存在唯一的元素 xr,〈r,xr〉>属于 H, 且存 Dr 上的关 系 Hr 属于 H;H={r,xl,<r,xr>,Hl, Hr}; (4) (Dl, Hl)是一棵合本定义的二叉树,称为根 r 的左子树,(Dr,Hr)是一棵符合定 义的二叉树,称为根的右子树。 其中,图 6.2 是各种形态的二叉树.

(1)为空二叉树 (2)只有一个根结点的二叉树 (3)右子树为空的二叉树 (4)左子树为空 的二叉树 (5)完全二叉树 二叉树的基本操作: (1)INITIATE(BT) 初始化操作。置 BT 为空树。 (2)ROOT(BT)\ROOT(x) 求根函数。求二叉树 BT 的根结点或求结点 x 所在二叉树的根结点。 若 BT 是空树或 x 不在任何二叉树上,则函数值为“空”。 (3)PARENT(BT,x) 求双亲函数。求二叉树 BT 中结点 x 的双亲结点。若结点 x 是二叉树 BT 的根结点或二叉树 BT 中无 x 结点,则函数值为“空”。 (4)LCHILD(BT,x)和 RCHILD(BT,x) 求孩子结点函数。分别求二叉树 BT 中结点 x 的左孩子 和右孩子结点。若结点 x 为叶子结点或不在二叉树 BT 中,则函数值为“空”。 (5)LSIBLING(BT,x)和 RSIBING(BT,x) 求兄弟函数。分别求二叉树 BT 中结点 x 的左兄弟和 右兄弟结点。 若结点 x 是根结点或不在 BT 中或是其双亲的左/右子树根,则函树值为“空”。 (6)CRT_BT(x,LBT,RBT) 建树操作。生成一棵以结点 x 为根,二叉树 LBT 和 RBT 分别为左, 右子树的二叉树。 (7)INS_LCHILD(BT,y,x)和 INS_RCHILD(BT,x) 插入子树操作。将以结点 x 为根且右子 树为空的二叉树分别置为二叉树 BT 中结点 y 的左子树和右子树。若结点 y 有左子树/右 子树,则插入后是结点 x 的右子树。 (8)DEL_LCHILD(BT,x)和 DEL-RCHILD(BT,x) 删除子树操作。 分别删除二叉树 BT 中以结点 x 为根的左子树或右子树。若 x 无左子树或右子树,则空操作。

6

(9)TRAVERSE(BT) 遍历操作。按某个次序依此访问二叉树中各个结点,并使每个结点只被 访问一次。 (10)CLEAR(BT) 清除结构操作。将二叉树 BT 置为空树。

5.2.2 二叉树的存储结构
一 顺序存储结构 连续的存储单元存储二叉树的数据元素。例如图 6.4(b)的完全二叉树, 可以向量 (一维数组 ) bt(1:6)作它的存储结构,将二叉树中编号为 i 的结点的数据元素存放在分量 bt[i]中,如图 6.6(a) 所示。但这种顺序存储结构仅适合于完全二叉树,而一般二叉树也按 这种形式来存储,这将造成存 贮浪费。如和图 6.4(c)的二叉树相应的存储结构图 6.6(b)所 示,图中以“0”表示不存在此结点.

二 链式存储结构 由二叉树的定义得知二叉树的结点由一个数据元素和分别指向左右子树的两个分支构 成,则表 示二叉树的链表中的结点至少包含三个域:数据域和左右指针域,如图(b)所示。有 时,为了便于找到结点的双亲,则还可在结点结构中增加一个指向其双亲受的指针域,如图 6.7(c)所示。

5.3 遍历二叉树
7

遍历二叉树(traversing binary tree)的问题, 即如何按某条搜索路径巡访树中每个结 点,使得每个结点均被访问一次,而且仅被访问一次。 其中常见的有三种情况:分别称之 为先(根)序遍历,中(根)序遍历和后(根)序遍历。

5.3.1 前序遍历
前序遍历运算:即先访问根结点,再前序遍历左子树,最后再前序遍历右子树。前序遍 历运算访问二叉树各结点是以根、左、右的顺序进行访问的。例如:

按前序遍历此二叉树的结果为:Hello!How are you? proc preorder(bt:bitreprtr) if (bt<>null)[ print(bt^); preorder(bt^.lchild); preorder(bt^.rchild);] end;

5.3.2 中序遍历
中序遍历运算:即先中前序遍历左子树,然后再访问根结点,最后再中序遍历右子树。 中序遍历运算访问二叉树各结点是以左、根、右的顺序进行访问的。例如:

按中序遍历此二叉树的结果为:a*b-c proc inorder(bt:bitreprtr) if (bt<>null)[ inorder(bt^.lchild); print(bt^);

8

niorder(bt^.rchild);] end;

5.3.3 后序遍历
后序遍历运算:即先后序遍历左子树,然后再后序遍历右子树,最后访问根结点。后序 遍历运算访问二叉树各结点是以左、右、根的顺序进行访问的。例如:

按后序遍历此二叉树的结果为:Welecome to use it! proc postorder(bt:bitreprtr) if (bt<>null)[ postorder(bt^.lchild); postorder(bt^.rchild);] print(bt^); end;


6.1 图的定义和术语
图是一种数据结构,它的形式化定义为 Graph=(v,r) 其中 V={ x|x<<dataobject} R={VR} VR={ <x,y> | P( x,y )^( x,y <<V)} 在图中的数据元素通常称作顶点 (vertex),V 是顶点的有穷非空集合,VR 是两 顶点 个顶点之间的关系的集合。若<x,y><<VR,则 <x,y> 表示从 x 到 y 的一条弧(arc),且称 x 弧 为弧尾(tail)或初始点(initial node)称 Y 为弧头(head)或终端点(TERMINAL NODE) 此 时的图称为有向图(DIGRAPH)。若〈X,Y 〉〈〈VR 必有〈Y,X〉〈〈VR,即 VR 是对称的, 则一无序对(X,Y)代替这两个有序对表示 X 和 Y 之间的一条边〈EDGE 此时的图称为无向 图(UNDIGRPAH)。例如图 7。1(A)中 G1 是有向图,-定义此图的谓词 P(X,Y)则表示从 X 到 Y 的一条单向通路.例如图 7.1(A)中 G1 是有向图,定义此图的谓词 P(X,Y)则表示从 X 到 Y 的一条单向通路. G1=(V1,{A1}) 其中: V1={V1,V2,V3,V4} A1={(<V1,V2>,<V1,V3>,<V3,V4>,<V4,V1>)}

9

图 7.1(B)中 G2 为无向图。 G2=(V2{E2}) 其中 V2={V1,V2,V3,V4,V5} E2={(V1,V2),(V1,V4)(V2,V3),(V2,V5)(V3,V4),(V3,V5)}

我们用 N 表示图中顶点数目,用 E 表示边或弧的数目.在下面的讨论中我们不考顶点到其自 身的弧或边,即若<Vi,Vj><<VR,则 Vi!=Vj,那么对于无向图,e 的取值范围是 0 到 1/2 N*(N-1).有 1/2 N*N(N-1)条边的无向图称为完全图(Completed graph);对于有向图,e 的取 值范围是 0 到 n*(n-1).具有 n*(n-1)条弧的有向图称为有向完全图.有很少条边或弧,(如 e<nlogn)的图称为稀疏图(sparse graph),反之称为稠密图(dense graph). 稀疏图 稠密图 有时图的边或弧具有与它相关的数,这种与图的边或弧相关的数叫做权(weight).这 些全可以表示从一个顶点到另一个顶点的距离或耗费.这种带权的图通常称为网(subgraph)

6.2 图的存储结构 6.2.1 数组表示法
用两个数组分别存储数据元素(顶点)的信息和数据元素之间的关系(边或弧)的信息。 其形式 定义如下: const vtxnum=...,{图的顶点数} type vtxptr=1..vtxnum;bit=0..1 vertex=record ...{和顶点相关的信息} end; arc=record adj:bit;{表示两个顶点之间是否存在关系} ... {和弧(或边)相关的其它信息} end; graph=record vexs:array[vtxptr]of vertex; arcs:array[vtxptr,vtxptr]ofarc end; 若图中顶点只有 1 至 vtxnum 的编号, 弧(或边)上亦无权及其它相关信息,则只要以一个二维 数组表示图的邻接矩阵即可,此时的存储结构可简单说明如下: adjmatrix=array arrayvtxptr,vtxptr]of bit; type array of

10

6.2.2 邻接表
邻接表(adhacency)是图的一种链式存储结构。在邻接表中,对图中每个顶点建立一个单 邻接表 链表,第 i 个单链表中的结点表示依附于顶点 vi 的边(对有向图是以顶点 vi 为尾的弧)。

若无向图中有 n 个顶点,e 条边,则它的邻接表需 n 个头结点和 2e 个表结点。 在无向图的邻接表中,顶点 vi 的度恰为第 i 个链表中的结点数;而在有向图中,第 i 个链 表中的结点个数只是顶点 vi 的出度。

6.2.4 邻接多重表
邻接多重表是无向图的另一种链式存储结构。 邻接多重表

其中,mark 为标志域,可用以标记该条边是否被搜索过;ivex 和 jvex 为该条边依附的两个 顶点在图中的位置; ilink 指向下一条依附于顶点 ivex 的边; jlink 指向下一条依附于顶点

11

jvex 的边。每一个顶点也用一个结点表示,它由如下所示的两个域组成:

其中,data 域存储和该顶点相关的信息,firstedge 域知识第一条依附于该顶点的边。 邻接多重表的类型说明如下: TYPE edgeptr=↑enode; enode=RECORD mark:0..1; ivex,jvex:vtxptr; ilink,jlink:edgeptr; END; vexnode=RECORD data:vertextype; firstedge:edgeptr; END; adjmulist=ARRAY[vxtptr] OF vexnode;

动态规划
一、动态规划的基本思想: 动态规划的基本思想: 动态规划算法通常用于求解具有某种最优性质的问题。 在这类问题中, 可能会有许多可行解。 每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其 基本思想也是将待求解问题分解成若干个子问题, 先求解子问题, 然后从这些子问题的解得 到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往 不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被 重复计算了很多次。 如果我们能够保存已解决的子问题的答案, 而在需要时再找出已求得的 答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子 问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就 是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式。 二、设计动态规划法的步骤: 设计动态规划法的步骤: 1、找出最优解的性质,并刻画其结构特征;
12

2、递归地定义最优值(写出动态规划方程); 3、以自底向上的方式计算出最优值; 4、根据计算最优值时得到的信息,构造一个最优解。 步骤 1-3 是动态规划算法的基本步骤。在只需要求出最优值的情形,步骤 4 可以省略,步骤 3 中记录的信息也较少;若需要求出问题的一个最优解,则必须执行步骤 4,步骤 3 中记录 的信息必须足够多以便构造最优解。 三、动态规划问题的特征: 动态规划问题的特征: 动态规划算法的有效性依赖于问题本身所具有的两个重要性质: 最优子结构性质和子问题重 叠性质。 1、最优子结构:当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性 质。 2、重叠子问题:在用递归算法自顶向下解问题时,每次产生的子问题并不总是新问题,有 些子问题被反复计算多次。 动态规划算法正是利用了这种子问题的重叠性质, 对每一个子问 题只解一次,而后将其解保存在一个表格中,在以后尽可能多地利用这些子问题的解。 四、习题: 习题: 1、防卫导弹: 问题描述:一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行,也可以用很快的速 问题描述 度向下飞行,可以毫无损伤地截击进攻导弹,但不可以向后或向上飞行。但有一个缺点,尽 管它发射时可以达到任意高度, 但它只能截击比它上次截击导弹时所处高度低或者高度相同 的导弹。现对这种新型 防卫导弹进行测试,在每一次测试中,发射一系列的测试导弹(这 些导弹发射的间隔时间固定,飞行速度相同),该防卫导弹所能获得的信息包括各进攻导弹 的高度,以及它们发射次序。现要求编一程序,求在每次测试中,该防卫导弹最多能截击的 进攻导弹数量,一个导弹能被截击应满足下列两个条件之一: 1、它是该次测试中第一个被防卫导弹截击的导弹; 2、 它是在上一次被截击导弹的发射后发射, 且高度不大于上一次被截击导弹的高度的导弹。 输入格式:从当前目录下的文本文件"CATCHER.DAT"读入数据 。该文 件的第一行是一个整 输入格式 数 N(0〈=N〈=4000),表示本次测试中,发射的进攻导弹数,以下 N 行每行各有一个整数 hi(0〈=hi〈=32767),表示第 i 个进攻导弹的高度。文件中各行的行首、行末无多余空格, 输入文件中给出的导弹是按发射顺序排列的。 输出格式:答案输出到当前目录下的文本文件"CATCHER.OUT"中,该文件第一行是一个整数 输出格式 max,表示最多能截击的进攻导弹数,以下的 max 行每行各有一个整数,表示各个被截击的 进攻导弹的编号(按被截击的先后顺序排列)。输出的答案可能不唯一,只要输出其中任一 解即可。 输入输出举例: 输入文件: CATCHER.DAT 3 25 36 23

输出文件: CATCHER.OUT 2 1 3

13

2、轮船(Ships) 描述 有一个国家被一条何划分为南北两部分, 在南岸和北岸总共有 N 个城镇, 每一城镇在对岸都 有唯一的友好城镇。 任何两个城镇都没有相同的友好城镇。 每一对友好城镇都希望有一条航 线来往。于是他们向政府提出了申请。由于河终年有雾。政府决定不允许有任两条航线交叉 (如果两条航线交叉,将有很大机会撞船)。 你的任务是缟写一个程序来帮政府官员决定他们应拨款兴建哪些航线以使到没有出现交叉 的航线最多。 输入数据 输入文件(ship.in)包括了若干组数据,每组数据格式如下: 第一行两个由空格分隔的整数 x,y,10〈=x〈=6000,10〈=y〈=100。x 表示河的长度而 y 表示宽。第二行是一个整数 N(1<=N<=5000),表示分布在河两岸的城镇对数。接下来的 N 行 每行有两个由空格分隔的正数 C,D(C、D〈=x〉,描述每一对友好城镇沿着河岸与西边境 线的距离,C 表示北岸城镇的距离而 D 表示南岸城镇的距离。在河的同一边,任何两个城镇 的位置都是不同的。整个输入文件以由空格分隔的两个 0 结束。 输出数据 输出文件(ship.ou)要在连续的若干行里给出每一组数据在安全条件下能够开通的最大航线 数目。 示例 Ship.in 30 4 7 22 4 2 6 10 3 15 12 9 8 17 17 4 2 0 0

分支限界
一、分支限界法: 分支限界法: 分支限界法类似于回溯法, 也是一种在问题的解空间树 T 上搜索问题解的算法。 但在一般情 况下, 分支限界法与回溯法的求解目标不同。 回溯法的求解目标是找出 T 中满足约束条件的 所有解, 而分支限界法的求解目标则是找出满足约束条件的一个解, 或是在满足约束条件的 解中找出使用某一目标函数值达到极大或极小的解,即在某种意义下的最优解。 由于求解目标不同, 导致分支限界法与回溯法在解空间树 T 上的搜索方式也不相同。 回溯法 以深度优先的方式搜索解空间树 T,而分支限界法则以广度优先或以最小耗费优先的方式搜 索解空间树 T。 分支限界法的搜索策略是: 在扩展结点处, 先生成其所有的儿子结点 (分支) ,
14

然后再从当前的活结点表中选择下一个扩展对点。 为了有效地选择下一扩展结点, 以加速搜 索的进程,在每一活结点处,计算一个函数值(限界),并根据这些已计算出的函数值,从 当前活结点表中选择一个最有利的结点作为扩展结点, 使搜索朝着解空间树上有最优解的分 支推进,以便尽快地找出一个最优解。 二、分支限界法的基本思想: 分支限界法的基本思想: 分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。问题 的解空间树是表示问题解空间的一棵有序树, 常见的有子集树和排列树。 在搜索问题的解空 间树时,分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中,每 一个活结点只有一次机会成为扩展结点。 活结点一旦成为扩展结点, 就一次性产生其所有儿 子结点。在这些儿子结点中,那些导致不可行解或导致非最优解的儿子结点被舍弃,其余儿 子结点被子加入活结点表中。此后,从活结点表中取下一结点成为当前扩展结点,并重复上 述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。 三、选择下一扩展结点的不同方式: 选择下一扩展结点的不同方式: 从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法。 最常见的有以下两种方 式: 1、队列式(FIFO)分支限界法:队列式分支限界法将活结点表组织成一个队列,并按队列的 先进先出原则选取下一个结点为当前扩展结点。 2、优先队列式分支限界法:优先队列式分支限界法将活结点表组织成一个优先队列,交按 优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。 四、习题: 习题: 1、0-1 背包:n=3,w=[16,15,15],p=[45,25,25],c=30 2、单源最短路径:求从起点到终点的最短路径。 3、装载问题:有一批共 n 个集装箱要装上 2 艘载重量分别为 c1 和 c2 的轮船,其中集装箱 i 的重量为 wi 且

。要求确定是否有一个合理的装载方案可将这 n 个集装箱装上这 2 艘轮船。如果有,找出一种装载方案。 4、布线问题:印刷电路板将布线区域划分成 n X m 个方格如图 a 所示。精确的电路布线问 题要求确定连接方格 a 的中点到方格 b 的中点的最短布线方案。 在布线时, 电路只能沿直线 或直角布线,如图 b 所示。为了避免线路相交,已布了线的方格做了封锁标记,其它线路不 允穿过被封锁的方格。

15

一个布线的例子:图中包含障碍。起始点为 a,目标点为 b。

分治策略
一、算法思想
任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。 问题规模越小, 解 题所需的计算时间往往也越少,从而也越容易计算。想解决一个较大的问题,有时是相当困 难的。 分治法的思想就是, 将一个难以直接解决的大问题, 分割成一些规模较小的相同问题, 以便各个击破,分而治之。 分治的基本思想是将一个规模为 n 的问题分解为 k 个规模较小的子问题, 这些子问题互 相独立且与原问题相同。找出各部分的解,然后把各部分的解组合成整个问题的解。 1、解决算法实现的同时,需要估算算法实现所需时间。分治算法时间是这样确定的: 解决子问题所需的工作总量(由 子问题的个数、解决每个子问题的工作量 决定) 合并所有子问题所需的工作量

16

2、分治法是把任意大小问题尽可能地等分成两个子问题的递归算法 3、分治的具体过程: begin {开始} if ①问题不可分 then ②返回问题解 else begin ③从原问题中划出含一半运算对象的子问题 1; ④递归调用分治法过程,求出解 1; ⑤从原问题中划出含另一半运算对象的子问题 2; ⑥递归调用分治法过程,求出解 2; ⑦将解 1、解 2 组合成整修问题的解; end; end; {结束}

二、例题分析
1、[金块问题]老板有一袋金块(共 n 块,n 是 2 的幂(n>=2)),将有两名最优秀的 雇员每人得到其中的一块, 排名第一的得到最重的那块, 排名第二的雇员得到袋子中最轻的 金块。假设有一台比较重量的仪器,我们希望用最少的比较次数找出最重的金块。 分析:问题可以简化为:在含 n(n 是 2 的幂(n>=2) )个元素的集合中寻找极大元和极小元。 明显的方法是逐个的进行比较查找。 (或者一次选择排序) p:=1; for i:=2 to n do if a[p]<a[i] then p:=i; m:=a[p];

(一次冒泡排序) m:=a[1]; for i:=2 to n do if m < a[i] then m:=a[i];

需要 n-1 次比较得到 max,而再经过 n-2 次比较得到 min,共进行 2*n-3 次比较可以找出极 大元和极小元。 用分治法可以较少比较次数地解决上述问题: 如果集合中只有 1 个元素,则它既是最大值也是最小值; 如果有 2 个元素, 则一次 maxnum(i,j) 一次 minnum(i,j)就可以得到最大值和最小值; 如果把集合分成两个子集合,递归的应用这个算法分别求出两个子集合的最大值和最 小值, 最后让子集合 1 的最大值跟子集合 2 的最大值比较得到整个集合的最大值; 让子集合 1 的最小值跟子集合 2 的最小值比较得到整个集合的最小值。 可得解题思想: {maxmin} ①if 问题不可分:n=2 ②问题的解求得(两个元素时):对两元素进行比较;return; ③for i:=1 to n div 2 do b[i]:=a[i]
17

④maxmin(n div 2,b,max1,min1),其中 max1 和 min1 为解 1 ⑤for i:=1 to n div 2 do b[i]:=a[i+ n div 2] ⑥maxmin(n div 2,b,max2,min2),其中 max2 和 min2 为解 2 ⑦max:=maxnum(max1,max2); min:=minnum(min1,min2); {maxmin} 其中对函数 maxnum 的求精: function maxnum(a,b:integer):integer; begin if a>b then maxnum:=a else maxnum:=b; end; 分析比较次数: 比较运算均在函数 maxnum 和 minnum 中进行, 当 n=2 时,比较次数 T(n)=1 当 n>2 时,比较次数 T(n)=2T(n/2)+2 ∵n 是 2 的 k 次幂 ∴设 n=2^k

2、快速排序 快速排序是基于分治策略的一个排序算法。按照分治法的思想分析快速排序: (1) 分解(Divide) 以元素 a[p]为基准元素将 a[p: q-1]划分为三段 a[p: q-1], a[q]和 a[q+1:
18

r],使得 a[p:q-1]中任何一个元素都小于 a[q],a[q+1:r]中任何一个元素大于等于 a[q], 下标 q 在划分中确定。 (2)递归求解(Conquer) 通过递归调用快速排序算法分别对 a[p:q-1] 和 a[q+1:r]进行排 序。 (3)合并(Merge) 由于 a[p:q-1] 和 a[q+1:r]的排序都是在原位置进行的,所以不必进行 任何合并操作就已经排好序了。 在上面三个步骤中,第一步:分解是关键。一次快速排序确定划分元素的位置,具体参见排 序算法----快速排序 3、归并排序 归并排序也是基于分治策略的另一个算法。 归并的思路是把两个已经排好序的数组合并 为一个。(源程序) 2-路归并排序示例: 初始值 一趟归并排序 两趟归并排序 三趟归并排序 E E E Y Y K B U E U K Y K L S U K U S L B Y L S S L B B

习题:对数字 49 38 40 97 76 13 27 进行归并排序 procedure mergesort(var r,r1:listtype;s,t:integer); {r,r1:均为链表,存储排序数据;过程 mergesort(r,r1,s,t)完成把链表 r 中的关键字进 行归并排序、并存放到链表 r1 中,其中 s 是下界 t 是上界} {过程 merge(r2,s,m,t,r1)把链表 r2 中排好序的子链 r2[s..m]和子链 r2[m+1..t]合并到 r1 中} if 问题不可分 then 求解 else (1)分出问题的一个子问题 1,并求解子问题 1 (2)分出问题的一个子问题 2,求解子问题 2 (3)合并子问题 1 和子问题 2 if s=t then r1[s]:=r[s] else mergesort(r,r2,s,(s+t)div 2); mergesort(r,r2,(s+t)div 2,t); merge(r2,s,(s+t)div 2,t,r1);

4、[循环赛问题](1999 年广东省青少年信息学奥林匹克竞赛 第三题:棒球联赛) 问题描述:广州市体委将举行一次由 N 支队伍(队伍编号为 1..N)参加的少年棒球联赛。 联赛总共不能多于 N 轮(同一时间内若干支队进行一次比赛为一轮),并且每两支队之间必 须而且仅必须进行一次比赛。请编程为这次比赛设计一个赛程表。 循环赛问题可以用分治法解决。下面是先假定 n=2^k
19

procedure table(k:integer;a:array[1..u1,1..u2] of integer); var n,i,j,m,s,t:integer; begin n:=1; for i:=1 to k do n:=n*2; for i:=1 to n do a[1,i]:=i; m:=1; for s:=1 to k do begin n:=n / 2; for t:=1 to n do for i:=m+1 to 2*m do for j:=m+1 to 2*m do begin a[i,j+(t-1)*m*2]:=a[i-m,j+(t-1)*m*2-m]; a[i,j+(t-1)*m*2-m]:=a[i-m,j+(t-1)*m*2]; end; m:=m*2; end;{for s} end;

三、练习题
[二分检索]假定在 A[1..9]中顺序存放这九个数:-7,-2,0,5,16,43,57,102,291 要求检索 291,16,101 是否在数组中。 给定已排好序的 n 个元素 A1,A2,A3,…,An, 找出元素 x 是否在 A 中,如果 x 在 A 中, 指出它在 A 中的位置。 递归源程序 { 二分检索的方法充分利用元素之间的次序关系,采用分治策略可以在最坏情况下用 O (log n)的时间完成任务。 } program search; const n=10; var a:array[1..n] of integer; i:integer; x:real; Procedure BinarySearch(low:integer;high:integer;var i:integer); var mid:integer; begin
20

if low>high then i:=0 else begin mid:=(low+high) div 2;{将 n 个元素分成大致相同的两半} if x=a[mid] then {取 a[n div 2]与 x 做比较} begin i:=mid; exit; end {如果 x=a[n div 2],则找到 x,算法结束。} else if x0 then writeln(x,' is the ',i,'th ',' one in the table.') else writeln(x,' is not in the table.') End.

program search; const n=10; var a:array[1..n] of integer; i:integer; x:real; 非递归源程序 Procedure BinarySearch(low:integer;high:integer;var i:integer); var mid:integer; begin while low<=high do begin mid:=(low+high) div 2; if x=a[mid] then begin i:=mid; exit; end else if x0 then writeln(x,' is the ',i,'th ',' one in the table.') else writeln(x,' is not in the table.')

End.

排序算法
一、插入排序(Insertion 一、插入排序(Insertion Sort)
1. 基本思想: 每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依然
21

有序;直到待排序数据元素全部插入完为止。 2. 排序过程: 【示例】: [初始关键字] [49] 38 65 97 76 13 27 49 J=2(38) [38 49] 65 97 76 13 27 49 J=3(65) [38 49 65] 97 76 13 27 49 J=4(97) [38 49 65 97] 76 13 27 49 J=5(76) [38 49 65 76 97] 13 27 49 J=6(13) [13 38 49 65 76 97] 27 49 J=7(27) [13 27 38 49 65 76 97] 49 J=8(49) [13 27 38 49 49 65 76 97]

Procedure InsertSort(Var R : FileType); //对 R[1..N]按递增序进行插入排序, R[0]是监视哨// Begin for I := 2 To N Do //依次插入 R[2],...,R[n]// begin R[0] := R[I]; J := I - 1; While R[0] < R[J] Do //查找 R[I]的插入位置// begin R[J+1] := R[J]; //将大于 R[I]的元素后移// J := J - 1 end
22

R[J + 1] := R[0] ; //插入 R[I] // end End; //InsertSort //

二、选择排序
1. 基本思想: 每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数 列的最后,直到全部待排序的数据元素排完。 2. 排序过程: 【示例】: 初始关键字 [49 38 65 97 76 13 27 49] 第一趟排序后 13 [38 65 97 76 49 27 49] 第二趟排序后 13 27 [65 97 76 49 38 49] 第三趟排序后 13 27 38 [97 76 49 65 49] 第四趟排序后 13 27 38 49 [49 97 65 76] 第五趟排序后 13 27 38 49 49 [97 97 76] 第六趟排序后 13 27 38 49 49 76 [76 97] 第七趟排序后 13 27 38 49 49 76 76 [ 97] 最后排序结果 13 27 38 49 49 76 76 97

Procedure SelectSort(Var R : FileType); //对 R[1..N]进行直接选择排序 // Begin for I := 1 To N - 1 Do //做 N - 1 趟选择排序//

23

begin K := I; For J := I + 1 To N Do //在当前无序区 R[I..N]中选最小的元素 R[K]// begin If R[J] < R[K] Then K := J end; If K <> I Then //交换 R[I]和 R[K] // begin Temp := R[I]; R[I] := R[K]; R[K] := Temp; end; end End; //SelectSort //

三、冒泡排序(BubbleSort) 三、冒泡排序(BubbleSort)
1. 基本思想: 两两比较待排序数据元素的大小, 发现两个数据元素的次序相反时即进行交换, 直到没 有反序的数据元素为止。 2. 排序过程: 设想被排序的数组 R[1..N]垂直竖立,将每个数据元素看作有重量的气泡,根据轻气 泡不能在重气泡之下的原则,从下往上扫描数组 R,凡扫描到违反本原则的轻气泡,就使其 向上"漂浮",如此反复进行,直至最后任何两个气泡都是轻者在上,重者在下为止。 【示例】: 49 13 13 13 13 13 13 13 38 49 27 27 27 27 27 27 65 38 49 38 38 38 38 38
24

97 65 38 49 49 49 49 49 76 97 65 49 49 49 49 49 13 76 97 65 65 65 65 65 27 27 76 97 76 76 76 76 49 49 49 76 97 97 97 97

Procedure BubbleSort(Var R : FileType) //从下往上扫描的起泡排序// Begin For I := 1 To N-1 Do //做 N-1 趟排序// begin NoSwap := True; //置未排序的标志// For J := N - 1 DownTo 1 Do //从底部往上扫描// begin If R[J+1]< R[J] Then //交换元素// begin Temp := R[J+1]; R[J+1 := R[J]; R[J] := Temp; NoSwap := False end; end; If NoSwap Then Return//本趟排序中未发生交换,则终止算法// end End; //BubbleSort//

25

四、快速排序(Quick Sort) 四、快速排序(Quick Sort)
1. 基本思想: 在当前无序区 R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为 X),用此基准将 当前无序区划分为左右两个较小的无序区:R[1..I-1]和 R[I+1..H],且左边的无序子区中数据 元素均小于等于基准元素,右边的无序子区中数据元素均大于等于基准元素,而基准 X 则 位于最终排序的位置上, R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H), R[1..I-1]和 R[I+1..H]均非 即 当 空时,分别对它们进行上述的划分过程,直至所有无序子区中的数据元素均已排序为止。 2. 排序过程: 【示例】: 初始关键字 [49 38 65 97 76 13 27 49] 第一次交换后 [27 38 65 97 76 13 49 49] 第二次交换后 [27 38 49 97 76 13 65 49] J 向左扫描,位置不变,第三次交换后 [27 38 13 97 76 49 65 49] I 向右扫描,位置不变,第四次交换后 [27 38 13 49 76 97 65 49] J 向左扫描 [27 38 13 49 76 97 65 49] (一次划分过程)

初始关键字 [49 38 65 97 76 13 27 49] 一趟排序之后 [27 38 13] 49 [76 97 65 49] 二趟排序之后 [13] 27 [38] 49 [49 65]76 [97] 三趟排序之后 13 27 38 49 49 [65]76 97 最后的排序结果 13 27 38 49 49 65 76 97 各趟排序之后的状态
26

Procedure Parttion(Var R : FileType; L, H : Integer; Var I : Integer); //对无序区 R[1,H]做划分,I 给以出本次划分后已被定位的基准元素的位置 // Begin I := 1; J := H; X := R[I] ;//初始化,X 为基准// Repeat While (R[J] >= X) And (I < J) Do begin J := J - 1 //从右向左扫描,查找第 1 个小于 X 的元素// If I < J Then //已找到 R[J] 〈X// begin R[I] := R[J]; //相当于交换 R[I]和 R[J]// I := I + 1 end; While (R[I] <= X) And (I < J) Do I := I + 1 //从左向右扫描,查找第 1 个大于 X 的元素/// end; If I < J Then //已找到 R[I] > X // begin J := J - 1 end Until I = J; R[J] := R[I]; //相当于交换 R[I]和 R[J]//

27

R[I] := X //基准 X 已被最终定位// End; //Parttion //

Procedure QuickSort(Var R :FileType; S,T: Integer); //对 R[S..T]快速排序// Begin If S < T Then //当 R[S..T]为空或只有一个元素是无需排序// begin Partion(R, S, T, I); //对 R[S..T]做划分// QuickSort(R, S, I-1);//递归处理左区间 R[S,I-1]// QuickSort(R, I+1,T);//递归处理右区间 R[I+1..T] // end; End; //QuickSort//

五、堆排序(Heap 五、堆排序(Heap Sort)
1. 基本思想: 堆排序是一树形选择排序,在排序过程中,将 R[1..N]看成是一颗完全二叉树的顺序存储结 构,利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。 2. 堆的定义: N 个元素的序列 K1,K2,K3,...,Kn.称为堆,当且仅当该序列满足特性: Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])

28

堆实质上是满足如下性质的完全二叉树:树中任一非叶子结点的关键字均大于等于其孩子 结点的关键字。 例如序列 10,15,56,25,30,70 就是一个堆, 它对应的完全二叉树如上图所示。 这种堆中根结点(称为堆顶)的关键字最小,我们把它称为小根堆。反之,若完全二叉树中 任一非叶子结点的关键字均大于等于其孩子的关键字,则称之为大根堆。 3. 排序过程: 堆排序正是利用小根堆(或大根堆)来选取当前无序区中关键字小(或最大)的记录实现排 序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是:将当前无序区调整为一个大 根堆,选取关键字最大的堆顶记录,将它和无序区中的最后一个记录交换。这样,正好和直 接选择排序相反,有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。 【示例】:对关键字序列 42,13,91,23,24,16,05,88 建堆

29

Procedure Sift(Var R :FileType; I, M : Integer); //在数组 R[I..M]中调用 R[I], 使得以它为完全二叉树构成堆。 事先已知其左、 右子树(2I+1 <=M 时)均是堆// Begin X := R[I]; J := 2*I; //若 J <=M, R[J]是 R[I]的左孩子// While J <= M Do //若当前被调整结点 R[I]有左孩子 R[J]// begin If (J < M) And R[J].Key < R[J+1].Key Then J := J + 1 //令 J 指向关键字较大的右孩子// //J 指向 R[I]的左、右孩子中关键字较大者// If X.Key < R[J].Key Then //孩子结点关键字较大// begin R[I] := R[J]; //将 R[J]换到双亲位置上// I := J ; J := 2*I //继续以 R[J]为当前被调整结点往下层调整// end; Else Exit//调整完毕,退出循环//
30

end R[I] := X;//将最初被调整的结点放入正确位置// End;//Sift//

Procedure HeapSort(Var R : FileType); //对 R[1..N]进行堆排序// Begin For I := N Div Downto 1 Do //建立初始堆// Sift(R, I , N) For I := N Downto 2 do //进行 N-1 趟排序// begin T := R[1]; R[1] := R[I]; R[I] := T;//将当前堆顶记录和堆中最后一个记录交换// Sift(R, 1, I-1) //将 R[1..I-1]重成堆// end End; //HeapSort//

六、几种排序算法的比较和选择 1. 选取排序方法需要考虑的因素: (1) 待排序的元素数目 n; (2) 元素本身信息量的大小; (3) 关键字的结构及其分布情况; (4) 语言工具的条件,辅助空间的大小等。 2. 小结: (1) 若 n 较小(n <= 50),则可以采用直接插入排序或直接选择排序。由于直接插

31

入排序所需的记录移动操作较直接选择排序多,因而当记录本身信息量较大时, 用直接选择排序较好。 (2) 若文件的初始状态已按关键字基本有序,则选用直接插入或冒泡排序为宜。 (3) 若 n 较大,则应采用时间复杂度为 O(nlog2n)的排序方法:快速排序、堆排 序或归并排序。 快速排序是目前基于比较的内部排序法中被认为是最好的方法。 (4) 在基于比较排序方法中,每次比较两个关键字的大小之后,仅仅出现两种可 能的转移,因此可以用一棵二叉树来描述比较判定过程,由此可以证明:当文件 的 n 个关键字随机分布时,任何借助于"比较"的排序算法,至少需要 O(nlog2n) 的时间。 (5) 当记录本身信息量较大时,为避免耗费大量时间移动记录,可以用链表作为 存储结构。

动态规划
一、动态规划的基本思想: 动态规划的基本思想: 动态规划算法通常用于求解具有某种最优性质的问题。 在这类问题中, 可能会有许多可行解。 每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其 基本思想也是将待求解问题分解成若干个子问题, 先求解子问题, 然后从这些子问题的解得 到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往 不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被 重复计算了很多次。 如果我们能够保存已解决的子问题的答案, 而在需要时再找出已求得的 答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子 问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就 是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式。 二、设计动态规划法的步骤: 设计动态规划法的步骤: 划法的步骤 1、找出最优解的性质,并刻画其结构特征; 2、递归地定义最优值(写出动态规划方程); 3、以自底向上的方式计算出最优值; 4、根据计算最优值时得到的信息,构造一个最优解。 步骤 1-3 是动态规划算法的基本步骤。在只需要求出最优值的情形,步骤 4 可以省略,步骤 3 中记录的信息也较少;若需要求出问题的一个最优解,则必须执行步骤 4,步骤 3 中记录 的信息必须足够多以便构造最优解。
32

三、动态规划问题的特征: 动态规划问题的特征: 动态规划算法的有效性依赖于问题本身所具有的两个重要性质: 最优子结构性质和子问题重 叠性质。 1、最优子结构:当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性 质。 2、重叠子问题:在用递归算法自顶向下解问题时,每次产生的子问题并不总是新问题,有 些子问题被反复计算多次。 动态规划算法正是利用了这种子问题的重叠性质, 对每一个子问 题只解一次,而后将其解保存在一个表格中,在以后尽可能多地利用这些子问题的解。 四、习题: 习题: 1、防卫导弹: 问题描述:一种新型的防卫导弹可截击多个攻击导弹。它可以向前飞行,也可以用很快的速 问题描述 度向下飞行,可以毫无损伤地截击进攻导弹,但不可以向后或向上飞行。但有一个缺点,尽 管它发射时可以达到任意高度, 但它只能截击比它上次截击导弹时所处高度低或者高度相同 的导弹。现对这种新型 防卫导弹进行测试,在每一次测试中,发射一系列的测试导弹(这 些导弹发射的间隔时间固定,飞行速度相同),该防卫导弹所能获得的信息包括各进攻导弹 的高度,以及它们发射次序。现要求编一程序,求在每次测试中,该防卫导弹最多能截击的 进攻导弹数量,一个导弹能被截击应满足下列两个条件之一: 1、它是该次测试中第一个被防卫导弹截击的导弹; 2、 它是在上一次被截击导弹的发射后发射, 且高度不大于上一次被截击导弹的高度的导弹。 输入格式:从当前目录下的文本文件"CATCHER.DAT"读入数据 。该文 件的第一行是一个整 输入格式 数 N(0〈=N〈=4000),表示本次测试中,发射的进攻导弹数,以下 N 行每行各有一个整数 hi(0〈=hi〈=32767),表示第 i 个进攻导弹的高度。文件中各行的行首、行末无多余空格, 输入文件中给出的导弹是按发射顺序排列的。 输出格式:答案输出到当前目录下的文本文件"CATCHER.OUT"中,该文件第一行是一个整数 输出格式 max,表示最多能截击的进攻导弹数,以下的 max 行每行各有一个整数,表示各个被截击的 进攻导弹的编号(按被截击的先后顺序排列)。输出的答案可能不唯一,只要输出其中任一 解即可。 输入输出举例: 输入文件: CATCHER.DAT 3 25 36 23

输出文件: CATCHER.OUT 2 1 3

2、轮船(Ships) 描述 有一个国家被一条何划分为南北两部分, 在南岸和北岸总共有 N 个城镇, 每一城镇在对岸都 有唯一的友好城镇。 任何两个城镇都没有相同的友好城镇。 每一对友好城镇都希望有一条航 线来往。于是他们向政府提出了申请。由于河终年有雾。政府决定不允许有任两条航线交叉 (如果两条航线交叉,将有很大机会撞船)。 你的任务是缟写一个程序来帮政府官员决定他们应拨款兴建哪些航线以使到没有出现交叉 的航线最多。
33

输入数据 输入文件(ship.in)包括了若干组数据,每组数据格式如下: 第一行两个由空格分隔的整数 x,y,10〈=x〈=6000,10〈=y〈=100。x 表示河的长度而 y 表示宽。第二行是一个整数 N(1<=N<=5000),表示分布在河两岸的城镇对数。接下来的 N 行 每行有两个由空格分隔的正数 C,D(C、D〈=x〉,描述每一对友好城镇沿着河岸与西边境 线的距离,C 表示北岸城镇的距离而 D 表示南岸城镇的距离。在河的同一边,任何两个城镇 的位置都是不同的。整个输入文件以由空格分隔的两个 0 结束。 输出数据 输出文件(ship.ou)要在连续的若干行里给出每一组数据在安全条件下能够开通的最大航线 数目。 示例 Ship.in 30 4 7 22 4 2 6 10 3 15 12 9 8 17 17 4 2 0 0

分支限界
一、分支限界法: 分支限界法: 分支限界法类似于回溯法, 也是一种在问题的解空间树 T 上搜索问题解的算法。 但在一般情 况下, 分支限界法与回溯法的求解目标不同。 回溯法的求解目标是找出 T 中满足约束条件的 所有解, 而分支限界法的求解目标则是找出满足约束条件的一个解, 或是在满足约束条件的 解中找出使用某一目标函数值达到极大或极小的解,即在某种意义下的最优解。 由于求解目标不同, 导致分支限界法与回溯法在解空间树 T 上的搜索方式也不相同。 回溯法 以深度优先的方式搜索解空间树 T,而分支限界法则以广度优先或以最小耗费优先的方式搜 索解空间树 T。 分支限界法的搜索策略是: 在扩展结点处, 先生成其所有的儿子结点 (分支) , 然后再从当前的活结点表中选择下一个扩展对点。 为了有效地选择下一扩展结点, 以加速搜 索的进程,在每一活结点处,计算一个函数值(限界),并根据这些已计算出的函数值,从 当前活结点表中选择一个最有利的结点作为扩展结点, 使搜索朝着解空间树上有最优解的分 支推进,以便尽快地找出一个最优解。 二、分支限界法的基本思想: 分支限界法的基本思想: 分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。问题 的解空间树是表示问题解空间的一棵有序树, 常见的有子集树和排列树。 在搜索问题的解空
34

间树时,分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中,每 一个活结点只有一次机会成为扩展结点。 活结点一旦成为扩展结点, 就一次性产生其所有儿 子结点。在这些儿子结点中,那些导致不可行解或导致非最优解的儿子结点被舍弃,其余儿 子结点被子加入活结点表中。此后,从活结点表中取下一结点成为当前扩展结点,并重复上 述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。 三、选择下一扩展结点的不同方式: 选择下一扩展结点的不同方式: 从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法。 最常见的有以下两种方 式: 1、队列式(FIFO)分支限界法:队列式分支限界法将活结点表组织成一个队列,并按队列的 先进先出原则选取下一个结点为当前扩展结点。 2、优先队列式分支限界法:优先队列式分支限界法将活结点表组织成一个优先队列,交按 优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。 四、习题: 习题: 1、0-1 背包:n=3,w=[16,15,15],p=[45,25,25],c=30 2、单源最短路径:求从起点到终点的最短路径。 3、装载问题:有一批共 n 个集装箱要装上 2 艘载重量分别为 c1 和 c2 的轮船,其中集装箱 i 的重量为 wi 且

。要求确定是否有一个合理的装载方案可将这 n 个集装箱装上这 2 艘轮船。如果有,找出一种装载方案。 4、布线问题:印刷电路板将布线区域划分成 n X m 个方格如图 a 所示。精确的电路布线问 题要求确定连接方格 a 的中点到方格 b 的中点的最短布线方案。 在布线时, 电路只能沿直线 或直角布线,如图 b 所示。为了避免线路相交,已布了线的方格做了封锁标记,其它线路不 允穿过被封锁的方格。

一个布线的例子:图中包含障碍。起始点为 a,目标点为 b。

35

分治策略
一、算法思想
任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。 问题规模越小, 解 题所需的计算时间往往也越少,从而也越容易计算。想解决一个较大的问题,有时是相当困 难的。 分治法的思想就是, 将一个难以直接解决的大问题, 分割成一些规模较小的相同问题, 以便各个击破,分而治之。 分治的基本思想是将一个规模为 n 的问题分解为 k 个规模较小的子问题, 这些子问题互 相独立且与原问题相同。找出各部分的解,然后把各部分的解组合成整个问题的解。 1、解决算法实现的同时,需要估算算法实现所需时间。分治算法时间是这样确定的: 解决子问题所需的工作总量(由 子问题的个数、解决每个子问题的工作量 决定) 合并所有子问题所需的工作量 2、分治法是把任意大小问题尽可能地等分成两个子问题的递归算法 3、分治的具体过程: begin {开始} if ①问题不可分 then ②返回问题解 else begin ③从原问题中划出含一半运算对象的子问题 1; ④递归调用分治法过程,求出解 1; ⑤从原问题中划出含另一半运算对象的子问题 2; ⑥递归调用分治法过程,求出解 2; ⑦将解 1、解 2 组合成整修问题的解; end; end; {结束}

二、例题分析
36

1、[金块问题]老板有一袋金块(共 n 块,n 是 2 的幂(n>=2)),将有两名最优秀的 雇员每人得到其中的一块, 排名第一的得到最重的那块, 排名第二的雇员得到袋子中最轻的 金块。假设有一台比较重量的仪器,我们希望用最少的比较次数找出最重的金块。 分析:问题可以简化为:在含 n(n 是 2 的幂(n>=2) )个元素的集合中寻找极大元和极小元。 明显的方法是逐个的进行比较查找。 (或者一次选择排序) p:=1; for i:=2 to n do if a[p]<a[i] then p:=i; m:=a[p];

(一次冒泡排序) m:=a[1]; for i:=2 to n do if m < a[i] then m:=a[i];

需要 n-1 次比较得到 max,而再经过 n-2 次比较得到 min,共进行 2*n-3 次比较可以找出极 大元和极小元。 用分治法可以较少比较次数地解决上述问题: 如果集合中只有 1 个元素,则它既是最大值也是最小值; 如果有 2 个元素, 则一次 maxnum(i,j) 一次 minnum(i,j)就可以得到最大值和最小值; 如果把集合分成两个子集合,递归的应用这个算法分别求出两个子集合的最大值和最 小值, 最后让子集合 1 的最大值跟子集合 2 的最大值比较得到整个集合的最大值; 让子集合 1 的最小值跟子集合 2 的最小值比较得到整个集合的最小值。 可得解题思想: {maxmin} ①if 问题不可分:n=2 ②问题的解求得(两个元素时):对两元素进行比较;return; ③for i:=1 to n div 2 do b[i]:=a[i] ④maxmin(n div 2,b,max1,min1),其中 max1 和 min1 为解 1 ⑤for i:=1 to n div 2 do b[i]:=a[i+ n div 2] ⑥maxmin(n div 2,b,max2,min2),其中 max2 和 min2 为解 2 ⑦max:=maxnum(max1,max2); min:=minnum(min1,min2); {maxmin} 其中对函数 maxnum 的求精: function maxnum(a,b:integer):integer; begin if a>b then maxnum:=a else maxnum:=b; end; 分析比较次数: 比较运算均在函数 maxnum 和 minnum 中进行, 当 n=2 时,比较次数 T(n)=1
37

当 n>2 时,比较次数 T(n)=2T(n/2)+2 ∵n 是 2 的 k 次幂 ∴设 n=2^k

2、快速排序 快速排序是基于分治策略的一个排序算法。按照分治法的思想分析快速排序: (1) 分解(Divide) 以元素 a[p]为基准元素将 a[p: q-1]划分为三段 a[p: q-1], a[q]和 a[q+1: r],使得 a[p:q-1]中任何一个元素都小于 a[q],a[q+1:r]中任何一个元素大于等于 a[q], 下标 q 在划分中确定。 (2)递归求解(Conquer) 通过递归调用快速排序算法分别对 a[p:q-1] 和 a[q+1:r]进行排 序。 (3)合并(Merge) 由于 a[p:q-1] 和 a[q+1:r]的排序都是在原位置进行的,所以不必进行 任何合并操作就已经排好序了。 在上面三个步骤中,第一步:分解是关键。一次快速排序确定划分元素的位置,具体参见排 序算法----快速排序 3、归并排序 归并排序也是基于分治策略的另一个算法。 归并的思路是把两个已经排好序的数组合并 为一个。(源程序) 2-路归并排序示例:

38

初始值 一趟归并排序 两趟归并排序 三趟归并排序

E E E

Y Y K B U E

U K Y K L

K U

S L B S U Y L S

L

B B S

习题:对数字 49 38 40 97 76 13 27 进行归并排序 procedure mergesort(var r,r1:listtype;s,t:integer); {r,r1:均为链表,存储排序数据;过程 mergesort(r,r1,s,t)完成把链表 r 中的关键字进 行归并排序、并存放到链表 r1 中,其中 s 是下界 t 是上界} {过程 merge(r2,s,m,t,r1)把链表 r2 中排好序的子链 r2[s..m]和子链 r2[m+1..t]合并到 r1 中} if 问题不可分 then 求解 else (1)分出问题的一个子问题 1,并求解子问题 1 (2)分出问题的一个子问题 2,求解子问题 2 (3)合并子问题 1 和子问题 2 if s=t then r1[s]:=r[s] else mergesort(r,r2,s,(s+t)div 2); mergesort(r,r2,(s+t)div 2,t); merge(r2,s,(s+t)div 2,t,r1);

4、[循环赛问题](1999 年广东省青少年信息学奥林匹克竞赛 第三题:棒球联赛) 问题描述:广州市体委将举行一次由 N 支队伍(队伍编号为 1..N)参加的少年棒球联赛。 联赛总共不能多于 N 轮(同一时间内若干支队进行一次比赛为一轮),并且每两支队之间必 须而且仅必须进行一次比赛。请编程为这次比赛设计一个赛程表。 循环赛问题可以用分治法解决。下面是先假定 n=2^k

procedure table(k:integer;a:array[1..u1,1..u2] of integer); var n,i,j,m,s,t:integer; begin n:=1; for i:=1 to k do n:=n*2; for i:=1 to n do a[1,i]:=i; m:=1; for s:=1 to k do begin n:=n / 2; for t:=1 to n do for i:=m+1 to 2*m do for j:=m+1 to 2*m do begin
39

a[i,j+(t-1)*m*2]:=a[i-m,j+(t-1)*m*2-m]; a[i,j+(t-1)*m*2-m]:=a[i-m,j+(t-1)*m*2]; end; m:=m*2; end;{for s} end;

三、练习题
[二分检索]假定在 A[1..9]中顺序存放这九个数:-7,-2,0,5,16,43,57,102,291 要求检索 291,16,101 是否在数组中。 给定已排好序的 n 个元素 A1,A2,A3,…,An, 找出元素 x 是否在 A 中,如果 x 在 A 中, 指出它在 A 中的位置。 递归源程序 { 二分检索的方法充分利用元素之间的次序关系,采用分治策略可以在最坏情况下用 O (log n)的时间完成任务。 } program search; const n=10; var a:array[1..n] of integer; i:integer; x:real; Procedure BinarySearch(low:integer;high:integer;var i:integer); var mid:integer; begin if low>high then i:=0 else begin mid:=(low+high) div 2;{将 n 个元素分成大致相同的两半} if x=a[mid] then {取 a[n div 2]与 x 做比较} begin i:=mid; exit; end {如果 x=a[n div 2],则找到 x,算法结束。} else if x0 then writeln(x,' is the ',i,'th ',' one in the table.') else writeln(x,' is not in the table.') End.

program search;

40

const n=10; var a:array[1..n] of integer; i:integer; x:real; 非递归源程序 Procedure BinarySearch(low:integer;high:integer;var i:integer); var mid:integer; begin while low<=high do begin mid:=(low+high) div 2; if x=a[mid] then begin i:=mid; exit; end else if x0 then writeln(x,' is the ',i,'th ',' one in the table.') else writeln(x,' is not in the table.')

End.

贪心算法
一、算法思想
贪心法的基本思路: ——从问题的某一个初始解出发逐步逼近给定的目标, 以尽可能快的地求得更好的解。 当达 到某算法中的某一步不能再继续前进时,算法停止。 该算法存在问题: 1. 不能保证求得的最后解是最佳的; 2. 不能用来求最大或最小解问题; 3. 只能求满足某些约束条件的可行解的范围。 实现该算法的过程: 从问题的某一初始解出发; while 能朝给定总目标前进一步 do 求出可行解的一个解元素; 由所有解元素组合成问题的一个可行解;

二、例题分析
1、[背包问题]有一个背包,背包容量是 M=150。有 7 个物品,物品可以分割成任意大小。 要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。
41

物品

A

B

C

D

E

F

G

重量 价值

35 10

30 40

60 30

50 50

40 35

10 40

25 30

分析: 目标函数: ∑pi 最大 约束条件是装入的物品总重量不超过背包容量:∑wi<=M( M=150) (1)根据贪心的策略,每次挑选价值最大的物品装入背包,得到的结果是否最优? (2)每次挑选所占空间最小的物品装入是否能得到最优解? (3)每次选取单位容量价值最大的物品,成为解本题的策略。 源程序

2、[单源最短路径]一个有向图 G,它的每条边都有一个非负的权值 c[i,j],“路径长度” 就是所经过的所有边的权值之和。 对于源点需要找出从源点出发到达其他所有结点的最短路 径。 E.Dijkstra 发明的贪婪算法可以解决最短路径问题。算法的主要思想是:分步求出最 短路径, 每一步产生一个到达新目的顶点的最短路径。 下一步所能达到的目的顶点通过如下 贪婪准则选取:在未产生最短路径的顶点中,选择路径最短的目的顶点。 设置顶点集合 S 并不断作贪心选择来扩充这个集合。 当且仅当顶点到该顶点的最短路径 已知时该顶点属于集合 S。初始时 S 中只含源。 设 u 为 G 中一顶点, 我们把从源点到 u 且中间仅经过集合 S 中的顶点的路称为从源到 u 特殊路径,并把这个特殊路径记录下来(例如程序中的 dist[i,j])。 每次从 V-S 选出具有最短特殊路径长度的顶点 u,将 u 添加到 S 中,同时对特殊路径长 度进行必要的修改。 一旦 V=S, 就得到从源到其他所有顶点的最短路径, 也就得到问题的解 。

42

Dijkstra.pas 3、[机器调度]现有 N 项任务和无限多台机器。任务可以在机器上处理。每件任务开始时间 和完成时间有下表: 任务 开始(si) 完成(fi) a 0 2 b 3 7 c 4 d 9 e 7 f 1 g 6 8

7 11 10 5

在可行分配中每台机器在任何时刻最多处理一个任务。 最优分配是指使用的机器最少的 可行分配方案。请就本题给出的条件,求出最优分配。

43

三、练习题: 练习题:
已知 5 个城市之间有班机传递邮件,目的是为了寻找一条耗油量较少的飞行路线。5 个城市 的联系网络如图所示。 图中编号的结点表示城市, 两个城市之间的连线上的值表示班机沿该 航线已行的耗油量,并假定从城市 i 到 j 和城市 j 到 i 之间的耗油量是相同的。

分析: 1. 运用贪心思想: 在每一步前进的选择上,选取相对当前城市耗油量最小的航线; 2. 图解:若从 1 出发,有图: 总耗油量=14 1-2-5-3-4-1 但若路线改为:1-5-3-4-2-1,则总耗油量=13 所以,这样的贪心法并不能得出最佳解。 3. 改善方案: 从所有城市出发的信心过程,求最优的。

编程: 1. 数据结构: 城市联系网络图的描述(图的邻接矩阵的描述): const c=array[1..5,1..5] of integer=((0,1,2,7,5), (1,0,4,4,3), (2,4,0,1,2), (7,4,1,0,3)); 2. 贪心过程: begin 初始化所有城市的算途径标志;
44

设置出发城市 V; for i:=1 to n-1 do {n-1 个城市} begin s:=从 V 至所有未曾到过的城市的边集中耗油量最少的那个城市; 累加耗油量; V:=s; 设 V 城市的访问标志; end; 最后一个城市返回第一个城市,累加耗油量; end; 3. 主过程:实现改善方案 begin for i:=1 to n do begin cost1:=maxint; {初始化} 调用贪心过程,返回本次搜索耗油量 cost; if cost<cost1 then 替换; end; 输出; end.

type dim1=array[0..11] of integer; const c:array[1..5,1..5] of integer=((0,1,2,7,5), (1,0,4,4,3), (2,4,0,1,2), (7,4,1,0,3), (5,3,2,3,0)); n=5; p=5; var tour:dim1; best:dim1; visit:array[1..n] of 0..1; cost,cost1:integer; i,j:integer; procedure greedy1(g:integer; var tour:dim1; var cost:integer); var v,s,k:integer; function findmin:integer;

45

var i,len,s1:integer; begin len:=maxint; for i:=1 to n do if (i<>v) and (visit[i]=0) and (c[v,i]

46


更多相关文档:

信息学奥赛数据结构辅导资料

信息学奥赛数据结构辅导资料信息学奥赛数据结构辅导资料隐藏>> 目录1、数据结构基础...78 数据结构数据结构是计算机专业基础课程之一, 是十分重要的核心课程。 计算机...

信息学奥赛数据结构知识点归纳最新背诵版

信息学奥赛数据结构知识点归纳最新背诵版_IT/计算机_专业资料。信息学奥赛 信息学奥赛数据结构知识点归纳 数据结构知识点归纳数据结构的定义:数据在计算机中的组织。...

信息学竞赛辅导资料

信息学竞赛辅导资料_学科竞赛_高中教育_教育专区。信息学奥赛。。第...文件操作(从文本文件中读入数据,并输出到文本文件中) 数据结构 程序设计 1....

信息学奥赛(初赛)辅导教材

快速排序)第 1 页 金华一中信息学(计算机)奥林匹克竞赛辅导教程 ③查找(顺序查找、二分法) ④回溯算法 二、复赛内容与要求 2.1 数据结构 ①指针类型 ②多维...

信息学奥赛辅导资料

信息学奥赛辅导资料_IT/计算机_专业资料。信息学奥赛辅导资料信息学奥赛 辅导资料信息组 目 录 1、数据结构基础知识………2 2、动态规划………17 3、分支限界…...

信息学奥赛辅导资料

信息学奥赛 辅导资料信息组 目 录 1、数据结构基础知识………2 2、动态规划…...要想更好地运用计算机来解决实际问题, 仅仅学 习计算机语言而缺乏数据结构知识是...

信息学奥赛自学材料

信息学奥赛培训资料 暂无评价 234页 3下载券 信息学奥赛数据结构辅导... 47页...今年是国际数学联盟确定的"2000--世界数 学年",又恰逢我国著名数学家华罗庚先生...

信息学奥赛培训练习题(数据结构)

信息学奥赛培训练习题(数据结构) 信息学奥赛培训练习题(数据结构)作者:薛浩 文章来源: 发布时间:2010-06-22 点击数:839 1. 数据结构被形式地定义为(K,R),...

NOIP高中信息技术竞赛资料 ----数据结构

NOIP高中信息技术竞赛资料 ---数据结构_学科竞赛_高中教育_教育专区。第 1 章...必须按某一拓扑序列安排学习计划,方能保证学习任一课 程时其先修课程均已学过...
更多相关标签:
信息学奥赛辅导资料 | 信息学奥赛辅导 | 信息学奥赛辅导教程 | 信息学奥赛辅导计划 | 数据结构考研辅导 | 数据结构考研辅导书 | 数据结构考研辅导 pdf | 数据结构考研辅导教程 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com