1、計 算 機(jī) 常 用 算 法,安吉實驗初中 陳國鋒,7、動態(tài)規(guī)劃,1、窮舉法（枚舉法）,2、遞歸法,3、回溯法,4、模擬法,6、分治法,5、貪心法,枚舉法窮舉法,枚舉法（通常也稱為窮舉法）是指在一個有窮的可能的解的集合中，枚舉出集合中的每一個元素，用題目給定的約束條件去判斷其是否符合條件，若滿足條件，則該元素即為整個問題的解；否則就不是問題的解。枚舉的思想往往是最容易想到的一種解題策略，枚舉法從本質(zhì)上說是一種搜索的算法，但適用枚舉法解題必須滿足下列條件：,1）可預(yù)先確定解元素的個數(shù)n,且問題的規(guī)模不是特別大；,2）對于每個解變量A1，A2，。An的可能值必須為 一個連續(xù)的值域。,枚舉法的算法流程

2、：設(shè)ai1為解變量Ai的最小值；aik為解變量的最大值；其中1 i n. A1 a11,a12,a1K A2 a21,A22,A2K Ai ai1,Ai2,AiK An an1,An2,AnK 我們稱解變量為枚舉變量。例如某問題的枚舉變量有三個： A1， A2， A3。,A11，2， A22，3，4， A3 5，6，7 則問題的可能解為（ A1 ，A2， A3 ） （1，2，5），（1，2，6），（1，2，7），（1，3，5）， （1，3，6），（1，3，7），（1，4，5），（1，4，6）， （1，4，7），（2，2，5），（2，2，6），（2，2，7）， （2，3，5），（2，3，6），（

3、2，3，7），（2，4，5）， （2，4，6），（2，4，7） 在上述18個可能解的集合中，滿足問題給定的檢驗條件的解元素即為問題的解。,枚舉法的優(yōu)化方法： 1）減少枚舉的變量，在使用枚舉法之前，先考慮一下解元素之 間的關(guān)聯(lián)，將一些非枚舉不可的解元素列為枚舉變量，其他元素通過計算得出解元素的可能值。,例1、巧妙填數(shù)。 將19這9個數(shù)字填入到9個空格中。每一橫行的三個數(shù)字組成一個三位數(shù)。如果要使第二行的三個三位數(shù)是第一行的2倍，第三行的三位數(shù)是第一行的三倍，應(yīng)怎樣填數(shù)。如圖,2）減少枚舉變量的值域,3）分解約束條件，將拆分的約束條件嵌套在相應(yīng)的循環(huán)體間。,本題目有9個格子，要求填數(shù)，如果不考慮問

4、題給出的條件，共有9！=362880種方案，在這些方案中符合條件的即為解。因此可以用枚舉法。,但仔細(xì)分析問題，顯然第一行的數(shù)不會超過400，實際上只要確定第一行的數(shù)就可以根據(jù)條件算出其他兩行的數(shù)了。這樣僅需枚舉400次。,例2、有四個學(xué)生，上地理課時提出我國四大淡水湖的排序如下： 甲：洞庭湖最大，洪澤湖最小，鄱陽湖第三； 乙：洪澤湖最大，洞庭湖最小，鄱陽湖第二，太湖第三； 丙：洪澤湖最小，洞庭湖第三； 丁：鄱陽湖最大，太湖最小，洪澤湖第二，洞庭湖第三；對于各個湖泊應(yīng)處的地位，每個人只說對了一個。根據(jù)以上情況，編程序判斷各個湖泊應(yīng)處的地位。,算法分析：本題是一個邏輯判斷題，一般的邏輯判斷題都采用

5、枚舉法進(jìn)行解決。四個湖的大小分別可以有4！=24種排列可能，因為24比較小，因此我們對每種情況進(jìn)行枚舉，然后根據(jù)給定的條件判斷哪些符合問題的要求。,源程序,例3、最佳游覽路線。 某旅游區(qū)的街道成網(wǎng)格狀。其中東西向的街道都是旅游街，南北向的街道都是林陰道。由于游客眾多，旅游街被規(guī)定為單行道，游客在旅游街上只能從西向東走，在林陰道上則既可從南向北走，也可以從北向南走。 阿龍想到這個旅游街游玩，他的好友阿福給了他一些建議，用分值表示所有旅游街相鄰兩個路口之見的街道值得游覽的程度，分值是從-100到100的整數(shù)，所有林陰道不打分。所有分值不可能全是負(fù)分。如圖：,北,南,東,西,輸入數(shù)據(jù)：輸入文件是in

6、put.txt.文件的第一行是兩個整數(shù)m和n,之間用一個空格隔開，m表示有多少條旅游街（1m100 ），n 表示有多少條林陰道（1n20001 ）。接下來的m行依次給出了由北向南每條旅游街的分值信息。每行有n-1個整數(shù)，依次表示了自西向東旅游街每一小段的分值。同一行相鄰兩個數(shù)之間用一個空格隔開。 輸出數(shù)據(jù)：輸出文件是output.txt。文件只有一行，是一個整數(shù)，表示你的程序找到的最佳游覽線路的總分值。,Lij為第I條旅游街上自西向東第j段的分值（1im,1jn-1 ）。例如樣例中L12=17，L23=-34，L34=34。 我們將網(wǎng)格狀的旅游區(qū)街道以林陰道為界分為n-1個段，每一段由m條旅游

