浅谈信息学思想与方法在数学学科中应用

王晨昊

【摘 要】近年来，信息技术产业引发越来越多的关注。其中包含的一些思想或方法得到人们的重视，值得学习与借鉴。此文对比信息学中所体现的思想方法与数学学科核心素养的相同之处，以一些经典问题作为例论，强调了信息学思想与方法在数学学科中的重要性，并最终上升到研究与学习方法层面，得出信息学思想与方法值得学习与借鉴的结论。

【关键词】条件处理;转化化归;数据分析

中图分类号： R197.3 文献标识码： A 文章编号： 2095-2457（2019）04-0285-002

DOI：10.19694/j.cnki.issn2095-2457.2019.04.111

0 引言

对于中学生而言，与信息技术接触最紧密的当属“五大竞赛”中的信息学竞赛。尽管与面向对象编程（OOP）与函数式编程（FP）等编程范式（programming paradigm）中内容有所不同，但信息学竞赛在服务于自己的题目的同时，也在其它学科中流露出相似的思想方法与思考过程。这使得许多竞赛选手回归课堂后，在其他科目中对题目的分析与解答上，获得了很大的提升。在数学这个与信息学联系最为紧密的学科中，这种影响尤为显著。

1 对条件的分类与处理

信息学竞赛作为一种将思维方式与解题方法转化为计算机语言的竞赛，逻辑的讲求尤为重要。通常，在编写代码的过程中均需出现多个用逻辑连接词与判断语句表示的判断与选择分支。通过此类分支的选用，结合题目要求与条件间关系（即并列关系，对应关系，对立关系），再加上合适算法的选择，我们就可以得到一个“正解”。从简单的“A+B Problem”到复杂的高级数据结构，利用分支结构对条件间关系的处理无处不在。

将这种条件分类处理方法类比到数学学科中，将题目所述条件可分析整合为上述三种关系。一般地，在数学学科中对前两种关系的处理通常归为一类，即较为常见的分析法和综合法，进而转化问题为对并列关系与对应关系之间优先级（顺序结构）的处理;而后一种，数学学科经常利用其对立关系（非此即彼）来“否定反面来肯定正面”，即反证法。反证法的应用十分巧妙，在许多难题，尤其在证明一些P或NP问题去掉某些约束后无法在多项式时间内完成证明或解答（即属于NPC类问题）中得到了广泛应用。比如，在证明命题“TSP问题在去掉代价函数c满足三角不等式的假设，则不可能在多项式时间内找到一个好的近似旅行路线，除非P=NP”[2]时用到的方法即反证法。在对条件整合后，我们根据条件关系会更明确地找到解答方向。

因此，信息学竞赛对条件的分类与处理思想在数学学科对条件的整合与利用中存在着导向作用，这二者间具有很多相似之处。

2 转化与化归思想

在信息学中，转化与划归思想可谓重中之重。首先，选手们需要从题面（有许多无实际用处只为增添趣味的内容）中过滤出有用的信息，并对筛选出的信息进行分析。例如，权值是否有实际意义（是否需要离散化），n、m等代表元的含义，给出的边是不是有向边等等。分析后思考其中包含的模型，最后根据数据范围来决定是否要在时间或空间上进行优化，要优化哪一部分。下面以一类“线性规划”题目为例：

给定n个实数变量与一些线性约束，确定这n个变量的值，使得某个线性函数最大化或最小化。[1]比如下面式子：

Maximum z=x1+2*x2-x3

2*x1+x2+x3≤14

4*x2+2*x2+3*x3≤28

2*x1+5*x2+5*x3≤30

x1，x2，x3≥0

为了方便，一般定义线性规划的标准形式为：目标函数最大化的;所有线性约束都为“左边小于某个常数”形式的;所有变量均为非负的。如上面的式子就是标准形式。

