数学建模在OI中的应用

《数学建模在OI中的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学建模在信息学竞赛中的应用江苏省常州高级中学曹文一、概述实际问题往往是纷繁而复杂的，而其中的规律也是隐藏着的，要想直接用计算机来求解实际问题往往有一定的困难。计算机擅长的是解决数学问题。因此，我们有必要将实际问题抽象成数学模型，然后再用计算机来对数学模型进行求解。数学模型(MathematicalModel)：对于现实中的原型，为了某个特定目的，作出一些必要的简化和假设，运用适当的数学工具得到一个数学结构。也可以说，数学建模是利用数学语言（符号、式子与图象）模拟现实的模型。把现实模型抽象、简化为某种数学结构是数学模型的基本特征。它或者能解释特定现象的现实状态，或者能预测到对

2、象的未来状况，或者能提供处理对象的最优决策或控制。与实际问题相比，数学模型有以下几个性质：1.抽象性：数学模型是实际问题的一种抽象，它去除了实际问题中与问题的求解无关的部分，简明地体现了问题的本质。这一点是下面两个性质的基础。2.高效性：数学模型中各个量之间的关系更为清晰，容易从中找到规律，从而提高求解的效率。由于这一点是由数学模型的抽象性决定的，因此数学模型的抽象化程度对数学模型效率的高低有重要的影响。3.可推广性：数学模型可以推广到具有相同性质的一类问题中。换句话说，解决了一个数学模型就解决了一类实际问题。这里的“相同性质”是指相同的本质，表面看似毫不相干的问题可能有着相

3、同的本质。由于这一点也是由数学模型的抽象性决定的，因此数学模型的抽象化程度对数学模型的推广范围也有重要的影响。二、建立数学模型的方法和步骤1.模型准备首先要了解问题的实际背景，明确建模目的，搜集必需的各种信息，尽量弄清对象的特征。在信息学竞赛中这一步意味着：审清题意，了解题目的来龙去脉，弄清哪些量是已知的（输入），需要求什么（输出），数据规模如何等等，这是解决问题的前提。2.建立模型根据所作的假设分析对象的因果关系，利用对象的内在规律和适当的数学工具，构造各个量间的等式关系或其它数学结构，使之能够简洁高效地表达出题目给出的现实模型。不过我们应当牢记，建立数学模型是为了让更多的

4、人明了并能加以应用，因此工具愈简单愈有价值。3.模型求解15建模之后就是要解决模型。这步顺利与否很大部分上取决于所建模型的可解性如何。可以采用解方程、画图形、证明定理、逻辑运算、数值运算等各种传统的和近代的数学方法，特别是计算机技术。一道实际问题的解决往往需要纷繁的计算，因此编程能力和熟悉数学知识便举足轻重。4.编程实现其中，２、３两步是关键。模型建立与解决得好与坏对能否成功解决该题起着决定性的作用。三、具体应用1.对于同一个现实问题，可能可以建立不同的数学模型这种现象十分普遍，也就是平时所说的一题多解。既然如此，这里有必要讨论一下数学模型的选择问题，其实也就是评判一个模型好

5、坏标准的问题。一个好的数学模型不仅要能够准确地反映出现实模型（可靠性），所建立的模型还必须能够被有效地解决（可解性）。这里“有效”指的是解决它的算法所需的空间与时间都在可以承受的范围之内。通常在解一些要求最优解或要求准确计数的一类具有唯一正确解的试题时，我们一般在保证可靠性的前提下，尽量提高模型的可解性。若几个模型都具有可靠性，则当然可解性越强的模型越好。例如第六届分区联赛高中组第四题【方格取数】就可以建立多种数学模型，各个模型的在可靠性与可解性方面各有千秋，请看下面的分析。【问题描述】设有N＊N的方格图（N≤8），我们将其中的某些方格中填入正整数，而其他的方格中则放入数字0

6、。如下图所示（见样例）：向右A1234567810000000020013006003000070004000140000向下502100040060015000007014000000800000000B某人从图的左上角的A点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。此人从A点到B点共走两次，试找出2条这样的路径，使得取得的数之和为最大。【输入】输入的第一行为一个整数N（表示N＊N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。【输出】只

7、需输出一个整数，表示2条路径上取得的最大的和。【样例】82313152663574414522156463157214000结果67【问题分析】本题是从1997年国际信息学奥林匹克的障碍物探测器一题简化而来，如果人只能从A点到B点走一次，则可以用动态规划算法求出从A点到B点的最优路径。具体的算法描述如下：从A点开始，向右和向下递推，依次求出从A点出发到达当前位置（i，j）所能取得的最大的数之和，存放在sum数组中，原始数据经过转换后用二维数组data存储，为方便处理，对数组sum和data加进零行与零列