7、街的對應(yīng)成段，即第j段成為L1j，L2j，。Lmj（1jn-1 ）。由于瀏覽方向規(guī)定橫向自西向東，縱向即可沿林陰道由南向北，也可由北向南，而橫行的街段有分值，縱行無分值，因此最佳游覽路現(xiàn)必須具備如下三個特證： 1）來自若干個連續(xù)的段，每一個段中取一個分值； 2）每一個分值是所在段中最大的； 3）起點段和終點段任意，但途經(jīng)段的分值和最大。 設(shè)Li為第i個段中的分值最大的段。即Li=maxL1i，L2i，。，Lmi（1in-1 ）。例如對于樣例數(shù)據(jù)：,L1=max（-50，17，-42）=17； L2=max（-47，-19，-3）=-3； L3=max（36，-34，-43）=36； L4=ma

8、x（-30，-13，34）=34； L5=max（-23，-8，-45）=-8；,我們把段設(shè)為頂點，所在段的最大分值設(shè)為頂點的權(quán)，各頂點按自西向東的順序相連，組成一條游覽路線。顯然，如果確定西端為起點，東端為終點，則這條游覽路線的總分值最大。,問題是某些段的最大分值可能是負(fù)值，而最優(yōu)游覽路線的起點和終點任意，在這種情況下，上述游覽路線就不是最佳了。因此，我們只能枚舉這條游覽路線的所有可能的子路線，從中找出一條子路線ii+1j(1 ij n-1),使得經(jīng)過頂點的權(quán)和Li+Li+1+Lj最大。,算法： best:=0;sum:=0; for i:=1 to n-2 do for j:=i+1 to

9、 n-1 do begin sum:=sum+Lj;(Li+Lj) if sumbest then best:=sum; end;,顯然，n在120001之間，時間復(fù)雜度比較高。于是，我們必須對這個算法進(jìn)行優(yōu)化。仍然從頂點1開始枚舉最優(yōu)路線。若當(dāng)前子路線延伸至頂點時我們發(fā)現(xiàn)總分值sum 0,則應(yīng)放棄當(dāng)前的子路線。因為無論Li+1為何值，當(dāng)前子路線延伸至頂點i+1后的總分值不會大于Li+1 。因此應(yīng)該從頂點i+1開始重新考慮新的子路線。,優(yōu)化后的算法： best:=0;sum:=0; for i:=1 to n-1 do begin sum:=sum+Li; If sumbest then be

10、st:=sum; if sum0 then sum:=0; End;,遞歸法,一個函數(shù)、過程、概念或數(shù)學(xué)結(jié)構(gòu)，如果在其定義或說明內(nèi)部直接或間接地出現(xiàn)有其本身的引用，或者是為了描述問題的某一狀態(tài)，必須用到它的上一狀態(tài)，而描述上一狀態(tài)，又必須用到它的上一狀態(tài)這種用自己來定義自己的方法，稱之為遞歸或者是遞歸定義。 在程序設(shè)計中，過程或函數(shù)直接或者間接調(diào)用自己，就被稱為遞歸調(diào)用。子程序直接調(diào)用自己，稱為直接遞歸；嵌套關(guān)系的子程序a和b,內(nèi)層的b調(diào)用外層的a,是間接遞歸；平級關(guān)系的子程序a和b,其中a調(diào)用了b,b又調(diào)用了a,這也是間接遞歸。,數(shù)學(xué)函數(shù)式遞歸,例1、階乘n!=1*2*3*（n-1）*n,算

11、法分析：要求n!,只需求出(n-1)!,因為n!=n*(n-1)!,要求出(n-1)!,只需求出(n-2)!,因為(n-1)!=(n-1)*(n-2)!,所以可得到階乘的遞歸定義式：,program factorial; var n:integer; t:longint; function fac(n:integer):longint; begin if n=0 then fac:=1 else fac:=n*fac(n-1) end;,Begin write(n=);readln(n); t:=fac(n); writeln(n!=,t); End.,例2、斐波那契數(shù)列0，1，1，2，3，5

12、，8，13，21，34，55，,從第三項開始，每一項是前兩項的和，其遞歸定義式為：,求此數(shù)列第n項。,參考程序： var n:integer; function fib(n:integer):integer; begin if n=0 then fib=0 else if n=1 then fib:=1 else fib:=fib(n-2)+fib(n-1); end;,begin writeln(input n=); readln(n); if n0 then writeln(data error!) else writeln(fib=,fib(n); end.,例3、樓梯共有n層臺階，上樓

13、可以一步走一層，也可以一步走兩層。編程序計算上n層臺階共有多少種走法？,離散事件的遞歸,例1、簡單的背包問題。設(shè)有一個背包，可以防如入的重量為s?，F(xiàn)有n件物品，重量分別為t1,t2,t3,ti,tn,ti(1 i n),均為正整數(shù)。從n件物品中挑選若干件，使得放入背包的重量之和正好為s., 算法分析：用snap(s,n)代表這一問題。 1）先取最后一個物品tn放入背包中，若tn =s,正好放入包中，問題解決，輸出結(jié)果（n,tn）,2)若tn 1），那么問題可以轉(zhuǎn)化為從剩下的n-1件物品中選取若干件，使得它們的重量和等于包里剩下的可放入重量(s- tn) ,即snap(s- tn,n-1);而選

14、中的tn還要看后續(xù)的問題snap(s-tn,n-1)是否有解，無解的話說明先取的tn不合適，就要放棄tn,在剩余物品中重新開始挑選，即有snap(s,n) snap(s,n-1)。,3）若tns，則不能放入包中，還得繼續(xù)挑選；若還剩物品（即n1），那么問題轉(zhuǎn)化為從剩余n-1件物品中選取若干個，使得她們的重量和等于s，即snap(s,n) snap(s,n-1)。 在2）、3）中就出現(xiàn)了遞歸定義，而1）是有解時遞歸結(jié)束的條件；如果無解時，只有當(dāng)2）、3）中所剩的物品不夠的話問題就不能繼續(xù)執(zhí)行，這也是遞歸結(jié)束的條件。,回溯法,回溯是重要的算法之一，有一些問題，要求找到一組解，或要求找到一個滿足某些

