簡(jiǎn)單枚舉算法

簡(jiǎn)單枚舉算法簡(jiǎn)單枚舉算法所謂枚舉，即對(duì)可能的解集合一一列舉。解題思路為：首先確定可能的解集合抽象出解包含的參數(shù)，確定每個(gè)參數(shù)的數(shù)據(jù)范圍對(duì)解的每個(gè)參數(shù)的數(shù)據(jù)范圍采用循環(huán)語(yǔ)句一一枚舉對(duì)每次枚舉，根據(jù)題意給定的條件判定是否解，是否是最優(yōu)解。枚舉法的優(yōu)點(diǎn)：⑴由于枚舉算法一般是現(xiàn)實(shí)生活中問(wèn)題的“直譯”，因此比較直觀，易于理解；⑵由于枚舉算法建立在考察大量狀態(tài)、甚至是窮舉所有狀態(tài)的基礎(chǔ)上，所以算法的正確性比較容易證明。枚舉法的缺點(diǎn)：枚舉算法的效率取決于枚舉狀態(tài)的數(shù)量以及單個(gè)狀態(tài)枚舉的代價(jià)，因此效率比較低。枚舉法優(yōu)缺點(diǎn)例1:邏輯判斷問(wèn)題在某次數(shù)學(xué)競(jìng)賽中,A、B、C、D、E五名學(xué)生被取為前五名。請(qǐng)據(jù)下列說(shuō)法判斷出他們的具體名次,即誰(shuí)是第幾名？條件1:你如果認(rèn)為A,B,C,D,E就是這些人的第一至第五名的名次排列,便大錯(cuò)。因?yàn)?沒(méi)猜對(duì)任何一個(gè)優(yōu)勝者的名次。也沒(méi)猜對(duì)任何一對(duì)名次相鄰的學(xué)生。條件2:你如果按D,A,E,C,B來(lái)排列五人名次的話,其結(jié)果是:說(shuō)對(duì)了其中兩個(gè)人的名次。還猜中了兩對(duì)名次相鄰的學(xué)生的名次順序。分析：本題是一個(gè)邏輯判斷題，一般的邏輯判斷題都采用枚舉法進(jìn)行解決。5個(gè)人的名次分別可以有5！=120種排列可能，因?yàn)?20比較小，因此我們對(duì)每種情況進(jìn)行枚舉，然后根據(jù)條件判斷哪些符合問(wèn)題的要求。分析:

