数学建模在OI中的应用.doc

数学建模在信息学竞赛中的应用江苏省常州高级中学曹文一、概述实际问题往往是纷繁而复杂的，而其中的规律也是隐藏着的，要想直接用计算机来求解实际问题往往有一定的困难。计算机擅长的是解决数学问题。因此，我们有必要将实际问题抽象成数学模型，然后再用计算机来对数学模型进行求解。数学模型(Mathematical Model)：对于现实中的原型，为了某个特定目的，作出一些必要的简化和假设，运用适当的数学工具得到一个数学结构。也可以说，数学建模是利用数学语言（符号、式子与图象）模拟现实的模型。把现实模型抽象、简化为某种数学结构是数学模型的基本特征。它或者能解释特定现象的现实状态，或者能预测到对象的未来状况，或者能提供处理对象的最优决策或控制。与实际问题相比，数学模型有以下几个性质：1.抽象性：数学模型是实际问题的一种抽象，它去除了实际问题中与问题的求解无关的部分，简明地体现了问题的本质。这一点是下面两个性质的基础。2.高效性：数学模型中各个量之间的关系更为清晰，容易从中找到规律，从而提高求解的效率。由于这一点是由数学模型的抽象性决定的，因此数学模型的抽象化程度对数学模型效率的高低有重要的影响。3.可推广性：数学模型可以推广到具有相同性质的一类问题中。换句话说，解决了一个数学模型就解决了一类实际问题。这里的“相同性质”是指相同的本质，表面看似毫不相干的问题可能有着相同的本质。由于这一点也是由数学模型的抽象性决定的，因此数学模型的抽象化程度对数学模型的推广范围也有重要的影响。二、建立数学模型的方法和步骤1. 模型准备首先要了解问题的实际背景，明确建模目的，搜集必需的各种信息，尽量弄清对象的特征。在信息学竞赛中这一步意味着：审清题意，了解题目的来龙去脉，弄清哪些量是已知的（输入），需要求什么（输出），数据规模如何等等，这是解决问题的前提。 2.建立模型根据所作的假设分析对象的因果关系，利用对象的内在规律和适当的数学工具，构造各个量间的等式关系或其它数学结构，使之能够简洁高效地表达出题目给出的现实模型。不过我们应当牢记，建立数学模型是为了让更多的人明了并能加以应用，因此工具愈简单愈有价值。3.模型求解建模之后就是要解决模型。这步顺利与否很大部分上取决于所建模型的可解性如何。可以采用解方程、画图形、证明定理、逻辑运算、数值运算等各种传统的和近代的数学方法，特别是计算机技术。一道实际问题的解决往往需要纷繁的计算，因此编程能力和熟悉数学知识便举足轻重。4.编程实现其中，、两步是关键。模型建立与解决得好与坏对能否成功解决该题起着决定性的作用。三、具体应用1.对于同一个现实问题，可能可以建立不同的数学模型这种现象十分普遍，也就是平时所说的一题多解。既然如此，这里有必要讨论一下数学模型的选择问题，其实也就是评判一个模型好坏标准的问题。一个好的数学模型不仅要能够准确地反映出现实模型（可靠性），所建立的模型还必须能够被有效地解决（可解性）。这里“有效”指的是解决它的算法所需的空间与时间都在可以承受的范围之内。通常在解一些要求最优解或要求准确计数的一类具有唯一正确解的试题时，我们一般在保证可靠性的前提下，尽量提高模型的可解性。若几个模型都具有可靠性，则当然可解性越强的模型越好。例如第六届分区联赛高中组第四题【方格取数】就可以建立多种数学模型，各个模型的在可靠性与可解性方面各有千秋，请看下面的分析。 【问题描述】 设有NN的方格图（N8），我们将其中的某些方格中填入正整数，而其他的方格中则放入数字0。如下图所示（见样例）： 向右A1234567810000000020013006003000070004000140000 向 下502100040060015000007014000000800000000B 某人从图的左上角的A点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。此人从A点到B点共走两次，试找出2条这样的路径，使得取得的数之和为最大。【输入】 输入的第一行为一个整数N（表示NN的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。【输出】 只需输出一个整数，表示2条路径上取得的最大的和。【样例】 8 2 3 13 2 6 6 3 5 7 4 4 14 5 2 21 5 6 4 6 3 15 7 2 14 0 0 0 结果 67【问题分析】 本题是从1997年国际信息学奥林匹克的障碍物探测器一题简化而来，如果人只能从A点到B点走一次，则可以用动态规划算法求出从A点到B点的最优路径。具体的算法描述如下：从A点开始，向右和向下递推，依次求出从A点出发到达当前位置（i，j）所能取得的最大的数之和，存放在sum数组中，原始数据经过转换后用二维数组data存储，为方便处理，对数组sum和data加进零行与零列，并置它们的零行与零列元素为0。易知sumi，j= datai，j 当i=0或j=0 max（sumi-1，j，sumi，j-1）+ datai，j 当i0,且j0求出sum数组以后，通过倒推即可求得最优路径，具体算法如下： 置sum数组零行与零列元素为0 for i:=1 to n do for j:=1 to n do if sumi-1,jsumi,j-1 then sumi,j:=sumi-1,j+datai,j else sumi,j:=sumi,j-1+datai,j; i:=n; j:=n; while (i1) or (j1) do if (i1) and (sumi,j=sumi-1,j+datai,j) then begin datai,j:=-1; i:=i-1 end else begin datai,j:=-1; j:=j-1 end; data1,1:=-1;凡是被标上-1的格子即构成了从A点到B点的一条最优路径。 那么是否可以按最优路径连续走两次而取得最大数和呢?这是一种很自然的想法,并且对样例而言也是正确的,具体算法如下：求出数组sum，s1:=sumn,n，求出最优路径，将最优路径上的格子中的值置为0，将数组sum的所有元素置为0，第二次求出数组sum，输出s1+sumn,n。 虽然这一算法保证了连续的两次走法都是最优的，但却不能保证总体最优，相应的反例也不难给出，请看下图： 图二按最优路径走一次后，余下的两个数2和3就不可能同时取倒了，而按图三中的非最优路径走一次后却能取得全部的数，这是因为两次走法之间的协作是十分重要的，而图2中的走法并不能考虑全局，因此这一算法只能算是“贪心算法”。虽然在一些情况下，贪心算法也能够产生最优解，但总的来说“贪心算法”是一种有明显缺陷的算法。既然简单的动态规划行不通，那么看看穷举行不行呢？因为问题的规模比较小，启发我们从穷举的角度出发去思考，首先让我们来看看N=8时，从左上角A到达右下角B的走法共有多少种呢？显然从A点到B点共需走14步，其中向右走7步，向下走7步，共有=3432种不同的路径，走两次的路径组合总数为=34323431/2=5887596，从时间上看是完全可以承受的，但是如果简单穷举而不加优化的话，对极限数据还是会超时的，优化的最基本的方法是以空间换时间，具体到本题就是预先将每一条路径以及路径上的数字之和（称之为路径的权weight）求出并记录下来，然后用双重循环穷举任意两条不同路径之组合即可。考虑到记录所有的路径需要大量的存储空间，我们可以将所有的格子逐行进行编号，这样原来用二维坐标表示的格子就变成用一个1到n2之间的自然数来表示，格子（i,j）对应的编号为（i-1）*n+j。一条路径及其权使用以下的数据结构表示：const maxn=8;type arraytype=array1.2*maxn-2 of byte; recordtype=record path:arraytype; weight:longint end;数组path依次记录一条路径上除左上和右下的全部格子的编号。将所有的路径以及路径的权求出并记录下来的算法可用一个递归的过程实现，其中i,j表示当前位置的行与列，step表示步数，sum记录当前路径上到当前位置为止的数之和，当前路径记录在数组position中（不记录起始格），主程序通过调用try(1,1,0,data1,1)求得所有路径。procedure try(i,j,step,sum:longint);begin if (i=n) and (j=n) then begin total:=total+1; atotal.path:=position; atotal.weight:=sum; end else begin if i+1=n then begin positionstep:=i*n+j; try(i+1,j,step+1,sum+datai+1,j) end; if j+1max then max:=current end; writeln(max-data1,1-datan,n);应该看到穷举的效率是十分低下的，如果问题的规模再大一些，穷举法就会超时，考虑到走一次可以使用动态规划，则只需穷举走第一次的路径，而走第二次可以用动态规划，这样可大大提高程序的效率，其算法复杂度为，实现时只需将前面二种算法结合起来即可，但这样做仍然不能使人满意，因为只要穷举了从A点到B点所有路径，算法的效率就不可能很高，要想对付尽可能大的n，还是要依靠动态规划算法。实际上本问题完全可以用动态规划解决，只是递推起来更为复杂些而已，前面在考虑只走一次的情况，只需考虑一个人到达某个格子（i，j）的情况，得出sumi，j=max（sumi-1，j，sumi，j-1）+datai，j，现在考虑两个人同时从A出发，则需考虑两个人到达任意两个格子(i1，j1)与(i2，j2)的情况，显然要到达这两个格子，其前一状态必为(i1-1，j1)，(i2-1，j2)；(i1-1，j1)，(i2，j2-1)；(i1，j1-1)，(i2-1，j2)；(i1，j1-1)，(i2，j2-1) 四种情况之一，类似地，可以推导出：设p=max(sumi1-1,j1,i2-1,j2,sumi1-1,j1,i2,j2-1,sumi1,j1-1,i2-1,j2,sumi1,j1-1,i2,j2-1)，则sumi1,j1,i2,j2= 0 当i1=0或j1=0或i2=0或j2=0 p + datai1,j1 当i1,j1,i2,j2均不为零，且i1=i2，j1=j2 p + datai1,j1+datai2,j2 当i1,j1,i2,j2均不为零,且i1i2或j1j2 具体算法如下： 置sum数组所有元素全为0; for i1:=1 to n do for j1:=1 to n do for i2:=1 to n do for j2:=1 to n do begin if sumi1-1,j1,i2-1,j2sumi1,j1,i2,j2 then sumi1,j1,i2,j2:=sumi1-1,j1,i2-1,j2; if sumi1-1,j1,i2,j2-1sumi1,j1,i2,j2 then sumi1,j1,i2,j2:=sumi1-1,j1,i2,j2-1; if sumi1,j1-1,i2-1,j2sumi1,j1,i2,j2 then sumi1,j1,i2,j2:=sumi1,j1-1,i2-1,j2; if sumi1,j1-1,i2,j2-1sumi1,j1,i2,j2 then sumi1,j1,i2,j2:=sumi1,j1-1,i2,j2-1; sumi1,j1,i2,j2:=sumi1,j1,i2,j2+datai1,j1; if (i1i2) or (j1j2) then sumi1,j1,i2,j2:=sumi1,j1,i2,j2+datai2,j2 end;writeln(sumn,n,n,n)【程序清单】const maxn=10;type arraytype=array 0.maxn,0.maxn of longint;var i,j,k,n,i1,i2,j1,j2:longint; data:arraytype; sum:array 0.maxn,0.maxn,0.maxn,0.maxn of longint;function max(x,y:longint):longint;begin if xy then max:=x else max:=y;end;BEGIN for i:=1 to maxn do for j:=1 to maxn do datai,j:=0; readln(n); repeat readln(i,j,k); datai,j:=k until (i=0) and (j=0) and (k=0); fillchar(sum,sizeof(sum),0); for i1:=1 to n do for j1:=1 to n do for i2:=1 to n do for j2:=1 to n do begin if sumi1-1,j1,i2-1,j2sumi1,j1,i2,j2 then sumi1,j1,i2,j2:=sumi1-1,j1,i2-1,j2; if sumi1-1,j1,i2,j2-1sumi1,j1,i2,j2 then sumi1,j1,i2,j2:=sumi1-1,j1,i2,j2-1; if sumi1,j1-1,i2-1,j2sumi1,j1,i2,j2 then sumi1,j1,i2,j2:=sumi1,j1-1,i2-1,j2; if sumi1,j1-1,i2,j2-1sumi1,j1,i2,j2 then sumi1,j1,i2,j2:=sumi1,j1-1,i2,j2-1; sumi1,j1,i2,j2:=sumi1,j1,i2,j2+datai1,j1; if (i1i2) or (j1j2) then sumi1,j1,i2,j2:=sumi1,j1,i2,j2+datai2,j2 end; writeln(Maxscore=,sumn,n,n,n)END.【运行示例】（下划线表示输入）31 1 101 3 52 2 62 3 43 1 83 2 20 0 0Maxscore=3071 3 21 4 32 3 33 3 35 5 46 5 47 3 27 5 40 0 0Maxscore=2581 1 131 3 71 8 142 2 12 4 24 3 55 5 46 2 67 8 160 0 0Maxscore=6081 1 11 8 12 2 22 7 23 4 33 5 34 4 34 5 37 2 27 7 28 1 18 8 10 0 0Maxscore=18综上所述，三种不同模型之间在可靠性和可解性两项指标上的对比可见下表：能性型模贪心穷举动态规划可靠性不可靠可靠可靠可解性好差好2.一个模型可能同时适用于多个现实问题。这也是我们要研究数学模型的主要原因之一。我们解决一个数学模型就相当于解决了一类问题。比如说，最短路径问题，可谓在现实生活中无处不在，这些数学模型的解决使得许多实际问题迎刃而解。然而，数学模型的解决只是解决一个现实问题的一半，另一半就是如何将现实问题转化为一个已经解决的数学模型，即如何建模。建模在现实与抽象之间起着桥梁的作用。尤其在竞赛中，后者有时显得更为重要。例如福建省2000年组队选拔赛试题【球迷购票问题】。【问题描述】盛况空前的足球赛即将举行。球赛门票售票处排起了球迷购票长龙。按售票处规定，每位购票者限购一张门票，且每张票售价为50元。在排成长龙的球迷中有m个人手持面值50元的钱币，另有n个人手持面值100元的钱币。假设售票处在开始售票时没有零钱。试问这m+n个球迷有多少种排队方式可使售票处不致出现找不出钱的尴尬局面。例如当m=3，n=2时，用A表示手持面值50元钱币的球迷，用B表示手持面值100元钱币的球迷，则最多可得到以下5组不同排队方式，使售票处不致出现找不出钱的尴尬局面。售票处AAABB售票处AABAB售票处ABAAB售票处AABBA售票处ABABA编程任务：对于给定的m和n的值( 0 m，n 5000)，编程计算出m+n个球迷有多少种排队方式可使售票处不致出现找不出钱的尴尬局面。数据输入：由键盘输入m和n的值。结果输出: 程序运行结束时，将计算出的排队方式数写入文件名为FOI2.* 的文本文件中，其中“*”与相应输入文件的扩展名一致。每个计算结果占2行，第1行为输出数据的十进制位数，第2行是相应的输出数据。输入示例输出文件示例m=3，n=2FOI2.00115【问题分析】假设将手持50元人民币的球迷记为S，持100元人民币的球迷则记为X，则m个手持50元人民币与n个手持100元人民币的球迷队伍就可表示为一个具有m个S和n个X的字符串，显然这样的字符串共有个，其中不满足问题要求的串一定存在一个最靠左的位置P，使得从第一个字符到第P个字符为止的子串中X的个数比S的个数大1，如SXSXX就是一个不满足条件的串，其中p=5。我们将从头到P为止的串中的字符S与X互换，则得到一个具有m+1个S和n-1个X的串，可以证明这种转换是一一对应的，即任意一个具有m+1个S，n-1个X的串都可以按照逆规则转换成一个不满足题目条件的串，转换规则为在任意一个m+1个S和n-1个X的串中找到最靠左边的位置P，使得从头到P的子串中S的个数比X的个数大1，将到P为止的子串中的字符S与X互换，则得到一个m个S和n个X的串，且此串肯定不满足题目要求，而具有m+1个S，n-1个X的串共有个，所以共有种排队方式可使售票处不致出现找不出钱的尴尬局面。再如求n个元素通过进栈、出栈总共能够得到多少种不同的序列。只要将进栈记为S，出栈记为X，则n个元素进栈、出栈的序列就对应一个具有m个S和n个X的字符串，由于进栈元素个数任何时候都要大于等于出栈元素个数，所以从第一个字符开始到任意一个字符为止的一段中S的个数必须大于等于X的个数，这样问题就变成上例的m=n时的情况，要求序列总数为。类似的问题还有结和律问题：有n个数a1,a2,a3, ,an依据加法结合律，不改变其顺序，通过插入括号改变其求和次序，问有几种不同的求和次序？如n=3，共有两种不同的求和次序，分别为a1+a2+a3与a1+(a2+a3)。实际上计算机中求表达式的值采用的是堆栈的方法，具体说来就是设置两个栈：操作数栈（ovs）和运算符栈（ops），用来分别存放表达式中的操作数和运算符。开始时操作数栈为空，运算符栈中放入一个特殊的标志运算符号#号，并在表达式的末尾加上一个#号，并规定#号的优先级最低，然后从左向右扫描表达式，凡遇操作数便一律进栈；若遇运算符，则判断其优先级是否大于运算符栈栈顶元素的优先级。若小，则栈顶运算符退栈，并从操作数栈中弹出两个操作数进行运算，运算结果进操作数栈，重复刚才的比较，直到栈顶运算符的优先级大于等于当前运算符的优先级，此时，若当前运算符的优先级大于栈顶运算符的优先级，则当前运算符进栈，继续扫描；若当前运算符的优先级等于栈顶运算符的优先级，则弹出栈顶运算符，继续扫描。扫描完该表达式后运算符栈为空，操作数栈中只有一个元素，该元素就是所要求的表达式值。借鉴上述表达式处理算法，可以推导得知只要改变表达式a1+a2+an中的加号进栈出栈的次序，就可以得到不同的求和次序，加号的出栈次序即为求和次序，加式中共有n-1个加号，所以要求的不同的求和次序共有种。3.如何建立数学模型要能够建立数学模型，首先必须熟悉一些经典的数学模型及其算法。这是建模的基础，没有这个基础则根本谈不上建立什么数学模型。竞赛中许多问题最终都可以转化为经典的数学模型，因此必须掌握这些常见的模型。其次建立数学模型需要选手有把实际问题相互联系，类比的能力。上文已经指出许多实际模型都有着相同或相似的数学模型。既然这样，它们之间必然存在着一些相同或相似。相互联系、类比是发掘这些信息的有效手段。例如CEOI1994的【Black and White】。【题目描述】寻找一个由n个整数组成的数列，其中任意连续p个整数之和为正，任意连续q个整数之和为负。若不存在这样的整数数列，则输出NO，否则输出其中一个数列。 本题看似数学问题，而本质却是图论问题，本题数学模型建立的关键在于连续数之和的表示。如果我们把紧跟在第i个整数之后的k个整数写作ai+1+ai+2+ai+k的话，数学模型就很难建立了，因为这里涉及k个整数之和。但是，我们可以利用连续这一特点，将其表示为Si+k-Si,这样的表示就十分简单，使得数学模型的建立相对容易些。我们记Si为数列中前i个整数之和，S00。根据题意，可以列出如下两组不等式：Si Si-p (pin)Si Si-q (qin)我们再建一个有向图，共有n1个顶点，分别是S0至Sn，若SiSj，那么就从Si往Sj引一条边。如图（n=6,p=5,q=3）。这样对于S0,S1,Sn来说，他们必须是拓扑有序的（S00），反过来，任何一组S0Sn都惟一地对应一个整数数列。现在，我们已经把这道题目转换为一个图论的拓扑排序的问题，而这个问题又是我们非常熟悉的。初看上去，本题似乎与图论没有任何关系。题目中并没有出现图论中常见的“城市”，“终端”等顶点，也没有“铁路”，“线路”等边，更没有“长度”，“传输时间”等权，但确确实实用图论模型漂亮地解决了，不由地让人发出感叹真没想到呀！其实，想到与没想到虽就一念之差，却不是偶然的：这里面既有经验的因素，也与你所掌握数学模型的多少有关，更重要的则是你的创造力。在上题中把Si作为顶点，大小关系作为边，以及权的确定都不可以不说是一种创造。而正是它们在上题的解决中起了关键性的作用。四、数学模型的评价很多时候我们面临的问题原型就好比一个“黑匣子”，我们在里面进行盲人Page: 11盲人摸象似的探索。思考问题的角度有多种多样，所建立的数学模型也Page: 11 是多种多样的。如果一个问题原型能对应多个数学模型，这时，我们就面临抉择。当然，我们期望所选择的模型是最好的。那么这就涉及到对模型的评价问题。我们在竞赛中建立模型后要对应到算法，那么对一个数学模型评价自然要着重于其对应算法的好坏。一般地，评价一个数学模型有以下几个原则：1.时间复杂度一个好的算法一般效率比较高。在竞赛中，试题常常会做一些算法运行时间上的限制。这就要求我们所建立的数学模型对应算法的效率一定要符合要求。这也是最重要的一个原则。2.空间复杂度出于计算机自身的限制，程序在运行时一般只被提供有限的内存空间。这也就要求我们建立模型时顾及到这一点。但对于模型对应的算法来说，并不是要求空间越低越好，只要不超过内存限制就可以了。3.编程复杂度相对而言，“编程复杂度”的要求要略低一些。但是在竞赛中，如果建立的算法实现起来十分繁琐，自然不利于比赛。所以，在建立模型时（特别是在竞赛中）这点也要纳入考虑之中。下面的H数问题就是一个对时空复杂度的一个很好说明。【问题描述】 所谓H数，是指该数除1以外最多只有2,3,5,7四种因子，如630即为H数，而22不是。要求对键盘输入的自然数N，求出第N个H数。如N=30，应输出49。规定要求的H数不超出长整型数的范围。从H数的定义可以看出，如果一个数是H数，那么将它的2,3,5,7四种因子去掉以后必然是剩下1。下面就根据H数的这一特性用穷举法来解决这个问题。首先用自然语言描述该算法:第一步：从键盘输入一个自然数给N;第二步：将h置为1，order置为1 表示第一个H数为1第三步：如果order=n 则转第七步；否则转第四步第四步：h增加1，并将k的值置为h第五步：将k中的2,3,5,7四种因子去掉第六步：如果k=1 则order 增加1第七步：输出h以上描述中第五步的描述不够明确，下面对去掉k中因子i作更进一步的说明：第一步：如果k是i的倍数，则转第二步，否则算法结束；第二步：将k置为k/I；第三步：转第一步；有了上述用自然语言描述的算法后，就很容易编写出求解H数问题的程序，借助计算机来计算结果了。程序中将2,3,5,7存放在数组mark中。【程序清单】const mark:array 1.4 of integer=(2,3,5,7);var i,h,k,n,order:longint;begin write(Input n:); readln(n); h:=1; order:=1; while ordern do begin h:=h+1; k:=h; for i:=1 to 4 do while k mod marki=0 do k:=k div marki; if k=1 then order:=order+1 end; writeln(The no.,n, H number is ,h)end.运行程序下划线表示输入Input n:450The no.450 H number is 23814Input n:1998The no.1998 H number is 7056000Input n:4095The no.4095 H number is 260112384Input n:5910The no.5910 H number is 2143750000上述H数问题的空间复杂度显然为O(1)，而时间复杂度很难估算，下面我们通过对模型的改进来对它作进一步的分析。在H数问题中，由于所要求的H数在长整型范围，最多可达2的31次方数量级，显然，用穷举与逐一判断的模型效率太低，对序号大的H数很难在规定时间内运行出正确结果，有没有更好的办法呢？分析H数问题，发现H数因子只有4种，可以考虑从因子出发由小到大地生成H数。假如用一个线性表来存放H数，称这个表为H数表，则H数表中每个元素的2倍、 3倍、5倍及7倍均是H数，不妨将由H数表中每个元素的2倍组成的线性表称为H数表的2倍表，设想再用4个线性表分别存放H数表的2倍表、3倍表、5倍表和7倍表，然后利用这5个表来生成H数表，生成方法如下：开始时H数表中存有第一个H数1，其它四个表为空表.将当前的H数的2倍、 3倍、5倍及7倍依次添加到四个表中去，这时四个表中各有一个元素，接下去的所有的H数将由这四个表来生成，每次将四个表的第一个元素中的最小者取出来，这个数就是下一个要求的H数，将它添加到H数表中去，并将这个H数的2倍、 3倍、5倍及7倍依次添加到四个表中去，然后从四个表中删除这个元素，如果表中有这个元素的话.重复这一过程，直到所要求的H数找到为止。程序中为了求出第n个H数，必须将它前面的所有的H数都求出来并加以保存，所以这一算法的空间复杂度为O(n)；在计算每一个H数的过程中，对4个H数的倍数表要进行删除操作，对线性表的删除操作的时间复杂度为O(n)，所以这一算法的总的时间复杂度为O(n)*O(n)，即O(n*n)。【程序清单】const maxn=3000;var i,j,n,min,t2,t3,t5,t7:longint; h,h2,h3,h5,h7:array1.maxn of longint;begin write(Input n(n=,maxn,):); readln(n); h1:=1; h21:=2; h31:=3; h51:=5; h71:=7; t2:=1; t3:=1; t5:=1; t7:=1; for i:=2 to n do begin min:=h21; if h31min then min:=h31; if h51min then min:=h51; if h71min then min:=h71; hi:=min; t2:=t2+1; h2t2:=hi*2; t3:=t3+1; h3t3:=hi*3; t5:=t5+1; h5t5:=hi*5; t7:=t7+1; h7t7:=hi*7; if h21=min then begin for j:=1 to t2-1 do h2j:=h2j+1; t2:=t2-1 end; if h31=min then begin for j:=1 to t3-1 do h3j:=h3j+1; t3:=t3-1 end; if h51=min then begin for j:=1 to t5-1 do h5j:=h5j+1; t5:=t5-1 end; if h71=min then begin for j:=1 to t7-1 do h7j:=h7j+1; t7:=t7-1 end end; writeln(The no.,n, H number is ,hn)end.通过运行程序，你会很遗憾地发现， 虽然程序运行的速度大大优于第一种算法，但当n较大时(如n=5000，用TP实现将空间不足)，程序运行将会造成空间不够。这是为什么呢？ 这是因为PASCAL语言允许程序使用的存储空间为64KB，而一个长整型数是用32位二进制数来表示的，即要用4个字节(Byte)来存放。而64KB=64*1024B=65536B，只能存放16000多个长整型数，而上述算法中的空间复杂度为O(n)，具体的值大约为n的5倍，因此当n太大(如n=5000)时，n*5的值就会远远超出16000，造成运行空间不够。如何解决这个问题呢?仔细分析上述算法，可以发现H数的四个倍数表中的所有元素与H数表中的所有元素相比，只相差一个倍数而已，可不可以不用这四个倍数表，而借用H数表来表示它们呢? 答案是肯定的，为了说明问题，首先引进线性表的指针的概念，在用数组描述线性表时，线性表中的元素的位置完全取决于数组下标的值，我们不妨将这个下标值即一个整数看作指向线性表中某一元素的指针。需要说明的是，这里的所谓的指针只是为了便于说明问题而定义的，与PASCAL语言中所指的指针是完全不同的。 这样就可以用四个指针分别指向H数表中的四个数，这四个数的2倍、3倍、5倍及7倍的值分别是四个倍数表中的首元素，以此表示H数的四个倍数表。一开始，它们均指向1，即当前的四个倍数表的首元素分别为2*1、3*1、5*1、7*1，取四数中最小者作为第二个H数2，记入H数表中，并将代表H数的2倍表的指针下移一，指向2，再比较2*2,3*1,5*1,7*1,取3，将代表H数的3倍表的指针下移一位即指向表中下一个H数2，表示H数的3倍表中的首元素变成了*=6，以此类推。直到插入表中的H数的总数满足要求为止。这个算法在改进空间复杂度的同时，也将时间复杂度降到了O(n)，因为用指针模拟H数的倍数表后，线性表的删除操作变成了指针的移动操作，而指针的移动操作只要用一个赋值语句即可。程序中4个指针由数组p实现，p1表示指针指向的H数表中元素的2倍为H数的2倍表的首元素，数组mark记录4个因子2、3、5、7。 H数表由数组h来表示。 四数中若有多个相等者，取一个即可，并将相应的多个指针均下移一格。【程序清单】const maxn=6000; mark:array 1.4 of integer=(2,3,5,7);var i,j,n,min:longint; p:array1.4 of longint; h:array1.maxn of longint;begin write(Input