资源描述：
《论文国家队周源》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、濮筱救形結含思您在信息摩竞赛屮的宗用安徽省芜湖一中周源目录日录1摘要2关键字2引子3以形助数3［例一］Raney引理的证明3［题意简述］3［分析］3H标图形化3小结4［例二］最大平均值问题(USACO2003MarchOpen)4［题意简述］4［分析］5H标图形化5构造下凸折线5维护下凸折线6最后的优化：利用图形的单调性7小结7以数助形7［例三］画室(POIoiVStageI)8［题意简述］8［分析］8目标数值化9动态规划解题9小结10总结10附录11关于2003年上海市选拔赛题Sequence11［题意简述］11［分析］11论文附件12参考文
2、献12第1页共12页摘要数与形是数学中两个最古老而又最基本的对象，数形结合又是一种重要的数学思想。本文主要以当今信息学奥赛中几道试题为例，从以形助数和以数助形两个侧重点讨论了数形结合思想在信息学竞赛解题中广阔的应用前景。最后文章分析指出数形结合思想的两个重要特性并由此提出“数形结合”重在有机的结合，希望对同学们在实际比赛中灵活的运用数形结合思想有一些帮助。关键字信息学竞赛数学思想数形结合思想以数助形以形助数辩证矛盾多元性个体差异性思维、编程、时间、空间复杂度第2页共12页引子数与形是数学中两个最古老而又最基本的对象，数形结合又是一种重要的数学思
3、想。心右当今信息学竞赛中，某些纷繁复杂的试题背后，往往蕴含着丰富的几何背景，而计算几何类问题却又需要借助计算机强人的实数运算能力。正如华罗庚先牛所说的“数形结合千般好”，在算法和程序设计中，巧妙地运用数形结合思想,可以顺利的破解问题，化难为易，找到问题的解题思路。数形结合思想常包括以形助数、以数助形两个方面。以形助数正如前文所述，一些试题屮繁杂的代数关系身后往往隐藏着丰富的儿何背景，而借助背景图形的性质，可以使那些原木复杂的数量关系和抽象的概念，显得直观，从而找到设计算法的捷径。［例一］Raney引理的证明［题意简述］设整数序列A={Ai,i=
4、l,2,・.・,"},且部分和SqAi+...+Ar,序列中所有的数字的和SN=1O证明：在A的N个循环表示】小，有且仅有一个序列B,满足B的任意部分和S/均大于零。［分析］先来看一个例子，若有序列A=<1,4,-5,3,-2,0>,其6个循环表示为1.v1,4,・5,3,・2,0>2.<4,・5,3,・2,0,1>3.v・5,3,・2,0,1,4>4.<3,-2,0,1,4,-5>5.<-2,0,1,4,・5,3>6.<0,1,4,-5,3,-2>其中只有第4个序列，部分和为3,1,1,2,6,1,满足成为序列B的条件。若更用一般的代数或是组
5、合方法來证明这个有趣的结论，似乎无从下手，但若要想到了用“形”來帮忙，问题就简单多了。目标图形化周期性的推广A序列，得到一个无穷序列，便于观察其循环表示，得到：先设一个序列是环状的，则从其任意一个字符处断开以后形成的菲环序列即为该序列的一个循环表示。笫3页共12页同时计算这个序列的部分和Si,因为这个序列是周期性的，因此对于所有的k>0,均有Sa+jv=Sa+1o如果做出这个函数的图像，则可以说函数有一个"平均斜率”为丨：每沿横轴正方向走N个单位，函数值就增加lo于是如下图所示，可以用两条斜率为
6、I的直线“夹住”函数包含的所有点：图1无穷序列的部分和函数图像图示中N=6,且使用了上文举的例子。注意较低的那条直线，在每连续的N个单位长度中，它与函数图像有且仅有一个交点，这是因为斜率是丨的直线在每N个单位长度屮最多到达一次整数点。这个交点是在这以后的N个点屮的最低值，因此由此处的厉一个位置导出的循环表示的所有部分和均为正数。而同时每连续N个单位长度仅有一个交点也证明了解的唯一性。小结一个简单的儿何论证就证叨了著名的Raney引理，其简练是其他方法不能企及的。Raney引理有很广泛的应用，Catalan数以及扩展Catalan数的组合公式就可
7、以用该引理轻松解决。比如今年上海市选拔赛第二天比赛中的序列(Sequence)以及OIBH练习赛中的项链，使用Raney引理都是最简单的方法之一。2用儿何图形辅助思考，不只停留在组合计数这一类屮，更渗透在算法设计和优化的每一个分支屮，近年來流行的“斜率优化”法是另一个很好的例子。［例二］最大平均值问题(USACO2003MarchOpen)［题意简述］读入一列正数，ai,a?,av,以及一个数F。定义ave(ij)="八+12用Raney引理解答Sequence的过程，详见附录。求Max{ave(a,b),1Wa,BWN,且oWb・F+l},即
8、求一段长度大于等于F且平均值最大的子串。范围：FWNW'g［分析］简单的枚举算法可以这样描述：每次枚举一对满足条件的(d,b),即gWAF+1,检查a