根據(jù)已知條件，A<>1,B<>2,C<>3,D<>4,E<>5,因此排除了一種可能性，只有4！=24種情況了。ProgramExam;VarA,B,C,D,E:Integer;Cr:Array[1..5]OfChar;BeginForA:=1To5DoForB:=1To5DoForC:=1To5DoForD:=1To5DoForE:=1To5DoBeginIf(A=1)Or(B=2)Or(C=3)Or(D=4)Or(E=5)ThenContinue;{ABCDE沒(méi)猜對(duì)一個(gè)人的名次}If[A,B,C,D,E]<>[1,2,3,4,5]ThenContinue;{他們名次互不重復(fù)}IfOrd(A=2)+Ord(B=5)+Ord(C=4)+Ord(D=1)+Ord(E=3)<>2ThenContinue;{DAECB猜對(duì)了兩個(gè)人的名次}If(B=A+1)Or(C=B+1)Or(D=C+1)Or(E=D+1)ThenContinue;{ABCDE沒(méi)猜對(duì)一對(duì)相鄰名次}IfOrd(A=D+1)+Ord(E=A+1)+Ord(C=E+1)+Ord(B=C+1)<>2ThenContinue;{DAECB猜對(duì)了兩對(duì)相鄰人名次}Cr[A]:='A';Cr[B]:='B';Cr[C]:='C';Cr[D]:='D';Cr[E]:='E';WRITELN(CR[1],'',CR[2],'',CR[3],'',CR[4],'',CR[5]);End;End.例2:火柴棒等式給你n根火柴棍，你可以拼出多少個(gè)形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整數(shù)（若該數(shù)非零，則最高位不能是0）。用火柴棍拼數(shù)字0-9的拼法如圖所示：注意：1.加號(hào)與等號(hào)各自需要兩根火柴棍2.如果A≠B，則A+B=C與B+A=C視為不同的等式（A、B、C>=0）3.n根火柴棍必須全部用上分析0~9的數(shù)字所用的火柴數(shù)：6,2,5,5,4,5,6,3,7,6對(duì)于N<=24，去掉+，=，實(shí)際上數(shù)字只有20根火柴。首先考慮解集合，因?yàn)樽疃酁?0根火柴組成數(shù)字：不可能為10個(gè)1；不可能8個(gè)1，1個(gè)4；不可能為7個(gè)1，2個(gè)7或1個(gè)0；…..C不會(huì)超過(guò)1000題意簡(jiǎn)述：John要在牛場(chǎng)中建造一個(gè)大型浴場(chǎng)，但是這個(gè)大型浴場(chǎng)不能覆蓋任何一個(gè)奶牛的產(chǎn)奶點(diǎn)。John的牛場(chǎng)和規(guī)劃的浴場(chǎng)都是矩形，浴場(chǎng)要完全位于牛場(chǎng)之內(nèi)，并且浴場(chǎng)的輪廓要與牛場(chǎng)的輪廓平行或者重合。要求所求浴場(chǎng)的面積盡可能大。參數(shù)約定：產(chǎn)奶點(diǎn)的個(gè)數(shù)S不超過(guò)5000,牛場(chǎng)的范圍N×M不超過(guò)30000×30000。例3：奶牛浴場(chǎng)最大子矩形問(wèn)題：在一個(gè)給定的矩形中有一些障礙點(diǎn)，要找出內(nèi)部不包含任何障礙點(diǎn)的，輪廓與整個(gè)矩形平行或重合的最大子矩形。問(wèn)題的模型定義和說(shuō)明定義有效子矩形為內(nèi)部不包含任何障礙點(diǎn)的，邊界與坐標(biāo)軸平行的子矩形。如下圖所示，第一個(gè)是有效子矩形，第二個(gè)不是。定義和說(shuō)明定義極大子矩形為每條邊都不能向外擴(kuò)展的有效子矩形。定義最大子矩形為所有有效子矩形中最大的一個(gè)（或多個(gè)）。極大化思想在一個(gè)有障礙點(diǎn)的矩形中的最大子矩形一定是一個(gè)極大子矩形。設(shè)計(jì)算法的思路：通過(guò)枚舉所有的極大子矩形，找出最大子矩形。算法1思路從極大子矩形的性質(zhì)入手。極大子矩形的性質(zhì)：一個(gè)極大子矩形的每條邊一定都不能向外擴(kuò)展。更進(jìn)一步地說(shuō)，一個(gè)有效子矩形是極大子矩形的條件是這個(gè)子矩形的每條邊要么覆蓋了障礙點(diǎn)，要么與整個(gè)矩形的邊界重合。算法設(shè)計(jì)基本算法算法：枚舉上下左右四個(gè)邊界，然后判斷組成的矩形是否是有效子矩形。復(fù)雜度：O(S5)可以改進(jìn)的地方：產(chǎn)生了大量的無(wú)效子矩形初步改進(jìn)算法算法：枚舉左右邊界，然后對(duì)處在邊界內(nèi)的點(diǎn)排序。每?jī)蓚€(gè)相鄰的點(diǎn)和左右邊界一起組成一個(gè)矩形。復(fù)雜度：O(S3)可以改進(jìn)的地方：枚舉了部分不是極大子矩形的情況算法改進(jìn)設(shè)計(jì)算法的方向：

1、保證每一個(gè)枚舉的子矩形都是有效的2、保證每一個(gè)枚舉的子矩形都是極大的

算法的過(guò)程：枚舉極大子矩形的左邊界

→根據(jù)確定的左邊界，找出相關(guān)的極 大子矩形

