国家集训队2000论文集 骆骥论文_24878.doc

数学模型的建立和选择 骆 骥 （芜湖一中, 安徽 , 241000） 目 录 【关 键 字】 【摘 要】 【正 文】 一、从信息原型到数学模型 二、数学模型的建立 §2.1 机理分析法 §2.1.1直接建模法 §2.1.2套用常用模型法 §2.1.3针对修改常用模型法 §2.1.4 综合创造法 §2.2 统计分析法 三、数学模型的选择 四、总结 【附 录】 【程 序】 【参考书目】  【关键字】信息原型 数学模型 建模 【摘 要】 本文主要探讨的是信息学竞赛中解题的关键：数学模型的建立和选择。首先分析了从信息原型到数学模型的重要性，提出了解题的简单过程：现实——理论——现实。然后将数学模型的建立方法分为机理分析法和统计分析法两类，并着重分析了在竞赛中常用的机理分析法建模。接着，文章又对数学模型的选择做了一些必要的概述，得出一些模型选择的原则。最后，根据整篇文章探讨的结果得出了数学模型建立和选择的一般方法。 【正 文】 从信息原型到数学模型 在大千世界中，我们所面对的事物形形色色，扑朔迷离。它们都是由许多信息构成的。这些现实世界中对客观问题表面的自然语言描述，称为信息原型。当然，在信息学竞赛中我们所面临的问题也是信息原型。 信息原型本身是由扑朔迷离的信息构成，掩盖了其重要的属性[1]。我们因而无法直接从信息原型入手找到问题的答案。为此，我们就需要一种方法来“改造”信息原型，使之既具有原来的重要属性，也具有可研究性。 于是，我们试图将信息原型的属性一起转移到一个模型中。模型即是对客观问题属性的模拟。显然，这个对应出的模型可以说是信息原型的代表。我们就可以对这个模型进行研究。 用什么方法将信息原型对应到模型上去呢？我们期望运用数学方法。这样对应出的模型即具有原问题的属性又具有数学的可研究性。我们称之为数学模型。数学模型：运用数学语言对信息原型通过抽象加以翻译归纳的产物叫做数学模型。 信息原型是现实的问题，对应到的数学模型又是理论上的模型，对该模型进行研究使我们得出了现实问题的解。这就是信息学竞赛中解题的简单过程：现实——理论——现实。如图一所示： 为了能快速地从信息原型得到信息原型的解，在整个分析解题的过程中，从信息原型到数学模型的这一转变过程至关重要。根据图一，我们称该过程为建模：利用数学思想将信息原型转化成数学模型的过程。 下面，我们就将讨论：如何从信息原型到数学模型。 数学模型的建立 从实践中积累的经验，我们知道，建模没有固定的套路可言，方法比较多样化。但总的来说一般分为机理分析法和统计分析法两大类。 §2.1 机理分析法 【定 义】 机理分析法：根据客观事物的特性，分析其内部的机理，弄清关系，在适当抽象的条件下，利用合适的数学工具得到描述事物属性的数学模型的方法。 【图表描述】 我们在信息学竞赛中常用这种方法建立模型，然后根据所对应的算法求出解。如图二所示： 由信息原型，我们运用机理分析法通过抽象建模得出数学模型，再根据得出的数学模型理论对应到算法，编程实现，通过算法的执行得到问题的解。 【分 类】 机理分析法也是多种多样的，我们在实际竞赛中往往各种机理分析方法混用，所以分类比较困难。根据建模的几个不同层次特点，一般将其分为四类： §2.1.1直接建模法 【诠 释】 当信息原型比较简单，其属性显而易见时，我们通常用直接建模法。该方法可以说是将信息原型的显而易见的属性按数学方法综合起来得出模型。这个得到的数学模型针对性强，不具有普遍意义。 【分 析】 实际上，该直接建模法是一种创造。但思维比较简单，没有理论上的新发现，我们称为一级创造。例如NOI’97的竞赛排名一题，信息原型的各个属性十分明确，题目本身也有一定的抽象程度，性质大都由数学语言描述，更有利于我们直接建立简单的模型解题。在竞赛中我们一般遇到的这类题目主要考察我们怎样较好地将信息原型已知的属性按数学方法综合起来。 建模方法既然有创造，就有摹仿。我们还经常摹仿已知的模型来建模。下面就要介绍两种摹仿建模的方法。 §2.1.2套用常用模型法 【诠 释】 建模时，我们抽象数学模型的方向往往向已知的常用模型上靠拢，而且一旦符合，就直接建立已知的模型，并且完全套用其算法。 【举例分析】 下面我们就结合NOI’99 的01串问题进行分析。 例1 01串问题[ 2 ] 这道试题信息原型很好地将数学模型遮掩了起来，使我们比较难从中理出头绪。首先还是来分析一下该题的信息原型的主要属性： 设序列S为问题的一个解，则其一定满足： si=0或si=1，1=i=N； 对于S的任何连续的长度为L0的子串sjsj+1…sj+L0-1(1=j=N-L0+1)，0的个数大于等于A0且小于等于