资源描述：
《浅谈数形结合思想在信息学竞赛中的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、浅谈数形结合思想在信息学竞赛中的应用安徽周源浅谈数形结合思想在信息学竞赛中的应用安徽周源目录目录1摘要2关键字2引子3以形助数3[例一]Raney引理的证明3[题意简述]3[分析]3目标图形化3小结4[例二]最大平均值问题(USACO2003MarchOpen)4[题意简述]4[分析]5目标图形化5构造下凸折线5维护下凸折线6最后的优化：利用图形的单调性7小结7以数助形7[例三]画室(POIoiVStageI)8[题意简述]8[分析]8目标数值化9动态规划解题9小结10总结10附录11关于2003年上海
2、市选拔赛题Sequence11[题意简述]11[分析]11论文附件12参考文献12loanapprovalandpostcreditapprovalofficer/atalllevelsinaccordancewithcreditapprovalrules,licensingandeventualexerciseofcreditdecisionpowerofpersonsorinstitutions.Reviewfindingsandreviewcomments,accordingtotheBank's
3、credit第11页共12页浅谈数形结合思想在信息学竞赛中的应用安徽周源摘要数与形是数学中两个最古老而又最基本的对象，数形结合又是一种重要的数学思想。本文主要以当今信息学奥赛中几道试题为例，从以形助数和以数助形两个侧重点讨论了数形结合思想在信息学竞赛解题中广阔的应用前景。最后文章分析指出数形结合思想的两个重要特性并由此提出“数形结合”重在有机的结合，希望对同学们在实际比赛中灵活的运用数形结合思想有一些帮助。关键字信息学竞赛数学思想数形结合思想以数助形以形助数辩证矛盾多元性个体差异性思维、编程、时间、空间
4、复杂度loanapprovalandpostcreditapprovalofficer/atalllevelsinaccordancewithcreditapprovalrules,licensingandeventualexerciseofcreditdecisionpowerofpersonsorinstitutions.Reviewfindingsandreviewcomments,accordingtotheBank'scredit第11页共12页浅谈数形结合思想在信息学竞赛中的应用安徽周源引
5、子数与形是数学中两个最古老而又最基本的对象，数形结合又是一种重要的数学思想。在当今信息学竞赛中，某些纷繁复杂的试题背后，往往蕴含着丰富的几何背景，而计算几何类问题却又需要借助计算机强大的实数运算能力。正如华罗庚先生所说的“数形结合千般好”，在算法和程序设计中，巧妙地运用数形结合思想，可以顺利的破解问题，化难为易，找到问题的解题思路。数形结合思想常包括以形助数、以数助形两个方面。以形助数正如前文所述，一些试题中繁杂的代数关系身后往往隐藏着丰富的几何背景，而借助背景图形的性质，可以使那些原本复杂的数量关系和
6、抽象的概念，显得直观，从而找到设计算法的捷径。[例一]Raney引理的证明[题意简述]设整数序列A={Ai,i=1,2,…,N}，且部分和Sk=A1+…+Ak，序列中所有的数字的和SN=1。证明：在A的N个循环表示先设一个序列是环状的，则从其任意一个字符处断开以后形成的非环序列即为该序列的一个循环表示。中，有且仅有一个序列B，满足B的任意部分和Si均大于零。[分析]先来看一个例子，若有序列A=<1,4,-5,3,-2,0>，其6个循环表示为1.<1,4,-5,3,-2,0>2.<4,-5,3,-2,0,
7、1>3.<-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的条件。若要用一般的代数或是组合方法来证明这个有趣的结论，似乎无从下手，但若要想到了用“形”来帮忙，问题就简单多了。目标图形化周期性的推广A序列，得到一个无穷序列，便于观察其循环表示，得到：loanapprovalandpostcreditapprovalofficer/atalllevelsinac
8、cordancewithcreditapprovalrules,licensingandeventualexerciseofcreditdecisionpowerofpersonsorinstitutions.Reviewfindingsandreviewcomments,accordingtotheBank'scredit第11页共12页浅谈数形结合思想在信息学竞赛中的应用安徽周源同时计算
