全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽培訓(xùn)習(xí)題與解答

（中學(xué)高級(jí)本）

目錄

習(xí)題篇與解析篇

第一章回溯法

1.1馬攔過河卒

1.2出棧序列統(tǒng)計(jì)

1.3算24點(diǎn)

1.4冗余依賴

1.5走迷宮

1.6單向雙軌道

1.7組合的輸出

1.8售貨員的難題

1.9駕車旅游

1.10關(guān)路燈

第二章遞規(guī)與遞推

2.1遍歷問題

2.2產(chǎn)生數(shù)

2.3出棧序列統(tǒng)計(jì)

2.4計(jì)數(shù)器

2.5諸侯安置

2.6括號(hào)序列

2.7新漢諾塔

2.8排序集合

2.9青蛙過河

2.10電話號(hào)碼

2.11編碼

第三章貪心法

3.1排隊(duì)接水

3.2智力大沖浪

3.3取火柴游戲

3.4加工生產(chǎn)調(diào)度

3.5最大乘積

3.6種樹

3.7餐巾

3.8馬拉松接力賽

3.9線性存儲(chǔ)問題

3.10扇區(qū)填數(shù)

第四章分治

4.1取余運(yùn)算

4.2地毯填補(bǔ)問題

4.3平面上的最接近點(diǎn)對(duì)

4.4求方程的根

4.5小車問題

4.6黑白棋子的移動(dòng)

4.7麥森數(shù)(NOIP2003)

4.8旅行家的預(yù)算(NOIP1999)

4.9飛行計(jì)劃

第五章圖

5.1醫(yī)院設(shè)置

5.2工程規(guī)劃

5.3服務(wù)器儲(chǔ)存信息問題

5.4間諜網(wǎng)絡(luò)(AGE)

5.5宮廷守衛(wèi)

5.6K-聯(lián)賽

5.7機(jī)器調(diào)度

5.8公路修建

5.9速度限制

第六章樹

6.1排序二叉樹

6.2樹的重量

6.3信號(hào)放大器

6.4“訪問”術(shù)館

6.5聚會(huì)的快樂

6.6重建道路

6.7有線電視網(wǎng)

第七章搜索

7.1最多因子數(shù)

7.2黑白棋游戲

7.3縱橫填字游戲

7.4魔術(shù)數(shù)字游戲

7.5魔板

7.6三維掃描

7.7拼字游戲

7.8公路修建

7.9單詞游戲

第八章動(dòng)態(tài)規(guī)劃

8.1字串距離

8.2血緣關(guān)系

8.3尼克的任務(wù)

8.4書的復(fù)制

8.5多米諾骨

8.6平板涂色

8.7三角形牧場(chǎng)

8.8分組

第九章數(shù)學(xué)問題

9.1多項(xiàng)式展開系數(shù)

9.2兩數(shù)之和

9.3盒子與球

9.4取數(shù)游戲

9.5磁盤碎片整理

9.6歐幾里德的游戲

9.7百事世界杯之旅

9.8倒酒

9.9班級(jí)聚會(huì)

第十章雜題

10.1排序

10.2木棍加工

10.3三角形

10.4多邊形面積

10.5網(wǎng)線切割

10.6最接近的分?jǐn)?shù)

10.7切孔機(jī)

10.8栓狗方案

10.9城市街道交通費(fèi)系統(tǒng)

10.10魔鬼之城

10.11可見矩形

第一章回溯法

1.1馬攔過河卒

源程序名knight.???(pas,c,cpp)

可執(zhí)行文件名knight.exe

輸入文件名knight.in

輸出文件名knight.out

【問題描述】

棋盤上A點(diǎn)有一個(gè)過河卒，需要走到目標(biāo)B點(diǎn)。卒行走的規(guī)則：可以向下、或者向右。同

時(shí)在棋盤上C點(diǎn)有一個(gè)對(duì)方的馬，該馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為對(duì)方馬的控

制點(diǎn)。因此稱之為“馬攔過河卒”。

棋盤用坐標(biāo)表示，A點(diǎn)(0,0)、B點(diǎn)(n,m)(n,m為不超過15的整數(shù))，同樣馬的位置坐標(biāo)是需

要給出的。現(xiàn)在要求你計(jì)算出卒從A點(diǎn)能夠到達(dá)B點(diǎn)的路徑的條數(shù)，假設(shè)馬的位置是固定

不動(dòng)的，并不是卒走一步馬走一步。

【輸入】

一行四個(gè)數(shù)據(jù)，分別表示B點(diǎn)坐標(biāo)和馬的坐標(biāo)。

【輸出】

一個(gè)數(shù)據(jù)，表示所有的路徑條數(shù)。

【樣例】

knight.inknight.out

66336

【算法分析】

從起點(diǎn)開始往下走(只有兩個(gè)方向可以走)，如果某個(gè)方向可以走再繼續(xù)下一步，直到終

點(diǎn)，此時(shí)計(jì)數(shù)。最后輸出所有的路徑數(shù)。這種方法可以找出所有可能走法，如果要輸出這些

走法的話這種方法最合適了，但是本題只要求輸出總的路徑的條數(shù)，當(dāng)棋盤比較大時(shí)，本程

序執(zhí)行會(huì)超時(shí)，此時(shí)最好能找出相應(yīng)的遞推公式更合適，詳見后面的遞推章節(jié)。

1.2出棧序列統(tǒng)計(jì)

源程序名stack1.???(pas,c:，Cpp)

可執(zhí)行文件名stackl.exe

輸入文件名stack1.in

輸出文件名stack1.out

【問題描述】

棧是常用的一種數(shù)據(jù)結(jié)構(gòu)，有n令元素在棧頂端一側(cè)等待進(jìn)棧，棧頂端另一側(cè)是出棧序

列。你已經(jīng)知道棧的操作有兩?種：push和pop,前者是將一個(gè)元素進(jìn)棧，后者是將棧頂元

素彈出?，F(xiàn)在要使用這兩種操作，由一個(gè)操作序列可以得到一系列的輸出序列。請(qǐng)你編程求

出對(duì)于給定的n,計(jì)算并輸出由操作數(shù)序列1,2,…，n,經(jīng)過一系列操作可能得到的輸出

序列總數(shù)。

【輸入】

一個(gè)整數(shù)n（l<=n<=15）

【輸出】

?個(gè)整數(shù)，即可能輸出序列的總數(shù)目。

【樣例】

stack1.instack1.out

35

