国家集训队2004论文集_周源

论文

浅谈数形结合思想在信息学竞赛中的应用

安徽省芜湖一中 周源

目录

目录............................................................1

摘要............................................................2

关键字..........................................................2

引子............................................................3

以形助数........................................................3

[例一]Raney引理的证明.......................................3

[题意简述]...............................................3

[分析]...................................................3

目标图形化............................................3

小结..................................................4

[例二]最大平均值问题(USACO 2003 March Open)..................4

[题意简述]...............................................4

[分析]...................................................5

目标图形化............................................5

构造下凸折线..........................................5

维护下凸折线..........................................6

最后的优化：利用图形的单调性..........................7

小结..................................................7

以数助形........................................................7

[例三]画室(POI oi V Stage I).................................8

[题意简述]...............................................8

[分析]...................................................8

目标数值化............................................9

动态规划解题..........................................9

小结.................................................10

总结...........................................................10

附录...........................................................11

关于2003年上海市选拔赛题Sequence..........................11

[题意简述]..............................................11

[分析]..................................................11

论文附件....................................................12

参考文献.......................................................12

论文

摘要

数与形是数学中两个最古老而又最基本的对象，数形结合又是一种重要的数学思想。

本文主要以当今信息学奥赛中几道试题为例，从以形助数和以数助形两个侧重点讨论了数形结合思想在信息学竞赛解题中广阔的应用前景。

最后文章分析指出数形结合思想的两个重要特性并由此提出“数形结合”重在有机的结合，希望对同学们在实际比赛中灵活的运用数形结合思想有一些帮助。

关键字

信息学竞赛 数学思想 数形结合思想

以数助形 以形助数

辩证矛盾 多元性 个体差异性

思维、编程、时间、空间复杂度

论文

引子

数与形是数学中两个最古老而又最基本的对象，数形结合又是一种重要的数学思想。

在当今信息学竞赛中，某些纷繁复杂的试题背后，往往蕴含着丰富的几何背景，而计算几何类问题却又需要借助计算机强大的实数运算能力。正如华罗庚先生所说的“数形结合千般好”，在算法和程序设计中，巧妙地运用数形结合思想，可以顺利的破解问题，化难为易，找到问题的解题思路。

数形结合思想常包括以形助数、以数助形两个方面。

以形助数

正如前文所述，一些试题中繁杂的代数关系身后往往隐藏着丰富的几何背景，而借助背景图形的性质，可以使那些原本复杂的数量关系和抽象的概念，显得直观，从而找到设计算法的捷径。

[例一]Raney引理的证明

[题意简述]

设整数序列A = {Ai, i=1, 2, …, N}，且部分和Sk=A1+…+Ak，序列中所有的数字的和SN=1。

证明：在A的N个循环表示1中，有且仅有一个序列B，满足B的任意部分和Si均大于零。

[分析]

先来看一个例子，若有序列A = <1, 4, -5, 3, -2, 0>，其6个循环表示为

1. <1, 4, -5, 3, -2, 0>

2. <4, -5, 3, -2, 0, 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序列，得到一个无穷序列，便于观察其循环表示，得到： 1 先设一个序列是环状的，则从其任意一个字符处断开以后形成的非环序列即为该序列的一个循环表示。

论文

<A1, A2, …, AN, A1, A2, …, AN, …>

同时计算这个序列的部分和Si，因为这个序列是周期性的，因此对于所有的k>0，均有Sk+N=Sk+1。如果做出这个函数的图像，则可以说函数有一个“平均斜

1率”为：每沿横轴正方向走N个单位，函数值就增加1。于是如下图所示，N

1可以用两条斜率为的直线“夹住”函数包含的所有点：

N

图 1 无穷序列的部分和函数图像

图示中N=6，且使用了上文举的例子。注意较低的那条直线，在每连续的N

1个单位长度中，它与函数图像有且仅有一个交点，这是因为斜率是的直线在N

每N个单位长度中最多到达一次整数点。这个交点是在这以后 …… 此处隐藏：10213字，全部文档内容请下载后查看。喜欢就下载吧 ……