動(dòng)態(tài)規(guī)劃準(zhǔn)備篇

1、圖一遞推法中我們重點(diǎn)研究?jī)蓚€(gè)關(guān)鍵問(wèn)題：建立遞推關(guān)系（式）和程序?qū)崿F(xiàn)遞推。前言動(dòng)態(tài)規(guī)劃算法在近幾年的各級(jí)信息學(xué)奧林匹克競(jìng)賽中代替了搜索算法的統(tǒng)治地位，成為 要想在信息學(xué)競(jìng)賽中取得好成績(jī)必須掌握的一種算法。然而很多同學(xué)學(xué)習(xí)動(dòng)態(tài)規(guī)劃時(shí)，被它復(fù)雜的算法定義以及表示方法弄的暈頭轉(zhuǎn)向，不知 所以，即便勉強(qiáng)掌握，往往一遇到復(fù)雜一點(diǎn)的動(dòng)態(tài)規(guī)劃，又不知如何下手分析出正確的結(jié)果。 為了使同學(xué)們能熟練、透徹地掌握這種算法。我們通過(guò)動(dòng)態(tài)規(guī)劃準(zhǔn)備篇、基礎(chǔ)篇、中級(jí)篇和 高級(jí)篇共四篇文章來(lái)進(jìn)行一個(gè)系統(tǒng)地講解。希望能對(duì)同學(xué)們的學(xué)習(xí)有所幫助。動(dòng)態(tài)規(guī)劃準(zhǔn)備篇在準(zhǔn)備篇學(xué)習(xí)之前我們先來(lái)看一個(gè)圖。（圖一）通過(guò)這個(gè)圖我們可以了解到遞推法

2、是動(dòng)態(tài)規(guī)劃的 一個(gè)基礎(chǔ)。所以我們?cè)跍?zhǔn)備篇中重點(diǎn)介紹遞推法。遞推法在信息學(xué)競(jìng)賽中直接出現(xiàn)的可能越來(lái)越少， 但是它的思想方法的應(yīng)用以及與其他算法的綜合使用 卻在任何的競(jìng)賽中都會(huì)出現(xiàn)。動(dòng)態(tài)規(guī)劃就是一個(gè)很好的 實(shí)例。所以掌握遞推法是我們學(xué)習(xí)動(dòng)態(tài)規(guī)劃的一個(gè)前 提。一、遞推關(guān)系定義:對(duì)于遞推關(guān)系其實(shí)我們并不陌生，從我們識(shí)數(shù)開(kāi)始這種遞推關(guān)系就陪伴我們，只不過(guò)我們沒(méi)有留心罷了。在小學(xué)階段我們都做過(guò)添數(shù)游戲，如:（1）1，2，3，5,（2）2，4，6，10，（3）1，3，9，81，其實(shí)這些數(shù)列都是遞推關(guān)系的數(shù)學(xué)表現(xiàn)形式，我們可以把它們轉(zhuǎn)換成遞推關(guān)系式，如：（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：給定一個(gè)數(shù)的序列h0，h1，hn，若存在整數(shù)n0，使當(dāng)n=n0時(shí)，可以 用等號(hào)（或大于號(hào)、小于號(hào)）將與其前面的某些項(xiàng)h.（0=in）聯(lián)系起來(lái)，這樣的式 子就叫做遞推關(guān)系。通過(guò)這個(gè)定義我們可知遞推關(guān)系的數(shù)學(xué)模型實(shí)質(zhì)就是一個(gè)數(shù)列。這個(gè)數(shù)列中的數(shù)與數(shù)（絕 大多數(shù)為相鄰的數(shù)）是有一定的關(guān)系連接的。這種關(guān)系就是遞推關(guān)系。代表這種關(guān)系的數(shù)學(xué) 表達(dá)式就是遞推關(guān)系式。解題時(shí)分析出遞推關(guān)系并推導(dǎo)出正確的遞推關(guān)系式成為首要問(wèn)題。二、數(shù)列數(shù)列是遞推關(guān)系的一種表現(xiàn)形式，所以我們令h 0，

