【摘要】
本文提出了在组合算法设计和组合算法选择方面所应当遵循的三个原则，即通用性、可计算性和较少的信息冗余量，并初步分析了它们之间的相互关系。这三个原则是整个组合算法设计的主导思想，也是数学建模和算法优化的方向。通过对三个问题的分析，提示了组合算法的设计方法，改进方向和优化技术，是对一系列组合数学原理的实际应用，也是对组合算法设计的初步研究。
【Abstract】
The disquisition brings forward three principle in combination arithmetic designing and combination arithmetic choice. There is currency, countability and less information redundancy. And the disquisition analyses the relation of them. The three principle is the dominant ideology in combination arithmetic designing. Also it is the aspect of making mathematics modeling and optimizing arithmetic. Then the disquisition analyses three questions, prompts the devisal’s method, betterment’s way and the technique optimizing arithmetic. That is actual appliance to a catena of combination mathematics elements and it is also initial research in combination arithmetic designing.
【正文】
一、引 论
组合数学是一个古老的数学分支，也是当代数学中非常重要的数学分支。它发源于有趣的数学游戏，许多古典的组合数学问题，无论在理论数学或应用数学上都有很重要的研究价值。
今天，一方面，极为成熟的组合计数理论为物理学、化学、生物学的发展奠定了坚实的基础，另一方面，由于计算机软硬件的限制，组合计数理论的计算机实践又必然涉及到基于多项式时间内的算法优化问题。本文正是基于以上情况，对一系列组合问题的算法设计做了一些初步探索。
二、组合算法的评价依据
任何事物都有好坏之分，算法也不例外。众所周知，时间复杂度与空间复杂度是算法评价的主要依据。那么，除了这两点外，组合算法的设计还应遵循怎样的原则呢？
1．通用性
通用性即可移植性。一个算法，是只适合于一个特殊问题，还是可以适用于一类问题，这是组合算法评价的一个主要依据，有些组合数学问题，许多信息学竞赛或数学建模竞赛选手一看到题目后往往使用模拟法或构造产生式系统[1]，然后用深度优先搜索（DFS），或广度优先搜索（BFS）求解，用这些方法设计的程序往往受到时间或空间的限制，而且由于在综合数据库中信息存储的数据结构不同，其算法实现时的规模[2]也不同，这必然影响到算法的通用性问题。解决问题的办法是对原问题进行数学抽象，取其精华，去其糟粕。只有对原问题的数学模型仔细分析，抓住本质，才能建立高效的组合算法，只有这种经过数学抽象的算法，才能具有较好的通用性，能够应付较大的规模。
另外，在大规模组合算法的设计过程中，强调通用性的好处是显而易见的，它便于算法的优化和升级。在实际应用中的某些条件改变时，可以重写较少的代码。从软件工程学的角度来说，通用性是必需的。
2．可计算性
这里指的可计算性，是指能够在多项式时间内得出结果。一般来说，对于递归函数来说，由于计算机系统中的空间一定，因此对问题的规模有较严格的限制（例如在Turbo Pascal 7.0系统中，栈的最大空间只有65520字节）因此说，对于大多数的递归函数具有较差的可计算性。通过组合方法，求递归函数的非递归形式是解决这类问题有主要方法，但并不是所有的递归函数都可转化为非递归形式，双递归函数（如Ackermann函数[3]）便不能转化为非递归形式，这类函数具有较小的可计算性。
当然，对于某些递归函数，通过寻找函数本身的组合意义进而将其转化为非递归函数也是一种方法。这种方法的应用读者将在后文中见到。
3、信息冗余量
在组合数学的建模过程中，大量的信息冗余是制约组合算法效率的一个重要因素，例如在递归程序运行的过程中，实际上产生了一棵解答树[4]，同一棵子树的结点间的信息不相互关联，这样便产生了大量的信息冗余，解决的方法之一便是引入记忆机制，将已得出的信息记录下来。这种机制实际上起到了剪枝的作用，但它严格受到空间的限制，实际上是时空矛盾在算法设计中的体现。这便是我们在组合算法设计中倡导函数非递归化的原因。它可以达到零信息冗余。
当然，组合算法的通用性、可计算性与信息冗余程度在一定程度上是对立的。例如双递归函数作为一种数学模型，能够反映一类问题，具有通用性，但却具有较差的可计算性和较大的信息冗余量，而有些问题虽具有较好的可计算性和较低的信息冗余量，却具有较差的通用性。总之，算法的时间复杂度，空间复杂度，通用性，可计算性和信息冗余量应是衡量组合算法的几个主要标准。
三、组合算法的选择实例
组合算法的评价依据同时也是建立数学模型和优化算法的指导思想。那么应该如何设计高效，通用的组合算法呢？下面我们通过几个实际的组合问题来初步研究。
例1．核反应堆中有α和β两种粒子，每秒钟内一个α粒子可以反应产生3个β粒子，而一个β粒子可以反应产生1个α粒子和2个β粒子。若在t=0时刻的反应堆中只有一个α粒子，求在t时刻的反应堆中α粒子和β粒子数。
这是一个物理学中的简单问题。我们通过对两种算法的比较来说明组合算法的通用性。
模型I：本题中共涉及两个变量，设在i时刻α粒子数为ni，β粒子数为mi，则有：n0=1,m0=0,ni=mi—1，mi=3ni—1+2mi
—1
本题便转化为求数列N和M的第t项，我们可用递推的方法求得nt和mt，此模型的空间需求较小，时间复杂度为O（n），但随着n的增大，所需时间越来越大，即：
T
n
此模型的算法如下：
算法1-1
Prog Arithmtic1_1;
Read(t);
n[0]:=1; //初始化操作
m[0]:=0;
for i:=1 to t do //进行t次递推
begin
n[i]:=m[i-1];
m[i]:=3*n[i-1]+2*m[i-1];
end;
write(n[t]); //输出结果
write(m[t]);
End. Arithmtic1_1
模型II：设在t时刻的α粒子数为f（t），β粒子数为g(t)，依题可知：
g(t)=3f(t -1)+2g(t -1) （1）
f(t)=g(t -1) （2）
g(0)=0,f(0)=1
下面求解这个递归函数的非递归形式
由（2）得f(t -1)=g(t-2) （3）
将（3）代入（1）得
g(t)=3g(t -2)+2g(t-1)
（t≥2） （4）
g(0)=0,g(1)=3
（4）式的特征根方程为：
x2—2x—3=0
其特征根为x1=3,x2= -1
所以该式的递推关系的通解为
g(t)=C1·3t+C2·( -1)t
代入初值g(0)=0,g(1)=3得
C1+C2=0
3C1
—C2=3
解此方程组得
所以该递推关系的解为
g(t)=
∴
即
算法1—2
Prog Arithmetic1_2;
read(t);
n:=trunc(exp(t*ln(3)));
m:=trunc(exp((t+1)*ln(3)));
if odd(t) then begin //判断( -1)t
n:=n-3;
m:=m+3;
end
else begin
n:=n+3;
m:=m-3;
end;
n:=trunc(n/4); // 4|n
m:=trunc(m/4); // 4|m
Write(n);
Write(m);
End. Arithmetic1_2
在模型II中，我们运用组合数学的方法建立了递归函数并转化为非递归函数。它的优点是算法的复杂性与问题的规模无关。针对某一具体数据，问题的规模对时间的影响微乎其微。
通过以上两个模型我们可以看出，模型II抓住了问题的本质，尤其成功地运用了组合数学中关于常系数线性齐次递推关系求解的有关知识，因而使算法本身既具有通用性和可计算性，同时达到了零信息冗余。
例2．在平面直角坐标系中，有n个圆心坐标为整点的单位圆，求它们所覆盖区域的总面积。
这是一道计算几何学的问题，关于图形并的问题，较为常用的方法是离散化，但是如果借助于组合数学的有关理论，是否可以设计出更好的算法呢？我们先来看几个简单的例子。
（1）两个圆的交（交集不为ф）
设圆i的圆心坐标为（xi,yi），我们定义一个异型函数（dissmilaruty function）如下：
在讨论两个圆的交的问题时，设两圆为圆1与圆2，它们的交有两种情况
①
设阴影部分面积为S，则
=
=
②
设阴影部分面积为S，则
S=
=
=
由于两个圆的非空交集问题是圆最简单的交问题。所以我们规定
的交为α型交， 的交为β型交，这个规定将在下文的讨论中用到。
2、三个圆的交（交集不为ф）
：
经过分析易证，若三个圆的交集不为空，则三个圆中任意两圆的交集一定不为空，反之亦成立。且在任意两圆相交所组成的三个交中，一定有2个α型交，1个β型交。如图所示，阴影部分面积为S，则有：
S=
=
3、四个圆的交（交集不为ф）
经分析可证，若四个圆的交集不为ф。则四个圆的圆心一定围成一个边长为1的正方形，这四个圆心按照顺时针（或逆时针方向）一定形成4个α型交，四个圆的交集如图中阴影部分所示，设其阴影部分面积为S，则：
S=
=
=
可以证明5个或5个以上互不重合的单位圆的交集必为φ。
分析至此，我们可以知道，任意多个单位圆的交集都可以通过2、3、4个圆的交而获得，那么任意多个单位圆的并集呢？由交集到并集，这使我们想起了容斥原理，于是得出：
模型有了，但是平面上的位置关系如何来表示呢？我们用带权有向图来有表示单位圆间的关系，边上的权函数定义如下：
0 Ai∩Aj=φ
C（i,j）= 1 Ai与Aj为α型交
2 Ai与Aj的β型交
于是所有单位圆之间的信息便可由一个三角矩阵表示出来。两个圆、三个圆、四个圆相交的情况可由下图表示：
i i i
1 2 2
j j k 1
(1) (2) (3) (4)
（1）图表示两圆为α型交的圆；（2）图表示两圆为β型为圆；（3）图表示3个圆相交的图，在3边中有 边权为2，其余两边权为1；（4）图为四个圆相交时的图。
题目标分析至此，我们便可轻松地设计出算法。
算法2
Func dissmilaruty_function(k1,k2:integer):integer;
Begin
l:=abs(x[k1]-x[k2])+abs(y[k1]-y[k2]);
//计算异型函数的值
if l>2 then return(0)
else return(l);
End; dissmilaruty_function
Proc Arithetic2;
Begin
count1:=0; //count1为а型交的个数
count2:=0; //count2为β型交的个数
area:=n*pi; //当所有圆都不相交时的面积值
for i:=1 to n-1 do
for j:=i+1 to n do
begin
list[i,j]:=dissmilaruty_function(i,j);
if list[i,j]=1 then count1:=count1+1; //两圆为α型交
else if list[i,j]=2 then count2:=count2+1;
//两圆为β型交
end;//判断两个圆的相交情况
area:=area-count1*s1-count2*s2;
count1:=0;
for i:=1 to n-2 do
for j:=i+1 to n-1 do
for k:=j+1 to n do
begin
check:=true;
p:=list[i,j]+list[j,k]+list[i,k];
if (list[i,j]=0) or (list[j,k]=0) or (list[i,k]=0)
then check:=false;
if (p=4) and check then //三边的权值都不为0且权值之和为4
begin
count1:=count1+1; //三个圆的交不为空的个数
if list[i,j]=2 then info[i,k]:=2
else if list[j,k]=2 then info[j,k]:=2
else if list[i,k]=2 then info[i,k]:=2;
end;//info供判断四个圆的交的情况时使用
end;//判断三个圆的交的情况
area:=area+s3*count1;
count1:=0;
for i:=1 to n-2 do
for j:=i+1 to n-1 do
for k:=j+1 to n do
if (j<>k) and (info[i,j]=2) and (list[j,k]=1) and (list[i,k]=1) then count1:=count1+1; //四个圆的交的个数
area:=area-s4*count1;
End; Arithetic2
这种算法建立在对问题进行深入分析，数学抽象的基础之上的，因而无论在时间上还是在空间上都是较优的。更为重要的是，这种算法比离散化算法更精确，更具一般性，能够解决诸如图形并等一系列问题。且算法的实质是一种计数问题，具有较强的可计算性。
例3．一场激烈的足球赛开始前，售票工作正在紧张的进行中，每张球票为50元。现有2n个人排队等待购票，其中有n 个人手持50元的钞票，另外n个人手持100元的钞票，假设开始售票时售票处没有零钱。问这2n个人有多少种排队方式，使售票处不至出现找不开钱的局面？
这是一道典型的组合计数问题。从表面上看很难找出规律，下面我们基于本题建立几个模型，最终揭示问题的本质。
I．搜索模型
我们用深度优先搜索（DFS）算法来直观地模拟所有情况。算法中指定一变量k记录售票处有50元钞票的张数，初始时令k=0，若某人手持100元钞票且k=0时则回溯，否则继续递归。若第2n个人购完票即递归进行到第2n层时计数器累加1。递归结束后，计数器中的值便为排队总数。
算法3-1
Proc DFS(i:integer); //I为递归层数
Begin
for j:=0 to 1 do //j=0表示某人手持50元的钞票 ，j=1表示某人手持100元钞票 begin
if (j=0) then begin
k:=k+1; //k表示计数器
m:=m+1; //m表示有多少人手持50元钞票购票
if (m=n) then total:=total+1 //若已有n个人手持50元钞票购票，那么其余手持100元钞票购票的人一定能找开钱。
else dfs(i+1);
k:=k-1;
m:=m-1;
end
else begin //表示手持100元钞票时
if k>0 then
begin
k:=k-1;
dfs(i+1);
k:=k+1;
end;
end;
endfor;
End; dfs
由于本算法的实质是模拟，因此算法实现起来时间复杂度较高，为指数级，这种算法严格限制了问题的规模，因而不是一个好的算法。
II．栈模型
通过对问题的分析我们可以得出这样的结论：在任何时刻，若第n个人手持100元的钞票买票，则在此之前，定有m个人手持50元的钞票买票，使得m≥n，我们通过分析还将得出：售票处收到的50元的钞票最终将全部找出，售票处收到的100元的钞票最终将全部留下，且一旦收到一张面值为100元的钞票，则一定找出一张面值为50元的钞票。由此我们想到了用栈来表示这一过程：若某人手持一张50元的钱币购票，相当于一个元素进栈；若某人手持一张100元的钱币购票，相当于一个元素出栈。则问题转化为：若1~n共n个元素依次进栈，问共有多少种出栈顺序。
n个 元素的全排列共有n!个，那么这n!种方案是否都是可能的出栈顺序呢？答案是否定的，我们可以证明，若a1,a2,……an是可能的依次出栈顺序，则一定不存在这样的情况：使得i<j<k且aj<ak<ai，证明如下：
若i<j<k，说明ai 最先出栈，aj次之，ak最后出栈，下面分两种情况讨论：
（i）如果ai>aj，那么当aj 出栈时，如果ak已在栈中，则ak比aj先入栈，由输入a序列知：ak<aj,所以有ak<aj<ai;当出栈时，如果ak尚未入栈，则由输入序列知aj<ai<ak
（ii）如果ai<aj，那么当aj出栈时，如果ak已入栈，则由输入序列知ak<aj,而ai与ak的关系取决于ai与ak哪个先入栈。但无论怎样，ai与ak均小于aj，当aj出栈时，如果ak尚未入栈，则由输入序列知ai<aj<ak
因此，输出序列中不可能出现当i<j<k时，aj<ak<ai
通过以上分析，我们得出栈模型的算法，算法先产生1~n共n个数的全排列，对于每种排列，若符合前面所讲的出栈规则，那么这n个排列便是一个可能的出栈序列，计数器加1，当n个元素的全排列列举结束时，计数器的值便是问题的解。
在此思想的指导下，为了与模型I的算法进行比较，我们在这里采用递归技术来产生n个元素的全排列，若在每产生一个排列后进行该排列是否为可能输出栈序列的判定，则算法的时间复杂度为O（nn），与模型I的算法比较起来，我们发现模型II中递归的深度降低，栈的使用空间减小，但在构造解答树的过程中，每层扩展的结点数则大量增加，而有些结点的增加是无意义的，所以我们在实际的算法设计中可以一边生成排列一边进行可能输出序列的判定性检验，若不满足条件，则及时剪枝，因而在n较大时该算法的时间复杂度应小于O（nn）
算法3-2
Func check(s:integer):boolean; //判断1～s共s个元素的出栈序列是否为可能的栈输出序列
begin
for a:=1 to s-2 do
for b:=a+1 to s-1 do
if (data[b]<data[s]) and (data[s]<data[a]) then return(false);
reture(true);
end; check
Proc stack(i:integer); //产生n个元素的全排列
begin
for j:=1 to n do
if not(j in flag) then
begin
data[i]:=j;
if check(i) then
begin
flag:=flag+[j];
if i=n then total:=total+1 //计数器加1
else stack(i+1);
flag:=flag-[j];
end;
endfor;
end; stack
但我们应该明确地看到，模型I与模型II在算法实现时解答树中的结点数目都是很多的，结点是栈所储存的信息，大量结点的出现必然影响算法可运行数据的规模，在模型III中，我们着重思考如何对问题进行数学抽象。
III递归算法：
令f(m,n)表示有m个人手持50元的钞票，n个人手持100元的钞票时共有的方案总数。我们分情况来讨论这个问题。
(1)n=0
n=0意味着排队购票的所有人手中拿的都是50元的钱币，那么这m个人的排队总数为1，即f(m,0 )=1
（2）m<n
若排队购票的(m+n)个人中有m个人手持50元的钞票，n个人手持100元的钞票，当m<n时，即使把m张50元的钞票都找出去，仍会出现找不开钱的局面，所以这时排队总数为0,即f(m,n)=0
（3）其它情况
我们思考（m+n）个人排队购票的情景，第(m+n)个人站在第（m+n-1）个人的后面，则第（m+n）个人的排队方式可由下列两种情况获得：
①第（m+n）个人手持100元的钞票，则在他之前的（m+n-1）个人中有m个人手持50元的钞票，有（n-1）个人手持100元的钞票，此种情况共有f(m,n-1)
②第（m+n）个人手持50元的钞票，则在他之前的（m+n-1）个人中有（m-1）个人手持50元的钞票，有n个人手持100元的钞票，此种情况共有f(m-1,n)
由加法原理得f(m,n)=f(m-1,n)+f(m,n-1)
于是我们得到f(m,n)的计算公式：
0 m<n
f(m,n)= 1 n=0 （*）
f(m,n-1)+f(m-1,n)
于是我们可以根据（*）式编写递归算法
算法3-3
Func f(a,b:integer):longint;
begin
if a<b then f:=0
else if b=0 then f:=1
else f:=f(a-1,b)+f(a,b-1);
end; f
IV 递推算法
递归算法是由终止条件向初始条件推导，而递推算法是由初始条件向终止条件推导。可以说，它们本质上是相同的。那么，把递归算法改为递推算法的意义何在呢？我们运用（*）式求解f(4,4)，递归程序执行时构造的解答树如下：
f(4，4)
f(3，4) f(4，3)
f(3，3) f(4，2)
f(2,3) f(3,2) f(3,2) f(4,1)
f(2,2) f(3,1) f(2,2) f(3,1)
f(1,2) f(2,1) f(1,2) f(2,1)
通过对解答树的仔细观察我们会发现，在树中诸如f（3,2）等结点大量重复计算。由此我们看出，递归算法虽具有通用性和可计算性，但产生了大量的数据冗余，这些大量的数据冗余是限制递归算法规模的主要因素，从而导致模型Ⅲ虽进行了数学抽象，但算法实践起来的效率并不高。那么应如何避免大数据冗余以至最终达到零数据冗余呢？请看如下的二维表格：
m f n
|
1
| 2
| 3
| 4
| 5
| 1
| 1
| 0
| 0
| 0
| 0
|
2
| 2
| 2
| 0
| 0
| 0
|
3
| 3
| 5
| 5
| 0
| 0
|
4
| 4
| 9
| 14
| 14
| 0
|
5
| 5
| 14
| 28
| 42
| 42
|
如果用矩阵的形式，则可表示为
1 0 0 0 0
2 2 0 0 0
3 5 5 0 0
4 9 14 14 0
5 14 28 42 42
我们仔细观察该矩阵可发现如下规律：
（1）该短阵为一个5阶下三角短阵
（2）ai，j=ai-1, j+ai，j-1
（3）ai，i=ai，i-1
于是我们便得到了如下算法：
算法3-4
Prog Arithmetic3_4;
Begin
read(n);
for a:=1 to n do data[a,1]:=a; //初始化赋值
for a:=2 to n do
for b:=2 to a do data[a,b]:=data[a-1,b]+data[a,b-1]; //递推
write(data[n,n]);
End. Arithmetic3_4
由此，本题的递推关系便建立起来，这个算法的时间复杂度为O(n2)，它与模型III的递归算法比较起来最大的优点在于它充分利用了已经得到的信息，从而使算法的时间复杂度大大降低，算法本身能够接受的规模也大大增加，达到了零信息冗余，可以说，这是一个较优化的算法。
V组合算法
我们下面用一种崭新的模型——二叉树来反映本题，我们依据以下原则建立一棵具有n 个结点的二叉树。
（1）若结点i是结点j的儿子结点，则i>j，若结点i是结点k 的左儿子，结点j是结点k的右儿子，则i<j。
（2）若结点i是结点j的儿子且i比j先出栈，则结点i是结点j的左儿子；若结点i比结点j后出栈，则结点i是结点j的右儿子。
由（1）可知，这棵具有几个结点的二叉树的先序遍历序列一定为1~n，由（2）可知，这棵树最左边的叶结点一定最先出栈，最后边的叶结点一定最后出栈。所以说，对于任意一棵具有几个结点的二叉树，它的前序遍历顺序便为1～n，即n个元素的入栈顺序，那么它的中序遍历顺序便是这n个元素的出栈顺序。即2n个人的排队方案总数即为具有n个结点的二叉树的个数，又因为具有n个结点的二叉树个数为
，即Catalan数，所以本题的不同排列总数为
算法3-5[5]
Prog Arithmetic3_5;
Begin
read(n);
total:=1;
a:=n+2;
b:=2;
while (a<=2*n) do
begin
total:=total*a;
while (total mod b=0) and (b<=n) do
begin
total:=total div b;
b:=b+1;
end;
a:=a+1;
end;
while b<n do
begin
total:=total div b;
inc(b);
end;
write(total);
End. Arithmetic3_5
本算法的时间复杂度为O（n），从建模方式看，组合算法的模型最抽象，也最不易理解，但这个模型却能抓住问题的本质，因而具有极大的可计算性，达到了零信息冗余。
四 总 结
组合算法作为当代组合数学研究的重要组成部分，在基础理论研究和社会实践中发挥着越来越重要的作用，本文着重讨论组合算法的评价依据，初步揭示了组合算法的设计和优化的基本问题。总之，只有掌握好组合算法的通用性，可计算性和信息冗余量的组合算法评价原则，才能设计出高效的组合算法。
【附 录】
【参考文献】
[1] 《组合数学》 卢开澄 清华大学出版社（1999）
[2] 《组合数学引论》 孙淑玲 许胤龙中国科学技术大学出版社（1999）
[3] 《青少年国际和全国信息学（计算机）奥林匹克竞赛指导—组合数学的算法与程序设计》 吴文虎 王建德 清华大学出版社（1997）
[4] 《离散数学》 Richard Johnsonbaugh 电子工业出版社（1999）
[5] 《算法与数据结构》傅清祥 王晓东 电子工业出版社 （1999）
[6]《人工智能导论》林尧瑞 马少平 清华大学出版社（1999）
【算法比较实验】
为了更好地反映组合算法设计中的三原则对算法效率的影响，我们对“球迷购票问题”的五个模型进行了实验，其总结如下：
一、系统设置：
CPU: Intel 633 Celeron
RAM: 128MB
OS: Windows Me
算法运行环境：Turbo Pascal 7.0
二、 规模确定：
由于此实验的目的是确定模型的优劣，所以测试数据所得结果控制在长整型以内。由计算得到1≤n≤17。为了更好地反映算法的效率，尤其是信息冗余对算法效率的影响，在进行n值选取时，我们选的是不均匀的。
三、时间测定算法：
Begin
t:=meml[$40:$6c];
主程序；
t:=(meml[$40:$6c]-t)/18.2;
out(t)
end.
四、实验结果
N
| 结果
| 模型1运行时间
| 模型2运行时间
| 模型3运行时间
| 模型4运行时间
| 模型5运行时间
|
5
| 42
| 0.0000
| 0.0000
| 0.0000
| 0.0000
| 0.0000
|
10
| 16796
| 0.0000
| 1.1538
| 0.0000
| 0.0000
| 0.0000
|
13
| 7429000
| 0.1099
| >60
| 0.2747
| 0.0000
| 0.0000
|
15
| 9694845
| 1.1538
| >60
| 3.6813
| 0.0000
| 0.0000
|
16
| 35357670
| 4.2308
| >60
| 13.5165
| 0.0000
| 0.0000
|
17
| 129644790
| 15.3846
| >60
| 49.5055
| 0.0000
| 0.0000
|
(时间单位：s)
【源程序】
[1] 算法1—1 的源程序
Program Arithmtic1_1;
Var n,m:array[0..100] of longint;
t,i:integer;
Begin
write('Please input t:');
readln(t);
n[0]:=1;
m[0]:=0;
for i:=1 to t do
begin
n[i]:=m[i-1];
m[i]:=3*n[i-1]+2*m[i-1];
end;
writeln('N=',n[t]);
writeln('M=',m[t]);
End.
[2] 算法1—2的源程序
Program Arithmetic1_2;
var t:integer;
n,m:longint;
begin
write('Please input t:');
readln(t);
n:=trunc(exp(t*ln(3)));
m:=trunc(exp((t+1)*ln(3)));
if odd(t) then begin
n:=n-3;
m:=m+3;
end
else begin
n:=n+3;
m:=m-3;
end;
n:=trunc(n/4);
m:=trunc(m/4);
writeln('N=',n);
writeln('m=',m);
end.
[3]算法2的源程序
Program Arithmetic2;
Const InFile='input.txt';
OutFile='output.txt';
pi=3.1415926535;
s1=2/3*pi-1.732/2;
s2=pi/2-1;
s3=5/12*pi-1.732/2;
Var list,info:Array[1..100,1..100] of shortint;
x,y: Array[1..100] of integer;
n: Integer;
area,s4: real;
Procedure init;
Var f:Text;
a:integer;
Begin
assign(f,InFile);
reset(f);
readln(f,n);
for a:=1 to n do
read(f,x[a],y[a]);
close(f);
s4:=4*sin(pi/12)*sin(pi/12)+pi/12-1/4;
End;
Function dissmilaruty_function(k1,k2:integer):integer;
Var l:integer;
Begin
l:=abs(x[k1]-x[k2])+abs(y[k1]-y[k2]);
if l>2 then dissmilaruty_function:=0
else dissmilaruty_function:=l;
End;
Procedure done;
var i,j,k,p,count1,count2:integer;
check: boolean;
Begin
count1:=0;
count2:=0;
area:=n*pi;
for i:=1 to n-1 do
for j:=i+1 to n do
begin
list[i,j]:=dissmilaruty_function(i,j);
if list[i,j]=1 then inc(count1)
else if list[i,j]=2 then inc(count2);
end;
area:=area-count1*s1-count2*s2;
count1:=0;
for i:=1 to n-2 do
for j:=i+1 to n-1 do
for k:=j+1 to n do
begin
check:=true;
p:=list[i,j]+list[j,k]+list[i,k];
if (list[i,j]=0) or (list[j,k]=0) or (list[i,k]=0)
then check:=false;
if (p=4) and check then
begin
inc(count1);
if list[i,j]=2 then info[i,k]:=2
else if list[j,k]=2 then info[j,k]:=2
else if list[i,k]=2 then info[i,k]:=2;
end;
end;
area:=area+s3*count1;
count1:=0;
for i:=1 to n-2 do
for j:=i+1 to n-1 do
for k:=j+1 to n do
if (j<>k) and (info[i,j]=2) and (list[j,k]=1) and (list[i,k]=1) then
inc(count1);
area:=area-s4*count1;
End;
Procedure out;
Var f:text;
Begin
assign(f,OutFile);
rewrite(f);
writeln(f,area:0:4);
close(f);
End;
Begin
Init;
Done;
Out;
End.
[4]算法3—1的源程序
{$A+,B-,D-,E+,F-,G+,I-,L-,N-,O-,P-,Q-,R-,S-,T-,V+,X+}
{$M 65520,0,655360}
Program Arithmetic3_1;
Var n,k,m:integer;
total:longint;
Procedure DFS(i:integer);
Var j:integer;
Begin
for j:=0 to 1 do
begin
if (j=0) then begin
inc(k);
inc(m);
if (m=n) then inc(total)
else dfs(i+1);
dec(k);
dec(m);
end
else begin
if k>0 then
begin
dec(k);
dfs(i+1);
inc(k);
end;
end;
end;
End;
Begin
read(n);
m:=0;
k:=0;
dfs(1);
writeln(total);
End.
[5]算法3—2的源程序
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S+,T-,V+,X+}
{$M 65520,0,655360}
program Arithmetic3_2;
var n:integer;
data:Array[1..100] of integer;
flag:set of byte;
total:longint;
function check(s:integer):boolean;
var a,b:integer;
begin
check:=false;
for a:=1 to s-2 do
for b:=a+1 to s-1 do
if (data[b]<data[s]) and (data[s]<data[a]) then exit;
check:=true;
end;
procedure stack(i:integer);
var j:integer;
begin
for j:=1 to n do
if not(j in flag) then
begin
data[i]:=j;
if check(i) then
begin
flag:=flag+[j];
if i=n then inc(total)
else stack(i+1);
flag:=flag-[j];
end;
end;
end;
begin
read(n);
stack(1);
writeln(total);
end.
[6]算法3—3的源程序
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S+,T-,V+,X+}
{$M 65520,0,655360}
program Arithmetic3_3;
var n:integer;
function f(a,b:integer):longint;
begin
if a<b then f:=0
else if b=0 then f:=1
else f:=f(a-1,b)+f(a,b-1);
end;
begin
read(n);
writeln(f(n,n));
end.
[7]算法3—4的源程序
Program Arithmetic3_4;
Var data :array[1..20,1..20] of longint;
a,b,n:integer;
Begin
readln(n);
for a:=1 to n do data[a,1]:=a;
for a:=2 to n do
for b:=2 to a do data[a,b]:=data[a-1,b]+data[a,b-1];
writeln(data[n,n]);
End.
[8]算法3—5的源程序
Program Arithmetic3_5;
Var n,a,b:integer;
total:longint;
Begin
readln(n);
total:=1;
a:=n+2;
b:=2;
while (a<=2*n) do
begin
total:=total*a;
while (total mod b=0) and (b<=n) do
begin
total:=total div b;
inc(b);
end;
inc(a);
end;
while b<n do
begin
total:=total div b;
inc(b);
end;
writeln(total);
End.
贪心策略的特点与在信息学竞赛
中的应用
【关键字】 贪心策略 特点 理论基础 应用
【摘要】
本文着重探讨的是贪心策略的数学模型、理论基础（“矩形胚”结构）和贪心策略的特点。（贪心选择性质和局部最优解）介绍了3种体现“贪心”思想的图形算法：Dijkstra算法、Prim算法和Kruskal算法，并着重给出了近几年来在各级各类程序设计竞赛中出现的一些题目。
【正文】
一、 引 论
信息，人类社会发展的重要标志。人类对信息的记载，可以追溯到原始社会。在漫长的人类社会发展过程中，伴随着科学技术的发展，人类对客观世界的认识不断加深，现实世界的信息量急剧增大。为了满足人们对大数据量信息处理的渴望，1946年世界上第一台电子数字计算机ENIAC应运而生。在此后的半个世纪中，为解决各种实际问题，计算机算法学得到了飞速的发展。线形规划、动态规划等一系列运筹学模型纷纷运用到计算机算法学中，解决了诸如经济决策等一系列现实问题。在众多的计算机解题策略中，贪心策略可以算得上是最接近人们日常思维的一种解题策略，正基于此，贪心策略在各级各类信息学竞赛、尤其在对NPC类问题的求解中发挥着越来越重要的作用。
二、 贪心策略的定义
【定义1】 贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。
其实，从“贪心策略”一词我们便可以看出，贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解。
三、贪心算法的特点
通过上文的介绍，可能有人会问：贪心算法有什么样的特点呢？我认为，适用于贪心算法解决的问题应具有以下2个特点：
1、贪心选择性质：
所谓贪心选择性质是指应用同一规则f，将原问题变为一个相似的、但规模更小的子问题、而后的每一步都是当前看似最佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。从全局来看，运用贪心策略解决的问题在程序的运行过程中无回溯过程。关于贪心选择性质，读者可在后文给出的贪心策略状态空间图中得到深刻地体会。
2、局部最优解：
我们通过特点2向大家介绍了贪心策略的数学描述。由于运用贪心策略解题在每一次都取得了最优解，但能够保证局部最优解得不一定是贪心算法。如大家所熟悉得动态规划算法就可以满足局部最优解，在广度优先搜索（BFS）中的解题过程亦可以满足局部最优解。
在遇到具体问题时，许多选手往往分不清哪些题该用贪心策略求解，哪些题该用动态规划法求解。在此，我们对两种解题策略进行比较。
图 1
【引例】在一个N×M的方格阵中，每一格子赋予一个数（即为权）。规定每次移动时只能向上或向右。现试找出一条路径，使其从左下角至右上角所经过的权之和最大。
我们以2×3的矩阵为例。
若按贪心策略求解，所得路径为：1→3→4→6； 图 二
若按动态规划法求解，所得路径为：1→2→10→6。
a
|
a
|