【算法分析】

先了解棧的兩種基本操作，進(jìn)棧push就是將元素放入棧頂，棧頂指針上移一位，等待

進(jìn)棧隊(duì)列也上移一位，出棧pop是將棧頂元素彈出，同時(shí)棧頂指針下移一位。

用一個(gè)過程采模擬進(jìn)出棧的過程，可以通過循環(huán)加遞歸來實(shí)現(xiàn)回溯：重復(fù)這樣的過程，

如果可以進(jìn)棧則進(jìn)一個(gè)元素，如果可以出棧則出一個(gè)元素。就這樣一個(gè)-?個(gè)地試探下去，當(dāng)

出棧元素個(gè)數(shù)達(dá)到n時(shí)就計(jì)數(shù)一次（這也是遞歸調(diào)用結(jié)束的條件）。

1.3算24點(diǎn)

源程序名point24.???(pas,c,cpp)

可執(zhí)行文件名point24.exe

輸入文件名point24.in

輸出文件名point24.out

【問題描述】

幾十年前全世界就流行一種數(shù)字游戲，至今仍有人樂此不疲.在中國(guó)我們把這種游戲稱

為“算24點(diǎn)”。您作為游戲者將得到4個(gè)1~9之間的自然數(shù)作為操作數(shù)，而您的任務(wù)是對(duì)這

4個(gè)操作數(shù)進(jìn)行適當(dāng)?shù)乃阈g(shù)運(yùn)算，要求運(yùn)算結(jié)果等于24。

您可以使用的運(yùn)算只有：+,-，*，/,您還可以使用（）來改變運(yùn)算順序。注意：所有

的中間結(jié)果須是整數(shù)，所以一些除法運(yùn)算是不允許的（例如，（2*2）/4是合法的，2*（2/4）是

不合法的）。下面我們給出?個(gè)游戲的具體例子：

若給出的4個(gè)操作數(shù)是：1、2、3、7,則一種可能的解答是1+2+3*7=24。

【輸入】

只有一行，四個(gè)1到9之間的自然數(shù)。

【輸出】

如果有解的話，只要輸出一個(gè)解，輸出的是三行數(shù)據(jù)，分別表示運(yùn)算的步驟。其中第一

行是輸入的兩個(gè)數(shù)和一個(gè)運(yùn)算符和運(yùn)算后的結(jié)果，第二行是第一行的結(jié)果和一個(gè)輸入的數(shù)

據(jù)、運(yùn)算符、運(yùn)算后的結(jié)果；第三行是第二行的結(jié)果和輸入的?個(gè)數(shù)、運(yùn)算符和“=24”。

如果兩個(gè)操作數(shù)有大小的話則先輸出大的。

如果沒有解則輸出“Noanswer!”

【樣例】

point24.inpoint24.out

12372+1=3

7*3=21

21+3=24

【算法分析】

計(jì)算24點(diǎn)主要應(yīng)用四種運(yùn)算.開始狀態(tài)有四個(gè)操作數(shù)，一個(gè)運(yùn)算符對(duì)應(yīng)兩個(gè)操作數(shù)，

所以?開始選擇兩個(gè)操作數(shù)分別對(duì)四個(gè)操作符進(jìn)行循環(huán)檢測(cè)，每一次運(yùn)算后產(chǎn)生了新的數(shù)，

兩個(gè)數(shù)運(yùn)算變成一個(gè)數(shù)，整體是少了一個(gè)操作數(shù)，所以四個(gè)數(shù)最終是三次運(yùn)算。由于操作的

層數(shù)比較少（只有三層），所以可以用回溯的算法來進(jìn)行檢測(cè)，當(dāng)找到?個(gè)解時(shí)便結(jié)束查找。

如果所有的情況都找過后仍然沒有，則輸出無解的信息。

1.4冗余依賴

源程序名redund.???(pas,c,cpp)

可執(zhí)行文件名redund.exe

輸入文件名redund.in

輸出文件名redund.out

【問題描述】

在設(shè)計(jì)關(guān)系數(shù)據(jù)庫(kù)的表格時(shí)，術(shù)語“函數(shù)依賴"（FD）被用來表示不同域之間的關(guān)系。

函數(shù)依賴是描述一個(gè)集合中的域的值與另一個(gè)集合中的域的值之間的關(guān)系。記號(hào)X->Y被用

來表示當(dāng)集合X中的域被賦值后，集合Y的域就可以確定相應(yīng)的值。例如，一個(gè)數(shù)據(jù)表格

包含“社會(huì)治安編號(hào)”（S）、“姓名”（N）、“地址”（A）、“電話”（P）的域，并且每個(gè)人都

與某個(gè)特定的互不相同的S值相對(duì)應(yīng)，根據(jù)域S就可以確定域N、A、P的值。這就記作

S->NAP,

寫一個(gè)程序以找出?組依賴中所有的冗余依賴。一個(gè)依賴是冗余的是指它可以通過組里

的其他依賴得到。例如，如果組里包括依賴A->B、B->C和A->C,那么第三個(gè)依賴是冗余

的，因?yàn)橛駽可以用前兩個(gè)依賴得到（域A確定了域B的值，同樣域B確定了域C的值）。

在A->B、B->C、C->A、A->C,C->B和B->A中，所有的依賴都是冗余的。

現(xiàn)在要求你編寫一個(gè)程序，從給定的依賴關(guān)系中找出冗余的。

【輸入】

輸A的文件第一行是一個(gè)不超過100的整數(shù)n,它表示文件中函數(shù)依賴的個(gè)數(shù)。從第二

行起每一行是一個(gè)函數(shù)依賴且互不重復(fù)，每行包含用字符“-”和“>”隔開的非空域列表。

列表月包含大寫的字母，函數(shù)依賴的數(shù)據(jù)行中不包括空格和制表符，不會(huì)出現(xiàn)“平凡”冗余

依賴（如A->A）。雖然文件中沒有對(duì)函數(shù)依賴編號(hào)，但其順序就是編號(hào)1到n。

【輸出】

每一個(gè)冗余依賴，以及其他依賴的一個(gè)序列以說明該依賴是冗余的，先是一個(gè)FD,然

后是依賴函數(shù)號(hào)，接著是"isredundantusingFDs：”最后是說明的序列號(hào)。

如果許多函數(shù)依賴的序列都能被用來說明個(gè)依賴是冗余的，則輸出其中最短的證明序

列。如果這些函數(shù)依賴中不包含冗余依賴，則輸出“NoredundantFDs”信息。