4、h 1 ， . . .，.表示一個(gè)數(shù)列。h叫做數(shù)列的一般項(xiàng)或生成項(xiàng)。將這個(gè)數(shù)列分成三類：算術(shù)數(shù)列、幾何數(shù)列、特殊數(shù)列。這三類數(shù)列也是遞推關(guān)系最基 本的三種表現(xiàn)形式，即所有的遞推關(guān)系都可以用這三種數(shù)列表示。我們先研究前兩種：算術(shù)數(shù)列和幾何數(shù)列。定義2-1：算術(shù)數(shù)列中的每一項(xiàng)比前一項(xiàng)大一個(gè)常數(shù)q，當(dāng)初始項(xiàng)h0和常數(shù)q確定后，數(shù)列形式為h0，h0+q，h0+2q， h0+nq，.定義2-2:幾何數(shù)列中的每一項(xiàng)比前一項(xiàng)的常數(shù)q倍，當(dāng)初始項(xiàng)h0和常數(shù)q確定后， 數(shù)列形式為h0，qh0，q2h0，qnh0，. 例：（算術(shù)數(shù)列）（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， 例：（幾何數(shù)列）（1）h0=1，q=2： 1，2，22，.（2）h0=5，q=3： 5，3*5，32*5 推導(dǎo)出：算術(shù)數(shù)列的部分和：1+2n，；正奇整數(shù)數(shù)列。4,；常數(shù)4數(shù)列。n，；非負(fù)整數(shù)數(shù)列。2n，；2的非負(fù)整數(shù)幕數(shù)列3n*5，.；幾何數(shù)列的部分和:=丈(h0 + kq) = (n + 1) h0 +qn (n + 1)丈 qkh0k = 0qn + 】-1 ,ih 0q -1(q 豐 1)(n +1)h0(q = 1)證明：q1時(shí)今土閂扁+乎席+圮叫；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）；三、遞推關(guān)系（式）遞推關(guān)系式一般分為兩種形式：常用式和一般式。常用式表示主要是第n項(xiàng)與前面幾項(xiàng)的關(guān)系式，以及初始項(xiàng)的值。一般式表示主要是一種函數(shù)表達(dá)式，以n為變量的函數(shù)式h（n）。注意：在競(jìng)賽當(dāng)中我們只要找出遞推關(guān)系式的常用式即可，當(dāng)然如果能寫出一般式會(huì)提 高運(yùn)算速度，而將遞推法轉(zhuǎn)換成了高精度算法，從而降低算法復(fù)雜度。我們給將兩個(gè)算式的轉(zhuǎn)化（主要是常用式轉(zhuǎn)化一般式）方法也介紹給同學(xué)們，但并不要 求一定掌握。但是遞推關(guān)系的

7、建立和遞推關(guān)系常用式的正確表示則必須熟練掌握。定義3-1：令h0，.，h，是一個(gè)數(shù)列。如果存在量a1，a2,，ak，akA0和量bn （每一個(gè)量都可能依賴于n） 使得h =a h h +.+a h ,+b （nk）n 1 n-12 n-2 k n-k n則稱該數(shù)列滿足k階線性遞推關(guān)系。如果bn=0，則線性遞推關(guān)系是齊次的，如果a1，a2,，ak是常數(shù)，則 h =a h h +.+a h ,為常系數(shù)線性齊次遞推關(guān)系。n-我們先給出常系數(shù)線性齊次遞推關(guān)系常用式轉(zhuǎn)化一般式的方法：定理3-1：常系數(shù)線性齊次遞推關(guān)系一般式的方法：令q為一非零數(shù)。則hn=qn是常系數(shù)線性齊次遞推關(guān)系h -ah -ah _

