1、總結(jié)1. 分析問題在“讀題”的階段嘗試把題目引入的概念抽象出來，并聯(lián)想這些概念相關(guān)聯(lián)的背景和經(jīng)典模型 2.解決問題 解決的重點(diǎn)往往不是對(duì)算法的設(shè)計(jì)上，而是如何在把題目中比較雜亂的信息以一個(gè)較簡(jiǎn)潔的方式實(shí)現(xiàn)出來。 3.超越問題 對(duì)題目的算法進(jìn)一步優(yōu)化以及做一些擴(kuò)展，對(duì)于更深入地挖掘這個(gè)問題，增加其利用價(jià)值。 均分紙牌 有 N 堆紙牌，編號(hào)分別為 1，2，, N。每堆上有若干張，但紙牌總數(shù)必為 N 的倍數(shù)?？梢栽谌我欢焉先∪粲趶埣埮?，然后移動(dòng)。移牌規(guī)則為：在編號(hào)為 1 堆上取的紙牌，只能移到編號(hào)為 2 的堆上；在編號(hào)為 N 的堆上取的紙牌，只能移到編號(hào)為 N-1 的堆上；其他堆上取的紙牌，可以移到

2、相鄰左邊或右邊的堆上?，F(xiàn)在要求找出一種移動(dòng)方法，用最少的移動(dòng)次數(shù)使每堆上紙牌數(shù)都一樣多。均分紙牌 例如 N=4，4 堆紙牌數(shù)分別為：98176移動(dòng)3次可達(dá)到目的：從 取 4 張牌放到 （9 8 13 10） - 從 取 3 張牌放到 （9 11 10 10）- 從 取 1 張牌放到（10 10 10 10）。輸 入：鍵盤輸入文件名。文件格式：N（N 堆紙牌，1 = N = 100）A1 A2 An （N 堆紙牌，每堆紙牌初始數(shù)，l= Ai =10000）輸 出：輸出至屏幕。格式為：所有堆均達(dá)到相等時(shí)的最少移動(dòng)次數(shù)。分析 設(shè)list為紙牌序列，其中l(wèi)isti為第i堆紙牌的張數(shù)（1in），ave為