15、限制的最優(yōu)解。對于解決這樣的問題，可以通過使用徹底的搜索方法來解決。然而，徹底搜索的運算量很大，有時大到計算機(jī)承受不了的程度。徹底的搜索，要進(jìn)行大量的比較，大量的舍棄，以大量的運算，大量的時間為代價。因此，用窮舉法解某些實際問題是不現(xiàn)實的，回溯算法為我們提供了一個好方法，使用回溯法可以大大減少實際的搜索。例如，迷宮問題，八皇后問題，騎士周游世界問題。,算法思想： 通過對問題的分析，找出一個解決問題的線索，然后沿著這個線索往前試探，若試探成功，就得到解，若試探失敗，就逐步往回退，換別的路線再往前試探。實際上是廣度與深度搜索結(jié)合的搜索，深度搜索過程中碰到條件不滿足，則退回上一層，在每一層上也進(jìn)行全

16、面的搜索。,關(guān)鍵：找到回溯的條件。,求解八皇后問題： 在n*n個方塊排成n行n列的棋盤上，如果兩個皇后位于同一行、同一列或同一對角線上，則稱它們互相攻擊?，F(xiàn)在要求找出使棋盤上n個皇后互不攻擊布局。,列號：（8，2，4，1，7，5，3，6）,分析： 為了找出互不攻擊的布局，需要對n*n個方案進(jìn)行檢查，將有攻擊的布局剔除掉。這是一種例舉法。但這種方法對于較大的n，其工作量會急劇的增大，而逐一例舉是沒有必要的。,算法：由于在第一行上的皇后在第一列，則第二行上的皇后就不可能在第一列。首先將每一行上安置一個皇后，并假設(shè)第i個皇后在第i行上，用一個一維數(shù)組queen1.n用于記錄安放皇后的過程中隨時記錄第

17、i行上的皇后所在的列號。由此可知，在這種情況下，實際上已經(jīng)剔除了兩個皇后在同一行的可能性。因此，在安置每一行上的皇后時，只需考慮每兩個皇后不能在同一列或同一對角線上的可能性。,從第一行（即i=1）開始布局。 設(shè)前i-1行上的皇后已布局好，即它們互不攻擊。現(xiàn)考慮安排第i行上皇后位置，使之與前i-1行上的皇后也互不攻擊。為了實現(xiàn)這一點，可以從第i行皇后的當(dāng)前位置開始向右搜索。,引進(jìn)集合a,b,c分別表示各列、各條右對角線和各條左對角線上是否放置了皇后。在同一右對角線上，i-j是常量。在同一左對角線上，i+j是常量。第i行第j列上放皇后在第i-j條右對角線和第i+j條左對角線上。能放皇后時為真，不能

18、放皇后時為假。數(shù)組queen存放各行皇后所在的列號。,騎士周游問題,騎士周游問題。給定一個n*n的方陣，共有n2個區(qū)域，有一個國際象棋的馬置于一個區(qū)域上，要求找到一條路徑，使馬按國際象棋的規(guī)則，從開始區(qū)域出發(fā)，不重復(fù)地把n2個區(qū)域都恰好經(jīng)過一次。,分析1：由于馬按“日”字走，馬從本區(qū)域起一步最多能達(dá)到八個區(qū)域。設(shè)馬所在區(qū)域坐標(biāo)為（i,j）,則下一步能達(dá)到的8個位置的坐標(biāo)如下：,分析2： 馬從初始位置（i,j）開始，按8個方向（從（1）（8）走，如下一位置在方陣中而且未到過，則馬跳到該位置，繼續(xù)走；如果8個方向的位置都不能落腳，則退一步，上一步為當(dāng)前步，再按下一個方向繼續(xù)試跳。,算法： Proc

19、edure 過程名； Begin 準(zhǔn)備初值； repeat while 選擇范圍不超過邊界且工作未完成 do begin 分析條件；保證不滿足條件不進(jìn)行 if 成功 then 進(jìn)棧；由第選擇開始進(jìn)入下一層次（往下走） else 本層更換選擇；橫向走 end ; if 工作未完成 then 退棧；原來的上一層更換為下一選擇，回溯，上層橫向走 until 全部工作完成； 輸出； end ;,隨機(jī)數(shù)的介紹 在自然界和日常生活中,許多現(xiàn)象具有不確定的性質(zhì),有些問題甚至很難建立數(shù)學(xué)模型,或者很難用計算機(jī)建立遞推,遞歸,枚舉,回溯法等算法.在這種情況下,一般采用模擬策略.在對實際問題中的隨機(jī)現(xiàn)象進(jìn)行數(shù)學(xué)模

20、擬時,利用計算機(jī)產(chǎn)生的隨機(jī)數(shù)是必不可少的,由于用計算機(jī)產(chǎn)生的隨機(jī)數(shù)總是受字長的限制,其隨機(jī)的意義要比實際問題中真實的隨機(jī)變量稍差,因此,通常將計算機(jī)產(chǎn)生的隨機(jī)數(shù)稱為偽隨機(jī)數(shù).,TURBO.PASCAL的系統(tǒng)中有兩個產(chǎn)生偽隨機(jī)數(shù)的單元: Randomize過程偽隨機(jī)數(shù)發(fā)生器初始化, Random(range)函數(shù)產(chǎn)生一個范圍在0 xrange的偽隨機(jī)數(shù)x，range和x都為word類型.,模擬法,模擬法: 就是模擬某個過程,通過改變數(shù)學(xué)的各種參數(shù),進(jìn)而觀察變更這些參數(shù)所引起過程狀態(tài)的變化.一般題目給定或者隱含某一概率.設(shè)計者利用隨機(jī)函數(shù)和取整函數(shù)設(shè)定某一范圍的隨機(jī)值,將符合概率的隨機(jī)值作為參數(shù).