【樣例1】【樣例2】

redund.inredund.outredund.inredund.out

3FD3isredundantusingFDs:126FD3isredundant

usingFDs:1

A->BD｛即C可以通過1、2得到｝P->RSTFD5isredundant

usingFDs:462

BD->CVRT->SQP

A->CPS->T

Q->TR

QS->P

SR->V

【算法分析】

一個(gè)依賴冗余，就是說它可以山其他依賴推導(dǎo)出來。如何判斷一個(gè)依賴能否被其他依賴

推導(dǎo)出來呢？假設(shè)判斷的依賴為“a->b”，先找出所有形式為的依賴，再由*開始找

相關(guān)依賴，直到出現(xiàn)“#->b”為止（這里a、b、*、#都表示任意一個(gè)域名）。

如何實(shí)現(xiàn)這種查找呢？可以通過筒單的回溯來完成。只是找出冗余（如果有的話）還不說

明工作就已結(jié)束，要到找出所有的能夠推導(dǎo)出b的依賴序列，選出其中長(zhǎng)度最短的（最短的

也可能并不惟一，因此本題答案有可能并不惟）最短的證明序列中一定不存在多余的依

賴，如果不是最短的證明序列，那么該證明序列中就有可能還有冗余依賴。

1.5走迷宮

源程序名maze.???(pas,c,cpp)

可執(zhí)行文件名maze.exe

輸入文件名maze.in

輸出文件名maze,out

【問題描述】

有一個(gè)m*n格的迷宮（表示有m行、n列），其中有可走的也有不可走的，如果用1表示

可以走，0表示不可以走，文件讀入這m*n個(gè)數(shù)據(jù)和起始點(diǎn)、結(jié)束點(diǎn)（起始點(diǎn)和結(jié)束點(diǎn)都是

用兩個(gè)數(shù)據(jù)來描述的，分別表示這個(gè)點(diǎn)的行號(hào)和列號(hào)）?，F(xiàn)在要你編程找出所有可行的道路,

要求所走的路中沒有重復(fù)的點(diǎn)，走時(shí)只能是上下左右四個(gè)方向。如果??條路都不可行，則輸

出相應(yīng)信息（用-1表示無路）。

【輸入】

第一行是兩個(gè)數(shù)m,n（l<m,n<15）,接下來是m行n列由1和0組成的數(shù)據(jù)，最后兩

行是起始點(diǎn)和結(jié)束點(diǎn)。

【輸出】

所有可行的路徑，描述?個(gè)點(diǎn)時(shí)用（x,y）的形式，除開始點(diǎn)外，其他的都要用“一>”

表示方向。

如果沒有一條可行的路則輸出-1。

【樣例】

maze.in

56

100101

111111

001110

111110

111011

11

56

maze.out

(1,2)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)

(l,l)->(2,l)->(2,2)->(2,3)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(2,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)

(l,l)->(2,l)->(2,2)->(2,3)->(2,4)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)

(l,l)->(2,l)->(2,2)->(2,3)->(3,3)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(3,4)->(4,4)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(2,4)->(2,5)->(3,5)->(4,5)->(5,5)->(5,6)

(l,l)->(2.1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(3,4)->(3,5)->(4,5)->(5,5)->(5,6)

(1,1)->(2,1)->(2,2)->(2,3)->(3,3)->(4,3)->(4,4)->(4,5)->(5,5)->(5,6)

【算法分析】

用一個(gè)a數(shù)組來存放迷宮可走的情況，另外用?個(gè)數(shù)組b來存放哪些點(diǎn)走過了。每個(gè)點(diǎn)

用兩個(gè)數(shù)字來描述，一個(gè)表示行號(hào)，另一個(gè)表示列號(hào)。對(duì)于某?個(gè)點(diǎn)(x,y),四個(gè)可能走的

方向的點(diǎn)描述如下表：

1

4x,y2

3

對(duì)應(yīng)的位置為：(x-l,y),(x,y+1),(x+l,y),(x,y-l)?所以每個(gè)點(diǎn)都要試探四個(gè)方向,如果

沒有走過(數(shù)組b相應(yīng)的點(diǎn)的值為0)且可以走(數(shù)組a相應(yīng)點(diǎn)的值為1)同時(shí)不越界，就走過去,

再看有沒有到達(dá)終點(diǎn)，到了終點(diǎn)則輸出所走的路，否則繼續(xù)走下去。

這個(gè)查找過程用search來描述如下：

proceduresearch(x,y,b,p)；｛x,y表示某一個(gè)點(diǎn)，b是已經(jīng)過的點(diǎn)的情況，p是已走過的路｝

begin

fori:=lto4do｛分別對(duì)4個(gè)點(diǎn)進(jìn)行試探｝

begin

先記住當(dāng)前點(diǎn)的位置，已走過的情況和走過的路；

如果第i個(gè)點(diǎn)(xl,yl)可以走，則走過去；

如果已達(dá)終點(diǎn)，則輸出所走的路徑并置有路可走的信息，

否則繼續(xù)從新的點(diǎn)往下查找search(xLyl,bl,pl)；

end；

end：

【思考與提高】

該程序通過引進(jìn)新的變量和數(shù)組來繼續(xù)新的查找，如果不引進(jìn)新的變量和數(shù)組，那么每

一次返回時(shí)要將原來的值還原才行，如果那樣，程序應(yīng)如何修改?其實(shí)那樣更加符合回溯的

思想——換條路再試。這類問題也可以歸為搜索的問題，如果m和n的值相對(duì)比較大，則

解可能很多，若題目只要找到一條路就結(jié)束程序時(shí)，在程序的輸出部分后面加上一個(gè)halt

就行了。

有些情況很明顯是無解的，如從起點(diǎn)到終點(diǎn)的矩形中有一行或一列都是為0的，明顯道

路不通，對(duì)于這種情況要很快地“剪掉”多余分枝得出結(jié)論，這就是搜索里所說的“剪枝”。

從起點(diǎn)開始往下的一層層的結(jié)點(diǎn)，看起來如同樹枝一樣，對(duì)于其中的“枯枝”——明顯無用

的節(jié)點(diǎn)可以先行“剪掉”，從而提高搜索速度。

1.6單向雙軌道

源程序名track.???(pas,c,cpp)

可執(zhí)行文件名track.exe

輸入文件名track.in

輸出文件名track.out

【問題描述】

如圖所示1,某火車站有B,C兩個(gè)調(diào)度站，左邊入口A處有n輛火車等待進(jìn)站（從左到

右以a、b、c、d編號(hào)），右邊是出口D,規(guī)定在這一段，火車從A進(jìn)入經(jīng)過B、C只能從左

向右單向開，并且B、C調(diào)度站不限定所能停放的車輛數(shù)。

從文件輸入n及n個(gè)小寫字母的一個(gè)排列，該排列表示火車在出口D處形成的從左到

右的火車編號(hào)序列。輸出為一系列操作過程，每行形如“hLR”的字母序列，其中h為

火車編號(hào)，L為h車原先所在位置（位置都以A、B、C、D表示），R為新位置?；蛘咻敵觥甆O'

表示不能完成這樣的調(diào)度。

【輸入】

一個(gè)數(shù)n（l〈n<27）及由n個(gè)小寫字母組成的字符串。

【輸出】

可以調(diào)度則輸出最短的調(diào)度序列，不可以調(diào)度時(shí)則輸出‘NO'。

【樣例】

track.intrack.out

3cAB

cbabAC

aAD

bCD

cBD

【算法分析】

這是一道類似于棧的操作題目，只不過是有兩個(gè)棧B和C可以操作，而對(duì)于A序列里

的元素，既可以進(jìn)入B,也可以進(jìn)入C,或直接到D。解決問題可以從D序列出發(fā)反過來看,

當(dāng)前要到D的字符在哪里，如果在A,再看它前面有沒有字符，如果有，先讓它們進(jìn)棧（B

或C）,否則直接到D；如果在B,看是否是棧頂元素，如果是，直接到D,否則將上面的

字符進(jìn)C；如果在C,看是否是棧頂元素，如果是，直接到D,否則無法進(jìn)行操作，因?yàn)橹?/p>