3、均分后每堆紙牌的張數(shù)，ans為最少移動(dòng)次數(shù)。我們按照由左而右的順序移動(dòng)紙牌。若第i堆紙牌的張數(shù)listi超出平均值，則移動(dòng)一次(ans+1)，將超出部分留給下一堆，既第i+1堆紙牌的張數(shù)增加listi-ave；若第i堆紙牌的張數(shù)listi少于平均值，則移動(dòng)一次(ans+1)，由下一堆補(bǔ)充不足部分，既第i+1堆紙牌的張數(shù)減少ave-listi； 右鄰堆取的牌問題是，在從第i+1堆中取出紙牌補(bǔ)充第i堆的過程中，可能會(huì)出現(xiàn)第i+1堆的紙牌數(shù)小于零(listi+1-(ave-listi)xu ud-yy-yzA.out文件： 31、分析變換規(guī)則設(shè)規(guī)則序列為rule，其中第i條規(guī)則為rulei，1rul

4、ei，2；當(dāng)前串為now，其中tmp為now的一個(gè)待匹配子串。由于匹配過程的由左而右進(jìn)行的，因此設(shè)j為now的指針，即從now的第j個(gè)字符開始匹配rulei,1。now適用第i條規(guī)則的條件是now中的子串被第i條規(guī)則替換后的長(zhǎng)度小于255，即 length(now)+length(rulei,2)-length(rulei,1)255rulei,1是now的一個(gè)子串（k=pos(rulei,1,tmp)0）在使用了第i條規(guī)則后，now變換為now= copy(now,1,j+k-1)+rulei,2+copy(now,j+k+length(rulei,1),255)由于now中可能有多個(gè)子串被

5、第i條規(guī)則替換，因此每替換一次后，為了方便地找出下一個(gè)替換位置，我們將當(dāng)前被替換串前（包括被替換串）的子串刪除。 2、使用回溯法計(jì)算最少替換次數(shù)由于原串a(chǎn)、目標(biāo)串b和規(guī)則rule是隨機(jī)輸入的，因此不可能找出直接計(jì)算最少替換次數(shù)best的數(shù)學(xué)規(guī)律，只能采用回溯搜索的辦法。設(shè) 狀態(tài)（need,now）:替換次數(shù)為need，替換結(jié)果為now； 邊界條件（needbest）和目標(biāo)狀態(tài)（now=b）：替換次數(shù)達(dá)到或超過目前得出的最小值為邊界；已經(jīng)替換出目標(biāo)串為目標(biāo)狀態(tài)； 搜索范圍i：嘗試每一條規(guī)則,即1i規(guī)則數(shù)n；約束條件（length(now)+length(rulei,2)-length(rulei

6、,1)255） now中的子串被第i條規(guī)則替換后的長(zhǎng)度小于255；由此得出計(jì)算過程： procedure solve(need；now)；從當(dāng)前串now出發(fā)，遞歸第need次替換var i,k,j:integer； tmp:string；begin if need=best then exit； 若到達(dá)邊界，則回溯 if now=b then begin 更新最優(yōu)值，回溯 bestneed； exit； end；for i1 to n do 搜索每一條規(guī)則 if length(now)+length(rulei,2)-length(rulei,1)0 do begin 反復(fù)在tmp 中尋找子串

7、rulei,1 solve(need+1，copy(now,1,j+k-1)+rulei,2+ copy(now，j+k+length(rulei，1)，255)； delete(tmp,1,k)；將當(dāng)前被替換串的子串刪除 jj+k； 右移匹配指針 kpos(rulei,1,tmp)； 繼續(xù)嘗試第i條規(guī)則 end；while end；thenend； solve 題三 自由落體問題描述: 在高為H 的天花板上有n個(gè)小球，體積不計(jì)，位置分別為0，1，2，n-1。在地面上有一個(gè)小車(長(zhǎng)為L(zhǎng)，高為K，距原點(diǎn)距離為S1)。已知小球下落距離計(jì)算公式為 S=1/2*g*t2，其中 g=10， t為下落時(shí)間

8、。地面上的小車以速度 V 前進(jìn)。如下圖： 小車與所有小球同時(shí)開始運(yùn)動(dòng)，當(dāng)小球距小車的距離0.00001時(shí)，即認(rèn)為小球被小車接受（小球落到地面后不能被接受）。請(qǐng)你計(jì)算出小車能接受到多少個(gè)小球。輸入：H，S1，v，L，k，n （1H，S1，v，L，k，n100000）輸出：小車能接受到的小球個(gè)數(shù)。算法分析由題意可知，車頂與天花板的距離為h-k，小球由天花板落至車頂所花費(fèi)的時(shí)間為t1= ，由天花板落至地面的時(shí)間為t2= 。小車與所有小球同時(shí)開始運(yùn)動(dòng)，當(dāng)小球距小車的距離0.00001時(shí)，即認(rèn)為小球被小車接受（小球落到地面后不能被接受）。顯然，若n1n2，則小車接受的小球數(shù)為n1-n2+1；否則小車未接

9、受任何一個(gè)小球。 小車在行駛了t1*v-0.00001路程后接受了第一個(gè)小球，其編號(hào)為n1=minn-1, 小車在行駛了t2*v+0.00001路程后小球落地，小車接受最后一個(gè)小球的編號(hào)為n2=max0， 。為什么在n1的公式中加上L？為什么在n2的公式中加上0.5？為什么n1取下整、n2取上整？矩形覆蓋問題描述：在平面上有n個(gè)點(diǎn) (n100)，每個(gè)點(diǎn)用一對(duì)整數(shù)坐標(biāo)表示。例如：當(dāng)n=4 時(shí)，4 個(gè)點(diǎn)的坐標(biāo)分別為： p1(1，1)， p2(2，2)， p3 (6，3)， p4(7，0)這些點(diǎn)可以用 k 個(gè)矩形( k4) 全部覆蓋，矩形的邊平行于坐標(biāo)軸。如圖一，當(dāng) k=2時(shí)，可用如圖二的兩個(gè)矩形s

10、1，s2覆蓋， s1，s2面積和為4。問題是當(dāng) n個(gè)點(diǎn)坐標(biāo)和 k 給出后，怎樣才能使得覆蓋所有點(diǎn)的k個(gè)矩形的面積之和為最小呢。約定： 覆蓋一個(gè)點(diǎn)的矩形面積為0；覆蓋平行于坐標(biāo)軸直線上點(diǎn)的矩形面積也為0；各個(gè)矩形間必須完全分開（邊線也不能重合）；算法分析 1、點(diǎn)和矩形的描述和關(guān)系 平面上的點(diǎn)由坐標(biāo)（x,y）表示。由于計(jì)算過程是按照由下而上、由左而右進(jìn)行的，因此我們按照x坐標(biāo)遞增的順序和y坐標(biāo)遞增的順序?qū)個(gè)點(diǎn)存入a序列。矩形由2條平行于x軸的邊界線和2條平行于y軸的邊界線圍成。為了計(jì)算最小矩形的方便，我們將空矩形的左邊界設(shè)為、右邊界為設(shè)-、下邊界設(shè)為、上邊界設(shè)為-。 2、計(jì)算覆蓋所有點(diǎn)的一個(gè)最小

11、矩形設(shè)目前最小矩形的四條邊界為maxx，maxy，minx，miny。如何按照面積最小的要求將a點(diǎn)加入矩形呢？顯然需要調(diào)整邊界線，使a點(diǎn)位于對(duì)應(yīng)的邊界線上。初始時(shí)，我們?cè)O(shè)最小矩形為空，即左邊界left為、右邊界right為-、下邊界top為、上邊界bottom為-。然后由左而右，依次往矩形放入n個(gè)點(diǎn)，調(diào)整對(duì)應(yīng)的邊界線。最后得出的矩形為最小矩形，其面積為（右邊界-左邊界）*（上邊界-下邊界）3、計(jì)算覆蓋所有點(diǎn)的兩個(gè)面積和最小的獨(dú)立矩形 我們稱彼此完全分開的矩形是獨(dú)立的。兩個(gè)覆蓋所有點(diǎn)的獨(dú)立矩形有兩種形態(tài)： 我們將覆蓋x軸左方點(diǎn)集a1,1.j的最小獨(dú)立矩形存入tac1,j；將覆蓋x軸右方點(diǎn)集a1,