21、然后根據(jù)這一模擬的數(shù)學(xué)模型展開算法.,模擬策略的關(guān)鍵: 是如何按照概率的要求確定隨機(jī)值的范圍.這個隨機(jī)值設(shè)計得好,模擬效果就好.,例一: 甲乙兩人抓n個棋子,誰抓最后一個誰贏.每一次只能抓一個或兩個,但不能為零個.甲方為計算機(jī),對弈方為乙(由隨機(jī)數(shù)替代).設(shè)計一個程序使計算機(jī)盡可能贏. 輸入:棋子數(shù)n,先下手的方k(k=b對方先下;k=a,計算機(jī)先下). 輸出:游戲過程.一行表示一步:現(xiàn)有棋子數(shù),被抓走的棋子數(shù).最后一行為贏方的名字.,這個問題的算法核心是:要置對方于死地,必須使余下的棋子是1+2=3的整數(shù)倍.因此,當(dāng)甲方處在棋子數(shù)是3的倍數(shù)時要小心等待.一旦對方錯一步,趕緊控制余下棋子數(shù)為3

22、 的倍數(shù).設(shè): b乙方抓走的棋子數(shù).每一次輪到乙方抓時,則隨機(jī)產(chǎn)生b(1+random(2). a- 甲方抓走的棋子數(shù).輪到甲方抓時,若剩余的棋子數(shù)非3的整數(shù)倍,則應(yīng)使抓掉后是3的整數(shù)倍.若剩余的棋子數(shù)為3的整數(shù)倍,則隨機(jī)產(chǎn)生a(1+random(2).,計算過程如下: 輸入棋子總數(shù)n和先下手一方的名字k Randomize; While n0 do begin if k=b then begin x:=random(2);b:=1+x; if n-b=0 then begin 輸出現(xiàn)有0枚棋子,乙方抓走n枚棋子; 輸出乙方贏; break; end else begin n:=n-b;,輸出

23、現(xiàn)有n枚棋子,乙方抓走b枚棋子; K:=a End; Else begin a:=n mod 3; if a0 then 若剩余棋子數(shù)為3的整數(shù)倍,則調(diào)整每次抓的棋數(shù) else x:=random(2);a:=1+x; if n-a=0 then begin 輸出現(xiàn)有0枚棋子,甲方抓走n 枚棋子; 輸出甲方贏; break; end,Else begin n:=n-a; 輸出現(xiàn)有n枚棋子,甲方抓走a枚棋子; K:=b; End; End; End;,練習(xí)： 假設(shè)有一堆小石子，二人輪流去取，誰拿走最后一顆石子便輸。先讓甲規(guī)定石子總數(shù)N以及每次最多取多少顆數(shù)k（n=2*k+1），甲每次取a顆, （

24、N,k,a均為隨機(jī)數(shù)），乙怎樣取贏的可能性最大？設(shè)甲為計算機(jī)產(chǎn)生的隨機(jī)數(shù)，乙為由你編的計算機(jī)程序。,猜數(shù)游戲： 人和計算機(jī)做猜數(shù)游戲。人默想一個四位數(shù)，由計算機(jī)來猜。計算機(jī)將所猜的數(shù)顯示到屏幕上，并問兩個問題： （1）有幾個數(shù)字猜對了？（2）猜對的數(shù)字中有幾個位置也對？ 人通過鍵盤來回答這兩個問題。計算機(jī)一次又一次地猜，直到猜對為止。比如我們默想的一個數(shù)是5122，假定計算機(jī)第一次猜1166，然后問你： （1）有幾個數(shù)字猜對了？1（2）猜對的數(shù)字中有幾個位置也對？1 假定計算機(jī)第二次猜1287 （1）有幾個數(shù)字猜對了？2（2）猜對的數(shù)字中有幾個位置也對？0 假定計算機(jī)第三次猜5122 （1）有

25、幾個數(shù)字猜對了？4（2）猜對的數(shù)字中有幾個位置也對？4 計算機(jī)顯示最后猜中的數(shù)，并報告共猜了幾次？,問題1：編程實現(xiàn)這樣一個猜數(shù)的游戲程序。屏幕顯示格式為： 第二行顯示計算機(jī)所猜的四位數(shù)。 第三行提問猜對的數(shù)字個數(shù)，用“Number:” 第四行提問位置對的數(shù)字個數(shù)，用“Position:” 第五行顯示當(dāng)前已猜的步數(shù)，用“Step xx”. 注：其中末尾數(shù)字由鍵盤輸入。最后給出結(jié)束信息，其他由編程者自定。,問題2 ：仍是這樣一個游戲，但要求計算機(jī)既是猜數(shù)者，又要模擬默想這個數(shù)的人（要猜的數(shù)由鍵盤輸入）。屏幕顯示格式為： 第一行顯示人所默想的數(shù)，用“xxxx”. 第二行至第五行同問題1，只不過末尾

26、數(shù)字不再由鍵盤輸入，而是計算機(jī)判斷后自動顯示。,問題3： 從文本文件guess.dat中讀入20個四位數(shù)，一個接一個讓計算機(jī)猜，統(tǒng)計猜中所需的總步數(shù)。,算法分析：1、計算機(jī)隨機(jī)產(chǎn)生一個猜數(shù) 設(shè)m-當(dāng)前的猜數(shù)集合。 var m:array1.9000 of integer; t:integer; m的長度； 初始時m=1000，1001，9999 t=9000 每一次猜數(shù)時，從m1mt中隨機(jī)取出一個四位數(shù)，該數(shù)即為計算機(jī)的一個猜數(shù)。若m集合為空（t=0）時還未猜中，則游戲以失敗告終。計算機(jī)產(chǎn)生猜數(shù)的過程如下： function get_next :integer; begin if t0 the

27、n get_next:=mrandom(t)+1 else get_next:=-1;返回失敗信息 End;get_next,計算機(jī)產(chǎn)生的猜數(shù)必須與m集合中的每一個四位數(shù)比較，以確定其中哪些四位數(shù)與猜數(shù)默想一方的應(yīng)答信息相符。出于逐位比較的方便，我們將猜數(shù)由整數(shù)類型轉(zhuǎn)化為整數(shù)數(shù)組類型。設(shè)： n由計算機(jī)產(chǎn)生的猜數(shù)，即n:=get_next; nown轉(zhuǎn)化為整數(shù)數(shù)組now0.3.定義如下： type nowtype=array0.3 of 0.9 var now:nowtype; 轉(zhuǎn)化過程如下： procedure put (n:integer,var now:nowtype); begin fo

28、r I:=0 to 3 do begin now3-i:=n mod 10;n:=n div 10;end;for end;put,2、縮小猜數(shù)范圍：計算機(jī)從m集合中隨機(jī)產(chǎn)生一個猜數(shù)now后，默想方必須應(yīng)答（由鍵盤輸入或由計算機(jī)計算）：猜對多少個數(shù)字，其中有多少個數(shù)字位置也對。根據(jù)這一信息，我們將m集合中的每一個元素與now 比較，由比較結(jié)果確定哪些元素應(yīng)從m集合中去除。設(shè)： keym集合中的某元素或默想數(shù)，其數(shù)據(jù)類型為nowtype; Now計算機(jī)產(chǎn)生的猜數(shù)，其數(shù)據(jù)類型亦為nowtype 。 我們通過test1(key,now)函數(shù)計算key中有多少數(shù)字曾在now中出現(xiàn)： 我們通過test2

29、(key,now)函數(shù)計算key中有多少數(shù)字曾在now中出現(xiàn)且位置一一對應(yīng)：,function test1(key,now:nowtype):integer; var h,i,j:integer;h為key和now中的相同數(shù)字個數(shù) mark:array0.3 of boolean;now和key間有重復(fù)數(shù)字的標(biāo)志。 begin fillchar(mark,sizeof(mark),false);mark初始化 h:=0; for I:=1 to 3 do 依次搜索key中的每一個數(shù)字 begin j:=0 在now中尋找與keyi相同的數(shù)字nowj while (jnowj) or (mark

30、j) do j:=j+1; if j=3 then begin markj:=true;h:=h+1; end;then end;for test1:=h; End;test1,Function test2(key,now:nowtype):integer; var h:integer; begin h:=0; for I:=0 to do if keyi=nowi then h:=h+1; Test:=h; End;test2,我們通過test2(key,now)函數(shù)計算key中有多少數(shù)字曾在now中出現(xiàn)且位置一一對應(yīng)：,當(dāng)默想數(shù)為key、計算機(jī)產(chǎn)生的猜數(shù)為now時，我們可以通過調(diào)用上述兩個

31、函數(shù)猜出猜對的數(shù)字個數(shù)t1t1:=test1(key,now)和猜對的數(shù)字中位置也對的數(shù)字個數(shù)t2t2;=test2(key,now).若t14或者t24，則計算機(jī)將now與m集合中的每一個四位數(shù)一一比較，將m中與now的相同數(shù)字個數(shù)為t1且相同數(shù)字中位置對應(yīng)的數(shù)字個數(shù)為t2的所有四位數(shù)mi(1t1) or (test2(key,now)t2) then 從m集合中剔除mi; Until It;,形成m的一個子集，m1mt(1t1) or (test2(key,now)t2) then begin mi:=mt;t:=t-1; I:=I-1; end;then Until It; End;de

32、lete,算法流程：問題（1）的算法。 for I:=1 to 9000 do mi:=I+999; t:=9000; randomize; Repeat n:=get_next; if n=-1 then begin 打印猜數(shù)失敗西信息；halt; end;then Put(n,now) 打印計算機(jī)產(chǎn)生的猜數(shù)now； 輸入猜對的數(shù)字個數(shù)t1和猜對數(shù)字中位置也對的數(shù)字個數(shù)t2; Delete(now); Until(t1=4) and (t2=4);,問題2的算法。 設(shè) step猜中一個數(shù)的不數(shù)。 step:=0; m集合初始化； 讀默想數(shù)key； Repeat n:=get_next;put

33、(n,now); t1:=test1(key,now);t2:=test2(key,now); 輸出t1和t2; Step:=step+1; Delete(now); Until(t1=4) and (t2=4);,問題3的算法：設(shè)total猜中二十個數(shù)的總步數(shù) Total:=0; For k:=0 to 19 do begin 執(zhí)行問題2的算法； Total:total+step; End;for 輸出猜中20個數(shù)所需的總步數(shù)total;,題目1: 某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高

34、于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲，由于該系統(tǒng)還在試用階段。所以一套系統(tǒng)有可能不能攔截所有的導(dǎo)彈。 輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度不大于30000的正整數(shù)）。計算要攔截所有的 導(dǎo)彈最少需配備多少套這種導(dǎo)彈攔截系統(tǒng)。 輸入： 導(dǎo)彈數(shù)n和n顆導(dǎo)彈依次飛來的高度（1=n=1000） 輸出：要攔截所有的導(dǎo)彈最少配備的系統(tǒng)數(shù)。,貪心法,貪心法是從問題的某一個初始解出發(fā),向給定的目標(biāo)推進(jìn).但不同的是 ,推進(jìn)的每一步不是依據(jù)某一固定的遞推式,而是做一個當(dāng)時看似最佳的貪心選擇,不斷地將問題實例歸納為更小的相似的子問題,并期望通過所做的局部最優(yōu)選擇產(chǎn)生出一個全局最優(yōu)解.,算法分析: k當(dāng)前配

35、備的系統(tǒng)數(shù). Lk被第k套系統(tǒng)攔截的最后一枚導(dǎo)彈的高度,簡稱系統(tǒng)k的最低高度.(1=k=n);,1.設(shè)導(dǎo)彈1被系統(tǒng)1所攔截(k:=1;Lk:=導(dǎo)彈1的高度).然后依次分析導(dǎo)彈2,3.導(dǎo)彈n的高度: 2.若導(dǎo)彈i的高度高于所有系統(tǒng)的最低高度,則斷定導(dǎo)彈i不能被這些系統(tǒng)所攔截,應(yīng)增設(shè)一套系統(tǒng)來攔截導(dǎo)彈 i(k:=k+1;Lk:=導(dǎo)彈i的高度).,3若導(dǎo)彈i的高度低于某些系統(tǒng)的最低高度，那么導(dǎo)彈I均可被這些系統(tǒng)所攔截。究竟選擇哪個系統(tǒng)攔截可使得配備的系統(tǒng)數(shù)最少。采取貪心策略：選擇其中最低高度最小（即導(dǎo)彈的的高度與系統(tǒng)最低高度最接近）的一套系統(tǒng)p(Lp=minLj|Lj導(dǎo)彈的的高度)；Lp:=導(dǎo)彈的的

36、高度。這樣，可以使得被一套系統(tǒng)攔截的導(dǎo)彈數(shù)盡可能增多。,4.依次類推，直至分析了n枚導(dǎo)彈的高度為止。 此時得出的k便為應(yīng)配備的最少系統(tǒng)數(shù)。,K:=1;L1:=導(dǎo)彈1的高度； For I:=2 to n do begin p:=0; for j:=1 to k do if (Lj=導(dǎo)彈I 的高度) and （p=0）or (LjLp)） then p:=j; If p=0 then begin k:=k+1;Lk:=導(dǎo)彈I的高度；end else Lp:=導(dǎo)彈I的高度； End; 輸出應(yīng)配備的最少系統(tǒng)數(shù)k.,旅行家問題一個旅行家想駕駛汽車以最少的費用從一個城市到另一個城市（假設(shè)出發(fā)時油箱是空的）

37、。給定兩城市之間的距離D1,汽車油箱的容量C（以升為單位），每升汽油能行駛的距離D2,出發(fā)時每升汽油價格為p.沿途有N個油站（1=N=100）,油站離出發(fā)點的距離為di,該油站每升汽油的價格為pi(i=1,n).計算結(jié)果四舍五入至小數(shù)點后兩位。如果無法到達(dá)目的地，則輸出“No solution”.輸入：D1 ,C, D2, P, N以下含n行。其中第（1=i=n）行為油站號i 該油站距出發(fā)點的距離di 該油站每升汽油的價格Pi輸出：最少的費用,分治策略指的是分而治之的方法。當(dāng)我們處理大規(guī)模問題時，求解可能比較困難，對于這類問題，我們可以將原問題分解成規(guī)模較小而結(jié)構(gòu)與原問題相似的子問題，然后遞歸

38、地解決這些子問題，最后由這些小問題的解構(gòu)造出原問題的解。因此一個問題能否用分治法解決，關(guān)鍵是看該問題算法能否將原問題分成n個規(guī)模較小而結(jié)構(gòu)與原問題相似的子問題。遞歸地解決這些子問題，然后合并其結(jié)果就得到原問題的解。當(dāng)n=2時的分治法又稱二分法。,分治策略一般分為三個步驟： 1、分解：將要解決的問題劃分成若干個規(guī)模較小的同類問題。 2、求解：當(dāng)子問題劃分得足夠小時，用較簡單的方法解決。 3、合并：按原問題的要求，將子問題的解逐層合并成原問題的解。,使用分治策略的問題常常要借助遞歸的結(jié)構(gòu)，逐層求解，當(dāng)問題規(guī)模達(dá)到某個簡單情況時，解容易直接得出，而不必繼續(xù)分解。其過程大致如下：,分 治 策 略,If

39、 問題不可分 then begin 直接求解； 返回問題的解； else begin 從原問題中劃分出含1/n運算對象的子問題1； 遞歸調(diào)用分治法過程，求出解1； 從原問題中劃分出含1/n運算對象的子問題2； 遞歸調(diào)用分治法過程，求出解2； 從原問題中劃分出含1/n運算對象的子問題n； 遞歸調(diào)用分治法過程，求出解n； 將解1、解2、解n組合成整個問題的解； end;,例1、求一組數(shù)中的最大值和最小值。,算法分析：假設(shè)數(shù)據(jù)個數(shù)為n，存放在數(shù)組A1.n中?？梢灾苯?進(jìn)行比較。 min:=a1;max:=a1; for i:=2 to n do if aimax then max:=ai else

40、if aimin then min:=ai,使用分治策略：把n(n2)個數(shù)據(jù)先分成兩組，分別求最大值、最小值，然后分別將這兩組的最大值和最小值進(jìn)行比較，求出全部元素的最大值和最小值。 若分組后元素個數(shù)還大于2，則再次分組，直至組內(nèi)元素小于等于2。,使用這一算法，比較次數(shù)為2（n-1）。若n=10，則比較18次。,源程序,例2、賽程問題 有n個編號為1到n的運動員參加某項運動的單循環(huán)比賽，即每個運動員要和所有其他運動員進(jìn)行一次比賽。試為這n個運動員安排一個比賽日程，使得每個運動員每天只能進(jìn)行一場比賽，且整個比賽在n-1天內(nèi)結(jié)束。 輸入數(shù)據(jù)：運動員人數(shù)n(n0時，Ai,j表示第i名 運動員在第j天

41、的比賽對手。,算法分析,由于n個運動員要進(jìn)行單循環(huán)比賽，且在n-1天內(nèi)要結(jié)束全部比賽，經(jīng)過分析，當(dāng)且僅當(dāng)n為2的整數(shù)次冪時，問題才有解，當(dāng)然解是唯一的。這樣可以將運動員分成兩組：1,2,n/2和n/2+1,n/2+2,n。給第一組運動員安排一個比賽日程，得到一個n/2階的方陣A1；同時給第二組的運動員安排一個比賽日程，同樣得到一個n/2階的方陣A2?？紤]到比賽的性質(zhì)，設(shè)定第i個運動員在某一天的比賽對手為第k個運動員，則第k個運動員在同一天的比賽對手必然是第i個運動員，即若有Ai,j:=k,則Ak,j:=i。因此原問題的解可以由分解后的兩個子問題的解合并起來。同時每一個子問題又可以按照上述二分法

42、分解下去，直至每個組中僅有2個運動員時為止。,源程序,例3、設(shè)有20名學(xué)生的姓名、數(shù)學(xué)成績，按照字典順序存放學(xué)生姓名及其相對應(yīng)的成績于數(shù)組中，現(xiàn)從鍵盤輸入一個學(xué)生的姓名，編程查找該學(xué)生是否在這20個學(xué)生中，如果在，請輸出他的姓名及數(shù)學(xué)成績，否則輸出“NO FOUND”,解析：1、根據(jù)題意，其數(shù)據(jù)存儲結(jié)構(gòu)為記錄型數(shù)組，有兩個域：姓名域、數(shù)學(xué)成績域。 2、數(shù)組中存放的數(shù)據(jù)，按照字典順序存放學(xué)生姓名及相應(yīng)成績。 3、查找一個學(xué)生的姓名及相應(yīng)成績：可以用順序查找，即從第一個學(xué)生姓名開始，順次查找到所需要的學(xué)生姓名，其時間復(fù)雜度為O(n)。 4、采用二分查找，其時間復(fù)雜度為O(long2n)。算法如下：

43、,首先看將要查找學(xué)生的姓名與中間位置的是否相同，若相同則查找成功，輸出該學(xué)生姓名和成績； 若查找學(xué)生姓名順序大于中間位置學(xué)生姓名，則余下查找在數(shù)據(jù)序列的后半部分查找； 若查找學(xué)生姓名順序小于中間位置學(xué)生姓名，則余下查找在數(shù)據(jù)序列的前半部分查找； 重復(fù)以上三步操作，直到查找到或查無此人為止。,從以上的二分查找算法可以看出，他是將原問題的規(guī)模，化為子問題（對半），其子問題的算法與原問題相同，通過不斷減少查找范圍，快速查找所需要的數(shù)據(jù)，因此，這是一個高效算法。,例4、AB兩地的距離為S公里，甲、乙、丙三人從A地到B地共同完成任務(wù)。從A地出發(fā)時，A地有X、Y兩種出租車可供利用，已知三

44、人步性速度都為V1，出租車Y速度為V2，并僅能載一人，出租車X的速度為V3，能載兩人。問題是從A出發(fā)時X只能載一人，回頭接人時才能載兩人，試問怎樣安排行程，才能使甲、乙、丙三人盡快同時到達(dá)B地后共同完成任務(wù)（已知V1V2V3）。,問題解析：1、從問題可以看出，要盡快同時到達(dá)B，則甲、乙、丙需要充分利用X、Y兩種出租車；,2、根據(jù)圖示可以說明安排方法,3、假設(shè)C點表示出租車X先載一人（設(shè)甲）的下車點，然后回頭接乙、丙相遇于D點； 4、D點表示出租車Y先載人（設(shè)乙）到E點下車，回頭接丙相遇于G點，再回頭追到乙于D點，這時出租車X正好到達(dá)D點。 5、由此可以看出：甲乘車到C，從C步行到B；乙乘Y車到

45、E，然后步行到D，再從D乘X車到達(dá)B地；丙步行到G點，被出租車Y接到D點會同乙乘出租車X到達(dá)B地。,分治法：假設(shè)取AB的中點作為出租車X載甲的下車點，計算結(jié)果若甲先到達(dá)B，則實驗點用折半方法往出發(fā)點靠，反之若乙丙先到達(dá)B則甲的下車點要向B靠，即在接近B的一半求新的實驗點。這里設(shè)出發(fā)點到甲下車點的距離為k 當(dāng)確定甲下車點C后，接著用同樣方法測試D點位置，此時測試區(qū)域為AC，確定點為D。 在C，D測試點確定后，再用二分法對區(qū)間AD試探乙乘出租車Y的下車點E。,源程序,動態(tài)規(guī)劃是對最優(yōu)化問題的一種新的算法設(shè)計方法。在實際生活中，有這樣的一類問題，它們的活動過程可以分為若干個階段，而且在任意一個階段x

46、，過程在階段x以后的行為，僅依賴于x階段的過程狀態(tài)，而與x之前過程如何達(dá)到這種狀態(tài)的方式無關(guān)，這樣的過程就構(gòu)成一個多階段決策過程。由此提出了解決這類問題的“最優(yōu)化原理”，創(chuàng)建了最優(yōu)化問題的一種新的算法設(shè)計方法-動態(tài)規(guī)劃。,動態(tài)規(guī)劃解題方法是一種高效率的解題方法，可以解決相當(dāng)大的信息量，其時間復(fù)雜度通常為O(n2)、O(n3)等。它適用的原則是優(yōu)化原則，它可以將整體優(yōu)化分解為若干個局部優(yōu)化。,動態(tài)規(guī)劃算法,動態(tài)規(guī)劃算法的一般模式： 1）劃分階段：按照問題的時間或空間特征，把問題分為若干個階段。在劃分階段時，注意有序或可排序。 2）確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個階段時所處的各種情況用不同狀態(tài)

47、表示出來。 3）確定決策并寫出狀態(tài)轉(zhuǎn)移方程：一般是根據(jù)相鄰兩個階段各狀態(tài)之間的關(guān)系來確定決策。 4）尋找終止條件：給出的狀態(tài)轉(zhuǎn)移方程是一個遞推式，必須有一個遞推的終止條件。 5）編寫程序。,例如：求從A點到D點的最短路徑。,通過三段路程的最短路徑可以用各自的最短路徑，求他們 的和。其和為AB，BC，CD的最短路徑之和，將其作為整個問題的最短路徑，且其解法為最優(yōu)解。,算法分析：窮舉法：時間復(fù)雜度：n1*n2*n3, 貪心法：時間復(fù)雜度：n1+n2+n3,可行。,動態(tài)規(guī)劃算法的應(yīng)用,例1、設(shè)有一個三角形的數(shù)塔，頂點為根結(jié)點，每個結(jié)點有一個整數(shù)值。從頂點出發(fā)，可以向左走或向右走，如圖：,從根結(jié)點13

48、出發(fā)向左、向右的路徑長度可以是： 13-11-7-14-7，其和為52 13-11-12-14-13，其和為63 若要求從根結(jié)點開始，找出一條路徑，使路徑之和最大，若存在多條請輸出任意一條。,解析： 1）用窮舉法：從根結(jié)點開始，將所有可能的路徑求和，找出最大值，但算法時間復(fù)雜度使問題成為不可能。當(dāng) N=1，P=1 N=2，P=2 N=3，P=4 N=k,P=2k-1。當(dāng)N=50，P=249=500萬億條路徑。 2）用貪心法：本題若用貪心法則：13-11-12-14-13，其和為63，實際上存在另一條路徑：13-8-26-15-24，其和為86；貪心法問題所在：眼光短淺。,3）動態(tài)規(guī)劃求解：動態(tài)

49、規(guī)劃求解問題的過程歸納為：自頂向下分析，自底向上計算?；痉椒ǎ?劃分階段：按三角形的行，劃分階段，若有n行，則有n-1個階段，找到問題求解的最優(yōu)途徑。 A、從根結(jié)點13出發(fā)，選取它的兩個方向中的一條支路，選擇的依據(jù)是比較兩個支路中其路徑和最大的支路； B、設(shè)x為從11出發(fā)到底端的最大路徑值，y為從8到底端的最大路徑值。 C、if xy then 選擇x 且取得最大和為13+x else 選擇y 且取得最大和為13+y 這樣，原先求根結(jié)點到底端的最大路徑問題，變?yōu)閺?1出發(fā)和和從8出發(fā)求路徑和的子問題。,同理，求從11出發(fā)到底端的最大路徑問題可以轉(zhuǎn)化為從12出發(fā)和從7出發(fā)的最大路徑問題。決策：

50、路徑和最大 狀態(tài)轉(zhuǎn)移方程：Fi=max(Fi-1(左), Fi-1(右),A、當(dāng)?shù)降箶?shù)第二層時，每個結(jié)點其后繼僅有兩個結(jié)點，可以直接比較，選擇最大值為前進(jìn)方向，從而求得從根結(jié)點開始到底端的最大路徑。終止條件 B、自底向上計算 從底層開始，本身數(shù)即為最大數(shù)； 倒數(shù)第二層的計算，取決于底層的數(shù)據(jù)：12+6=18，13+14=27，24+15=39，24+8=32 最后的路徑為：13-8-26-8-24,4）數(shù)據(jù)結(jié)構(gòu)及算法設(shè)計： A、圖形轉(zhuǎn)化：直角三角形，便于搜索，向下或向右 B、用三維數(shù)組表示數(shù)塔：ax,y,1表示行、列及結(jié)點本身數(shù)據(jù) ax,y,2表示能夠取得最大值 ax,y,3表示前進(jìn)方向，0向下，1向右。 C、算法：數(shù)組初始化，輸入每個結(jié)點值以及初始的最大路徑、前進(jìn)方向0；從倒數(shù)第二層開始向上一層求最大路徑，共循環(huán)n-1次；從頂向下，輸出路徑：關(guān)鍵是j的值，由于行逐漸遞增，表示向下，究竟是向下還是向右取決于列的值。若j的值比原先多1則向右，否則向下。,源程序分析,