能向右不能向左，這時(shí)要回溯。如果所有的情況都檢測(cè)過，某個(gè)字符不能進(jìn)行到D的操作,

則輸出無解信息。

由于A里的非直接進(jìn)入D的字符可以進(jìn)入B或C,可以跟二進(jìn)制建立起對(duì)應(yīng)關(guān)系，將

所有情況列舉一遍，再找出其中步驟最少的輸出。

1.7組合的輸出

源程序名track.???(pas,c,cpp)

可執(zhí)行文件名track.exe

輸入文件名track.in

輸出文件名track.out

【問題描述】

排列與組合是常用的數(shù)學(xué)方法，其中組合就是從n個(gè)元素中抽出r個(gè)元素(不分順序且

r<=n),我們可以簡(jiǎn)單地將n個(gè)元素理解為自然數(shù)1,2,n,從中任取r個(gè)數(shù)。

現(xiàn)要求你不用遞歸的方法輸出所有組合。

例如n=5,r=3,所有組合為：

123124125134135145234235245345

【輸入】

一行兩個(gè)自然數(shù)n、r(l<n<21,l<=r<=n)o

【輸出】

所有的組合，每一個(gè)組合占一行且其中的元素按由小到大的順序排列，每個(gè)元素占三個(gè)

字符的位置，所有的組合也按字典順序。

【樣例】

compages.incompages.out

53123

124

125

134

135

145

234

235

245

345

【算法分析】

如果通過循環(huán)加遞歸來實(shí)現(xiàn)回溯比較簡(jiǎn)單，相應(yīng)程序?yàn)椋?/p>

constmax=20;

vara:array[0..max]ofinteger;

n,r:l..max;

procedurecompages(k:integer);｛選取第k個(gè)元素｝

vari,j:integer;

begin

｛當(dāng)前所選元素最小為前一個(gè)元素加1，最大為n-(r-k),因?yàn)楹竺孢€有(r-k)個(gè)元素要選取，至

少為每次選取留一個(gè)｝

fori:=a[k-l]H-lton-(r-k)dobegin

a[k]:=i;｛選取一個(gè)元素｝

ifk=rthenbegin

forj:=ltordowrite(a[j]:3);

writein;

end

elsecompages(k-t-l)；

end;

end;

begin｛main｝

readln(n,r);

compages(l);｛從第一個(gè)元素開始選取給合數(shù)｝

end.

本題要求不用遞歸來實(shí)現(xiàn)回溯，關(guān)鍵要定好回溯的條件。如果選取第i個(gè)元素時(shí)選擇了

a[i],根據(jù)輸出條件應(yīng)有a[i]-i<=n-r,如果不滿足這個(gè)條件說明當(dāng)前第i個(gè)元素已再無數(shù)可

取，要進(jìn)行回溯，將其值減1，退到上一步將上一步原來的值再增加1,重復(fù)上述過程。當(dāng)

全部選取完時(shí)，i回到了0,a[0]的值增加1后變?yōu)?,這是整個(gè)選取過程結(jié)束的條件。

1.8售貨員的難題

源程序名salesman.???(pas,c,cpp)

可執(zhí)行文件名salesman.exe

輸入文件名salesman.in

輸出文件名salesman.out

【問題描述】

某鄉(xiāng)有n個(gè)村莊(l<n<40),有一個(gè)售貨員，他要到各個(gè)村莊去售貨，各村莊之間的路程

s(0<s<1000)是已知的，且A村到B村與B村到A村的路大多不同。為了提高效率，他從商

店出發(fā)到每個(gè)村莊一次，然后返回商店所在的村，假設(shè)商店所在的村莊為1，他不知道選擇

什么樣的路線才能使所走的路程最短。請(qǐng)你幫他選擇?條最短的路。

【輸入】

村莊數(shù)n和各村之間的路程(均是整數(shù))。

【輸出】

最短的路程。

【樣例】

salesman.insalesman.out

3｛村莊數(shù)｝3

021｛村莊1到各村的路程｝

102｛村莊2到各村的路程｝

210｛村莊3到各村的路程｝

【算法分析】

題目給定的村莊數(shù)不多(W40),所以可以用回溯的方法，從起點(diǎn)(第一個(gè)村莊)出發(fā)找出

所有經(jīng)過其他所有村莊的回路，計(jì)算其中的最短路程。當(dāng)村莊數(shù)n比較大時(shí)這種方法就不太

適用了。

用一個(gè)過程road（step,line：byte）來描述走的狀況，其中step是當(dāng)前已到村莊數(shù)、line

是當(dāng)前所在的村莊。如果step=n,下面只能回起點(diǎn)了，直接看第line個(gè)村莊到第一個(gè)村莊

