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

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