8、-a h ,=0 (a 0,nk) n 1 n-12 n-2 k n-kk 的解，當(dāng)且僅當(dāng)q是多項(xiàng)式方程xk-a1xk-1-a2xk-2-_-a =0的一個(gè)根。如果多項(xiàng)式方程有k個(gè)不同的根q1，h =匕 q; + c2 q; +例1 ：求Fibonacci的一般式解：Fibonacci的常用式是非常熟悉的：f-f -f =0 n n-1 n-2找一般式的形式f =qn的一個(gè)解，其中q是一個(gè)非零數(shù)。所以常用式可寫成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遞推關(guān)系的解。由于Fibonacci遞推關(guān)系是線性(1)的和齊次的，通過(guò)直接計(jì)算得到1 +、，5LJ-) + C2(2根據(jù)初始值f0=0f1=1可計(jì)算出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，的遞推關(guān)系h =2h+h 2-2/ 3的一般式。解：該遞推關(guān)系的特征方程為：x3-2x2-x+2=0；-解的它的三個(gè)根為1，-1

10、，2后得出h =c11n+c2(-1)n+c32n；再根據(jù)初始值求出常數(shù)c1，c2和c3。c1+c2+c3=1(n=0)c1-c2+2c3=2 (n=1)c1+c2+4c3=0 (n=2)這個(gè)方程組的唯一解為c1=2, c2=-2/3和c3=-1/3。最后得出一般式為：hn=2-2/3*(-1)n-1/3*2n(1)線性：同學(xué)們可畫出Fibona；ci的函數(shù)圖像，就可發(fā)現(xiàn)fn與fn_1，fn_2與fn是線性的即 f =G f，f =C f。3n-11 n n-22 n如果同學(xué)們細(xì)心的話，會(huì)發(fā)現(xiàn)定理3-1有一個(gè)缺陷，在解特征方程xk-a1xk-i-a2xk-2-ak=0 的時(shí)候會(huì)有可能出現(xiàn)重根的

11、情況，這時(shí)在運(yùn)用定理3-1求遞推的一般式就會(huì)出現(xiàn)錯(cuò)誤。我們 在給出一個(gè)定理解決這個(gè)問(wèn)題。令q1，q2,，qt為常系數(shù)線性齊次遞推關(guān)系h =a h h o+_+a h , (a 0,nk) n 1 n-12 n-2 k n-k k 定理3-2：常系數(shù)線性齊次遞推關(guān)系一般式的方法(有重根)： 的特征方程的互異的根。此時(shí)如果qi是si的重根，則該遞推關(guān)系對(duì)qi的部分一般解為，H(i) = c1qn + c2nqn + c3n2qn +. + c ni-1qn遞推關(guān)系的一般式為h = H + H(2)+ . + H (t)例：求遞推關(guān)系外二氣嚴(yán)外書(shū)底外書(shū)立外“ (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；根據(jù)定理3-2：H =c1(-1) n + c 2 n(-1) n + c3 n 2(-1) nH (2) = c 42 n匚布祚-士口書(shū)泌曰 2；| h = c (1)n + c n(1)n + c n 2 (1)n + c 2n 上面兩式相加得到：n1 2

13、 34再根據(jù)初始條件得到：(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：對(duì)于日非齊次的線性遞推關(guān)系一般式的方法：利用分散模擬，將非齊次的線性遞推關(guān)系分成兩部分考慮：先分別求出：(1)求齊次關(guān)系部分的一般式(2)求非齊次部分的一個(gè)特解(也可認(rèn)為是一個(gè)一般式)然后后將(1)和(2)聯(lián)合相加，根據(jù)初始值，解出(1)式中要求的常數(shù)值。最后

14、得到非齊次的線性遞推關(guān)系一般式。在(2)式中有如下幾種情況： hn=r(常數(shù))如果bn=d(常數(shù)) 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,有一個(gè)特征根q=3，故一般式為hn=c13n。再求非齊次部分。由于bn=-4n符合情況(b)，所以有hn=rn+s的形式根據(jù)題目必有 rn+s=3(r(n-1)+s)-4n右邊變?yōu)閞n+s=(3r-4)n+(-3r+3s)；方程兩邊n的系數(shù)和常數(shù)項(xiàng)相等，得到

15、兩個(gè)式子: r=3r-4和s=-3r+3s。得到r=2和s=3；從而得到非齊次部分的一般式：hn=2n+3。兩式合并得到hn=c13n+2n+3,根據(jù)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，有一個(gè)特征根q=3，故一般式為hn=c13n。再求非齊次部分。由于bn=3n符合情況(d)，所以有hn=pdn的形式根據(jù)題目必有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，根據(jù)h0=2得到c1=2。最后得出一般式：hn=2*3n+n3n=(2+n)3n。推論 3-1：對(duì)于 hn=ahn 1+bn (n=1)的 a=1 的 hn=hn 1+bn (n=1)的一般式解法：由迭代產(chǎn)生：hn=h0+b1+b2+.+bn (n=1)；因此一般式與級(jí)數(shù)b1+b2+. .+bn的求和相同。例 3：求 hn=hn1+n3 (n=1)， h0=0 的一般式。解：根據(jù)推論 3-1 有 h =03+13+23+.+n3=(0+1+2+.+n)2=(n2(n+1)2)/4；對(duì)于這個(gè)

17、 結(jié)果可利用數(shù)學(xué)歸納法驗(yàn)證n (證略)。練習(xí)：求以下遞推關(guā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；答案： 根據(jù)定理3-1,得到特征方程x2-4=0的兩個(gè)根x1=2, x2=-2； hn=c1*2n+c2*(-2)n； 根據(jù) 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根據(jù)定理3-2,得到特征方程x3-3x+4=0的三個(gè)根：二個(gè)重根，一個(gè)實(shí)根。x1=x2=1, x =-2。得到 h =c +c n+c (-2)n；根據(jù) 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 )根據(jù)定理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。根據(jù)定理 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。根據(jù)推論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；數(shù)學(xué)歸納法證明：n=0時(shí)代入得到h0=2 ；假設(shè)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；所以得到的一般式 正確。+四、建立遞推關(guān)系建立遞推關(guān)系的關(guān)鍵在于尋找第n項(xiàng)與前面幾項(xiàng)的關(guān)系式，以及初始項(xiàng)的值。它不是一 種抽象的概念，是需要針對(duì)某一具體題目或一類題目而言的。4-1、Fibonacci 數(shù)列在所有的遞推關(guān)系中，F(xiàn)ibonacci數(shù)列應(yīng)該是最為大家所熟悉的。Fibo

21、nacci數(shù)列類的題 目因?yàn)榻夥ㄏ鄬?duì)容易一些，逐漸退出了競(jìng)賽的舞臺(tái)。可是這不等于說(shuō)Fibonacci數(shù)列沒(méi)有研 究?jī)r(jià)值，恰恰相反，一些此類的題目還是能給我們一定的啟發(fā)的。Fibonacci數(shù)列的代表問(wèn)題是由意大利著名數(shù)學(xué)家Fibonacci于1202年提出的“兔子繁殖 問(wèn)題”(又稱“Fibonacci問(wèn)題”)。問(wèn)題的提出：有雌雄一對(duì)兔子，假定過(guò)兩個(gè)月便可繁殖雌雄各一的一對(duì)小兔子。問(wèn)過(guò)n 個(gè)月后共有多少對(duì)兔子？解：設(shè)滿x個(gè)月共有兔子fx對(duì)，其中當(dāng)月新生的兔子數(shù)目為Nx對(duì)。第x-1個(gè)月留下的兔 子數(shù)目設(shè)為Ox對(duì)。則：hx=Nx+Ox而Ox=hx1，Nx=Ox-1=hx-2 (即第x-2個(gè)月的所有兔

22、子到第x個(gè)月都有繁殖能力了)hx=hx1+hx2 邊界條件：h0=0，h1=1由上面的遞推關(guān)系可依次得到h =h +h =1， h =h +h =2， h =h +h =3， h =h +h =5，。.210321432543Fibonacci數(shù)列應(yīng)用：(4-1-1)骨牌覆蓋：2xn的棋盤用1x2的骨牌作完全覆蓋，求不同的覆蓋方式數(shù)Cn解：對(duì)于n=0有一種空覆蓋方式。n=1可知有一種覆蓋方式。即h0=0，h1=1；當(dāng)n=2時(shí)，我們將2xn的棋盤劃分成兩部分A和B：我們將含有第一塊骨牌豎直的覆蓋在棋盤左上角方格的那些完全覆蓋放在A中。那么A的完全覆蓋與2x(n-1)的棋盤的完全覆蓋方式數(shù)一樣，即

