动态规划准备篇

1、图一递推法中我们重点研究两个关键问题：建立递推关系（式）和程序实现递推。前言动态规划算法在近几年的各级信息学奥林匹克竞赛中代替了搜索算法的统治地位，成为 要想在信息学竞赛中取得好成绩必须掌握的一种算法。然而很多同学学习动态规划时，被它复杂的算法定义以及表示方法弄的晕头转向，不知 所以，即便勉强掌握，往往一遇到复杂一点的动态规划，又不知如何下手分析出正确的结果。 为了使同学们能熟练、透彻地掌握这种算法。我们通过动态规划准备篇、基础篇、中级篇和 高级篇共四篇文章来进行一个系统地讲解。希望能对同学们的学习有所帮助。动态规划准备篇在准备篇学习之前我们先来看一个图。（图一）通过这个图我们可以了解到递推法

2、是动态规划的 一个基础。所以我们在准备篇中重点介绍递推法。递推法在信息学竞赛中直接出现的可能越来越少， 但是它的思想方法的应用以及与其他算法的综合使用 却在任何的竞赛中都会出现。动态规划就是一个很好的 实例。所以掌握递推法是我们学习动态规划的一个前 提。一、递推关系定义:对于递推关系其实我们并不陌生，从我们识数开始这种递推关系就陪伴我们，只不过我们没有留心罢了。在小学阶段我们都做过添数游戏，如:（1）1，2，3，5,（2）2，4，6，10，（3）1，3，9，81，其实这些数列都是递推关系的数学表现形式，我们可以把它们转换成递推关系式，如：（1）F（n）=F（n-1）+1， F（1）=1；答案：

3、4（2）F（n）=F（n-1）+2， F（1）=2；答案：8（3）F（n）=F（n-1）*3, F（1）=1；答案：27定义1-1：给定一个数的序列h0，h1，hn，若存在整数n0，使当n=n0时，可以 用等号（或大于号、小于号）将与其前面的某些项h.（0=in）联系起来，这样的式 子就叫做递推关系。通过这个定义我们可知递推关系的数学模型实质就是一个数列。这个数列中的数与数（绝 大多数为相邻的数）是有一定的关系连接的。这种关系就是递推关系。代表这种关系的数学 表达式就是递推关系式。解题时分析出递推关系并推导出正确的递推关系式成为首要问题。二、数列数列是递推关系的一种表现形式，所以我们令h 0，

4、h 1 ， . . .，.表示一个数列。h叫做数列的一般项或生成项。将这个数列分成三类：算术数列、几何数列、特殊数列。这三类数列也是递推关系最基 本的三种表现形式，即所有的递推关系都可以用这三种数列表示。我们先研究前两种：算术数列和几何数列。定义2-1：算术数列中的每一项比前一项大一个常数q，当初始项h0和常数q确定后，数列形式为h0，h0+q，h0+2q， h0+nq，.定义2-2:几何数列中的每一项比前一项的常数q倍，当初始项h0和常数q确定后， 数列形式为h0，qh0，q2h0，qnh0，. 例：（算术数列）（1）h=1，q=2： 1， 3， 5，.，（2）h=4，q=0： 4， 4，

5、4，.，（3）h0=0，q=1： 0，1，2， 例：（几何数列）（1）h0=1，q=2： 1，2，22，.（2）h0=5，q=3： 5，3*5，32*5 推导出：算术数列的部分和：1+2n，；正奇整数数列。4,；常数4数列。n，；非负整数数列。2n，；2的非负整数幕数列3n*5，.；几何数列的部分和:=丈(h0 + kq) = (n + 1) h0 +qn (n + 1)丈 qkh0k = 0qn + 】-1 ,ih 0q -1(q 丰 1)(n +1)h0(q = 1)证明：q1时今土闩扁+乎席+圮叫；qSn=qh0+q2h0+.+qnh0+qn+1 h0；qSn+h0=qh0+q2h0+

6、+qnh0+qn+1 WqSn+h0=Sn+qn+1*h0；qSn-Sn=qn+1*h0-h0；Sn（q-1）= h0（qn+1-1）；Sn=h0（qn+1-1）/（q-1）；三、递推关系（式）递推关系式一般分为两种形式：常用式和一般式。常用式表示主要是第n项与前面几项的关系式，以及初始项的值。一般式表示主要是一种函数表达式，以n为变量的函数式h（n）。注意：在竞赛当中我们只要找出递推关系式的常用式即可，当然如果能写出一般式会提 高运算速度，而将递推法转换成了高精度算法，从而降低算法复杂度。我们给将两个算式的转化（主要是常用式转化一般式）方法也介绍给同学们，但并不要 求一定掌握。但是递推关系的

