遞推與動態(tài)規(guī)劃.doc

目錄第一章 遞推與動態(tài)規(guī)劃2001年普及組第1題-數(shù)的計(jì)數(shù)-ok-2003年提高組第3題-加分二叉樹-ok-2000年普及組第3題-乘積最大-ok-2003年普及組第2題-數(shù)字游戲-ok-2001年提高組第3題-統(tǒng)計(jì)單詞個(gè)數(shù)-ok-1997年普及組第3題-街道路徑條數(shù)-ok-2002年普及組第4題-過河卒-ok-1997年普及組第1題-統(tǒng)計(jì)正方形和長方形個(gè)數(shù)-ok-1997年提高組第3題-騎士游歷-ok-2000年提高組第4題-方格取數(shù)-ok-2003年普及組第3題-棧-ok-1996年提高組第3題-挖地雷-ok-1999年提高組第1題-攔截導(dǎo)彈-ok-2004年提高組第3題-合唱隊(duì)形-ok-2001年普及組第4題-裝箱問題-ok- 1996年提高組第4題-砝碼秤重-ok-第一章 遞推與動態(tài)規(guī)劃2001年普及組第1題-數(shù)的計(jì)數(shù)【問題描述】我們要求找出具有下列性質(zhì)數(shù)的個(gè)數(shù)(包含輸入的自然數(shù)n)：先輸入一個(gè)自然數(shù)n（n1000）, 然后對此自然數(shù)按照如下方法進(jìn)行處理：（1）不作任何處理；（2）在它的左邊加上一個(gè)自然數(shù)，但該自然數(shù)不能超過原數(shù)的一半；（3）加上數(shù)后，繼續(xù)按此規(guī)則進(jìn)行處理，直到不能再加自然數(shù)為止?！据斎敫袷健?輸入文件count.in中只有一個(gè)數(shù)n【輸出格式】 輸出文件count.out只有一行，該行只有一個(gè)數(shù)，表示求得的滿足要求的數(shù)的個(gè)數(shù)?！据斎霕永?6【輸出樣例】6【輸入/輸出樣例說明】輸入數(shù)字6按以上處理方法，能得到如下的6個(gè)數(shù)字：6162612636136【官方測試數(shù)據(jù)】序號輸入輸出11121014350786410098285198195830【分析】一 題意分析以fi表示i經(jīng)處理能得到的數(shù)的個(gè)數(shù)。則：11圖1 數(shù)1處理后,只能得到11如圖1所示，1經(jīng)處理，只能得到1本身（1個(gè)數(shù)）。因此f1=1；221221圖2 數(shù)2處理后,得到2、122如圖2所示，2經(jīng)處理，能得到的數(shù)的個(gè)數(shù)f2：（1）2本身（1個(gè)數(shù)）。（2）2前加1；對1繼續(xù)處理，能得到的數(shù)個(gè)數(shù)為f1；因此，f2=1+f1=1+1=2。33圖3 數(shù)3處理后,得到3、1313133如圖3所示，3經(jīng)處理，能得到的數(shù)的個(gè)數(shù)f3：（1）3本身（1個(gè)數(shù)）。（2）3前加1；對1繼續(xù)處理，能得到的數(shù)個(gè)數(shù)為f1；因此，f3=1+f1=1+1=2。44圖4 數(shù)4處理后,得到4、14、24、124141424241212444如圖4所示，4經(jīng)處理，能得到的數(shù)的個(gè)數(shù)f4：（1）4本身（1個(gè)數(shù)）。（2）4前加1；對1繼續(xù)處理，能得到的數(shù)個(gè)數(shù)為f1；（3）4前加2；對2繼續(xù)處理，能得到的數(shù)個(gè)數(shù)為f2；因此，f4=1+f1 +f2=1+1+2=4。5如圖5所示，5經(jīng)處理，能得到的數(shù)的個(gè)數(shù)f5：（1）5本身（1個(gè)數(shù)）。（2）5前加1；對1繼續(xù)處理，能得到的數(shù)個(gè)數(shù)為f1；（3）5前加2；對2繼續(xù)處理，能得到的數(shù)個(gè)數(shù)為f2；因此，f5=1+f1 +f2=1+1+2=4。55圖5 數(shù)5處理后,得到5、15、25、1251515252512125566圖6 數(shù)6處理后,得到6、16、26、126、36、1361616262612126636361313666如圖6所示，6經(jīng)處理，能得到的數(shù)的個(gè)數(shù)f6：（1）6本身（1個(gè)數(shù)）。（2）6前加1；對1繼續(xù)處理，能得到的數(shù)個(gè)數(shù)為f1；（3）6前加2；對2繼續(xù)處理，能得到的數(shù)個(gè)數(shù)為f2；（4）6前加3；對3繼續(xù)處理，能得到的數(shù)個(gè)數(shù)為f3；因此，f6=1+f1 +f2 +f3=1+1+2+2=6。fi=1+f1原數(shù)i,只有1個(gè)i前加1,1按照規(guī)則能產(chǎn)生數(shù)的個(gè)數(shù)+f2i前加2,2按照規(guī)則能產(chǎn)生數(shù)的個(gè)數(shù)+ +fi div 2i前加i/2,i/2按照規(guī)則能產(chǎn)生數(shù)的個(gè)數(shù)圖7 fi的計(jì)算公式如圖7所示，一般地，對數(shù)字i處理后，能得到的數(shù)的個(gè)數(shù)為：fi=1+f1+f2+fi div 2。二如圖8所示，求數(shù)12經(jīng)處理后，能得到的數(shù)的個(gè)數(shù)的過程f1f2f1f3f1f2f1f5f4f2f1f2f1f3f6f2f1f3f12f4f5f6圖8 f12的計(jì)算過程1。計(jì)算f1; f1=1；2。由f1計(jì)算f2; f2=1+f1=1+1=2；3。由f1計(jì)算f3; f3=1+f1=1+1=2；4。由f1、f2計(jì)算f4; f4=1+f1 +f2=1+1+2=4；5。由f1、f2計(jì)算f5; f5=1+f1 +f2=1+1+2=4；6。由f1、f2、f3計(jì)算f6; f6=1+f1 +f2 +f3=1+1+2+2=6；7。由f1、f2、f3、f4、f5、f6計(jì)算f12; f12=1+f1 +f2 +f3 +f4 +f5 +f6=1+1+2+2+4+4+6=20；【算法1】1輸入n；2f11；3for i2 to n div 2 do計(jì)算f2至fn div 24 fi1+f1+f2+fi div 2；5fn1+f1+f2+fn div 2；6輸出fn；【參考程序1】program p2001_1(input,output);const maxn=10000;var i,j,n:Integer; f:array1.maxn of longint;begin assign(input,count.in); reset(input); assign(output,count.out); rewrite(output);readln(n); close(input); f1:=1;for i:=2 to n div 2 do begin fi:=1; for j:=1 to i div 2 do fi:=fi+fj; end; fn:=1; for i:=1 to n div 2 do fn:=fn+fi; writeln(fn); close(output);end.【算法的復(fù)雜性】求fn的運(yùn)算次數(shù)：1f1:=1的1次；2求fi的二重循環(huán)的運(yùn)算次數(shù)不大于：(1+i/2)i=2n/2=(n/2-1) +(n/2+2)(n/2-1)/4=n2/16+5n/8-3/23fn:=1的1次；4求fn的循環(huán)的運(yùn)算次數(shù)不大于n/2次：因此合計(jì)運(yùn)算次數(shù)不大于：1+ n2/16+5n/8-3/2+1+ n/2= n2/16+9n/8+1/2次。因此此算法的時(shí)間復(fù)雜度為O(n2)。【算法的改進(jìn)】一遞推式的改進(jìn)如果輸入數(shù)據(jù)要求n最大規(guī)模達(dá)到1000000。此時(shí)，上述O(n2)的算法在n較大時(shí)，必定超時(shí)。我們尋找更好的算法。我們將求fi的遞推式fi=1+f1+f2+fi div 2作一改進(jìn)。（1）f2k+1=1+ f1+f2+f(2k+1) div 2 =1+ f1+f2+fk =1+ f1+f2+f(2k) div 2 =f2k； 即f2k+1= f2k（2）f2k+2=1+ f1+f2+fk+1 =1+ f1+f2+fk+fk+1 =f2k+fk+1 即f2k+2= f2k+fk+1二幾個(gè)實(shí)例求解過程1 求f16，如圖9所示。f1f2f3f2f2f2f4f2f1f3f16f4f5f6圖9 f16的計(jì)算過程f5f4f3f4f6f7f6f4f6f8f7f8（1）求初值f1、f2：f1=1；f2=2；（2）求f3 、f4： f3=f3-1=f2=2； f4=f4-2+f4 div 2=f2+ f2=2+2=4；（3）求f5 、f6： f5=f5-1=f4=4； f6=f6-2+f6 div 2=f4+ f3=4+2=6；（4）求f7 、f8： f7=f7-1=f6=6； f8=f8-2+f8 div 2=f6+ f4=6+4=10；（5）求f16： f16= 1+ f1+f2+f3 +f4 +f5 +f6 +f7+f8=1+1+2+2+4+4+6+6+10=36；2求f15（1）求初值f1、f2：f1=1；f2=2；（2）求f3 、f4： f3=f3-1=f2=2； f4=f4-2+f4 div 2=f2+ f2=2+2=4；（3）求f5 、f6： f5=f5-1=f4=4； f6=f6-2+f6 div 2=f4+ f3=4+2=6；（4）求f7 、f8： f7=f7-1=f6=6； f8=f8-2+f8 div 2=f6+ f4=6+4=10；（5）求f15： f15= 1+ f1+f2+f3 +f4 +f5 +f6 +f7 =1+1+2+2+4+4+6+6=26；【算法2】1輸入n；2f11；3f22；4s2；5逐對產(chǎn)生f2k+1、f2k+2的值f2k+1f2k和f2k+2f2k+fk+1；6fn1+f1+f2+fn div 2；7輸出fn；【參考程序2】program p2001_1(input,output);const maxn=500000;var i,n,m,s:longint; f:array1.maxn of real; g:real; begin assign(input,count.in); reset(input); assign(output,count.out); rewrite(output); readln(n); close(input); f1:=1; f2:=2; m:=n div 2 div 2;其實(shí)產(chǎn)生(n div 2-1) div 2對即可 s:=2; for i:=1 to m do產(chǎn)生m對 begins:=s+1; fs:=fs-1;f2k+1s:=s+1;fs:=fs-2+fs div 2;f2k+2 end; g:=1; for i:=1 to n div 2 dog=1+f1+f2+fn div 2 g:=g+fi; writeln(g:0:0); close(output);end.【算法2的復(fù)雜性】1時(shí)間復(fù)雜度： （1）產(chǎn)生m對f2k+1和f2k+2時(shí)，fs的計(jì)算次數(shù)為：2*m=2* (n div 2 div 2)n/2。 （2）產(chǎn)生m對f2k+1和f2k+2時(shí)，s類加次數(shù)為：2*m=2* (n div 2 div 2)n/2。 （3）產(chǎn)生g（fn）時(shí)的循環(huán)，計(jì)算n div 2n/2。 因此最多計(jì)算3n/2次。算法2的時(shí)間復(fù)雜度為O(n)。2空間復(fù)雜度： 需要一個(gè)f數(shù)組保存中間結(jié)果。每個(gè)real型數(shù)據(jù)占8B，因此，需要額外空間為：500000*8B=4000000B4000KB4MB?！締栴}】上述程序2運(yùn)行時(shí)，n輸入最大的值1000000時(shí)，輸出為： 1.646006492004638E042表示當(dāng)n=100萬時(shí)，fn= 1.646006492004638*1042。即f100萬有43位數(shù)。而real實(shí)型最多只有16位有效數(shù)字。因此，必須采用高精度數(shù)來保存各fi的值。若以1位整數(shù)表示10進(jìn)制的1位數(shù)字，43位數(shù)，需要一個(gè)43元素的數(shù)組來保存。則每計(jì)算1次fi的值，需計(jì)算43次。因此合計(jì)計(jì)算量為43n。當(dāng)取100萬時(shí)，需進(jìn)行4300萬次運(yùn)算。這在限時(shí)1秒的情況下，肯定超時(shí)。（當(dāng)n=100萬時(shí)，在某機(jī)器上，程序2實(shí)際測得運(yùn)行時(shí)間為6秒23）。下面的程序3以1位長整型（longint）來表示高精度數(shù)的9位數(shù)字。每個(gè)fi的43位數(shù)，可以用5個(gè)長整型數(shù)來表示。如：（1）1的計(jì)數(shù)為1，以f1,1=1，f1,2=0，f1,3=0，f1,4=0，f1,5=0；（2）4550的計(jì)數(shù)為187894009136422，如圖10所示，以f4550,1=9136422，f4550,2=187894，f4550,3=0，f4550,4=0，f4550,5=0來表示。000187894009136420020f4550,1f4550,2f4550,3f4550,4f4550,5圖10 4550的計(jì)數(shù),以5個(gè)長整型數(shù)表示因?yàn)殚L整型可表示-21億多至21億多的數(shù)，即它有10位數(shù)位。求f2k+2時(shí)，f2k+2的第j位= f2k的第j位+ fk+1的第j位+求第j-1位時(shí)產(chǎn)生的進(jìn)位。f2k的第j位和fk+1的第j位都小于10億，兩者相加，小于20億，在長整型表示范圍內(nèi)。當(dāng)某位相加和超過999999999時(shí)，向下一位進(jìn)位。處理方法其實(shí)類似10進(jìn)制。我們可以當(dāng)作10億進(jìn)制處理。具體算法參見【參考程序3】?！緟⒖汲绦?】program p2001_1(input,output);const maxn=500000;type num=array1.5 of longint;以5位長整型來表示1個(gè)數(shù)var i,j,n,m,s:longint; f:array1.maxn of num; g:num; c:integer;進(jìn)位值begin assign(input,count.in); reset(input); assign(output,count.out); rewrite(output); readln(n); close(input); 以下2行求得f1=1，以0 0 0 0 1 表示f1,1:=1; for j:=2 to 5 do f1,j:=0; 以下2行求得f2=2，以0 0 0 0 2 表示 f2,1:=2; for j:=2 to 5 do f2,j:=0; m:=n div 2 div 2; s:=2; for i:=1 to m do求得m對f2k+1和f2k+2 begin s:=s+1; for j:=1 to 5 do第1至第5位 fs,j:=fs-1,j;f2k+1的1至5位f2k+1的1至5位s:=s+1;以下7行實(shí)現(xiàn)：f2k+2f2k+ fk+1 c:=0;第0位向第1位的進(jìn)位為0 for j:=1 to 5 do處理第j位加法 beginf2k+2的第j位f2k的第j位+fk+1的第j位+第j-1位向j位的進(jìn)位 fs,j:=fs-2,j+fs div 2,j+c; c:=fs,j div 1000000000;第j位向下一位的進(jìn)位值 fs,j:=fs,j mod 1000000000;當(dāng)前第j位值，去除進(jìn)位后的剩余 end; end; g1:=1;以下2行，fn=1 for j:=2 to 5 dogj:=0;以下10行，在fn（即g）原值1基礎(chǔ)上，加上f1、f2、fn div 2 for i:=1 to n div 2 do每次循環(huán)加上fi begin c:=0; 第0位向第1位的進(jìn)位為0 for j:=1 to 5 do處理第j位加法 begin gj:=gj+fi,j+c;將fi的第j位加至fn上 c:=gj div 1000000000;取得第j位向下一位的進(jìn)位 gj:=gj mod 1000000000;去除進(jìn)位后的剩余值 end; end; i:=5;以下4行，輸出最高位 while gi=0 do i:=i-1; write(gi); i:=i-1; while (i0) do輸出最高位外的其余位 begin if gi10 then只有1位數(shù)，補(bǔ)8個(gè)0；其余依次類推 write(00000000) else if gi100 then write(0000000) else if gi1000 then write(000000) else if gi10000 then write(00000) else if gi100000 then write(0000) else if gi1000000 then write(000) else if gi10000000 then write(00) else if gi100000000 then write(0); write(gi); i:=i-1; end; writeln; close(output);end.【算法3的復(fù)雜性】1時(shí)間復(fù)雜性： （1）產(chǎn)生m對f2k+1和f2k+2時(shí)，fs的計(jì)算次數(shù)為：2*m*5=10* (n div 2 div 2)5n/2。 （2）產(chǎn)生m對f2k+1和f2k+2時(shí)，s類加次數(shù)為：2*m=2* (n div 2 div 2)n/2。 （3）產(chǎn)生g（fn）時(shí)的循環(huán)，計(jì)算5*（n div 2）5n/2。 因此最多計(jì)算11n/2次。算法3的時(shí)間復(fù)雜度為O(n)。當(dāng)n=100萬時(shí)，最多計(jì)算550萬次。因此在一秒的時(shí)限內(nèi)，不會超時(shí)。2空間復(fù)雜性： 每個(gè)長整型占4B，因此需額外空間：50萬*5*4B=1000萬B10000KB10MB?！酒渌夥ā勘绢}的遞歸解法，參見第 冊2003年提高組第3題-加分二叉樹【問題描述】設(shè)一個(gè)n個(gè)節(jié)點(diǎn)的二叉樹tree的中序遍歷為（l,2,3,n），其中數(shù)字1,2,3,n為節(jié)點(diǎn)編號。每個(gè)節(jié)點(diǎn)都有一個(gè)分?jǐn)?shù)（均為正整數(shù)），記第i個(gè)節(jié)點(diǎn)的分?jǐn)?shù)為di，樹tree及它的每個(gè)子樹都有一個(gè)加分，任一棵子樹subtree（也包含tree本身）的加分計(jì)算方法如下：subtree的左子樹的加分 subtree的右子樹的加分subtree的根的分?jǐn)?shù)若某個(gè)子樹為空，規(guī)定其加分為1，葉子的加分就是葉節(jié)點(diǎn)本身的分?jǐn)?shù)。不考慮它的空子樹。試求一棵符合中序遍歷為（1,2,3,n）且加分最高的二叉樹tree。要求輸出； （1）tree的最高加分 （2）tree的前序遍歷【輸入格式】 輸入文件binary.in的第1行：一個(gè)整數(shù)n（n30），為節(jié)點(diǎn)個(gè)數(shù)。 第2行：n個(gè)用空格隔開的整數(shù)，為每個(gè)節(jié)點(diǎn)的分?jǐn)?shù)（分?jǐn)?shù)100）?！据敵龈袷健?輸出文件binary.out的第1行：一個(gè)整數(shù)，為最高加分（結(jié)果不會超過4,000,000,000）。 第2行：n個(gè)用空格隔開的整數(shù)，為該樹的前序遍歷。【輸入樣例】55 7 1 2 10【輸出樣例】1453 1 2 4 5【官方測試數(shù)據(jù)】序號輸入輸出159115 7 8 18 194 2 1 3 52108397015 4 8 9 19 2 1 40 20 227 4 2 1 3 5 6 9 8 10315636679427 38 9 19 2 1 4 2 2 4 5 6 7 8 95 3 1 2 4 12 8 6 7 10 9 11 14 13 1542031735896917 18 9 19 3 1 4 2 2 4 5 6 7 8 9 3 8 4 5 65 3 1 2 4 16 12 8 6 7 10 9 11 14 13 15 18 17 19 205257814952389 8 9 9 5 7 4 2 2 4 5 6 7 8 9 3 3 4 5 1 2 1 2 3 28 4 2 1 3 6 5 7 16 12 10 9 11 14 13 15 20 18 17 19 23 21 22 24 25【分析】采用動態(tài)規(guī)劃算法 以樣例數(shù)據(jù)為例。此時(shí)，有5個(gè)數(shù)依次為5 7 1 2 10；pIp-1p+1J由節(jié)點(diǎn)I,I+1,p,J 組成的子樹，它的根為p號節(jié)點(diǎn) 因?yàn)閚個(gè)數(shù)組成的二叉樹的中序序列為1，2，,n依次遞增排列,所以在該樹中, 若某子樹由第i個(gè)至第j個(gè)元素組成，它的根為p,則它的左子樹的節(jié)點(diǎn)序號均小于p,右子樹的節(jié)點(diǎn)序號均大于p。(如下圖)從第i個(gè)至第j個(gè)元素構(gòu)成的所有二叉樹中，能取得最高加分值記為fi,j，取得此最高加分時(shí)，該樹的根序號為ri,j。則針對樣例數(shù)據(jù)，有以下結(jié)論：1）最高加分為f1,5；2）取得最高加分時(shí)的根為r1,5；3）所有左子樹中的元素序號在1至r1,5-1之間；4）所有右子樹中的元素序號在r1,5+1至5之間；求fi,j的遞推公式如下：fi,j=maxfi,p-1*fp+1,j+fp,p,其中pi,j【樣例數(shù)據(jù)的求解過程】一計(jì)算一個(gè)元素組成的子樹系統(tǒng)15第1元素組成加分二叉樹最大值f1,1=5最大值時(shí)根序號r1,1=127第2元素組成加分二叉樹最大值f2,2=7最大值時(shí)根序號r2,2=231第3元素組成加分二叉樹最大值f3,3=1最大值時(shí)根序號r3,3=342第4元素組成加分二叉樹最大值f4,4=2最大值時(shí)根序號r4,4=4510第5元素組成加分二叉樹最大值f5,5=10最大值時(shí)根序號r5,5=5二計(jì)算二個(gè)元素組成的子樹系統(tǒng)27312731第2-3元素組成加分二叉樹最大值f2,3=1*1+7=8最大值時(shí)根序號r2,3=215271527第1-2元素組成加分二叉樹最大值f1,2=1*7+5=12最大值時(shí)根序號r1,2=131423142第3-4元素組成加分二叉樹最大值f3,4=1*2+1=3最大值時(shí)根序號r3,4=34251042510第4-5元素組成加分二叉樹最大值f4,5=1*10+2=12最大值時(shí)根序號r4,5=4三計(jì)算三個(gè)元素組成的子樹系統(tǒng)第1-3元素組成加分二叉樹最大值f1,3=13最大值時(shí)根序號r1,3=115f2,3以1號元素為根時(shí)最大值為1*8+5=1327f3,3以2號元素為根時(shí)最大值為5*1+7=12f1,131f1,2以3號元素為根時(shí)最大值為12*1+1=132第2-4元素組成加分二叉樹最大值f2,4=15最大值時(shí)根序號r2,4=327f3,4以2號元素為根時(shí)最大值為1*3+7=1031f4,4以3號元素為根時(shí)最大值為7*2+1=15f2,24f2,3以4號元素為根時(shí)最大值為8*1+2=10第3-5元素組成加分二叉樹最大值f3,5=13最大值時(shí)根序號r3,5=331f4,5以3號元素為根時(shí)最大值為1*12+1=1342f5,5以4號元素為根時(shí)最大值為1*10+2=12f3,3510f3,4以5號元素為根時(shí)最大值為3*1+10=13四計(jì)算四個(gè)元素組成的子樹系統(tǒng)第1-4元素組成加分二叉樹最大值f1,4=25 最大值時(shí)根序號r1,4=315f2,4以1號元素為根時(shí)最大值為1*15+5=2027f3,4以2號元素為根時(shí)最大值為5*3+7=22f1,131f1,2以3號元素為根時(shí)最大值為12*2+1=25f4,442f1,3以4號元素為根時(shí)最大值為13*1+2=15第2-5元素組成加分二叉樹最大值f2,5=85最大值時(shí)根序號r2,5=327f3,5以2號元素為根時(shí)最大值1*7+13=2031f4,5以3號元素為根時(shí)最大值為7*12+1=85f2,242f2,3以4號元素為根時(shí)最大值為8*10+2=82f5,5510f2,4以5號元素為根時(shí)最大值15*1+10=25第1-5元素組成加分二叉樹最大值f1,5=145 最大值時(shí)根序號r1,5=315f2,5以1號元素為根時(shí)最大值為1*85+5=9027f3,5以2號元素為根時(shí)最大值為5*13+7=72f1,131f1,2以3號元素為根時(shí)最大值為12*12+1=145f4,542f1,3以4號元素為根時(shí)最大值為13*10+2=132510f1,4以5號元素為根時(shí)最大值為25*1+10=35f5,5五計(jì)算所有五個(gè)元素組成的二叉樹系統(tǒng)的最大加分和根因此，最高加分為f1,5=145，獲得最高加分時(shí)的樹根是3號元素。最高加分時(shí)的前序序列的構(gòu)造過程：1。輸出序號15的根r1,5=32。輸出3號節(jié)點(diǎn)的左子樹，即序號12的根r1,2=1 2.1。1號節(jié)點(diǎn)的左子樹為空 2.2。輸出1號節(jié)點(diǎn)的右子樹，即序號2的根r2,2=23。輸出3號節(jié)點(diǎn)的右子樹，即序號45的根r4,5=4 3.1。4號節(jié)點(diǎn)的左子樹為空 3.2。輸出4號節(jié)點(diǎn)的右子樹，即序號5的根r5,5=5【參考程序】program t2003_3(input,output);const maxn=30;var n,i,j,k,p:integer; r:array1.maxn,0.maxnof integer;節(jié)點(diǎn)i至j組成的子樹，得到最大加分時(shí)的根為ri,j f:array1.maxn,0.maxnof real; 節(jié)點(diǎn)i至j組成的子樹，得到的最大加分為fi,j first:boolean;輸出節(jié)點(diǎn)I至j組成的子樹的前序序列procedure out(i,j:integer);var k:integer;begin k:=ri,j; if k0 then begin 節(jié)點(diǎn)i至j組成的子樹非空 if first then 輸出根 begin write(k);first:=false;end else write( ,k); out(i,k-1); 輸出左子樹 out(k+1