23、A=h ；n-1B的覆蓋方式為將第一塊和第二塊骨牌水平的覆蓋在棋盤的最前兩列，那么B的完全覆蓋與2x(n-2)的棋盤的完全覆蓋方式數(shù)一樣，即B=hn 2；將A和B的方式數(shù)相加即為hn=hn-1+hn-2；結(jié)果與Fibonacci數(shù)列一致。(4-1-2)蜂巢問(wèn)題：有一只經(jīng)過(guò)訓(xùn)練的蜜蜂只能爬向右側(cè)相鄰的蜂房，不能反向爬行。 試求出蜜蜂從蜂房a爬到蜂房b的可能路線數(shù)。解：這是一道很典型的Fibonacci數(shù)列類題目，其中的遞推關(guān)系很明顯。由于蜜蜂只能 爬向右側(cè)相鄰的蜂房，不能反向爬行”的限制，決定了蜜蜂到b點(diǎn)的路徑只能是從b-1點(diǎn)或 b-2 點(diǎn)到達(dá)的，故 f =f i+f)(a+2=n=b)，邊界條

24、件 f =1，f =10 n n-1n-2a a+1(4-1-3 )有口階臺(tái)階，一次可上1階，也可一次上2階，問(wèn)有多少種走法？解：設(shè)有h種走法，其遞推公式為h =h 1+h 2；與Fibonacci數(shù)列一致。(4-1-4)寫一個(gè)計(jì)算機(jī)程序，讓計(jì)算機(jī)和人玩紙牌游戲，爭(zhēng)取計(jì)算機(jī)獲勝，并顯示整個(gè) 游戲過(guò)程。該游戲是：兩個(gè)選手(計(jì)算機(jī)一方，人為另一方)比賽：有n張(3n10000)紙牌， 兩個(gè)選手交替地拿取(計(jì)算機(jī)先拿)，誰(shuí)取走最后一張即誰(shuí)勝。拿取規(guī)則為：第一個(gè)選手拿走1 到n-1張牌(可拿任意張，但不能拿完)；以后，每個(gè)人可取1張或1張以上，但不得取走大于對(duì)方剛?cè)?shù)目的2倍（設(shè)對(duì)方剛?cè)∽遙張，則可取

25、1到2b張）。解：這到題目看上去是一道很明顯的動(dòng)態(tài)規(guī)劃試題，以剩余牌數(shù)劃分階段，狀態(tài)F表示剩余p張牌，且第一人最多可以取k張牌的情況是必?cái)↑c(diǎn)還是必贏點(diǎn)。，注：如果你還不會(huì)動(dòng)態(tài)規(guī)劃，這一塊就不必看了。狀態(tài)轉(zhuǎn)移方程是：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張牌全部取完。.計(jì)算機(jī)一定會(huì)輸。（2）若 1=xFi+1，F(xiàn)i 2-Fi=Fi 1 且 Fi 1 是 Fibonacci 數(shù).計(jì)算機(jī)無(wú)法通過(guò)一種取牌方案，使計(jì)算機(jī)在某一次取

