2018年全国青少年信息学奥林匹克竞赛我校共有四名学生获奖，再创佳绩。

上海市一等奖：王梓宁（高二1班）、王重瑞（高一1班）；

王梓宁

王重瑞

上海市三等奖：张为奕（高一1班）、彭之恒（高一1班）。

张为奕

彭之恒

为每一位学生创建温馨的校园环境，为每一位学生搭建发展平台，我们一直在路上。

12月10日周一升旗仪式上，王梓宁同学作为获奖代表发言。

向上滑动阅览

尊敬的老师，亲爱的同学：

大家好，我很荣幸能够作为获奖学生代表在升旗仪式上发言，在这里我要感谢学校和老师们的支持和帮助以及同学们的鼓励。我也要感谢学校为我们请来的专业指导，让我们有了进一步的提升，有了获奖的可能。

程序等于算法加数据结构。下面我想简单地谈一谈我所认为的算法在生活中可能的应用。

举个例子，最近同学们写了许多明信片寄给外校，假设外联部的同学要通过地铁从我们学校出发将明信片送到本部。作为交附闵分的学生，自然希望节约路上时间用于学习，可是遗憾的是，他没办法使用智能手机进行导航，他现在只能靠自己找路了。

影响时间的因素有许多，我们忽略换乘的时间，并且认为任意2站之间的用时相同，即所花费的总时间与经过站的数目成正比。可以知道的是在非换乘站换乘反方向的列车一定不是最优的，所以我们只要考虑在换乘站的选择即可。

取所有的n个换乘站以及起点和终点组成一个新的集合，计算集合中相邻站之间的距离，1站视为1个距离单位，不相邻的站之间的距离视为无穷大。地铁线路是联通的，所以一定存在方案到达终点，又因为边权全部为正，易知最优解最多经过了所有换乘站，且最优解路线上的任意2点间的最短路线也一定是整体路线的子集。

所以枚举每一个换乘站，将集合中的任意2站经过所枚举的换乘站所经过的距离与原来计算的距离作比较，取较小值为新的最短距离，同时记录下较小值对应的线路。这样，经过n3的时间复杂度的枚举，我们就得到了起点与终点间的最短路，同学们的明信片可以送到本部了。

实际上在这个过程中我们同时求出了集合中任意2站间的最短距离。计算图中的最短路的算法有许多，由于数学中定义的图比日常生活中的地图的范围大很多，不同的算法有不同的适用范围和速度。我只希望以此为例说明算法在实际生活中的重要性，吸引同学加入到信息学竞赛中。谢谢大家！

王梓宁

2018年12月10日

交大附中闵行分校

网址：http://www.jdfzmh.sjtu.edu.cn/

微信号：jdfzmhfx

--end--

声明：本文章由网友投稿作为教育分享用途，如有侵权原作者可通过邮件及时和我们联系删除：freemanzk@qq.com