创新实习报告

《创新实习报告》由会员分享，可在线阅读，更多相关《创新实习报告（8页珍藏版）》请在金锄头文库上搜索。

1、（20132014学年 第2学期）实习名称 专项名称 专业 学号 姓名 实习地点 实习时间 实习成绩：项目制实习2014ACM暑期培训计算机通信20138568易圆皓西南交通大学犀浦校区8 月 8 日8 月 20 日指导教师（签字）：西南交通大学峨眉校区2014年 8月 20 日、实习目的：通过系统学习 ACM/ICPC 竞赛相关的算法，数据结构等，综合提高编程，解 决问题的能力。通过相关教师的培训，我们学习动态规划，数论，计算几何，图 论等几个板块。并且通过安排适当的比赛和训练模拟比赛，锻炼实际动手编程能 力。二、实习基本要求通过模拟比赛训练实际比赛时的动手能力；自己动手在各个OJ上做题，熟

2、悉各种体型 学习 ACM 竞赛相关的数据结构。 学习了离散数学相关知识； 综合掌握一些常见的算法并能灵活应用； 提前学习C语言，C+语言的相关知识； 熟悉使用相关的编译器；三、实习内容此次实习从 7 月 8 日开始，到 7 月 20 日结束，总共 13 天，我们所学的主要 包括以下方面的内容(部分摘自教学 ppt)1. 动态规划 动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有 许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规 划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求 解子问题，然后从这些子问题的解得到原问题的解。与分治

3、法不同的是，适合于 用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来 解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。 如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这 样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的 子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填 入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们 具有相同的填表格式。2. 计算几何复习向量的基本概念及定理。1. 多边形面积设顶点分别为：p1=(x1,y1),p2=(x2,y2),.,pn=(x

4、n,yn)，其面积为S=|p1,p2,. .，pn,pl| / 2,其中| p1, p2, . . . , pn, p1 |的形式如下：|x1, x2,.,xn,x1|y1, y2,.,yn,y1|= (x1*y2 + x2*y3 + .+ xn*y1) - (y1*x2 + y2*x3 + .+ yn*x1)2. 三角形外接圆 外接圆圆心叫外心，外心是三角形三条边中垂线的交点。3，判断点在直线上判断点P(x,y)是否在线段P1P2上，其中P1(x1,y1),P2(x2,y2) 需要验证两条4. 判断两线段是否相交(1) 快速排斥试验(2) 跨立试验5. 判断线段是否在多边形内 线段在多边形内

5、的一个必要条件是线段的两个端点都在多边形内，但由于多边 形可能为凹，所以这不能成为判断的充分条件。6. 凸包 凸包是对平面是上的某个点集而言的 凸包是一个最小凸多边形，满足点集中的所有点都在该凸多边形内 Graham 扫描法:排序选出点集中最左下角点(先取 y 坐标最小的点，若有多个再在其中取 x 坐 标最小的点)，设该点为 p0；将其余的按以p0为中心的极角坐标逆时针排序，多于相同极角的点只保留距离 P0最远的一个，这样就可以得到一个点的序列p1,p2, p2,pn;将p0, p1, p2压入栈，一次处理pi(i = 2 & i = n)，不断让栈顶的元素 出栈，直到栈顶的下一个元素，栈顶元

6、素，以及pi构成的折线不拐向左侧，将 pi 压入栈中；最后栈中的元素即为所求的凸包的顶点序列。3. 数论1) 求素数的方法pN存储所有的素数，二重循环，用已经求出的不大于平方根的所有素 数试除 第一种方法:for(i=2;in;+i) for(j=0;jm & pj*pj=n;+j)如果pj整除i,则i不是素数如果都不能整除，则i是素数，添加到素数列表pN。 第二种方法：增加布尔型数组bN记录是否为素数，初始化所有值二1,从头开始遍历, 如果bi=1，则i是素数，将所有的i的倍数j均修改为bj=0 for(i=2;in;+i)如果bi=1则添加到素数列表p，然后利用循环for(j二i;jn;j

7、+二i) bj=0 将 i 的所有倍数删掉。2) 二分法计算乘方1) 计算a*a*a*a*a*a,需要计算n-1次乘法，时间复杂度O(n)2) 考虑实例a4，计算b=a*a,再算c=b*b，则c二a4，但是只用了两次 乘法，效率提高。比如a9=a*(a4)*(a4)，只需用4次乘法，一般的, an时间复杂度为O(logn)。3) gcd 和 lcmEuclid 算法int gcd ( int a, int b ) int mod;while ( mod = a % b ) a = b, b = mod; return b;/注意这里面必须a,b都为正数，否则要加其他判断语句Extended-E