→檢查和處理遺漏的情況算法1首先，將所有障礙點(diǎn)按橫坐標(biāo)從小到大的順序?qū)Ⅻc(diǎn)標(biāo)為1號(hào)點(diǎn)，2號(hào)點(diǎn)……1234算法1為了處理方便，在矩形的四個(gè)頂點(diǎn)上各增加1個(gè)障礙點(diǎn)。算法1第一次取1號(hào)點(diǎn)作為所要枚舉的極大子矩形的左邊界設(shè)定上下邊界為矩形的上下邊界左邊界上邊界下邊界1算法1從左向右掃描，第一次遇到2號(hào)點(diǎn)，可以得到一個(gè)有效的極大子矩形，如圖所示左邊界上邊界下邊界12算法1因?yàn)樽筮吔绺采w1號(hào)點(diǎn)且右邊界在2號(hào)點(diǎn)右邊的有效子矩形都不能包含2號(hào)點(diǎn)，所以需要修改上下邊界2號(hào)點(diǎn)在1號(hào)點(diǎn)上方，因此要修改上邊界左邊界上邊界下邊界12算法1繼續(xù)掃描到3號(hào)點(diǎn)，又得到一個(gè)極大有效子矩形，如圖所示左邊界上邊界下邊界13算法1因?yàn)?號(hào)點(diǎn)在1號(hào)點(diǎn)下方，所以要修改下邊界。左邊界上邊界下邊界13算法1以此類推，可以得到所有以1號(hào)點(diǎn)為左邊界的極大有效子矩形。然后將左邊界移動(dòng)到2號(hào)點(diǎn)、3號(hào)點(diǎn)……橫坐標(biāo)的位置。開(kāi)始掃描以2號(hào)點(diǎn)、3號(hào)點(diǎn)……為左邊界的極大子矩形。左邊界上邊界下邊界23算法1遺漏的情況前面的做法可以找出所有左邊界覆蓋了一個(gè)障礙點(diǎn)的極大子矩形，此外，還有兩類遺漏的情況。算法1遺漏的情況一類是左邊界與整個(gè)矩形的左邊界重合，右邊界覆蓋一個(gè)障礙點(diǎn)的情況。解決方法：用類似的方法從右向左掃描一次。算法1遺漏的情況另一類是左邊界與整個(gè)矩形的左邊界重合，且右邊界也與整個(gè)矩形的右邊界重合的情況。解決方法：預(yù)處理時(shí)增加特殊判斷。算法1優(yōu)劣分析算法1的時(shí)間復(fù)雜度為O(S2)，空間復(fù)雜度為O(S)。優(yōu)點(diǎn)：利用了極大化思想，復(fù)雜度可以接受，編程實(shí)現(xiàn)簡(jiǎn)單。缺點(diǎn)：使用有一定的局限性，不適合障礙點(diǎn)較密集的情況。算法2設(shè)計(jì)的目的和思路因?yàn)樗惴?有使用的局限性，所以我們需要一種在障礙點(diǎn)很密集的時(shí)候仍能奏效的算法。設(shè)計(jì)一種復(fù)雜度依賴于整個(gè)矩形面積的算法說(shuō)明：如果整個(gè)矩形面積很大，可以通過(guò)離散化處理來(lái)優(yōu)化。算法2懸線有效豎線：除了兩個(gè)端點(diǎn)外，不覆蓋任何障礙點(diǎn)的豎直線段。懸線：上端點(diǎn)覆蓋了一個(gè)障礙點(diǎn)或達(dá)到整個(gè)矩形上端的有效豎線。圖中所示的線段均為懸線。算法2懸線每個(gè)懸線都與它底部的點(diǎn)一一對(duì)應(yīng)。矩形中的每一個(gè)點(diǎn)（矩形頂部的點(diǎn)除外）都對(duì)應(yīng)了一個(gè)懸線。懸線的個(gè)數(shù)＝(N－1)×M算法2懸線與極大子矩形如果把一個(gè)極大子矩形按x坐標(biāo)不同切割成多個(gè)與y軸平行的線段，則其中至少存在一個(gè)懸線。……YX算法2懸線與極大子矩形如果把一個(gè)懸線向左右兩個(gè)方向盡可能移動(dòng)，就能得到一個(gè)矩形，不妨稱為這個(gè)懸線對(duì)應(yīng)的矩形。懸線對(duì)應(yīng)的矩形不一定是極大子矩形，因?yàn)橄逻吔缈赡苓€可以向下擴(kuò)展。設(shè)計(jì)算法原理：所有懸線對(duì)應(yīng)矩形的集合一定包含了極大子矩形的集合。通過(guò)枚舉所有的懸線，找出所有的極大子矩形。算法規(guī)模：懸線個(gè)數(shù)＝(N－1)×M

極大子矩形個(gè)數(shù)≤懸線個(gè)數(shù)算法2關(guān)鍵點(diǎn)解決問(wèn)題的關(guān)鍵：對(duì)每個(gè)懸線的處理時(shí)間。解決方法：充分利用前面得到的信息。算法2處理方法具體方法：設(shè)H[i,j]為點(diǎn)(i,j)對(duì)應(yīng)的懸線的長(zhǎng)度。

