1、数学模型及其在信息学竞赛中的应用数学模型及其在信息学竞赛中的应用【关键字】数学模型，可靠性，可解性【引言】数学模型是人们解决现实问题的有力武器。人们把现实问题经过科学地抽象、提炼得到数学模型，再用数学方法去解决。数学模型可分为离散和连续两种。连续数学模型需要大量的高等数学知识，中学生很少接触。在信息学竞赛经常出现的则是离散数学模型。本文主要介绍的就是离散数学模型的一般概念及建立方法。【正文】 所谓数学模型，就是现实世界中某一类特殊的运动变化过程、关系或结构的一种模拟性的数学结构，其实也就是对现实模型进行科学抽象后得到的模型。在信息学竞赛中，试题给出的问题通常是一个现实问题，这也就需要选手在审清
2、题意后首先把问题的关键因素总结、提炼出来，形成一个抽象的数学模型，这样有利于问题的分析与解决。 一般来说，我们在解一道有关现实问题的试题时，需要分以下几个步骤：1审清题意，了解题目的来龙去脉，弄清哪些量是已知的（输入），需要求什么（输出），数据规模如何等等。这是解决问题的前提。2建立模型，使之能够简洁高效地表达出题目给出的现实模型。3解决模型，得出算法。建模之后就是要解决模型。这步顺利与否很大部分上取决于所建模型的可解性如何。4编程实现。 其中，、两步是关键。模型建立与解决得好与坏对能否成功解决该题起着决定性的作用。（一）对于同一个现实问题，可能可以建立不同的数学模型 这种现象十分普遍，也就是
3、平时所说的一题多解。既然如此，这里有必要讨论一下数学模型的选择问题，其实也就是评判一个模型好坏标准的问题。一个好的数学模型不仅要能够准确地反映出现实模型（可靠性），所建立的模型还必须能够被有效地解决（可解性）。这里“有效”指的是解决它的算法所需的空间与时间都在可以承受的范围之内。通常在解一些要求最优解或要求准确计数的一类具有唯一正确解的试题时，我们一般在保证可靠性的前提下，尽量提高模型的可解性。若几个模型都具有可靠性，则当然可解性越强的模型越好。 例： 最佳旅行路线问题 IOI93 【问题描述】你在加拿大航空公司组织的一次竞赛中获奖，奖品是一张免费机票，可在加拿大旅行，从最西的一个城市出发，单
4、方向从西向东经若干城市到达最东的一个城市（必须到达最东的城市）；然后再单方向从东向西飞回起点（可途径若干城市）。除起点城市外，任何城市只能访问次，起点城市被访问次：出发一次；返回一次。除指定的航线外，不允许乘其他航线也不允许使用其他交通工具。求解的问题是：给定城市表列及两城市之间的直通航线表列，请找出一条旅行路线，在满足上述限制条件下，使访问的城市数尽可能多。 这是一个现实问题，我们首先可以做如下的抽象：把每个城市抽象成一个顶点。不妨设由西到东的城市对应编号分别是1至n。若两个城市之间有直通航线，则在相应的两点之间连一条边。这样，所有城市与直通航线就被抽象成了一个无向图。 【盲目搜索】这是最原
5、始的想法。我们一开始假想有两架飞机都从最西边的城市飞向最东边的城市，并且在搜索的过程中保证两条路线中的城市除起点与终点外都不相同。记下所有找到的路线中所经城市最多的方案，把其中的一条作为向东旅行的路线，一条作为向西旅行的路线，合并起来即得最佳旅行路线。 因为搜索的时间复杂度是指数级的，所以这样做的话，时间效率不够理想。究其主要原因就是所有模型的抽象程度不够，没有把试题中的限制充分融入数学模型中，盲目性太大。【网络流模型】为了把更多的试题中的限制融入模型中，我们在原有的模型的基础上建立了如下的最大费用最大流的模型：1）为了保证每个城市最多只能被访问一次，我们把每个城市i拆成两个顶点i和i，并在两
6、个顶点之间连接一条i至i的有向弧，单位费用设为0。2）将原图中的无向边改为有向弧：若城市i到城市j有直通航线（ij，或i=j=n时，我们考虑i的前趋顶点，不妨设为k。此时，到达顶点k与j的两条路线的所需乘航线之和也一定最大，否则与fi,j最大矛盾。若ij时，结论同理可得。由此，我们有如下的动态规则方程：f i, i 无意义 (1in）实际最多可能的访问城市数为f n,n-2。时间复杂度降为O（N2）。 对于最佳旅行路线这一个问题，我们建立了三种不同的数学模型。这三种模型都具有可靠性（可以得出最优解），但可解性不同。一般来说，建立的模型越简洁，抽象程度越高，算法实现时不必要的操作也越少，运行效率
7、也就越高。 值得注意的是，最近的一些竞赛中有时会出现根据解的近似程度给分的题目。对于这类题目，我们更多考虑的则是所建模型的可解性。当然，可靠性的降低也是有限度的，这个限度就是方案的可行性及误差允许范围。此外，许多数学模型有近似解法，这些都是通过适当牺牲模型自身可靠性来提高模型的可解性。 （二）一个模型可能同时适用于多个现实问题。 这也就是我们要研究数学模型的主要原因之一。我们解决一个数学模型就相当于解决了一类问题。比如说，最短路径问题，可谓在现实生活中无处不在，上文中提到的网络流的模型也有着很高的实用价值。这些数学模型的解决使得许多实际问题迎刃而解。然而，数学模型的解决只是解决一个现实问题的一
8、半，另一半就是如何将现实问题转化为一个已经解决的数学模型，即如何建模。建模在现实与抽象之间起着桥梁的作用。尤其在竞赛中，后者有时显得更为重要。（三）如何建立数学模型？ 要能够建立数学模型，首先必须熟悉一些经典的数学模型及其算法。这是建模的基础，没有这个基础则根本谈不上建立什么数学模型。竞赛中许多问题最终都可以转化为经典的数学模型，因此必须掌握这些常见的模型。 其次建立数学模型需要选手有把实际问题相互联系，类比的能力。上文已经指出许多实际模型都有着相同或相似的数学模型。既然这样，它们之间必然存在着一些相同或相似。相互联系、类比是发掘这些信息的有效手段。这里先给出一个大家都很熟悉的模型： 【凸n边
9、形分割】一个凸n边形，可以通过不相交的(n-3)根对角线，把n边形拆分成(n-2)个三角形。求方案数hn。当n=5时，方案数h5=5。 【配对括号序列】求由n个左括号(，n个右括号)，能组成多少种不同的配对括号序列，记作Qn。一个序列的配对与否定义如下： 1（）是配对的。2若A是配对的，则(A)也是配对的。3若A、B都是配对的，则AB也是配对的。这两题的模型都是大家十分熟悉的Catalan数Cn=1/(n+1)*C(2n,n)。通过数学计算可知，hn=Cn-2，Qn=Cn（证明略）。 【结和律】有n个数a1,a2,a3,an依据加法结合律，不改变其顺序，只用括号表示成对的和，问有几种求和方案P
10、n？ 因为题目只要求求配对方案数，与a1,a2,a3,an的值无关。我们不妨令S=a1+a2+a3+an，并把ai（0=i Si-p (pin)Si Si-q (qin) 我们再建一个有向图，共有n1个顶点，分别是S0至Sn，若SiSj，那么就从Si往Sj引一条边。如图（n=6,p=5,q=3）。这样对于S0,S1,Sn来说，他们必须是拓扑有序的（S00），反过来，任何一组S0Sn都惟一地对应一个整数数列。现在，我们已经把这道题目轮换为一个图论的拓扑排序的问题，而这个问题又是我们非常熟悉的。程序见附录。回到NOI99的那道题，将此题与CEOI94的那题相互联系，我们发觉这两题都涉及到连续这个概
11、念。我们也同样可以建一个图，顶点分别表示S0Sn，这里Sn表示所求串第i位以前（包括第i位）1的出现次数。略有不同的是，这次不但Si与Sj之间有大小关系，还需要表示出到底大多少。我们把这个量作为Si与Sj之间的边上的权。具体地说，若SjSi+k，则我们就从Si向Sj引一条权为k的单向边。至此，题目中的两个条件都已经在图中体现出来了。还有一点需要注意的是，本题与上题不同，它要求每个字符非 0 即 1 ，所以我们也需要把这点体现在图中，即再加2n个不等式：Si+1Si，Si+1Si+1。接下来的问题就是求其它各点到S0的最长路。其实，本题与上题都可以转化为同一个模型，即图论最长路问题，因为我们可以
12、把上题图中边的权就看作是1。初看上去，以上两题都似乎与图论无甚关系。题目中并没有出现图论中常见的“城市”，“终端”等顶点，也没有“铁路”，“线路”等边，还没有“长度”，“传输时间”等权，但都确确实实用图论模型漂亮地解决了，不由地让人发出感叹真没想到呀！其实，想到与没想到虽就一念之差，却不是偶然的：这里面既有经验的因素，也与你所掌握数学模型的多少有关，更重要的则是你的创造力。在上两题中把Si作为顶点，大小关系作为边，以及权的确定都不可以不说是一种创造。而正是它们在上两题的解决中起了关键性的作用。 纵观人类的进步史， 创造力有着举足轻重的作用。计算机发展至今，无论是性能的提高，软件的发展，还是网络
13、的诞生，处处体现了人类非凡的创造力。创造力是研究信息学的基本素质之一，也是信息学竞赛考察的重点。【参考书目】青少年国际和全国信息学（计算机）奥林匹克竞赛指导丛书组合数学的算法与程序设计 吴文虎、王建德 编著图论的算法与程序设计 吴文虎、王建德 编著 清华大学出版社数学模型基础 王树禾 编著 中国科学技术大学出版社【附程序】Black and White，CEOI94:$A+，B-，D-，E-，F-，G+，I-，l-，N-，O-，P-，Q-，R-，S-，T-，V-，X-$M 65520，0，655360program Black_and_White(input, output);const ma
14、xn = 1000;var i, n, p, q, count: integer; count: 拓朴排序的序号 s, d: array0.maxn of integer; di为顶点i的入度 next: boolean; 拓朴排序结束标记begin write(n,p,q = ); readln(n, p, q);计算入度 fillchar(d, sizeof(d), 0); for i := 0 to n do begin if i + p = n then inc(di + p); S(i) = 0 then inc(di - q); S(i) S(i-q) end;拓朴排序 count
15、 := 0; repeat next := false; for i := 0 to n do if di = 0 then begin si := count; inc(count); if i + p = 0 then dec(di - q); di := -1; next := true; end; until not next or (count = n + 1); 直到所有顶点已被赋上序号或无0度顶点为止输出 if count n + 1 then 存在环 writeln(NO) else for i := 1 to n do writeln(si - si - 1);end.01串
16、，NOI99：$A+，B-，D-，E-，F-，G+，I-，l-，N-，O-，P-，Q-，R-，S-，T-，V-，X-$M 65520，0，655360program sequence (input，output)；const inputfile=input.txt； 输入文件名串 outputfile=output.txt； 输出文件名串 var head:array0.1000，1.6of record 有向图。headi，k顶点k引出的第k条有向边，其中 no，v:integer；headi，k.no为该边的终点序号；headi，k.v为该边的权 end； num:array0.1000o
17、f shortint； numi顶点i引出的边数 s:array0.1000of integer； si0位i位中1的个数 n，a0，b0，l0，a1，b1，l1:integer；n串长；l0，a0，b0连续长度为l0的子串中，0的个数的下限和上限为a0、b0；l1，a1，b1连续长度为l1的子串中，1的个数的下限和上限为a1、b1procedure addedge(a，b，c:integer)； 从顶点a 出发，构造一条权为c的有向边 begin inc(numa)； 累计顶点a引出的边数 heada，numa.no:=b； 设置该边的终点和权 heada，numa.v:=c； end； a
18、ddedgeprocedure init； 输入数据，构造有向图head var i:integer； begin readln(n，a0，b0，l0，a1，b1，l1)； 输入数据 fillchar(head，sizeof(head)，0)； 有向图初始化 for i:=1 to n do begin 逐个顶点地构造有向图 if i=l0 then begin 根据a0l0-(si-)b0构造有向边 addedge(i，i-l0，a0-l0)； addedge(i-l0，i，l0-b0)； end； then if i=l1 then begin 根据a1si-b1构造有向边 addedge
19、(i-l1，i，a1)； addedge(i，i-l1，-b1)； end； then addedge(i-1，i，0)； 根据si-1si构造有向边 addedge(i，i-1，-1)； 根据sisi-1+1构造有向边 end； for end； initprocedure main； 计算顶点0至其余顶点的最长路径 var i，j，k:integer； begin fillchar(s，sizeof(s)，0)； s数组清零 for i:=1 to n do 逐条边地延长路径 for j:=0 to n do 枚举第i条边的所有可能情况 for k:=1 to numj do if sj+
20、headj，k.vsheadj，k.no 若顶点0至顶点headj，k.no的所有路径中，经过顶点j的第k条有向边的一条路径为目前最长，则记下 then begin sheadj，k.no:=sj+headj，k.v； if sheadj，k.noheadj，k.no then begin 若0位headj，k.no位全填1也不能满足条件，则无解退出 writeln(-1)； exit； end； then end； then for j:=0 to n do 检查有向图。若出现有向环，则无解退出 for k:=1 to numj do if sj+headj，k.vsheadj，k.no t
21、hen begin writeln(-1)； exit； end； then for i:=1 to n do 根据s数组的值构造满足条件的01串 if si=si-1 then write(0) else write(1)； writeln； end； mainbegin assign(input，inputfile)； 输入文件名串与文件变量连接 reset(input)； 输入文件读准备 assign(output，outputfile)； 输出文件名串与文件变量连接 rewrite(output)； 输出文件写准备 init； 输入数据，构造有向图 main； 计算和输出一个满足所有条件的01串 close(input)； 关闭输入文件和输出文件 close(output)；end. 程序结束