26、過(guò)少于Fi+1/2張牌后，剩下Fi+1 張牌。.當(dāng)剩下Fi+1張牌的時(shí)候，必然輪到計(jì)算機(jī)取，且計(jì)算機(jī)這時(shí)不能一次將所有牌取完;,/Fi+1 是 Fibonacci 數(shù)。.計(jì)算機(jī)一定會(huì)輸。又Vpe(F.+1,F.+2),即剩下p張牌輪到人取的時(shí)候，人一定獲勝；.R是必贏牌數(shù)：(3)由1、2可得結(jié)論成立。證畢。4-2、平面分割問(wèn)題問(wèn)題的提出：設(shè)有n條封閉曲線畫在平面上，而任何兩條封閉曲線恰好相交于兩點(diǎn)，且 任何三條封閉曲線不相交于同一點(diǎn)，問(wèn)這些封閉曲線把平面分割成的區(qū)域個(gè)數(shù)。n=1n=2n=3n=4解：設(shè)an為n條封閉曲線把平面分割成的區(qū)域個(gè)數(shù)。由圖可以看出：a2-a1=2； a3-a2=4； a

27、4-a3=6。從這些式子中可以看出a -a 1=2(n-1)。當(dāng)然，上面的式子只是我們通過(guò)觀察4幅 圖后得出的結(jié)論，它的正確性尚不能保證。下面不妨讓我們來(lái)試著證明一下。當(dāng)平面上已有 n-1條曲線將平面分割成a 1個(gè)區(qū)域后，第n-1條曲線每與曲線相交一次，就會(huì)增加一個(gè)區(qū) 域，因?yàn)槠矫嫔弦延辛?n-1條封閉曲線，且第n條曲線與已有的每一條閉曲線恰好相交于兩 點(diǎn)，且不會(huì)與任兩條曲線交于同一點(diǎn)，故平面上一共增加2(n-1)個(gè)區(qū)域，加上已有的a 1個(gè) 區(qū)域，一共有a 1+2(n-1)個(gè)區(qū)域。所以本題的遞推關(guān)系是a=a 1+2(n-1)，邊界條件是a1=2。平面分割問(wèn)題是競(jìng)賽中經(jīng)常觸及到的一類問(wèn)題，由于其

28、靈活多變，常常讓感到棘手，關(guān) 鍵還是要仔細(xì)分析，掌握規(guī)律。平面分割問(wèn)題應(yīng)用：(4-2-1) N條直線將平面分成多少個(gè)域？假定無(wú)三線共點(diǎ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)若上例中的直線改為鋸齒線，如圖所示，每根鋸齒線都和其他鋸齒線兩兩相交， 且無(wú)三線共點(diǎn)，試問(wèn)n條鋸齒線將平面分成多少個(gè)域？解：第n條鋸齒線每一支都和前面的n-1條鋸齒線相交于2(n-1)個(gè)點(diǎn)。將鋸齒線每一支 分成2(n-1)+1段，所以第n條鋸齒線加入看作是2n條直線問(wèn)題，但少了兩段兩線相交后延 長(zhǎng)的部分。即 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èi)的n(n=2)條直線相交于同一點(diǎn)，則這 n條直線最多能將平面分割成多少個(gè)不同的區(qū)域？解：這道題目與4-2-1的平面分割問(wèn)題十分相似，不同之處就在于線條的曲直以及是否 存在共點(diǎn)線條。由于共點(diǎn)直線的特殊性，我們決定先考慮p條相交于一點(diǎn)的直線，然后再考 慮剩下的n-p條直線(這n-p條直線符合4-2-1的條件)。首先可以直接求出p條相交于一點(diǎn)的直線將平面劃分成的區(qū)域數(shù)為2p個(gè)，然后在平面上已經(jīng)有k(k=p)條直線的基礎(chǔ)上，加上 一條直線，最多可以與k條直線相交，而每次相交都

30、會(huì)增加一個(gè)區(qū)域，與最后一條直線相交 后，由于直線可以無(wú)限延伸，還會(huì)再增加一個(gè)區(qū)域。所以f =f 1+m(mp)，邊界條件在前面 已經(jīng)計(jì)算過(guò)了，是f=2p。雖然這題看上去有兩個(gè)參數(shù)，但是在實(shí)際做題中會(huì)發(fā)現(xiàn)，本題還 是屬于帶一個(gè)參數(shù)的的遞推關(guān)系。4-3、Catalan 數(shù)Catalan數(shù)首先是由Euler在精確計(jì)算對(duì)凸n邊形的不同的對(duì)角三角形剖分的個(gè)數(shù)問(wèn)題 時(shí)得到的，它經(jīng)常出現(xiàn)在組合計(jì)數(shù)問(wèn)題中。問(wèn)題的提出：在一個(gè)凸n邊形中，通過(guò)不相交于n邊形內(nèi)部的對(duì)角線，把n邊形拆分成案，故=5。求對(duì)于Pi解：設(shè)Cn表示凸n邊形的拆分方案總數(shù)。由題目中的要求可知一個(gè)凸n邊形的任意一若干三角形，不同的拆分?jǐn)?shù)目用hn