的路程加上己走的總路程，如果比最小值還小則替換最小值（要保存路徑的話也可保存，這

是回溯算法的優(yōu)點(diǎn)，考慮到達(dá)最小值的路徑可能不止?條，不便于測(cè)試，題目沒要求輸出路

徑）。如果step還小于n,那么將還沒有到過的村莊一個(gè)一個(gè)地試過去，再調(diào)用下一步

road（step+l,新到的村莊號(hào)）。

1.9駕車旅游

源程序名tour.???(pas,c,cpp)

可執(zhí)行文件名tour.exe

輸入文件名tour.in

輸出文件名tour.out

【問題描述】

如今許多普通百姓家有了私家車，一些人喜愛自己駕車從一個(gè)城市到另一個(gè)城市旅游。

自己駕車旅游時(shí)總會(huì)碰到加油和吃飯的問題，在出發(fā)之前，駕車人總要想方設(shè)法得到從一個(gè)

城市到另一個(gè)城市路線上的加油站的列表，列表中包括了所有加油站的位置及其每升的油價(jià)

（如3.25元/L）。駕車者-一般都有以下的習(xí)慣：

（1）除非汽車無法用油箱里的汽油達(dá)到下一個(gè)加油站或目的地，在油箱里還有不少于

最大容量一半的汽油時(shí)，駕駛員從不在加油站停下來；

（2）在第一個(gè)停下的加油站總是將油箱加滿；

（3）在加油站加油的同時(shí)，買快餐等吃的東西花去20元。

（4）從起始城市出發(fā)時(shí)油箱總是滿的。

（5）加油站付錢總是精確到0.1元（四舍五入）。

（6）駕車者都知道自己的汽車每升汽油能夠行駛的里程數(shù)。

現(xiàn)在要你幫忙做的就是編寫一個(gè)程序,計(jì)算出駕車從一個(gè)城市到另一個(gè)城市的旅游在加

油和吃飯方面最少的費(fèi)用。

【輸入】

第一行是一個(gè)實(shí)數(shù)，是從出發(fā)地到目的地的距離（單位：km）。

第二行是三個(gè)實(shí)數(shù)和一個(gè)整數(shù)，其中第一個(gè)實(shí)數(shù)是汽車油箱的最大容量（單位：I。）；第

二個(gè)實(shí)數(shù)是汽車每升油能行駛的公里數(shù)；第三個(gè)實(shí)數(shù)是汽車在出發(fā)地加滿油箱時(shí)的費(fèi)用（單

位元）；一個(gè)整數(shù)是1到50間的數(shù)，表示從出發(fā)地到目的地線路上加油站的數(shù)目。

接下來n行都是兩個(gè)實(shí)數(shù)，第一個(gè)數(shù)表示從出發(fā)地到某一個(gè)加油站的距離（單位：km）；

第二個(gè)實(shí)數(shù)表示該加油站汽油的價(jià)格（單位：元）。

數(shù)據(jù)項(xiàng)中的每個(gè)數(shù)據(jù)都是正確的，不需判錯(cuò)。一條線路上的加油站根據(jù)其到出發(fā)地的距

離遞增排列并且都不會(huì)大于從出發(fā)地到目的地的距離。

【輸出】

就一個(gè)數(shù)據(jù)，是精確到0.1元的最小的加油和吃飯費(fèi)用

【樣例】

tour.intour.out

600379.6

408.51283

2003.52

3503.45

500365

【算法分析】

駕車者從出發(fā)地出發(fā)后對(duì)于每個(gè)加油站都可能有兩種操作，一是進(jìn)去加油買食品，二是

不進(jìn)去繼續(xù)前行（如果當(dāng)前汽車的余油可以的話），這樣有n個(gè)加油站最多可能有2n種選擇。

由于加油站數(shù)目不太多，可以采用回溯的算法來解決問題。從第一個(gè)加油站開始，依次選擇

所要停下的下一個(gè)加油站，從而找出總費(fèi)用最少的方案，加油站數(shù)目最多為50,這樣回溯

不會(huì)進(jìn)行得很深。在選擇下一個(gè)要停下的加油站時(shí)比較麻煩，不能完全一個(gè)一個(gè)地試過去，

這樣時(shí)間太長(zhǎng)?？梢杂眠@樣的方法：先找出第一個(gè)要停下的加油站，判斷其后面的加油站是

否可以到達(dá)，如果不可到達(dá)就必須在這里停下來加油；否則就找出可以到達(dá)但如果只用一半

汽油則無法到達(dá)的所有加油站，依次進(jìn)行停靠。

1.10關(guān)路燈

源程序名power.???(pas,c,cpp)

可執(zhí)行文件名power.exe

輸入文件名power.in

輸出文件名power.out

【問題描述】

某一村莊在條路線匕安裝了n盞路燈，每盞燈的功率有大有?。赐?段時(shí)間內(nèi)消耗

的電量有多有少）。老張就住在這條路中間某一,路燈旁，他有一項(xiàng)工作就是每天早上天亮?xí)r

一盞一盞地關(guān)掉這些路燈。

為了給村里節(jié)省電費(fèi)，老張記錄下了每盞路燈的位置和功率，他每次關(guān)燈時(shí)也都是盡快

地去關(guān)，但是老張不知道怎樣去關(guān)燈才能夠最節(jié)省電。他每天都是在天亮?xí)r首先關(guān)掉自己所

處位置的路燈，然后可以向左也可以向右去關(guān)燈。開始他以為先算一下左邊路燈的總功率再

算一下右邊路燈的總功率，然后選擇先關(guān)掉功率大的一邊，再回過頭來關(guān)掉另一邊的路燈，

而事實(shí)并非如此，因?yàn)樵陉P(guān)的過程中適當(dāng)?shù)卣{(diào)頭有可能會(huì)更省一些。

現(xiàn)在已知老張走的速度為lm/s,每個(gè)路燈的位置（是一,個(gè)整數(shù)，即距路線起點(diǎn)的距離,

單位：m）、功率（W）,老張關(guān)燈所用的時(shí)間很短而可以忽略不計(jì)。

請(qǐng)你為老張編-程序來安排關(guān)燈的順序，使從老張開始關(guān)燈時(shí)刻算起所有燈消耗電最少

（燈關(guān)掉后便不再消耗電了）。

【輸入】

文件第一行是兩個(gè)數(shù)字n（0<n<50,表示路燈的總數(shù)）和c（l<=c<=n老張所處位置的路燈

號(hào)）；

接下來n行，每行兩個(gè)數(shù)據(jù)，表示第1盞到第n盞路燈的位置和功率。

【輸出】

一個(gè)數(shù)據(jù)，即最少的功耗（單位：J,U=lW?s）?

【樣例】

power,inpower.out

53270｛此時(shí)關(guān)燈順序?yàn)?4215,不必輸出這個(gè)關(guān)燈順序｝