對于非标准形式线性规划问题，如何转化为标准形式呢？如果目标函数是最小化的，目标函数取个相反数即可;约束A≥B写成B≤A;约束A=B拆成两个约束A≤B和B≥A（如果左边有变量则移项到右边）;而对于没有非负约束的变量xi，拆成两个变量xi=（xi`-xi``）。转化为标准线性规划后，我们就可以用统一的方法如单纯形法求解了。

相似的，如果一个系统由n个变量和m个约束条件组成，形成m个形如ai-aj≤k的不等式（i，j∈[1，n]，k为常数），则称其为差分约束系统。现需寻找一个满足所有约束的a的最大值或最小值。以寻找最大值为例，我们注意到每个约束可写成ai+k≥aj（k为常数）的形式。此种形式让人想起了最长路中的转移d[i]+w≥d[j]（其中d[k]，k∈[1，n]表示从初始点出发到达点k的路径最大值，w为点i到点j边权）。我们若对于每个约束建立一条i到j的边权值为a，最终得到一张无向图则将其转化为点1到点n的最长路来求解。这是求解关于一组变量的特殊不等式组的方法。

无论是线性规划还是差分约束，在其变形或处理过程中，转化与划归思想发挥了很大作用。

对应到数学学科上来，这两种核心思想也对应数学核心素养——数学建模与数学抽象。在传统题目“哥尼斯堡七桥问题”中，这两种思想得到了完美结合。

题目叙述：1736年，年仅29岁的数学家欧拉来到普鲁士的古城哥尼斯堡。普瑞格尔河正好从市中心流过，河中心有两座小岛，岛和两岸之间建筑有七座古桥。现问是否有一走法使得每座桥恰好走过一遍并回到原出发点。

首先，我们注意到题目并不是用数学语言叙述的;对于用非数学语言叙述的题面，我们应该先将其转化为数学语言并过滤出有用信息。以此题为例，题目描述经过整合后可以归纳为，给出一张无向（可相互到达）联通图，询问是否存在一笔画的方法？

其次，对于这个略显复杂的图，我们可以将地点抽象为点，而把连接他们的桥看作无向边，从而忽略无用的信息（如形状，面积等）就得到了一个简单得多的图如下。

接下来，我们考虑假设每座桥都恰好走过一次，那么对于A、B、C、D四个顶点中的每一个顶点，需要从某条边进入，同时从另一条边离开。进入和离开顶点的次数是相同的，即每个顶点有多少条进入的边，就有多少条出去的边，也就是说，每个顶点相连的边是成对出现的，即每个顶点的相连边的数量必须是偶数。所以问题至此转换为判断图中是否存在连接奇数条边的点。若存在连接奇数条边的点，那么由上述证明结果可得，该途中一定没有符合条件的（欧拉）路径;反之则至少存在一条。

由于上图中A、B两点为连接奇数条边（即奇数度数）的点，所以上图中不存在一条符合条件的路径。

从这个问题的求解中不难看出，面对一道题面用非数学语言叙述且包含许多无用信息的题，我们应先运用数学抽象方法把问题用数学语言叙述;然后对剩余信息进行分析来进行数学建模，从自己的知识库中寻找相似结构从而确定研究问题的大致方向;再沿大致方向完成已知结构到目标形式的转化。在转化过程中需重视二者之间的差异性，通过差异来选取合适的变形方法，最终得到目标结论，该题的解答也就完成了。

3 数据处理与运算结合

在信息学竞赛中，某些题目需要选手们对小规模数据暴力求解出的结果进行分析，从而得出不易直接由數学推导证明出的结论。例如下面这道题（HNOI2009）：

题目描述：

我们称一个长度为2n的数列是有趣的，当且仅当该数列满足以下三个条件：

（1）它是从1到2n共2n个整数的一个排列{ai};

（2）所有的奇数项满足a1

（3）任意相邻的两项a2i-1与a2i（1≤i≤n）满足奇数项小于偶数项，即：a2i-1

现在的任务是：对于给定的n，请求出有多少个不同的长度为2n的有趣的数列。因为最后的答案可能很大，所以只要求输出答案 mod P的值。

对小规模数据暴力模拟输出后，我们不难发现这一列数其实是卡特兰数。这使得我们联想到出栈序列问题（结果同为卡特兰数），但题目叙述与出栈序列问题描述相差甚远，因此不妨尝试在不改变满足题目约束的前提下进行变化，使得题目变为求出栈序列方案数的问题。

考虑令从左到右依次处理时，把一个数放在奇数项看作入栈，放在偶数项看作出栈，则不难注意到栈中数（列）满足递增规律，栈外剩余数（列）也为递增数列，且一定满足对于序号相同的元素，栈内元素小于栈外元素。至此题目转化为求出栈序列方案数问题，完成了模型之间的转换。结果可用卡特兰数通项公式求解。（正确性证明略）

数学上，这种通过以少量特殊性结论来猜想一般性结论的方法被称为数学归纳法。我们可以根据猜想得出的一般性结论找到证明方向，返回来证明猜想的正确性。这种数学归纳法与证明结合的方法，其实质是将数学运算与数据分析相结合，先通过数据分析找出规律，判断处理方向，再利用数学运算证明。我们需对一些常见模型足够熟悉才能灵活运用此方法解题。这种基于假设的方法，在证明不等式成立等问题中有广泛应用。

4 结语

信息竞赛作为“五大竞赛”中唯一脱离中学课程之外的竞赛，其许多思想与方法在各学科中均有体现，并不局限于数学。在理工类科目中，结合信息技术，可以模拟实验结果，对物理模型或概念模型的正确性进行验证;在社科类科目中，结合信息技术可通过建立合适的模型来预测结果或进行大数据分析。有人曾设想以元胞自动机为原型制造一个模拟经营系统以找到己方公司最优的发展方法;理论上来说这种设想是完全正确的。此外，在编程中体现出的“优化到极致”以提高性能的思想更是体现在生活中的方方面面。因此，我们对信息学中体现出的思想与方法应有足够的重视。至少，作为学生我们可以把原来单科独立学习转变为从自己优势学科中提炼解题方法与内涵，将其中的方法与思想推广到其他科的学习中去。

【参考文献】

[1]刘汝佳，陈锋.算法竞赛入门经典——训练指南[I].北京：清华大学出版社，2012.

[2]（美）托马斯·科尔曼，（美）查尔斯·雷瑟尔森等.算法导论（第三版）[I].殷建平，徐云等译.北京：机械工业出版社，2013.