L[i,j]為點(diǎn)(i,j)對(duì)應(yīng)的懸線向左最多能夠移動(dòng)到的位置。R[i,j]為點(diǎn)(i,j)對(duì)應(yīng)的懸線向右最多能夠移動(dòng)到的位置。圖示L[i,j]R[i,j]H[i,j]點(diǎn)(i,j)考慮點(diǎn)(i,j)對(duì)應(yīng)的懸線與點(diǎn)(i-1,j)對(duì)應(yīng)的懸線的關(guān)系。算法2遞推關(guān)系如果(i－1,j)為障礙點(diǎn)，那么，如圖所示，(i,j)對(duì)應(yīng)的懸線長(zhǎng)度1，左右能移動(dòng)到的位置是整個(gè)矩形的左右邊界。即H[i,j]＝1,L[i,j]=0,R[i,j]=m(i-1,j):障礙點(diǎn)(i,j):當(dāng)前點(diǎn)R[i,j]L[i,j]H[i,j]=1算法2遞推關(guān)系如果(i－1,j)不是障礙點(diǎn)，那么，如圖所示，(i,j)對(duì)應(yīng)的懸線長(zhǎng)度為(i-1,j)對(duì)應(yīng)的懸線長(zhǎng)度＋1。即H[i,j]＝H[i-1,j]+1(i-1,j):非障礙點(diǎn)(i,j):當(dāng)前點(diǎn)某個(gè)障礙算法2遞推關(guān)系如果(i－1,j)不是障礙點(diǎn)，那么，如圖所示，(i,j)對(duì)應(yīng)的懸線左右能移動(dòng)的位置要在(i-1,j)的基礎(chǔ)上變化。L[i-1,j]L[i,j]=max(i-1,j)左邊第一個(gè)障礙點(diǎn)的位置

(i,j):當(dāng)前點(diǎn)某個(gè)障礙L[i-1,j]L[i,j](i-1,j)算法2遞推關(guān)系同理，也可以得到R[i,j]的遞推式R[i-1,j]R[i,j]=min(i-1,j)右邊第一個(gè)障礙點(diǎn)的位置

L[i,j]R[i,j]H[i,j]點(diǎn)(i,j)算法2優(yōu)劣分析算法2的時(shí)間復(fù)雜度為O(NM)，空間復(fù)雜度為O(S)。優(yōu)點(diǎn)：復(fù)雜度與障礙點(diǎn)個(gè)數(shù)沒(méi)有直接關(guān)系。缺點(diǎn)：障礙點(diǎn)少時(shí)處理較復(fù)雜，不如算法1兩個(gè)不同的算法算法1時(shí)間復(fù)雜度：O(S2)空間復(fù)雜度：O(S)優(yōu)點(diǎn)：復(fù)雜度可以接受，編程實(shí)現(xiàn)簡(jiǎn)單缺點(diǎn)：使用有一定的局限性，不適合障礙點(diǎn)較密集的情況。算法2時(shí)間復(fù)雜度：O(NM)空間復(fù)雜度：O(S)

優(yōu)點(diǎn)：復(fù)雜度與障礙點(diǎn)個(gè)數(shù)沒(méi)有直接關(guān)系。缺點(diǎn)：障礙點(diǎn)少時(shí)因?yàn)橐x散化處理，實(shí)際復(fù)雜度較高。思考題1:跳遠(yuǎn)在水平面上整齊的放著n個(gè)正三角形，相鄰兩個(gè)三角形的底邊之間無(wú)空隙，如左圖所示。一個(gè)小孩子想站在某個(gè)三角形i的頂端，跳到三角形j的頂端上(i<j)。他總是朝著斜向45度的方向起跳，且初始水平速度v不超過(guò)一個(gè)給定值v0。在跳躍過(guò)程中，由于受到重力作用（忽略空氣阻力），小孩子將沿著拋物線行進(jìn)，水平運(yùn)動(dòng)方程為x=x0+vt，豎直運(yùn)動(dòng)方程為y=y0+vt–0.5gt2，運(yùn)動(dòng)軌跡是一條上凸的拋物線。取g=10.0，(x0，