210

320

520

630

810

【算法分析】

設(shè)老張開始所在位置為C,以起始點(diǎn)c為分界點(diǎn)，算出左右兩部分總的功率p_left和

p_right,再來分別看向左與向右的情況。

向左走時(shí)，相應(yīng)地可以減小左邊應(yīng)費(fèi)的功，而增加右邊應(yīng)費(fèi)的功，如果到一?個(gè)點(diǎn)（一盞

路燈處）所要時(shí)間為t,減少的功為（p_left+w[i]）*t,增加的功為p_right*2to

向右走時(shí)，相應(yīng)地可以減小右邊應(yīng)費(fèi)的功，而增加左邊應(yīng)費(fèi)的功，如果到一個(gè)點(diǎn)（一盞

路燈處）所要時(shí)間為t,減少的功為（p_righ+w[i]）*t，增加的功為p_left*2t。

比較向左與向右的情況，找出比較好的一種確定方法。大部分情況能夠解出最小值，但

不能求出所有情況下最佳的解。

對(duì)于每一個(gè)所處位置，都可以選擇向左或向右，不管是向左還是向右，相應(yīng)耗電的變化

都跟上面所述一樣。所以可以選擇回溯的算法來實(shí)現(xiàn)有限的搜索，對(duì)每一個(gè)點(diǎn)試探向左與向

右的情況，在所有可能的情況中找出最優(yōu)解。

【思考與提高】

上面的程序運(yùn)算的范圍很有限，當(dāng)n比較大時(shí)就會(huì)棧溢出，如n>30時(shí)速度就比較慢了。

實(shí)際情況調(diào)頭的次數(shù)并不會(huì)多的，到底在什么時(shí)候掉頭根據(jù)情況而定。我們可以從最后一步

來思考：

最后一次關(guān)的可能是第一個(gè)燈也可能是最后?個(gè)燈，哪種情況所費(fèi)的功小就選哪種；

最后一次關(guān)的是第一個(gè)燈的話，說明最后的方向是從最后到最前（右邊到左邊），最后倒

數(shù)第二次的方向?yàn)閺淖蟮接?，起點(diǎn)可能是原始起點(diǎn)（此時(shí)是第?趟），也可能是原始起點(diǎn)左邊

的點(diǎn)（此時(shí)至少是第二趟），一個(gè)個(gè)地試過去，先設(shè)拐一次彎，有可能拐的點(diǎn)都試過去，再試

有兩次拐彎換方向的情況，當(dāng)再多的拐彎超過已有的解時(shí)就不要再向下試了。采用這種回溯

方法，效率更高。

如果n再大一些，如到300以匕上述方法也有它的局限性，此時(shí)最好從動(dòng)態(tài)規(guī)劃法或

貪心法的角度去思考。

第二章遞規(guī)與遞推

2.1遍歷問題

源程序名travel.???(pas,c,cpp)

可執(zhí)行文件名travel.exe

輸入文件名travel,in

輸出文件名travel.out

【問題描述】

我們都很熟悉二叉樹的前序、中序、后序遍歷，在數(shù)據(jù)結(jié)構(gòu)中常提出這樣的問題：已知

一棵二叉樹的前序和中序遍歷，求它的后序遍歷，相應(yīng)的，已知一棵二叉樹的后序遍歷和中

序遍歷序列你也能求出它的前序遍歷。然而給定一棵二叉樹的前序和后序遍歷，你卻不能確

定其中序遍歷序列，考慮如下圖中的幾棵二叉樹：

aaaa

//\\

bbbb

所有這些二叉樹都有著相同的前序遍歷和后序遍歷，但中序遍歷卻不相同。

【輸入】

輸A數(shù)據(jù)共兩行，第一行表示該二叉樹的前序遍歷結(jié)果si,第二行表示該二叉樹的后

序遍歷結(jié)果s2o

【輸出】

輸出可能的中序遍歷序列的總數(shù)，結(jié)果不超過長(zhǎng)整型數(shù)。

【樣例】

travel.intravel.out

abc4

bca

【算法分析】

根據(jù)二叉樹先序遍歷和后序遍歷的特點(diǎn)，可以知道，先序遍歷的第一個(gè)結(jié)點(diǎn)是后序

遍歷的最后一個(gè)結(jié)點(diǎn)，對(duì)于中序遍歷來說卻是中間的一個(gè)結(jié)點(diǎn)，這里所說的中間也只是相對(duì)

而言的中間。如果一棵二叉樹的根結(jié)點(diǎn)沒有左子樹，那么先序遍歷的第一個(gè)結(jié)點(diǎn)也是中序遍

歷的第一個(gè)結(jié)點(diǎn)，如果一棵二叉樹的根結(jié)點(diǎn)沒有右子樹，那么先序遍歷的第一個(gè)結(jié)點(diǎn)是中序

遍歷的最后一個(gè)結(jié)點(diǎn)。我們這里還認(rèn)為就是中序遍歷的中間結(jié)點(diǎn)，上面兩種情況只是特殊的

情況。

設(shè)二叉樹的結(jié)點(diǎn)總數(shù)為n（對(duì)于輸入的字符串來說是它的長(zhǎng)度），對(duì)于先序遍歷的結(jié)果，

第一個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)，從第二個(gè)結(jié)點(diǎn)到最后一個(gè)結(jié)點(diǎn)分為n種情況：

根結(jié)點(diǎn)的左子樹結(jié)點(diǎn)個(gè)數(shù)為n-l,右子樹結(jié)點(diǎn)的個(gè)數(shù)為0；

根結(jié)點(diǎn)的左子樹結(jié)點(diǎn)個(gè)數(shù)為n-2,右子樹結(jié)點(diǎn)的個(gè)數(shù)為1：

