浅谈信息学中状态的合理设计与应用.ppt

该【浅谈信息学中状态的合理设计与应用 】是由【88jmni97】上传分享，文档一共【29】页，该文档可以免费在线阅读，需要了解更多关于【浅谈信息学中状态的合理设计与应用 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。浅谈信息学中状态的合理设计与应用福建省福州第三中学 刘弈
此处添加副标题内容
引言
A
在日常生活中，工作时间与工作数量、单位效率的关系可以用下面的这个式子来表达：
B
工作时间=工作数量*单位效率
引言
在信息学中，程序的运行时间是由两个因素决定的，程序中所处理的状态的总数目和处理每个状态所花费的时间。
程序运行时间=状态总数*单位效率
02
01
引言
信息学中的状态总数有时隐藏着许多冗余状态。我们对状态的合理设计与应用不仅能优化的算法效率，还能够帮助编程人员理清思路，降低思维难度。
例一 Square Root 状态分析
合理地分析状态数目
例二 Banal Tickets 状态优化
对状态进行优化
例三 Shoot Your Gun 状态设计
重新设计状态
1
2
例三 Shoot Your Gun
定义边平行于坐标轴的简单多边形为矩形多边形。
01
已知在一个大的矩形多边形M中有两个小的矩形多边形G和T。G边上的任意一点可以向其左上、左下、右上、右下四个方向发射出射线。射线在遇到M的边时会发生光的镜面反射。
02
求从G边上的任意一点发出一条射线到T所需要的最少反射次数。
03
矩形多边形最多包含50条边，顶点坐标为整数在[0，4000]之内。
04
枚举？
只需要处理整点和1/2点即可。
题目分析
使用普通的状态表示法，将每个点发射出的4个方向分别做为4个点，进行构图并使用最短路算法进行求解。
01
这样的状态数是O(n2)级别的，不能很好的解决此题。
02
分析条件
题目条件：
路线轨迹遵循光的传播路线
光是沿直线传播的，只有在遇到障碍物时才会发生反射
只有发生反射时，路线方向才会发生改变。也就是说，只有在边上才可能使方向发生变化。