31、表之，hn即為Catalan數(shù)。例如五邊形有如下五種拆分方條邊都必然是一個(gè)三角形的一條邊，邊P1Pn也不例外，再根據(jù)“不在 同一直線上的三點(diǎn)可以確定一個(gè)三角形，只要在P2, P3, .，Pn1 點(diǎn)中找一個(gè)點(diǎn)Pk(1k=0，(k=1，2，3，2n)的數(shù)列個(gè)數(shù)等于第n個(gè)Catalan數(shù)hn = n + 1 C1(n=0)。C n證明：n個(gè)+1和n個(gè)-1構(gòu)成的總數(shù)列個(gè)數(shù)為C 2n我們?cè)O(shè)其部分和滿足a1+a2+.+ak=0的數(shù)列個(gè)數(shù)為An，而不滿足部分和的數(shù)列個(gè)數(shù)為 U，這樣我們只要求出U，那么A自然也就求出了。n考慮n個(gè)+1和n個(gè)-1組成的不滿足數(shù)列中，必定存在從1k個(gè)部分和為a1+a2+.+ak=

32、-1 的數(shù)列，在這個(gè)部分?jǐn)?shù)列中-1的個(gè)數(shù)比+1的個(gè)數(shù)恰好多1,而剩下的+1的個(gè)數(shù)比-1的個(gè)數(shù) 恰好多1。如果將這部分的數(shù)列的每一個(gè)數(shù)取其相反數(shù)，而對(duì)剩下的數(shù)保持不變，這樣就變 成一個(gè)(n+1 )個(gè)+1 和(n-1)個(gè)-1的數(shù)列。按照這樣的一個(gè)思想，我們認(rèn)為每一個(gè)不滿足部分和的數(shù)列對(duì)應(yīng)一 個(gè)(n+1)個(gè)+1和(n-1) 個(gè)-1的數(shù)列。這樣就變成一個(gè)求(n+1)個(gè)+1和(n-1)個(gè)-1的共2n個(gè)數(shù)的數(shù)列總數(shù)。(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數(shù)一致。(4-3-2) 一場(chǎng)音樂(lè)會(huì)票價(jià)50元一張，排隊(duì)買票的顧客中有m位持有50元的鈔票，n 位持有100元的鈔票，售票處無(wú)50元的零錢，試問(wèn)有多少種排隊(duì)方案，能使購(gòu)票順利進(jìn)行， 不出現(xiàn)找不出零錢的情況？假定每位顧客只買一張。解：將50元的鈔票看做-1,而將100元的鈔票看做+1,那么答案與4-3-1 一致：1 , 一,C 2n ；如果買票的顧客進(jìn)行“實(shí)名制”排隊(duì)，那么排列方案為(n) !(n n+r C n =(2n!)/(n+1)。(4-3-3)n個(gè)1和n個(gè)0組成2n位的二進(jìn)制數(shù)，要求從左到右掃描1的累計(jì)數(shù)，不小 于0的累計(jì)數(shù)，求

34、滿足這個(gè)條件的數(shù)有多少？解：這個(gè)問(wèn)題仔細(xì)分析屬于Catalan數(shù)。(4-4-4) 一位大城市的經(jīng)理在他住所以北n個(gè)街區(qū)和以東n個(gè)街區(qū)工作。每天他要走 2n個(gè)街區(qū)去上班(如圖)如果他不穿越對(duì)角線(但可以碰到)從家到辦公室的對(duì)角線，那么 有多少條可能的道路？解：由題意可知路線不在對(duì)角線上面就在對(duì)角線下面。所以我們只要求出對(duì)角線上面的 路線數(shù)，在乘以2即可。我們將向北的方向標(biāo)識(shí)為+1，路線由n個(gè)+1和n個(gè)-1的數(shù)列，向東的方向標(biāo)識(shí)為-1,于是每條由于不能穿越對(duì)角線，所以滿足所以對(duì)角線上面的路線數(shù)滿足a1+a2+.+ak=0，1Catalan 數(shù) hnCn n + 1 2 n數(shù)列的部分和2 r 路線總

35、數(shù)為：廠三Cn(4-4-5) P=a1a2an是n個(gè)數(shù)的連乘積，依乘法結(jié)合律，不改變其順序，只用加入括 號(hào)來(lái)表示乘積的順序，試問(wèn)有多少種乘法方案？分析：令P等于n個(gè)數(shù)乘積的n-1對(duì)括號(hào)插入的不同方案數(shù)%=piPn-l + P2Pn-2+匕尺顯然噸14-4、第二類 Stirling 數(shù)在典型的遞推關(guān)系中，第二類Stirling是最不為大家所熟悉的。也正因?yàn)槿绱耍覀冇?必要先解釋一下什么是第二類Strling數(shù)。定義4-1 n個(gè)有區(qū)別的球放到m個(gè)相同的盒子中，要求無(wú)一空盒，其不同的方案數(shù)用 S(n,m)表示，稱為第二類Stirling數(shù)。下面就讓我們根據(jù)定義4-1來(lái)推導(dǎo)帶兩個(gè)參數(shù)的遞推關(guān)系一第二

36、類Stirling數(shù)。解：設(shè)有n個(gè)不同的球，分別用b1,b2,bn表示。從中取出一個(gè)球bn，bn的放法有以 下兩種：bn獨(dú)自占一個(gè)盒子；那么剩下的球只能放在m-1個(gè)盒子中，方案數(shù)為S2(n-1,m-1)；bn與別的球共占一個(gè)盒子;那么可以事先將b1,b2,bn1這n-1個(gè)球放入m個(gè)盒子中，然后再將球bn可以放入其中一個(gè)盒子中，方案數(shù)為mS2(n-1,m)。綜合以上兩種情況，可以得出第二類Stirling數(shù)定理：定理 4-1 S(n,m)=mS(n-1,m)+S(n-1,m-1) (n1,m=1)；推論4-1當(dāng)盒子是有區(qū)別的，則S2(n,m)=m!*S(n,m)邊界條件可以由定義4-1 推導(dǎo)出：

37、S(n,0)=0； S(n,1)=1； S(n,n)=1； S(n,k)=0(kn)。第二類Stirling數(shù)應(yīng)用：(4-4-1)第一類Stirling數(shù)：n個(gè)有區(qū)別的球排成k個(gè)循環(huán)排列的圓圈，要求每個(gè)循環(huán) 里至少有一個(gè)球，其不同的方案數(shù)用S(n,m)表示，稱為第一類Stirling數(shù)。解：設(shè)有n個(gè)不同的球，分別用b1,b2,bn表示。從中取出一個(gè)球bn，bn的放法有以 下兩種：某一個(gè)圓圈里只有一個(gè)球b ；那么剩下的球方案數(shù)為S(n-1,m-1)；bn與至少一個(gè)別的球在一個(gè)圓圈中；那么就變成將b1,b2,bn1這n-1個(gè)球排成k個(gè) 循環(huán)排列的圓圈的方案數(shù)并且bn可以放到b1,b2,bn- 1的

38、任何一個(gè)球的左邊，得到方案數(shù) 為(m-1)S(n-1,m)。綜合以上兩種情況，可以得出第一類Stirling數(shù)：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數(shù)直接在競(jìng)賽中較少出現(xiàn)，但它的思想方法卻在競(jìng)賽中的遞推中廣泛應(yīng) 用。就是：其核心思想類似于分治。在Catalan數(shù)中的求法中也有這樣的思想。(4-4-2) 有 n 個(gè)+1 和 n 個(gè)-1 構(gòu)成的 2n 項(xiàng)：a1，a2，.，a2n；其部分和滿足a1+a2+.+ak=0，(k=1, 2, 3，

39、.，2n)的數(shù)列個(gè)數(shù)?解：本題的Catalan數(shù)的結(jié)果證明已經(jīng)在上面給出了證明。我們應(yīng)用一下第二類Strling 數(shù)的思想方法來(lái)解決。令f(m,n)表示m個(gè)+1和n個(gè)-1時(shí)方案總數(shù)。分三種情況討論：當(dāng)n=0時(shí)表示在數(shù)列中所有的數(shù)值都為+1，故f(m,0)=1；當(dāng)mn時(shí)表示在數(shù)列中永遠(yuǎn)也滿足不了部分和a1+a2+.+ak=0，(k=1, 2, 3,.，2n),所以 f(m,n)=0；(3)其它情況我們討論第(m+n)個(gè)數(shù)(即最后一個(gè))排在在第(m+n-1)個(gè)數(shù)后面，這第(m+n)個(gè)數(shù)排列 方式分兩種情況：最后一個(gè)數(shù)為-1，則在它之前的(m+n-1)個(gè)數(shù)中有m個(gè)+1和n-1個(gè)-1，此種情況共有 f

40、(m,n-1)；最后一個(gè)數(shù)為+1，則0在它之前的(m+n-1)個(gè)數(shù)中有m-1個(gè)+1和n個(gè)-1，此種情況共有 f(m-1,n)；綜合上面的各種情況得到遞推關(guā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以后就數(shù)據(jù)超界，而且有誤差（雖然為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.顯示結(jié)果無(wú)誤差。必須至少兩個(gè)數(shù)組，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 )最大范圍：目標(biāo)點(diǎn)與出發(fā)點(diǎn)之差不超過(guò)4000程序6-2： 高精度計(jì)算部分有優(yōu)化typeTarr=array0.1000 of byte;Tnum=array1.4 of Tarr;Tlen=array1.4 of word;varstart,finish:longint;出發(fā)點(diǎn)和目標(biāo)點(diǎn)num:Tnum;num1num3 分別保存到達(dá)相鄰三個(gè)蜂 巢的路徑數(shù)；num4 是用于交換的臨時(shí)變量len:Tlen;計(jì)算長(zhǎng)度leni表示numi的長(zhǎng)度procedure DataInit; 數(shù)據(jù)初始化var i:integer;b

45、eginfor i:=1 to 3 dobeginfillchar(numi,sizeof(numi),0);num i1 :=1;leni:=1;end;end;procedure Add;高精度加法運(yùn)算：num3=num1+num2var i,carry:word;carry 是進(jìn)位數(shù)字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);長(zhǎng)度加 1num3i+1:=carry;end;end;procedure Work;求從出發(fā)點(diǎn)到目標(biāo)點(diǎn)的路 徑總數(shù)var i:longint;beginnum11:=1;num21:=1;for i:=start+2 to finish dobeginAdd;高精度加法運(yùn)算：num3=num1+num2num4:=num1;num1:=num2;num2:=num3;num3:=num4;len4:=len1;move(len2, en1,6);end;end;procedure Out;輸出結(jié)果 var i:integer;beginfor i:=len2 downto 1 do