根結(jié)點(diǎn)的左子樹結(jié)點(diǎn)個(gè)數(shù)為n-i,右子樹結(jié)點(diǎn)的個(gè)數(shù)為i-1：{0<=i<=n-l）；

根結(jié)點(diǎn)的左子樹結(jié)點(diǎn)個(gè)數(shù)為0,右子樹結(jié)點(diǎn)的個(gè)數(shù)為n-U

根據(jù)這n種情況，分別將二叉樹拆分為左子樹和右子樹，左子樹結(jié)點(diǎn)個(gè)數(shù)為n-i,右子

樹結(jié)點(diǎn)的個(gè)數(shù)為i-I（0<=i<=n-l）,先序遍歷的結(jié)果是從第二個(gè)結(jié)點(diǎn)（字符）開始取，而后序遍

歷的結(jié)果里是從第1個(gè)結(jié)點(diǎn)字符開始取。也就是說對(duì)于每一種情況，分兩步處理：第一步在

先序遍歷和后序遍歷的結(jié)果里取左子樹，看是否符合規(guī)則，統(tǒng)計(jì)這部分可能有的中序遍歷的

結(jié)果數(shù)目；第二步在先序遍歷和后序遍歷的結(jié)果里取右子樹，看是否符合規(guī)則，統(tǒng)計(jì)這部分

可能有的中序遍歷的結(jié)果數(shù)目。這兩步都遞歸調(diào)用了統(tǒng)計(jì)過程，不再遞歸調(diào)用的條件就是當(dāng)

統(tǒng)計(jì)的是空樹或只有一個(gè)結(jié)點(diǎn)的樹，這時(shí)返回的值是可能有的中序遍歷結(jié)果數(shù)目。

結(jié)合”分類相加原理”和“分步相乘原理”，可以得到下面的遞歸函數(shù)：

Functioncount（先序結(jié)果first,后序結(jié)果last:string）:longint;

begin

Len:=遍歷結(jié)果的長(zhǎng)度；

如果len為0或1,則返回結(jié)果即count:=l

否則begin

t為當(dāng)前統(tǒng)計(jì)后符合條件的數(shù)目，初值為0；

分類統(tǒng)計(jì)fori:=len-ldownto0do

begin

在first中取出長(zhǎng)度為i的左子樹結(jié)果LF；

在last中取出長(zhǎng)度為i的左子樹結(jié)果LL；

在first中取出長(zhǎng)度為len-1-i的左子樹結(jié)果RF；

在last中取出長(zhǎng)度為lcn-1-i的右子樹結(jié)果RL；

如果LF、LL符合基本規(guī)則（LF的首字符跟LL的尾字符相同、LF中，所有

的

字符在LL中也都有)

并且RF、RL也符合基本規(guī)則，那么

t:=t+count(LF,LL)*count(RF,RL);

｛分步相乘、分步相加｝

｛這里count函數(shù)中遞歸調(diào)用了count)

end;

返回值為t即count:=t;

end;

end;

其中，檢查先序結(jié)果和后序結(jié)果兩個(gè)字符串是否符合基本規(guī)則，可以再通過一個(gè)函數(shù)來實(shí)

現(xiàn)：

functioncheck(先序字符串F,后序字符串L)：boolean；

begin

Check:=true;

如果F的首字符不等于L的尾字符則check:=false;

從F的第二個(gè)字符取到最后一個(gè)字符，如果該字符不在L中，則check:=false;

end;

【思考與提高】

上面的算法通過遞歸，結(jié)合統(tǒng)計(jì)的基本原理“分步相乘，分類相加”，從而統(tǒng)計(jì)出所有可能

解的個(gè)數(shù)，如果輸入的兩個(gè)字符串沒有解，上述算法同樣能得到結(jié)果。

在肯定有解的情況下，上述算法最終可以遞歸調(diào)用到0、1個(gè)結(jié)點(diǎn)，如果有多組解，那么調(diào)

用到兩個(gè)結(jié)點(diǎn)時(shí)，如先序?yàn)閍b、后序?yàn)閎a,此時(shí)有可能有如下兩種結(jié)構(gòu)：

aa

/\

bb

這兩種結(jié)構(gòu)的中序遍歷結(jié)果分別為：ba、ab,有兩種。

根據(jù)分步相乘的原理，對(duì)比兩個(gè)字符串，每出現(xiàn)一次如上的情況，可能有的結(jié)構(gòu)數(shù)目(結(jié)

構(gòu)不同，中序遍歷結(jié)果也不同，因此可能有的二叉樹結(jié)構(gòu)的數(shù)目就是可能有的中序遍歷結(jié)果

數(shù)目)就乘以2—次，最終得到總的數(shù)目。這也可以理解為一種遞推的方法。

從這里可以看到，在肯定有解的情況F,給定先序遍歷的結(jié)果和后序遍歷的結(jié)果，可能

有2n種可能的結(jié)構(gòu)，也就是中序遍歷可能得到2n種不同的結(jié)果，其中n>=0。那么這里的

n最大可能是多少呢？可以證明n的最大值為字符串的長(zhǎng)度加1整除2。

遞推的程序如下：

Programtravel(intput,output);

Var

Total,I,m:longint;

Sl,s2:string;

Begin

Assign(input,9travel.in9);

Assign(output,travel.out9);

Reset(input);rewrite(output);

Readln(s1);readln(s2);total:=1;

Fori:=ltolength(sl)-ldo

Begin

M:=pos(sl[i],s2);

Ifm>lthenifs[i+l]=s[m-l]thentotal:=total*2;

End;

Writeln(total);close(iinput);close(output);

End.

2.2產(chǎn)生數(shù)

源程序名build.???(pas,c,cpp)

可執(zhí)行文件名build.exe

輸入文件名build.in

輸出文件名build.out

【問題描述】

給出一個(gè)整數(shù)n（n<1030）和m個(gè)變換規(guī)則（mW20）。

約定：一個(gè)數(shù)字可以變換成另一個(gè)數(shù)字，規(guī)則的右部不能為零，即零不能由另一個(gè)數(shù)字

變換而成。而這里所說的一個(gè)數(shù)字就是指一個(gè)一位數(shù)。

現(xiàn)在給出一個(gè)整數(shù)n和m個(gè)規(guī)則，要你求出對(duì)n的每一位數(shù)字經(jīng)過任意次的變換（0次

或多次），能產(chǎn)生出多少個(gè)不同的整數(shù)。

【輸入】

共m+2行，第一行是一個(gè)不超過30位的整數(shù)n,第2行是一個(gè)正整數(shù)m,接下來的m

行是m個(gè)變換規(guī)則，每一規(guī)則是兩個(gè)數(shù)字x、y,中間用一個(gè)空格間隔，表示x可以變換成