12、j.n的最小獨(dú)立矩形存入tdc1,j；將覆蓋y軸下方點(diǎn)集a2,1.j的最小獨(dú)立矩形存入tac2,j；將覆蓋y軸上方點(diǎn)集a2,j.n的最小獨(dú)立矩形存入tdc2,j（注意：當(dāng)k=3時(shí)，對(duì)應(yīng)的點(diǎn)集不包括被矩形1覆蓋的點(diǎn)（1j n ）。 Tac1,j-1Tdc1,jTac2,j-1Tdc2,j為什么一定要考慮兩個(gè)軸向,如果僅考慮一個(gè)軸向的話,有什么反例?問題是面積和最小的兩個(gè)獨(dú)立矩形究竟取哪一個(gè)形態(tài)，區(qū)分兩個(gè)矩形的分界線j為何值，我們無法確定。不得已，只能將所有可能的情況枚舉出來。設(shè)var best，now:longint；兩個(gè)獨(dú)立矩形的最小面積和、當(dāng)前方案中兩個(gè)獨(dú)立矩形的面積和枚舉過程如下： 計(jì)算t

13、ac和tdc序列； bestmaxlongint； 最小矩形面積初始化 for i1 to 2 do begin 依次分析x軸向和y軸向 k=3時(shí)順序?qū)ふ襥軸向上第一個(gè)未被矩形1覆蓋的點(diǎn)j； while jn do枚舉i軸向上所有可能的兩個(gè)獨(dú)立矩形，找出最佳方案 begin 記下i軸向上點(diǎn)j的坐標(biāo)h； 順序?qū)ふ襥軸向上最接近h點(diǎn)(k=3時(shí)，該點(diǎn)未被矩形1覆蓋)的點(diǎn)j；if 點(diǎn)j存在并且k=2，或者k=3時(shí)以點(diǎn)j為分界線的左矩形和右矩形與矩形1沒有交集 then begin now(taci，j-1，1-taci，j-1，3)*(taci，j-1，2-taci，j-1，4)+(tdci，j，1-

14、tdci，j，3)*(tdci，j，2-tdci，j，4)； 則計(jì)算兩個(gè)獨(dú)立矩形的面積和 if nowbest then bestnow； 若面積和為目前最小，則記下 end；thenend；whileend；for if best=maxlongint 若找不到的兩個(gè)獨(dú)立矩形 then返回失敗標(biāo)志-1 else返回兩個(gè)矩形的最小面積和best；end；getans4、計(jì)算覆蓋所有點(diǎn)的三個(gè)面積和最小的獨(dú)立矩形我們先枚舉第一個(gè)矩形，該矩形覆蓋x軸向上的點(diǎn)1、點(diǎn)i、點(diǎn)j、點(diǎn)h（1in, ijn, jhn）,求出覆蓋它們的最小矩形。該矩形的上邊界、下邊界、左邊界和右邊界分別記為bottom、top、

15、left、right。顯然其面積為(bottom-top)*(right-left)。我們將該矩形稱為矩形1。那么，平面上還有哪些點(diǎn)未在矩形1內(nèi)，這些點(diǎn)將被另外兩個(gè)獨(dú)立的矩形所覆蓋。 判斷（x,y）是否在矩形1內(nèi)的條件 (xleft) and (xright) and (ybottom) and (ytop) 判斷矩形是否與矩形1相交的條件min(x1,right)max(x2,left)and(min(y1,bottom)max(y2,top)我們?cè)诘贸鼍匦?的基礎(chǔ)上，直接調(diào)用上述算法計(jì)算與矩形1分開的另外兩個(gè)獨(dú)立矩形的面積和，加上矩形1的面積便是三個(gè)獨(dú)立矩形的面積和。問題是矩形1究竟覆蓋了

16、哪些點(diǎn)才能得出最優(yōu)解呢？我們無法得知。無奈之下，只能通過枚舉法搜索所有的可能情況for i1 to n do 枚舉x軸向上三個(gè)點(diǎn)（點(diǎn)i、點(diǎn)j、點(diǎn)h）的所有可能組合 for ji to n do for hj to n do begin 計(jì)算覆蓋點(diǎn)1、點(diǎn)i、點(diǎn)j、點(diǎn)h的最小矩形（矩形1）的四條邊界 now(bottom-top)*(right-left)； 計(jì)算未被矩形1覆蓋的點(diǎn)集u； 計(jì)算覆蓋u且與矩形1不相交的兩個(gè)獨(dú)立矩形的最小面積和g； if (g0) and (g+nowbest) then bestg+now； 若三個(gè)獨(dú)立矩形的面積和為目前最小，則記下 end；for 輸出最小面積和best；由此得出主程序：讀點(diǎn)數(shù)n和矩形數(shù)k；讀平面上的n個(gè)點(diǎn)；分別沿x軸和y軸對(duì)n