tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> IT/计算机 >>

国家集训队2008论文集从立体几何问题看降低


从立体几何问题看降低编程复杂度

人大附中 高亦陶

引言:一类立体几何问题
O(1)的空间复杂度 O(1)的时间复杂度 并非公认的简单题

巨大的编程复杂度

1 运用合适的思维方式
使用方程是一种进步 方程是一种抽象的,通用的解题方法 但是方程有时会忽略一部分已知信息 通过具体地思考,充分利用已知信息可以 从本质入手,降低编程复杂度

例1 Model Rocket Height
给出两条直线的起点和方向,求它们公垂 线中点的高度. 直线方向用仰角和方向角表示.

数据的初步处理和思路
公垂线 叉积
n = a×b

方向向量

(1, tan α ,sec α tan θ )

尝试解题
uuu uuur uuur uuu r r AB = AD + DE BE

= λ1 a + λ3 n λ2 b

根据空间向量基本定理 有唯一解 可以化成 三元一次方程组 消元?行列式? 麻烦 浮点误差?

进一步思考
uuu uuur uuur uuu r r AB = AD + DE BE
uuu r uuur uuur AB n = DE n = DE n uuur uuu r uuur DE AB n DE = n = n 2 n n

另外两个未知量

uuur uuu uuur uuur uuu r r AB′ = AB DE = AD BE

三角形内已知一边和内角,求另一边长

最后一步
uuur uuur uuur AB′ b = PB′ b = PB′ b uuur uuur uuur PB′ AB′ b b = b PB′ = 2 b b uuur uuu r AD cos ∠DAP = AP uuur uuu r uuu 2 r uuu uuur uuur r AD AP uuur AP AP = AB′ PB′ uuu r r AD = a= a = uuu a a a AP a AP uuu a r a AP

小结
uuu r uuur AB n DE = n 2 n uuur uuu uuur r AB′ = AB DE uuur uuur AB′ b PB′ = b 2 b uuu uuur uuur r AP = AB′ PB′ uuu 2 r uuur AP r AD = uuu a a AP uuur uuu uuur 1 uuur r OC = OA + AD + DE 2

将盲目的方程组求解 改为一系列向量运算 降低了编程复杂度

2 注意分类讨论
大量的分类+复杂的判断=难以承受的编程 复杂度 合理地把不同的情况合并起来可以大大改 善这种状况

例2 Crossing Prisms
平面内有一个简单多 现在将这个多边形分 边形. 分别以这两个多边 别放置在xz面和yz面 形为底,以y轴和x 多边形边数≤4,每个 上.它们关于面x=y 轴为母线,以10为 顶点都是整点,坐标 对称. 高作两个棱柱. 取值范围为[0,10].顶 点按照逆时针方向排 求这两个棱柱的交 序. 的表面积.

关注表面
观察某个柱的一个侧面 它的一部分是交的表面

多数情况
如果侧面与底面不平行 交的表面一定是 用侧面截柱得到的截面 面积×cos二面角=射影面积 二面角很容易求 射影面积=柱底图形与y1 ≤ y ≤ y2的交的 面积

重要情况
如果侧面与底面平行 边数≤4 可以证明 只有图中两种情况

形状特殊的面

柱底图形 在特定高度上的宽 面积=宽2-(宽-边长)2

对正方形也适用!

继续利用这个宽

也可以用来计算射影面积! 射影面积=sum((宽1+宽2)*高/2) 需要对高度排序

算法框架
对高度排序 计算每点高度处的宽 枚举每一条边
判断平行与否 宽2-(宽-边长)2 或者 2*射影面积/cos二面角

计算宽 处理特殊情况
求所有边与y=yk的交点 最大值-最小值? ? 完全不考虑不规范交点? 利用逆时针顺序关系确定交点方向

面积≠(宽1+宽2)*高/2 ?
特判会打破先前的算法 框架 在局部改变宽的定义, 利用点的逆时针序忽略 一些边,使两个宽不同 修改两个点的高度顺序 最终使得面积可以照常计算

一种具体的处理办法
忽略和每个点相邻的边, 让凹角顶点对应的宽较 大 同时确保四个点的高按 逆时针顺序呈 1,2+,2-,3或3,2-,2+,1的 形式

小结:合并的效果
情况 判断 情况 情况 情况 判断 情况 情况 处理 中间量 比较复杂的计算途径 有点复杂的计算途径 另外的计算途径

另外的计算途径 剩下的计算途径

总结和启示
算法是多样化的,选择时要注重适用 适用性 适用 在遇到新问题时,首先想一想能不能在现 有框架内解决,而不是随意添加新的内容 对算法同样可以从类似内容中合并相同点 从而达到精简的效果

谢谢


推荐相关:
网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com