y。

【輸出】

僅一行，表示可以產(chǎn)生的不同整數(shù)的個(gè)數(shù)。

【樣例】

build.inbuild.out

1236

2

12

23

【算法分析】

如果本題用搜索，搜索的范圍會(huì)很大（因?yàn)閚可能有30位!），顯然無法在規(guī)定的時(shí)間內(nèi)

出解。而我們注意到本題只需計(jì)數(shù)而不需要求出具體方案，所以我們稍加分析就會(huì)發(fā)現(xiàn)，可

以用乘法原理直接進(jìn)行計(jì)數(shù)。

設(shè)F[i]表示從數(shù)字i出發(fā)可以變換成的數(shù)字個(gè)數(shù)（這里的變換可以是直接變換，也可以是

間接變換，比如樣例中的1可以變換成2,而2又可以變換成3,所以1也可以變換成3；

另外自己本身不變換也是一種情況）。那么對(duì)于一個(gè)長(zhǎng)度為m位的整數(shù)a,根據(jù)乘法原理，

能產(chǎn)生的不同的整數(shù)的個(gè)數(shù)為：F[a[l]]*F[a[2]]*F[a[3]]*-*F[a[m]]o

下面的問題是如何求F[i]呢？山于這些變換規(guī)則都是反映的數(shù)字與數(shù)字之間的關(guān)系，所

以定義一個(gè)布爾型的二維數(shù)組g[0—9,0..9]來表示每對(duì)數(shù)字之間是否可以變換，初始時(shí)都為

False；根據(jù)輸入的數(shù)據(jù)，如果數(shù)字i能直接變換成數(shù)字j,那么g[i,j]置為True,這是通過

一次變換就能得到的；接下來考慮那些間接變換可得到的數(shù)字對(duì)，很明顯：如果i可以變?yōu)?/p>

k,k又可以變?yōu)閖,那么i就可以變?yōu)閖,即：

fork:=0to9do

fbri:=0to9do

forj:=0to9do

g[i，j]=g[ij]or(g[i,k]andg[kj])；

最后還要注意，當(dāng)n很大時(shí)，解的個(gè)數(shù)很大，所以要用高精度運(yùn)算。

2.3出棧序列統(tǒng)計(jì)

源程序名stack.???(pas,c,cpp)

可執(zhí)行文件名stack.exe

輸入文件名stack,in

輸出文件名stack.out

【問題描述】

棧是常用的一種數(shù)據(jù)結(jié)構(gòu)，有F個(gè)元素在棧頂端一側(cè)等待進(jìn)棧，棧頂端另一側(cè)是出棧序

列。你已經(jīng)知道棧的操作有兩種：push和pop,前者是將一個(gè)元素進(jìn)棧，后者是將棧頂元素

彈出?，F(xiàn)在要使用這兩種操作，由一個(gè)操作序列可以得到?系列的輸出序列。請(qǐng)你編程求出

對(duì)于給定的n,計(jì)算并輸出由操作數(shù)序列1,2,n,經(jīng)過一系列操作可能得到的輸出序

列總數(shù)。

【輸入】【輸出】

就一個(gè)數(shù)n(lWnW1000)。一個(gè)數(shù)，即可能輸出序列的

總數(shù)目。

【樣例】

stack.instack.out

35

【算法分析】

在第一章練習(xí)里，我們通過回溯的方法計(jì)算并輸出不同的出棧序列，這里只要求輸出不

同的出棧序列總數(shù)目，所以我們希望能找出相應(yīng)的遞推公式進(jìn)行處理。

從排列組合的數(shù)學(xué)知識(shí)可以對(duì)此類問題加以解決。

我們先對(duì)n個(gè)元素在出棧前可能的位置進(jìn)行分析，它們有n個(gè)等待進(jìn)棧的位置，全部進(jìn)

棧后在棧里也占n個(gè)位置，也就是說n個(gè)元素在出棧前最多可能分布在2*n位置上。

出棧序列其實(shí)是從這2n個(gè)位置上選擇n個(gè)位置進(jìn)行組合，根據(jù)組合的原理，從2n個(gè)位

置選n個(gè)，有C(2n,n)個(gè)。但是這里不同的是有許多情況是重復(fù)的，每次始終有n個(gè)連續(xù)的

空位置，n個(gè)連續(xù)的空位置在2n個(gè)位置里有n+1種，所以重復(fù)了n+1次。所以出棧序列的

種類數(shù)目為：

C(2n,n)/(n+1)=2n*(2n-1)*(2n-2)-*(n+1)/n!/(n+l)=2n*(2n-l)*(2n-2)*-*(n+2)/n!。

考慮到這個(gè)數(shù)據(jù)可能比較大，所以用高精度運(yùn)算來計(jì)算這個(gè)結(jié)果。

本題實(shí)際是一個(gè)經(jīng)典的Catalan數(shù)模型。有關(guān)Catalan數(shù)的詳細(xì)解釋請(qǐng)參考《組合數(shù)學(xué)》

等書。

【思考與提高】

我們知道，在某個(gè)狀態(tài)下，所能做的操作(移動(dòng)方法)無非有兩種：

(1)將右方的等待進(jìn)棧的第一個(gè)元素進(jìn)棧；(2)將棧頂?shù)脑爻鰲?，進(jìn)入左邊的

出棧序列。

設(shè)此時(shí)右方、棧、左方的元素個(gè)數(shù)分別為a,b,Co我們就能用(a,b,c)表示出當(dāng)前的狀

態(tài)。顯然n=a+b+c,則c=n-a-b。即已知a和b,c就被確定,所以我們可以用(a,b)來作為狀

態(tài)的表示方法。則起始狀態(tài)為(n,0),目標(biāo)狀態(tài)為(0,0)。

又由上面的兩種移動(dòng)方法，我們可類似的得到兩種狀態(tài)轉(zhuǎn)移方式：

再設(shè)f(a,b)為從狀態(tài)(a,b)通過移動(dòng)火車變?yōu)闋顟B(tài)(0,0)的所有移動(dòng)方法。類似于動(dòng)態(tài)

規(guī)劃的狀態(tài)轉(zhuǎn)移方程，我們可寫出以下遞歸式：

邊界值：出0,0)=1。

有了這個(gè)遞歸公式后，再寫程序就比較簡(jiǎn)單了，請(qǐng)讀者自己寫出遞歸程序。

2.4計(jì)數(shù)器

源程序名