浅谈信息学中状态的合理设计与应用.ppt
《浅谈信息学中状态的合理设计与应用.ppt》由会员分享,可在线阅读,更多相关《浅谈信息学中状态的合理设计与应用.ppt(29页珍藏版)》请在三一文库上搜索。
1、浅谈信息学中状态的合理设计与应用 福建省福州第三中学 刘弈,引言,在日常生活中,工作时间与工作数量、单位效率的关系可以用下面的这个式子来表达: 工作时间=工作数量*单位效率,引言,在信息学中,程序的运行时间是由两个因素决定的,程序中所处理的状态的总数目和处理每个状态所花费的时间。 程序运行时间=状态总数*单位效率,引言,信息学中的状态总数有时隐藏着许多冗余状态。我们对状态的合理设计与应用不仅能优化的算法效率,还能够帮助编程人员理清思路,降低思维难度。,例一 Square Root 状态分析 合理地分析状态数目 例二 Banal Tickets 状态优化 对状态进行优化 例三 Shoot You
2、r Gun 状态设计 重新设计状态,例三 Shoot Your Gun,定义边平行于坐标轴的简单多边形为矩形多边形。 已知在一个大的矩形多边形M中有两个小的矩形多边形G和T。G边上的任意一点可以向其左上、左下、右上、右下四个方向发射出射线。射线在遇到M的边时会发生光的镜面反射。 求从G边上的任意一点发出一条射线到T所需要的最少反射次数。 矩形多边形最多包含50条边,顶点坐标为整数在0,4000之内。,下图左描绘出了一个例子,下图中描述了在特 殊点时的反射规则。射线方向如下图右。,题目中G边上的任意一点都可以发射出射线。,枚举?,只需要处理整点和1/2点即可。,题目分析,使用普通的状态表示法,将
3、每个点发射出的4个方向分别做为4个点,进行构图并使用最短路算法进行求解。 这样的状态数是O(n2)级别的,不能很好的解决此题。,分析条件,题目条件: 路线轨迹遵循光的传播路线 光是沿直线传播的,只有在遇到障碍物时才会发生反射 只有发生反射时,路线方向才会发生改变。也就是说,只有在边上才可能使方向发生变化。,如下图,图中加粗的边为射线的轨迹。,设计状态,因此我们不妨将边上的点作为状态 使用spfa算法则可以满足题目时间和空间的要求。 用spfa算法解决此题效果并不好。,深入思考,光路是不会部分重叠的,要么完全不重叠,要么完全重叠。 只需要枚举起点,然后每次遇到多边形的边的时候模拟反射,直到到达T
4、集合。 这样做之后,程序实现起来十分简单,运行效率也很高。至此,我们很好地解决了此题。,总结,对状态优化的方法是基于对状态的表示和对题目条件的深入分析而设计的。 在很多时候,对单位效率进行优化难以奏效,对状态进行合理地优化与设计却能大显身手,取得良好的效果。 对状态进行合理地分析及设计能帮助我们更好的理清头绪并设计出简洁的算法。,谢 谢,例一 Square Root,若整数x满足 x2 a (mod n),则称x 是以n为模时a的平方根,记root(a,n)为满足以上条件的x的集合。题目包含k个询问,每次询问给出a和n,其中n为质数,且a与n互质,要求出所有在(0,n-1)区间内的root(a
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 浅谈 信息学 状态 合理 设计 应用
链接地址:https://www.31doc.com/p-2594260.html