8、uclid 算法：同时求出 v, u 使 gcd(a,b)=u*a+v*b 重要) LCM ( a, b ) = a * b / GCD ( a, b )4) 中国剩余定理中国剩余定理的内容如下：令n=n1n2.nk，其中ni是两两互质的数，则对0二an与0=ai b*x + (a - a/b*b)*y = a*y + b*(x - a/b*y) ，4.图论所以 a*x + b*y = d 的解 x1 = y0， y1 = x0 - a/b*y0; 这样我们可 以程序迭代了。图论的相关的模块有：a. 拓扑排序拓扑排序的计算机实现：采用邻接表作为有向图的存储结构，且在头结 点中增加一个有效顶点的

9、入度，入度为零的顶点即为没有前趋的顶点， 删除顶点及弧可以使对应的顶点的入度减 1。 为避免重复检测入度 为零的顶点，可另设一堆栈存储所有入度为零的顶点，每当输出入度为 零的顶点，并从堆栈中删除该节点，反之，当有新的入度为零的顶点则 插入。b. 最短路最短路问题是指给定一个边带权的图G,求从某个起始点到某个终点e的权值和最小的路径。分为以下几类：(1) 非负边权的单源最短路(2) 任意边权的单源最短路(3) 任意边权的所有顶点之间的最短路c. 最小生成树设G=是一个无向图，如果T=是由G的全部顶点及一 部分边组成的子图并且T是树，则称T是G的一个生成树。当边带有权 值，对于G的任意一个生成树，

10、把属于T的各条边的长度加起来的和成 为T的长度，在G的所有生成树中，路径长度最小的称为最小生成树。kruskal 算法思想:取所有结点中距离最小的两个结点 ,看这两个结 点的路径是否与已经存在的结点路径构成回路,如果不构成回路,那么这 两个结点的路径就是最小生成树的一条路,否的话舍弃这条路,继续找所 有结点最小的路直到所有的路都遍历完.d. 图的连通问题需要掌握的概念：连通,点割集，割点,边割集，割边等。在一个无向连通图G中，如果任意去掉一个顶点i及依附于i的所有边后得到的 图依然是连通的，则该图G为2-连通图。否则，如果删除了结点i后, 得到两个或两个以上的连通分量，那么该图就不是2-连通的

11、，结点i称 为割点(关节点)。由深度优先生成树可得出割点的两类特性：1) 若生成树的根为割点，当且仅当其有两棵或两棵以上的子树。2) 若生成树的非根结点u为割点，当且仅当其存在一个u在深搜树中的 子女，能够通过回边指向u的祖先。(即u不为根且存在一个u在深搜树 中的子女v使得LOWv三Du。)e. 图的着色问题着色的算法 1穷举法（鲍威尔算法）1）将图 G 中的结点按照度数的递减次序进行排列（排列可能不唯一）2）用第一种颜色对第一点着色，并且按照排列次序，对与前面着色点不 邻接的每一点着上相同的颜色3）用第二种颜色对尚未着色的点重复步骤2，用第三种颜色继续这种做 法，直到所有点都全部着色为止。

12、着色的算法2回溯法（求解m着色问题）首先把所有顶点的颜色初始化为 0，然后依次为每个顶点着色。 在 图着色问题的解空间树中，如果从根结点到当前结点对应一个部分解， 也就是所有的颜色指派都没有冲突，则在当前结点处选择第一棵子树继 续搜索，也就是为下一个顶点着颜色 1，否则，对当前子树的兄弟子树 继续搜索，也就是为当前顶点着下一个颜色，如果所有m种颜色都已尝 试过并且都发生冲突，则回溯到当前结点的父结点处，上一个顶点的颜 色改变，以此类推。f. 最大流Ford-Fulkerson （福特-弗格森）方法：不断寻找可以使得流量增大的一 条增广路。所谓增广路，就是一条从源点 s 出发到汇点 t 的可以传

13、送比 当前更多流的一条路径。因为只要这样的路径存在，证明当前的流还可 以被改进，可以得到一个比原来流量更大的新流。最大流定理：如果残留网络上找不到增广路径，则当前流为最大流 反之，如果当前流不为最大流，则一定有增广路径。方法步骤：先找到一条s到t的路径，对于已经找到一条从s到t的路 径的网络中，只要在这条路径上，把C（u,v）的值更新为C（u,v）-P（u,v）, 并且添加反向弧C（v,u），得到一个网络成为“残留网络”对应的增广 路径为残留网络上从S到T的一条简单路径。如果残留网络上找不到增 广路径，则当前流为最大流。g. 二分图匹配问题二分图指的是这样一种图：其所有的顶点分成两个集合M和N，其中 M或N中任意两个在同一集合中的点都不相连。二分图可描述为：1）顶点的集合；2）将该顶点集分为两部分的一个划分；3）连接一部分的一个顶点与另一部分的一个顶点的边的集合； 二分图匹配是指求出一组边，其中的顶点分别在两个集合中，并且任意 两条边都没有相同的顶点，这组边叫做二分图的匹配，而所能得到的最 大的边的个数，叫做最大匹配。计算二分图的算法有：网络流算法和匈牙利算法。匈牙利算法描述：1）置M为空集2）寻找一条相对于M的增广路径P,且