7、建立和递推关系常用式的正确表示则必须熟练掌握。定义3-1：令h0，.，h，是一个数列。如果存在量a1，a2,，ak，akA0和量bn （每一个量都可能依赖于n） 使得h =a h h +.+a h ,+b （nk）n 1 n-12 n-2 k n-k n则称该数列满足k阶线性递推关系。如果bn=0，则线性递推关系是齐次的，如果a1，a2,，ak是常数，则 h =a h h +.+a h ,为常系数线性齐次递推关系。n-我们先给出常系数线性齐次递推关系常用式转化一般式的方法：定理3-1：常系数线性齐次递推关系一般式的方法：令q为一非零数。则hn=qn是常系数线性齐次递推关系h -ah -ah _

8、-a h ,=0 (a 0,nk) n 1 n-12 n-2 k n-kk 的解，当且仅当q是多项式方程xk-a1xk-1-a2xk-2-_-a =0的一个根。如果多项式方程有k个不同的根q1，h =匕 q; + c2 q; +例1 ：求Fibonacci的一般式解：Fibonacci的常用式是非常熟悉的：f-f -f =0 n n-1 n-2找一般式的形式f =qn的一个解，其中q是一个非零数。所以常用式可写成qn-qn-1-qn-2=0-kq2，qk，则+ c qn k k(n=2)； f0=0，f1=1；首先我们寻分解成qn-2(q2-q-i)=0由于q是非零的，所以我们断言q2-q-1