47、write(num2i);writeln;end;beginDataInit; 數(shù)據(jù)初始化write(Input:);readln(start,finish);Work; 求從出發(fā)點(diǎn)到目標(biāo)點(diǎn)的路徑總數(shù)Out;輸出結(jié)果end.程序6-3-1：搜索算法，用k記錄售票處50元鈔票的數(shù)目，初始時(shí)k=0，若某人手持100元而售票處k=0則回溯，否則繼續(xù)遞歸搜索。若手持50元鈔票的人都買完票，則總排列數(shù)加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開(kāi)始取100元的if k0 then 找的開(kāi)零錢 begindec(k);dfs(i+1);inc(k);endendendend;beginreadln(n);m:=0;k:=0;dfs(1);writeln(total:10:0);end.程序6-3-2：遞歸倒推算法，遞推關(guān)系應(yīng)用第二類Strling數(shù)的思想方法，為f (m, n)= 0m n1n

49、 = 0f (m, n 1) + f (m 1, n 1)其它情況速度極慢，因?yàn)檫f歸展開(kāi)有很多無(wú)效數(shù)據(jù)，這些數(shù)據(jù)產(chǎn)生不但使時(shí)間浪費(fèi)，且占據(jù)大量 空間。效率極低。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); 讀取人這次取多少?gòu)埮芖ork(a2-Youget);end;begin 主程序write(Total card:);readln(total);Youget:=(total-1) div 2; 通過(guò)限定Youget給計(jì)算機(jī)可以取的最大牌數(shù)限界Work(total); 對(duì)total張牌設(shè)計(jì)一種取法使計(jì)算機(jī)能取到最后一張牌writeln(I win!);readln;end.(6-5)問(wèn)題描述：用關(guān)系“”和日將

