没有合适的资源?快使用搜索试试~ 我知道了~
浅析信息学竞赛中一类与物理有关的问题1
需积分: 0 0 下载量 163 浏览量
2022-08-03
22:47:21
上传
评论
收藏 688KB PDF 举报
温馨提示
试读
21页
摘要1关键字 1目录 2正文 3序言 3题目大意 3初步分析 4物理模型的转化 4平衡及稳定的判定 5对于退化数据的一些研究 6小结及拓展 6题目大意 7初步分
资源详情
资源评论
资源推荐
2008 年信息学奥领匹克竞赛冬令营论文 浙江 方戈
浅析信息学竞赛中一类与物理有关的问题
杭州学军中学 方戈
摘要
目前,信息学竞赛中出现许多与其他学科有关联的问题,这也是
信息学竞赛发展到一定阶段的必然趋势。而物理,作为一种实用性很
强的学科,与信息学也有着越来越紧密的联系,许多信息学竞赛中的
问题都或多或少跟物理有联系。而这类与物理有关的问题,正是本文
研究的重点。首先,本文将阐述研究与物理有关的问题的重要性,并
提出些典型的有物理特色的问题类型。然后,本文将重点解析几道典
型而有趣的问题。最后,本文将简单介绍作者在研究这类问题时碰到
的困难以及一些心得与体会。希望本文能对同学们更好地理解此类问
题有一定帮助。
关键字
信息学竞赛 物理 平衡
2008 年信息学奥领匹克竞赛冬令营论文 浙江 方戈
目录
浅析信息学竞赛中一类与物理有关的问题 ................................................................................... 1
摘要........................................................................................................................................... 1
关键字 ....................................................................................................................................... 1
目录........................................................................................................................................... 2
正文........................................................................................................................................... 3
序言 ................................................................................................................................... 3
例一[Ars Longa](World Final 2006 Problem C) .............................................................. 3
题目大意 ................................................................................................................... 3
初步分析 ................................................................................................................... 4
物理模型的转化 ....................................................................................................... 4
平衡及稳定的判定 ................................................................................................... 5
对于退化数据的一些研究 ....................................................................................... 6
小结及拓展 ............................................................................................................... 6
例二[water tanks](World Final 2007 Problem I) .............................................................. 7
题目大意 ................................................................................................................... 7
初步分析 ................................................................................................................... 7
一些简单的性质 ....................................................................................................... 8
对一类特殊情况的分析 ........................................................................................... 9
对一类特殊情况的算法 ......................................................................................... 10
从特殊到一般 ......................................................................................................... 10
一般情况的解决 ..................................................................................................... 11
小结 ......................................................................................................................... 13
例三[3D Musical Water-fence](陈启峰,PKU3242) ..................................................... 13
题目大意 ................................................................................................................. 13
初步分析 ................................................................................................................. 14
第一步优化——大胆猜测 ..................................................................................... 14
第一种算法 ............................................................................................................. 15
第二步优化——压缩 ............................................................................................. 16
第二种算法 ............................................................................................................. 18
小结 ......................................................................................................................... 19
总结 ................................................................................................................................. 19
附录......................................................................................................................................... 19
附录一:关于[例三]中的证明 ...................................................................................... 19
附录二:附件 ................................................................................................................. 20
附录三:供测试的网址 ................................................................................................. 20
感谢......................................................................................................................................... 20
2008 年信息学奥领匹克竞赛冬令营论文 浙江 方戈
正文
序言
虽然我们讨论的是有关物理的题目,但事实上他们并不需要很多物理的知
识,实际上它们中有很多只是用物理做了下背景而已。这些题目的种类很多,比
如像一类“倒水”的问题,又比如牵扯到“平衡”或“稳定”等字眼的一类问题,
而随便引入几个物理概念,就又能编出一类完全不同的题目了,可谓是五花八门,
千奇百怪。
但经观察又可以发现,这些题目还是有些共性的,比如,它们的背景一般是
三维的,这就需要我们对空间有很好的感觉,至少我们要能想象出题目描述的是
怎么样的情况,这需要我们对题目有很好的感性认识。
而然后,这类题目的做法也不是非常好想的,得到算法是一个盘旋上升的过
程,而这中间需要很严谨的思维,对于每一个结论,也必须有严密的证明,这就
需要我们对题目有很好的理性认识。
因此说,这类问题是需要感性和理性的结合的。它们考察的是一个人的各方
面综合素质,而从另一个角度上,它们的确涉猎了各个方面的算法——计算几何,
数学、动态规划、搜索、模拟、枚举,而考察各方面能力也正是信息学问题的发
展趋势,这也是目前此类问题非常重要的原因之一。
同时,由于背景是三维的,这些问题也就更贴近实际,更具有实用价值,而
不像很多数学题,动态规划题,只是思维的游戏,它们在这个三维的世界上有着
更好的用处,而这,就是此类问题非常重要的另一个原因。
这类问题通常是非常有趣的,并且它们的算法实现非常简单,程序不怎么长,
但他们的算法设计需要的是一个很长的一个过程,其间更需要的是有条理的分析
和很好的耐性,下面就来看一些例题吧。
例一[Ars Longa](World Final 2006 Problem C)
题目大意
在空间中有一个结构,由 N 个点和一些连接他们的边组成,给出 N 个点的
位置,点质量均为 1KG,点的 z 坐标是非负的,z 坐标是 0 的点是粘在地上不能
移动的,而 z 坐标大于 0 的点可以随意地移动。给出 M 条边,故略边的质量,
边十分牢固,可以承受无限大的力,忽略边之间的作用力。每条边连接两个点,
边可以绕着点无摩擦地转动,长度即为连接的两个点的初始位置之间的距离。边
对点的作用力可以是推,也可以是拉。
题目的保证不会有这样的退化数据,如一个点只收到水平的边的作用,这会
造成一些很难解决的情况。
称这个结构是平衡的,如果这个结构在重力作用下不会移动。
2008 年信息学奥领匹克竞赛冬令营论文 浙江 方戈
称这个结构是稳定
1
的,如果这个结构是平衡的,并且无论怎么给结构中的点
施加怎么样的力(可以给多点同时施力,并且力可以不同)也不会使雕塑移动。
现在要确定这个雕塑是否平衡或稳定。其中 N≤100,M≤100。
上面是两个例子,括号中是点的坐标,其中左图是稳定的,就像一个三角架,
而右图是平衡而非稳定的,上面三点的重心刚好在地面点的正上方,因此它能保
持平衡,但显然只要推它一下,它就倒了。
初步分析
这是一道非常贴近实际的题,因此我们对它会有许多的感性认识。显然的,
这需要用到物理中有关物体平衡的简单定理:
保持静止的物体是平衡的。
平衡物体所受到的合力为 0。
这样点的物理模型就出现了,然后是边的,注意到题目中的一句重要的话:
边可以绕着点无摩擦转动,这个实际上说明了边对点的作用力是在边所在直线上
的。边是理想化无重力的模型,因此边对两个点的作用力是相等并且相反的。
那么,整道题的物理模型就构建好了,然而此物理模型中包含着复杂多样的
情况,我们无法用计算机对此物理模型进行分析和计算,因此我们需要对模型进
行一些转化。
物理模型的转化
所受合力为 0,这样的判断句给我们的第一感受就是可以转化为等式。事实
上,如果把每个边所承受的力用未知数表示的话,那么对于某个在空中的点,它
的 x,y,z 坐标均可以建立一个平衡,这实际上就把平衡物体的物理模型等价转
化为了三个等式——数学模型。
其中边的力也就是未知数的数值,而边对两点的推和拉也就是未知数的正负
符号。
若空中点数有 P 个,那么对于每个空中的点都这样转化就会出现 3*P 方程,
这些方程有 M 个未知数,这些方程组成一个 M 元一次方程组。至此物理模型就
完全转化为了数学的模型。具体转化如下:
1
原题中所说的是“稳定(stable)”,但在物理学中,更严谨的讲法是“刚性(rigid)”,下同
剩余20页未读,继续阅读
爱设计的唐老鸭
- 粉丝: 19
- 资源: 291
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0