9、=0，q为方程x2-x-1=0的根。求出方程的根为1 + v5q 12因此f (5)；和 f (三臣)；n 2 n 2两者都是Fibonacci递推关系的解。由于Fibonacci递推关系是线性(1)的和齐次的，通过直接计算得到1 +、，5LJ-) + C2(2根据初始值f0=0f1=1可计算出c1和c2的值c1+c2=0 (n=0)/1 + -51 * 5(n=1)C1(一n+C 2(解的-1最后得到一般式(n=0)例2：求解满足初始值h=1，h1=2， h2=0，的递推关系h =2h+h 2-2/ 3的一般式。解：该递推关系的特征方程为：x3-2x2-x+2=0；-解的它的三个根为1，-1

10、，2后得出h =c11n+c2(-1)n+c32n；再根据初始值求出常数c1，c2和c3。c1+c2+c3=1(n=0)c1-c2+2c3=2 (n=1)c1+c2+4c3=0 (n=2)这个方程组的唯一解为c1=2, c2=-2/3和c3=-1/3。最后得出一般式为：hn=2-2/3*(-1)n-1/3*2n(1)线性：同学们可画出Fibona；ci的函数图像，就可发现fn与fn_1，fn_2与fn是线性的即 f =G f，f =C f。3n-11 n n-22 n如果同学们细心的话，会发现定理3-1有一个缺陷，在解特征方程xk-a1xk-i-a2xk-2-ak=0 的时候会有可能出现重根的

11、情况，这时在运用定理3-1求递推的一般式就会出现错误。我们 在给出一个定理解决这个问题。令q1，q2,，qt为常系数线性齐次递推关系h =a h h o+_+a h , (a 0,nk) n 1 n-12 n-2 k n-k k 定理3-2：常系数线性齐次递推关系一般式的方法(有重根)： 的特征方程的互异的根。此时如果qi是si的重根，则该递推关系对qi的部分一般解为，H(i) = c1qn + c2nqn + c3n2qn +. + c ni-1qn递推关系的一般式为h = H + H(2)+ . + H (t)例：求递推关系外二气严外书底外书立外“ (n=4)满足初值h0=1,h1=0,h

12、2=1和hg=2的一般式。解：求其特征方程x4+x3-3x2-5x-2=0的根x3(x+1)-(x+1)(3x+2)=0(x+1)(x3-3x-2)=0(x+1)(x3+1-(3x+3)=0(x+1)(x+1)(x2-x+1)-3(x+1)=0(x+1)(x+1)(x2-x-2)=0(x+1)3(x-2)=0 x123=-1; x4=2；根据定理3-2：H =c1(-1) n + c 2 n(-1) n + c3 n 2(-1) nH (2) = c 42 n匚布祚-士口书泌曰 2；| h = c (1)n + c n(1)n + c n 2 (1)n + c 2n 上面两式相加得到：n1 2

13、 34再根据初始条件得到：(n=0) c1+c4=0(n=1) -c1-c2-c3+2c4=0(n=2) c1+2c2+4c3+4c4=0(n=3) -c1-3c2-9c3+8c4=0得到解：c=7/9，。2=-3/9，。3=0，。4=2/9。因此一般式为：h =7/9(-1)n-(3/9)*n*(-1)n+(2/9)*2n。定理3-3：对于日非齐次的线性递推关系一般式的方法：利用分散模拟，将非齐次的线性递推关系分成两部分考虑：先分别求出：(1)求齐次关系部分的一般式(2)求非齐次部分的一个特解(也可认为是一个一般式)然后后将(1)和(2)联合相加，根据初始值，解出(1)式中要求的常数值。最后

14、得到非齐次的线性递推关系一般式。在(2)式中有如下几种情况： hn=r(常数)如果bn=d(常数) h：=rn+s如果 b：=dn+ch：=rn2+sn+t 如果 bn=fn2+dn+c hn=pdn如果 bn=dn例 1 ：解 h =3h 1-4n (n=1) h0=2 的一般式。解：先求出hn=3hn-1的一般式：特征方程为x-3=0,有一个特征根q=3，故一般式为hn=c13n。再求非齐次部分。由于bn=-4n符合情况(b)，所以有hn=rn+s的形式根据题目必有 rn+s=3(r(n-1)+s)-4n右边变为rn+s=(3r-4)n+(-3r+3s)；方程两边n的系数和常数项相等，得到

15、两个式子: r=3r-4和s=-3r+3s。得到r=2和s=3；从而得到非齐次部分的一般式：hn=2n+3。两式合并得到hn=c13n+2n+3,根据h0=2得到2=c1+3,从而c1=-1。最后得出一般式：hn=-3n+2n+3例 2：解 hn=3hn-1+3n (n=1) h0=2 的一般式。解：先求出hn=3hn-1的一般式：特征方程为x-3=0，有一个特征根q=3，故一般式为hn=c13n。再求非齐次部分。由于bn=3n符合情况(d)，所以有hn=pdn的形式根据题目必有p3n=3(p3n-1)+ 3n；得到p=p+1，这是不可能的。因此改为hn=pndn；得到pn3n=3(p(n-1

16、)3n-1)+ 3n；得到p=1，故hn=n3n是非齐次部分的一般式。两式合并得到hn=c13n+n3n，根据h0=2得到c1=2。最后得出一般式：hn=2*3n+n3n=(2+n)3n。推论 3-1：对于 hn=ahn 1+bn (n=1)的 a=1 的 hn=hn 1+bn (n=1)的一般式解法：由迭代产生：hn=h0+b1+b2+.+bn (n=1)；因此一般式与级数b1+b2+. .+bn的求和相同。例 3：求 hn=hn1+n3 (n=1)， h0=0 的一般式。解：根据推论 3-1 有 h =03+13+23+.+n3=(0+1+2+.+n)2=(n2(n+1)2)/4；对于这个

17、 结果可利用数学归纳法验证n (证略)。练习：求以下递推关系的一般式：(1)(2)(3)(4)(5)hn=4hn-2 (n=2) h0=0；h1=1。hn=3hn-2-2hn-3 (n=3) h0=1 ； h1=0； h2=0。hn=4hn-1+3*2n (n=1) h0=1；hn=2hn-1+n (n=1) h0=1；hn=hn-1-n+3 (n=1) h0=2；答案： 根据定理3-1,得到特征方程x2-4=0的两个根x1=2, x2=-2； hn=c1*2n+c2*(-2)n； 根据 h =0 和 h =1；得出 c+c =0 和 2c-2c =0； c1=2-2，c2=-(2)-2； T

18、OC o 1-5 h z 011212，一般式：hn=2-2-2n-2-2-(-2)n=2n-2-(-2)n-20根据定理3-2,得到特征方程x3-3x+4=0的三个根：二个重根，一个实根。x1=x2=1, x =-2。得到 h =c +c n+c (-2)n；根据 h =1 ； h =0； h =0；得到ij c +c =1、c +c -2c =0 和。、3II 12301213123c1+2c2+4c3=0； c1=8/9、c2=-2/3 和 c3=1/9；一般式：hn=8/9-(2/3)n+(1/9)(-2)n。(3 )根据定理3-3，得到齐次部分hn=c4n ；特解部分：hn=p-3-

19、2n ； p-3-2n=4-(p-3-2n-1)+3-2n； p=2p+1 ； p=-1； hn=-3-2n；合解：hn= c4n-32n； h0=1 ； c1-3=1 ； c1=4；一般式：hn=4n+132n。根据定理 3-3,得到齐次部分 hn=c2n；特解部分：hn=rn+s ； rn+s=2(r(n-1)+s)+n ； r=2r+1 ； r=-1 ； s=2s2r； s=-2； h =-n-2；合解：hn=c1 -2n-n-2； h=1； c1-2=1 ； c1=3；一般式：hn=32n-n-2。根据推论3-1, hn=h0+b1+b2+.+bn=2+(3-1)+(3-2)+(3-3

20、)+. .+(3-n)=2+3*n-(1+2+3+. .+n)=2+3n-(n(n+1)/2=-(n2-5n-4)/2；数学归纳法证明：n=0时代入得到h0=2 ；假设hn成立，那么 hn+1=hn-(n-1)+3=(-n2+3n+8)/2； hn+1=-(n+1)2-5(n+1)-4)/2=(-n2+3n+8)/2；所以得到的一般式 正确。+四、建立递推关系建立递推关系的关键在于寻找第n项与前面几项的关系式，以及初始项的值。它不是一 种抽象的概念，是需要针对某一具体题目或一类题目而言的。4-1、Fibonacci 数列在所有的递推关系中，Fibonacci数列应该是最为大家所熟悉的。Fibo

21、nacci数列类的题 目因为解法相对容易一些，逐渐退出了竞赛的舞台。可是这不等于说Fibonacci数列没有研 究价值，恰恰相反，一些此类的题目还是能给我们一定的启发的。Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖 问题”(又称“Fibonacci问题”)。问题的提出：有雌雄一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔子。问过n 个月后共有多少对兔子？解：设满x个月共有兔子fx对，其中当月新生的兔子数目为Nx对。第x-1个月留下的兔 子数目设为Ox对。则：hx=Nx+Ox而Ox=hx1，Nx=Ox-1=hx-2 (即第x-2个月的所有兔

22、子到第x个月都有繁殖能力了)hx=hx1+hx2 边界条件：h0=0，h1=1由上面的递推关系可依次得到h =h +h =1， h =h +h =2， h =h +h =3， h =h +h =5，。.210321432543Fibonacci数列应用：(4-1-1)骨牌覆盖：2xn的棋盘用1x2的骨牌作完全覆盖，求不同的覆盖方式数Cn解：对于n=0有一种空覆盖方式。n=1可知有一种覆盖方式。即h0=0，h1=1；当n=2时，我们将2xn的棋盘划分成两部分A和B：我们将含有第一块骨牌竖直的覆盖在棋盘左上角方格的那些完全覆盖放在A中。那么A的完全覆盖与2x(n-1)的棋盘的完全覆盖方式数一样，即

23、A=h ；n-1B的覆盖方式为将第一块和第二块骨牌水平的覆盖在棋盘的最前两列，那么B的完全覆盖与2x(n-2)的棋盘的完全覆盖方式数一样，即B=hn 2；将A和B的方式数相加即为hn=hn-1+hn-2；结果与Fibonacci数列一致。(4-1-2)蜂巢问题：有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。 试求出蜜蜂从蜂房a爬到蜂房b的可能路线数。解：这是一道很典型的Fibonacci数列类题目，其中的递推关系很明显。由于蜜蜂只能 爬向右侧相邻的蜂房，不能反向爬行”的限制，决定了蜜蜂到b点的路径只能是从b-1点或 b-2 点到达的，故 f =f i+f)(a+2=n=b)，边界条

24、件 f =1，f =10 n n-1n-2a a+1(4-1-3 )有口阶台阶，一次可上1阶，也可一次上2阶，问有多少种走法？解：设有h种走法，其递推公式为h =h 1+h 2；与Fibonacci数列一致。(4-1-4)写一个计算机程序，让计算机和人玩纸牌游戏，争取计算机获胜，并显示整个 游戏过程。该游戏是：两个选手(计算机一方，人为另一方)比赛：有n张(3n10000)纸牌， 两个选手交替地拿取(计算机先拿)，谁取走最后一张即谁胜。拿取规则为：第一个选手拿走1 到n-1张牌(可拿任意张，但不能拿完)；以后，每个人可取1张或1张以上，但不得取走大于对方刚取数目的2倍（设对方刚取走b张，则可取

25、1到2b张）。解：这到题目看上去是一道很明显的动态规划试题，以剩余牌数划分阶段，状态F表示剩余p张牌，且第一人最多可以取k张牌的情况是必败点还是必赢点。，注：如果你还不会动态规划，这一块就不必看了。状态转移方程是：F k=（p=k） or F kl or not F k2 k （1=p=n，1=k=Fi，则 p=Fi+1，+VFi=Fi+Fi 1 且 Fi 1=Fi +.F=2F.-i+1 i.p=2x.人可以一次将剩下的p张牌全部取完。.计算机一定会输。（2）若 1=xFi+1，Fi 2-Fi=Fi 1 且 Fi 1 是 Fibonacci 数.计算机无法通过一种取牌方案，使计算机在某一次取

26、过少于Fi+1/2张牌后，剩下Fi+1 张牌。.当剩下Fi+1张牌的时候，必然轮到计算机取，且计算机这时不能一次将所有牌取完;,/Fi+1 是 Fibonacci 数。.计算机一定会输。又Vpe(F.+1,F.+2),即剩下p张牌轮到人取的时候，人一定获胜；.R是必赢牌数：(3)由1、2可得结论成立。证毕。4-2、平面分割问题问题的提出：设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且 任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。n=1n=2n=3n=4解：设an为n条封闭曲线把平面分割成的区域个数。由图可以看出：a2-a1=2； a3-a2=4； a

27、4-a3=6。从这些式子中可以看出a -a 1=2(n-1)。当然，上面的式子只是我们通过观察4幅 图后得出的结论，它的正确性尚不能保证。下面不妨让我们来试着证明一下。当平面上已有 n-1条曲线将平面分割成a 1个区域后，第n-1条曲线每与曲线相交一次，就会增加一个区 域，因为平面上已有了 n-1条封闭曲线，且第n条曲线与已有的每一条闭曲线恰好相交于两 点，且不会与任两条曲线交于同一点，故平面上一共增加2(n-1)个区域，加上已有的a 1个 区域，一共有a 1+2(n-1)个区域。所以本题的递推关系是a=a 1+2(n-1)，边界条件是a1=2。平面分割问题是竞赛中经常触及到的一类问题，由于其

28、灵活多变，常常让感到棘手，关 键还是要仔细分析，掌握规律。平面分割问题应用：(4-2-1) N条直线将平面分成多少个域？假定无三线共点，且两两相交。解：D(n)=D(n-1)+nD(n)=1+ (n(n+1)/2D(1)=2 D(4)=11 D(5)=16 D(6)=22(4-2-2)若上例中的直线改为锯齿线，如图所示，每根锯齿线都和其他锯齿线两两相交， 且无三线共点，试问n条锯齿线将平面分成多少个域？解：第n条锯齿线每一支都和前面的n-1条锯齿线相交于2(n-1)个点。将锯齿线每一支 分成2(n-1)+1段，所以第n条锯齿线加入看作是2n条直线问题，但少了两段两线相交后延 长的部分。即 D(

29、n)=D(2n)-2n D(1)=2 D(2)=D(4)-2=7 D(3)=D(6)-6=22-6=16(4-2-3)同一平面内的n(n=2)条直线相交于同一点，则这 n条直线最多能将平面分割成多少个不同的区域？解：这道题目与4-2-1的平面分割问题十分相似，不同之处就在于线条的曲直以及是否 存在共点线条。由于共点直线的特殊性，我们决定先考虑p条相交于一点的直线，然后再考 虑剩下的n-p条直线(这n-p条直线符合4-2-1的条件)。首先可以直接求出p条相交于一点的直线将平面划分成的区域数为2p个，然后在平面上已经有k(k=p)条直线的基础上，加上 一条直线，最多可以与k条直线相交，而每次相交都

30、会增加一个区域，与最后一条直线相交 后，由于直线可以无限延伸，还会再增加一个区域。所以f =f 1+m(mp)，边界条件在前面 已经计算过了，是f=2p。虽然这题看上去有两个参数，但是在实际做题中会发现，本题还 是属于带一个参数的的递推关系。4-3、Catalan 数Catalan数首先是由Euler在精确计算对凸n边形的不同的对角三角形剖分的个数问题 时得到的，它经常出现在组合计数问题中。问题的提出：在一个凸n边形中，通过不相交于n边形内部的对角线，把n边形拆分成案，故=5。求对于Pi解：设Cn表示凸n边形的拆分方案总数。由题目中的要求可知一个凸n边形的任意一若干三角形，不同的拆分数目用hn

31、表之，hn即为Catalan数。例如五边形有如下五种拆分方条边都必然是一个三角形的一条边，边P1Pn也不例外，再根据“不在 同一直线上的三点可以确定一个三角形，只要在P2, P3, .，Pn1 点中找一个点Pk(1k=0，(k=1，2，3，2n)的数列个数等于第n个Catalan数hn = n + 1 C1(n=0)。C n证明：n个+1和n个-1构成的总数列个数为C 2n我们设其部分和满足a1+a2+.+ak=0的数列个数为An，而不满足部分和的数列个数为 U，这样我们只要求出U，那么A自然也就求出了。n考虑n个+1和n个-1组成的不满足数列中，必定存在从1k个部分和为a1+a2+.+ak=

32、-1 的数列，在这个部分数列中-1的个数比+1的个数恰好多1,而剩下的+1的个数比-1的个数 恰好多1。如果将这部分的数列的每一个数取其相反数，而对剩下的数保持不变，这样就变 成一个(n+1 )个+1 和(n-1)个-1的数列。按照这样的一个思想，我们认为每一个不满足部分和的数列对应一 个(n+1)个+1和(n-1) 个-1的数列。这样就变成一个求(n+1)个+1和(n-1)个-1的共2n个数的数列总数。(2n)!所以 Un 为(n + 1)!(n -1)!；An=d -(2n)!=q(1 -w2y)C(n)!(n)!(n + 1)!(n -1)!(n)!(n -1)! n n +1(n)!(

33、n -1)! n(n +1) n +1 2n与Catalan数一致。(4-3-2) 一场音乐会票价50元一张，排队买票的顾客中有m位持有50元的钞票，n 位持有100元的钞票，售票处无50元的零钱，试问有多少种排队方案，能使购票顺利进行， 不出现找不出零钱的情况？假定每位顾客只买一张。解：将50元的钞票看做-1,而将100元的钞票看做+1,那么答案与4-3-1 一致：1 , 一,C 2n ；如果买票的顾客进行“实名制”排队，那么排列方案为(n) !(n n+r C n =(2n!)/(n+1)。(4-3-3)n个1和n个0组成2n位的二进制数，要求从左到右扫描1的累计数，不小 于0的累计数，求

34、满足这个条件的数有多少？解：这个问题仔细分析属于Catalan数。(4-4-4) 一位大城市的经理在他住所以北n个街区和以东n个街区工作。每天他要走 2n个街区去上班(如图)如果他不穿越对角线(但可以碰到)从家到办公室的对角线，那么 有多少条可能的道路？解：由题意可知路线不在对角线上面就在对角线下面。所以我们只要求出对角线上面的 路线数，在乘以2即可。我们将向北的方向标识为+1，路线由n个+1和n个-1的数列，向东的方向标识为-1,于是每条由于不能穿越对角线，所以满足所以对角线上面的路线数满足a1+a2+.+ak=0，1Catalan 数 hnCn n + 1 2 n数列的部分和2 r 路线总

35、数为：厂三Cn(4-4-5) P=a1a2an是n个数的连乘积，依乘法结合律，不改变其顺序，只用加入括 号来表示乘积的顺序，试问有多少种乘法方案？分析：令P等于n个数乘积的n-1对括号插入的不同方案数%=piPn-l + P2Pn-2+匕尺显然吨14-4、第二类 Stirling 数在典型的递推关系中，第二类Stirling是最不为大家所熟悉的。也正因为如此，我们有 必要先解释一下什么是第二类Strling数。定义4-1 n个有区别的球放到m个相同的盒子中，要求无一空盒，其不同的方案数用 S(n,m)表示，称为第二类Stirling数。下面就让我们根据定义4-1来推导带两个参数的递推关系一第二

36、类Stirling数。解：设有n个不同的球，分别用b1,b2,bn表示。从中取出一个球bn，bn的放法有以 下两种：bn独自占一个盒子；那么剩下的球只能放在m-1个盒子中，方案数为S2(n-1,m-1)；bn与别的球共占一个盒子;那么可以事先将b1,b2,bn1这n-1个球放入m个盒子中，然后再将球bn可以放入其中一个盒子中，方案数为mS2(n-1,m)。综合以上两种情况，可以得出第二类Stirling数定理：定理 4-1 S(n,m)=mS(n-1,m)+S(n-1,m-1) (n1,m=1)；推论4-1当盒子是有区别的，则S2(n,m)=m!*S(n,m)边界条件可以由定义4-1 推导出：

37、S(n,0)=0； S(n,1)=1； S(n,n)=1； S(n,k)=0(kn)。第二类Stirling数应用：(4-4-1)第一类Stirling数：n个有区别的球排成k个循环排列的圆圈，要求每个循环 里至少有一个球，其不同的方案数用S(n,m)表示，称为第一类Stirling数。解：设有n个不同的球，分别用b1,b2,bn表示。从中取出一个球bn，bn的放法有以 下两种：某一个圆圈里只有一个球b ；那么剩下的球方案数为S(n-1,m-1)；bn与至少一个别的球在一个圆圈中；那么就变成将b1,b2,bn1这n-1个球排成k个 循环排列的圆圈的方案数并且bn可以放到b1,b2,bn- 1的

38、任何一个球的左边，得到方案数 为(m-1)S(n-1,m)。综合以上两种情况，可以得出第一类Stirling数：S(n,m)=(m-1)S(n-1,m)+S(n-1,m-1)(n1,m=1)；边界条件：S(n,0)=0； S(n,1)=1； S(n,n)=1； S(n,k)=0(kn)。第二类Stirling数直接在竞赛中较少出现，但它的思想方法却在竞赛中的递推中广泛应 用。就是：其核心思想类似于分治。在Catalan数中的求法中也有这样的思想。(4-4-2) 有 n 个+1 和 n 个-1 构成的 2n 项：a1，a2，.，a2n；其部分和满足a1+a2+.+ak=0，(k=1, 2, 3，

39、.，2n)的数列个数?解：本题的Catalan数的结果证明已经在上面给出了证明。我们应用一下第二类Strling 数的思想方法来解决。令f(m,n)表示m个+1和n个-1时方案总数。分三种情况讨论：当n=0时表示在数列中所有的数值都为+1，故f(m,0)=1；当mn时表示在数列中永远也满足不了部分和a1+a2+.+ak=0，(k=1, 2, 3,.，2n),所以 f(m,n)=0；(3)其它情况我们讨论第(m+n)个数(即最后一个)排在在第(m+n-1)个数后面，这第(m+n)个数排列 方式分两种情况：最后一个数为-1，则在它之前的(m+n-1)个数中有m个+1和n-1个-1，此种情况共有 f

40、(m,n-1)；最后一个数为+1，则0在它之前的(m+n-1)个数中有m-1个+1和n个-1，此种情况共有 f(m-1,n)；综合上面的各种情况得到递推关系：0m nf (m, n) = 1 then fi:=fi(n-1)+fi(n-2);end;beginreadln(n);writeln(fi(n):10:0);readlnend.程序6-1-2：非递归顺推和非高精度法：速度快，n=92以后就数据超界，而且有误差（虽然为19位，而真正正确显示仅15位)。var n:integer;fi:array0.10000 of comp;procedure main;var i:integer;b

41、eginfi0:=0;fi1:=1.0;for i:=2 to n dofii:=fii-1+fii-2;程序 6-1-3：非递归顺推和高精度法：速度快， 交替相加。const maxn=1000;var n,i,j:integer;num1,num2:array0.maxn of byte;procedure sum(n2:integer);var i,s,t:integer;beginif odd(n2) thenbeginfor i:=maxn downto 1 dobegins:=(num1i+num2i) mod 10;t:=(num1i+num2i) div 10;num2i:=s

42、;num2i-1:=num2i-1+t;endendelsebeginfor i:=maxn downto 1 dobegins:=(num1i+num2i) mod 10;t:=(num1i+num2i) div 10;num1i:=s;num1i-1:=num1i-1+t;end;beginreadln(n);fillchar(fi,sizeof(fi),0);main;writeln(fin);readlnend.显示结果无误差。必须至少两个数组，endend;procedure fi(n1:integer);beginrepeatn1:=n1+1;sum(n1);until n1=n;

43、end;beginwrite(n=);readln(n);fillchar(num1,sizeof(num1),0);fillchar(num2,sizeof(num2),0);num2maxn:=1;fi(0);if odd(n) thenbegini:=1;j:=1;while num2i=0 dobegininc(i);inc(j)end;endfor i:=j to maxn do write(num2i);inc(i);endinc(j)elseend;beginfor i:=j to maxn do write(num1i);i:=1;end;j:=1;writeln;while

44、num1i=0 doreadlnbeginend.(6-2 )题目(4-1-2 )最大范围：目标点与出发点之差不超过4000程序6-2： 高精度计算部分有优化typeTarr=array0.1000 of byte;Tnum=array1.4 of Tarr;Tlen=array1.4 of word;varstart,finish:longint;出发点和目标点num:Tnum;num1num3 分别保存到达相邻三个蜂 巢的路径数；num4 是用于交换的临时变量len:Tlen;计算长度leni表示numi的长度procedure DataInit; 数据初始化var i:integer;b

45、eginfor i:=1 to 3 dobeginfillchar(numi,sizeof(numi),0);num i1 :=1;leni:=1;end;end;procedure Add;高精度加法运算：num3=num1+num2var i,carry:word;carry 是进位数字begincarry:=0;for i:=1 to len2 dobegincarry:=carry+num2i+num1i;num3i:=carry mod 10;carry:=carry div 10;end;len3:=i;if carry0 then(6-3)题目(4-3-2)begininc(le

46、n3);长度加 1num3i+1:=carry;end;end;procedure Work;求从出发点到目标点的路 径总数var i:longint;beginnum11:=1;num21:=1;for i:=start+2 to finish dobeginAdd;高精度加法运算：num3=num1+num2num4:=num1;num1:=num2;num2:=num3;num3:=num4;len4:=len1;move(len2, en1,6);end;end;procedure Out;输出结果 var i:integer;beginfor i:=len2 downto 1 do

47、write(num2i);writeln;end;beginDataInit; 数据初始化write(Input:);readln(start,finish);Work; 求从出发点到目标点的路径总数Out;输出结果end.程序6-3-1：搜索算法，用k记录售票处50元钞票的数目，初始时k=0，若某人手持100元而售票处k=0则回溯，否则继续递归搜索。若手持50元钞票的人都买完票，则总排列数加1。此算法很差，不适合得高分。var n,k,m:integer;total:comp;procedure dfs(i:integer);var j:integer;beginfor j:=0 to 1

48、do0 表示 50 元,1 表示 100 元beginif j=0 thenbegininc(k);inc(m);if m=n then total:=total+1else dfs(i+1);dec(k);dec(m)endelse begin开始取100元的if k0 then 找的开零钱 begindec(k);dfs(i+1);inc(k);endendendend;beginreadln(n);m:=0;k:=0;dfs(1);writeln(total:10:0);end.程序6-3-2：递归倒推算法，递推关系应用第二类Strling数的思想方法，为f (m, n)= 0m n1n

49、 = 0f (m, n 1) + f (m 1, n 1)其它情况速度极慢，因为递归展开有很多无效数据，这些数据产生不但使时间浪费，且占据大量 空间。效率极低。end;beginreadln(n);writeln(c(n,n):10:0);end.var n:integer;function c(m,n:integer):comp;beginif n=0 then c:=1else if m=0)。直接算出姑果。此方法改成高精度也是很方便的。var n:integer;total:longint;procedure main;var i,j:integer;begintotal:=1;i:=n

50、+2;j:=2;while (i=2*n) dobegintotal:=total*i;while (total mod j=0) and (j=n) dobegintotal:=total div j;inc(j)(6-4)题目(4-1-4)end;inc(i)end;while j0) and (Youget=n then是否能够一次取完beginwriteln(I: ,n);dec(total,n);writeln(Remain: ,total);exit;end;a1:=0;a2:=1;a3:=1;while a3=a2) or (n-a2Youget*2) then Work(n-a

51、2)else beginwriteln(I: ,n-a2);dec(total,n-a2);writeln(Remain: ,total);end;GetYourAnswer(n-a2); 读取人这次取多少张牌Work(a2-Youget);end;begin 主程序write(Total card:);readln(total);Youget:=(total-1) div 2; 通过限定Youget给计算机可以取的最大牌数限界Work(total); 对total张牌设计一种取法使计算机能取到最后一张牌writeln(I win!);readln;end.(6-5)问题描述：用关系“”和日将

52、3个数A，B，C依序排列有13种不同的序关系：A=B=C，A=BC，AB=C，ABC，ACB，A=CB，BA=C，BAC，B=CA，CA=B，CAB，CBA。编程任务：求出给定的N个数(1=N!1!1AAB=CB CA BA=BCCBBA=CC A111、11、1 1)1)B CACA BC ABB=CACA=BC=A0 thenbeginh:=h+1;nh:=cendendend;procedure thpint.multiplys(o:longint);var i:integer;a,c:longint;插入一个新值，可得到t种新的(m,t)方案，所以F(m-1,t-1)xt种新的(m,n

53、)方案。(2)(m-1,t)方案，添上一个与其他t种值中的某一种相同的数，组成(m,t)方案。类似(1)， 对于每种(m-1,t)方案，分别在点1点t处添一个数，得到t种新的(m,t)方案，所以F(m-1,t)xt 种新的(m,n)方案。综上所述，递推公式为 F(m,t)=(F(m-1,t-1)+ F(m-1,t)*t边界条件：F(1,1)=1;F(1,t)=0(t0)；程序6-5：const maxe=200;de=4;ce=10000;separator,；typethpint=objecth:integer;n:array0.maxe of integer;procedure displ

54、ay;procedure plus(o:thpint);procedure multiplys(o:longint);end;procedure thpint.display;var i:integer;s:string20;beginwrite(nh);for i:=h-1 downto 0 dobeginwrite(separator);str(ni,s);while ength(s)De do s:=0+s;write(s);endend;procedure thpint.plus(o:thpint);var i,j:integer;a,c:longint;beginc:=0;if h0

55、 thenaj.plus(aj-1);beginaj.multiplys(j);h:=h+1;end;nh:=cend;ends.h:=0;end;s.n0:=0;var N:integer;for i:=1 to n do s.plus(ai);a:array1.50 of thpint;write(s=);s,temp:thpint;s.display;i,j:integer;writeln;beginreadlnwrite(N=);end.(6-6 )问题描述：一个核电站有N个放核物质的坑，坑排列在一条直线上。如果连续M个坑中放入核物 质，则会发生爆炸，于是，在某些坑中可能不放核物质。任

56、务：对于给定的N和M，求不发生爆炸的放置核物质的方案总数输入：输入文件只一行，两个正整数N，M( 1N50，2M5)输出：输出文件只有一个正整数S，表示方案总数。Sample Input Sample Output4 313解题思路：利用第二类Stirling的思想方法，设N个坑不会发生爆炸的方案数为f(n)；讨 论在前面n-1个坑的左面的第n个坑的情况：当第n个坑的右边已有了 m-1个连续的坑，那么第n个坑只能不放核物质，所以第n-m+1n这m个坑的状态是固定的，所以第一种情况的方案数为f(n-1-m)；其它情况第n个坑可以放也可以不放。那么就是前n-1个坑的总方案数f(n-1)减去第一种情

57、况 f(n-1-m)再乘以 2，即 2* (f(n-1)-f(n-1-m)两种情况相加得到递推关系：2* f(n-1)-f(n-1-m)；初始值f(0)=1,f(n-m)=1 (n=m)程序6-6-1：非高精度var x:array-1.50of comp;n,m:integer;procedure Init;var f:text;beginassign(f,input.txt);reset(f);readln(f,n,m);close(f);end;procedure Main;var i,j,s:integer; f:text; ans:comp;beginx-1:=1;x0:=1;for

58、 i:=1 to n dobegins:=i-m;if s0 then ss:=chr(g mod 10+48)+ss;tnum=string;varn,m,i,j:word;add:=ss;end;begintemp:array1.100of tnum;assign(f,filein); reset(f);s:string;readln(f,n,m);f:text;close(f);function add(a,b:string):string;temp1:=0;var ss:string;temp2:=0;i,g:byte;temp3:=1;begintemp4:=1;if length(

59、a)length(b) thentemp5:=2;begin ss:=a; a:=b;for i:=2 to n do begins:=;b:=ss;for j:=0 to m-1 doend;s:=add(s,temp5-j);for i:=1 to length(a)-length(b) dofor j:=1 to 4 do tempj:=tempj+1;b:=0+b;ss:=;temp5:=s; end;g:=0;assign(f,fileout); rewrite(f);for i:=length(a) downto 1 dowriteln(f,temp5);beging:=g+ord(ai)-48+ord(bi)-48;close(f); end.ss:=chr(g mod 10+48)+ss;(6-7 )问题描述：设有一个 N*M (l=N=50, l=M=10 thenbeginaj,k+1:=aj,k+1+1;aj,k:=aj,k-10endendend;k:=len;while (k1)and(an,k=0)do k:=k-1;for i:=k downto 1 do write(an,i);writelnend.(6-8)问题描