52、3個(gè)數(shù)A，B，C依序排列有13種不同的序關(guān)系：A=B=C，A=BC，AB=C，ABC，ACB，A=CB，BA=C，BAC，B=CA，CA=B，CAB，CBA。編程任務(wù)：求出給定的N個(gè)數(shù)(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;插入一個(gè)新值，可得到t種新的(m,t)方案，所以F(m-1,t-1)xt種新的(m,n

53、)方案。(2)(m-1,t)方案，添上一個(gè)與其他t種值中的某一種相同的數(shù)，組成(m,t)方案。類似(1)， 對(duì)于每種(m-1,t)方案，分別在點(diǎn)1點(diǎn)t處添一個(gè)數(shù)，得到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 )問(wèn)題描述：一個(gè)核電站有N個(gè)放核物質(zhì)的坑，坑排列在一條直線上。如果連續(xù)M個(gè)坑中放入核物 質(zhì)，則會(huì)發(fā)生爆炸，于是，在某些坑中可能不放核物質(zhì)。任

56、務(wù)：對(duì)于給定的N和M，求不發(fā)生爆炸的放置核物質(zhì)的方案總數(shù)輸入：輸入文件只一行，兩個(gè)正整數(shù)N，M( 1N50，2M5)輸出：輸出文件只有一個(gè)正整數(shù)S，表示方案總數(shù)。Sample Input Sample Output4 313解題思路：利用第二類Stirling的思想方法，設(shè)N個(gè)坑不會(huì)發(fā)生爆炸的方案數(shù)為f(n)；討 論在前面n-1個(gè)坑的左面的第n個(gè)坑的情況：當(dāng)?shù)趎個(gè)坑的右邊已有了 m-1個(gè)連續(xù)的坑，那么第n個(gè)坑只能不放核物質(zhì)，所以第n-m+1n這m個(gè)坑的狀態(tài)是固定的，所以第一種情況的方案數(shù)為f(n-1-m)；其它情況第n個(gè)坑可以放也可以不放。那么就是前n-1個(gè)坑的總方案數(shù)f(n-1)減去第一種情

57、況 f(n-1-m)再乘以 2，即 2* (f(n-1)-f(n-1-m)兩種情況相加得到遞推關(guān)系：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 )問(wèn)題描述：設(shè)有一個(gè) 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)問(wèn)題描