算法合集之《数学模型的建立比较和应用》.docVIP

数学模型的建立、比较和应用 数学模型的建立、比较和应用 - PAGE 4 - IOI’99中国集训队优秀论文选 IOI’99中国集训队优秀论文选 - PAGE 5 - IOI’99中国集训队优秀论文选 - PAGE 1 - 数学模型的建立、比较和应用 苏州中学 邵铮 关键字: 数学模型 算法 母函数 【摘要】 数学模型是解决实际问题的一种基本工具。将实际问题抽象成一个数学模型，运用数学工具进行求解，并将结果应用于具有相同特征的一类问题中，是解决问题的一种基本的途径。本文首先介绍了数学模型的一些性质，然后建立了三种不同的数学模型来求解一个问题，将三种数学模型相互比较，得出数学模型抽象性与高效性之间的关系，再将数学模型推广应用于另两个问题的求解，得出数学模型抽象性与可推广性之间的关系，最后总结全文，揭示出有关数学模型的一些普遍规律 一、引论 实际问题往往是纷繁而复杂的，而其中的规律也是隐藏着的，要想直接用计算机来求解实际问题往往有一定的困难。计算机擅长的是解决数学问题。因此，我们有必要将实际问题抽象成数学模型，然后再用计算机来对数学模型进行求解。 与实际问题相比，数学模型有以下几个性质： 抽象性：数学模型是实际问题的一种抽象，它去除了实际问题中与问题的求解无关的部分，简明地体现了问题的本质。这一点是下面两个性质的基础。 高效性：数学模型中各个量之间的关系更为清晰，容易从中找到规律，从而提高求解的效率。由于这一点是由数学模型的抽象性决定的，因此数学模型的抽象化程度对数学模型效率的高低有重要的影响，这一点将在第二部分中详细阐述。 可推广性：数学模型可以推广到具有相同性质的一类问题中。换句话说，解决了一个数学模型就解决了一类实际问题。这里的“相同性质”是指相同的本质，表面看似毫不相干的问题可能有着相同的本质。由于这一点也是由数学模型的抽象性决定的，因此数学模型的抽象化程度对数学模型的推广范围也有重要的影响，这一点将在第三部分中详细阐述。 二、数学模型的建立和比较 由于考虑问题的角度不同，面对同一个实际问题，可能建立起各种各样的数学模型。在各种数学模型中，我们要寻找的是效率高的模型。模型的效率同模型的抽象化程度有关，下面从一个实例中来分析它们之间的具体关系。 【多边形分割问题】将一个凸n边形用n-3条互不相交的对角线分割为n-2个三角形,求分割方案的总数. 如:n=5时,有以下几种分割方案: 这道题可用以下几种方法来求解: 1.有哪些信誉好的足球投注网站法: 这种方法的思路是将各种分割方案全都列举出来。 显然，一组n-3条互不相交的对角线对应于一种分割方案，因此可把问题看作是求不同的对角线组的数目。 将n边形的n个顶点按顺时针方向编号为1、2、3……n，则一条对角线可表示为一个数对(a1,a2)，a1、a2分别表示对角线两端顶点的序号，a1a2，a1为对角线的始端，a2为末端。 对角线在对角线组中的顺序是无关紧要的，因此，一个对角线组是一个集合，它的元素是对角线。 判断两条对角线是否相交是一个必须解决的问题。设两条对角线分别为(a1,a2)与(b1,b2)，若把表示对角线的数对看作开区间，那么两条对角线不相交的充要条件是两个区间有包含关系或他们的交集为空集。 于是，我们建立起解决本问题的第一个数学模型： 已知：n的值, 一个集合由(n-3)个不同的开区间(i,j)组成, i∈{1..n-2}, j∈{i+2..n},(i≠1)或(j≠n) 同一个集合中任两个不同的开区间(i1,j1),(i2,j2)满足： ((i1,j1)∩(i2,j2)=空集)或((i1,j1)包含(i2,j2))或((i2,j2)包含(i1,j1)) 求：不同的集合的个数 有哪些信誉好的足球投注网站时，先考虑以顶点1为始端的对角线，可以不连任何对角线(图一中A)，也可以连(1,3)(图一中B)，或连(1,4)(图一中C)，或同时连(1,3)(1,4) (图一中D)。对于每一种情况，再考虑以顶点2为始端的对角线，依此类推。当得到n-3条互不相交的对角线时，便找到了一种方案(参见图一)。 图一 在考虑以顶点i为始端的对角线时，有以下几条规则必须遵循： 1.与原有对角线相交的对角线不得选取。 2.当i=3时，若顶点i-1为始端的对角线一条都未连，则对角线(i-2,i)必须是已经连的。 3.对角线的末端顶点序号必须大于i。否则，顶点i将成为对角线的末端，另一个顶点j(ji)成为对角线的始端，这条对角线已在考虑以顶点j为始端的对角线时考虑过了，再考虑将引起重复。 按照以上三条规则，即可得到如图一的有哪些信誉好的足球投注网站树(图中打√的叶结点为不同的分割方案)。 有哪些信誉好的足球投注网站法的数学模型较为复杂，用它可以求出具体方案，但它的抽象化程度不高，导致了求解时的低效率。为了使用上面的规则2来提高效率，求解