【正文】 for I:=1 to 3 do {依次搜索 key中的每一個數(shù)字 } begin j:=0 {在 now中尋找與 key[i]相同的數(shù)字 now[j]} while (j=3) and ((key[i]now[j]) or (mark[j])) do j:=j+1。{then} end。 var h:integer。 End。 if (test1(key,now)t1) or (test2(key,now)t2) then 從 m集合中剔除 m[i]。 Begin I:=0。t:=t1。 End。 randomize。{then} Put(n,now) 打印計算機產(chǎn)生的猜數(shù) now； 輸入猜對的數(shù)字個數(shù) t1和猜對數(shù)字中位置也對的數(shù)字個數(shù) t2。 設(shè) step—猜中一個數(shù)的不數(shù)。 t1:=test1(key,now)。 Delete(now)。 End。 某天 ， 雷達捕捉到敵國的導彈來襲 ， 由于該系統(tǒng)還在試用階段 。 輸入 ： 導彈數(shù) n和 n顆導彈依次飛來的高度 （ 1=n=1000） 輸出 ：要攔截所有的導彈最少配備的系統(tǒng)數(shù) 。L[k]:=導彈 i的高度 ). 3若導彈 i的高度低于某些系統(tǒng)的最低高度，那么導彈 I均可被這些系統(tǒng)所攔截。 ，直至分析了 n枚導彈的高度為止。 for j:=1 to k do if (L[j]=導彈 I 的高度 ) and （（ p=0） or (L[j]L[p])） then p:=j。給定兩城市之間的距離 D1,汽車油箱的容量 C（以升為單位），每升汽油能行駛的距離D2,出發(fā)時每升汽油價格為 N個油站（ 1=N=100） ,油站離出發(fā)點的距離為 di,該油站每升汽油的價格為 pi(i=1,… n).計算結(jié)果四舍五入至小數(shù)點后兩位。因此一個問題能否用分治法解決，關(guān)鍵是看該問題算法能否將原問題分成 n個規(guī)模較小而結(jié)構(gòu)與原問題相似的子問題。 求解：當子問題劃分得足夠小時，用較簡單的方法解決。 例 求一組數(shù)中的最大值和最小值。max:=a[1]。 若 n=10， 則比較 18次 。 輸出數(shù)據(jù)：一個 n階方陣 A[1..n,0..n1]，當 j0時， A[i,j]表示第 i名 運動員在第 j天的比賽對手?？紤]到比賽的性質(zhì)，設(shè)定第 i個運動員在某一天的比賽對手為第 k個運動員，則第 k個運動員在同一天的比賽對手必然是第 i個運動員，即若有 A[i,j]:=k,則 A[k,j]:=i。 數(shù)組中存放的數(shù)據(jù)，按照字典順序存放學生姓名及相應成績。 從以上的二分查找算法可以看出，他是將原問題的規(guī)模，化為子問題（對半），其子問題的算法與原問題相同，通過不斷減少查找范圍，快速查找所需要的數(shù)據(jù)，因此，這是一個高效算法。 [問題解析 ]： 從問題可以看出，要盡快同時到達 B，則甲、乙、丙需要充分利用 X、 Y兩種出租車； 根據(jù)圖示可以說明安排方法 假設(shè) C點表示出租車 X先載一人（設(shè)甲）的下車點，然后回頭接乙、丙相遇于 D點； D點表示出租車 Y先載人（設(shè)乙）到 E點下車，回頭接丙相遇于 G點，再回頭追到乙于 D點，這時出租車 X正好到達 D點。 在 C， D測試點確定后，再用二分法對區(qū)間 AD試探乙乘出租車 Y的下車點 E。 動態(tài)規(guī)劃解題方法是一種高效率的解題方法，可以解決相當大的信息量，其時間復雜度通常為 O(n2)、 O(n3)等。 2）確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個階段時所處的各種情況用不同狀態(tài)表示出來。 例如：求從 A點到 D點的最短路徑。 動態(tài)規(guī)劃算法的應用 例 設(shè)有一個三角形的數(shù)塔，頂點為根結(jié)點，每個結(jié)點有一個整數(shù)值。 當 N=50， P=249=500萬億條路徑。 A、從根結(jié)點 13出發(fā)，選取它的兩個方向中的一條支路，選擇的依據(jù)是比較兩個支路中其路徑和最大的支路； B、設(shè) x為從 11出發(fā)到底端的最大路徑值， y為從 8到底端的最大路徑值。 [終止條件 ] B、自底向上計算 從底層開始，本身數(shù)即為最大數(shù)； 倒數(shù)第二層的計算，取決于底層的數(shù)據(jù)： 12+6=18， 13+14=27，24+15=39， 24+8=32 最后的路徑為： 13826824 4）數(shù)據(jù)結(jié)構(gòu)及算法設(shè)計： A、圖形轉(zhuǎn)化：直角三角形，便于搜索，向下或向右 B、用三維數(shù)組表示數(shù)塔： a[x,y,1]表示行、列及結(jié)點本身數(shù)據(jù) a[x,y,2]表示能夠取得最大值 a[x,y,3]表示前進方向， 0向下， 1向右。 [ 問題描述 ] ：設(shè)有一個正整數(shù)序列 b1,b2,b3,… ,bn, 若下標為i1i2i3,… ik且有 bi1≤ bi2≤ … bik則稱存在一個長度為 k的不下降序列 。 算法 ： 初始化： b[i,1]存放本身數(shù)據(jù) ， b[i,2]表示最長的長度 ， 開始為1， b[i,3]開始為 0， 表示沒有連接 。 從倒數(shù)第三項開始在其后有 2項 ， 因此需要做兩次比較 ， 得到目前最長的不下降序列長度為 2， 其鏈接情況如下表： ... 11 12 13 14 ... 22 63 15 ... 2 1 1 ... 13 0 0 ... 11 12 13 14 ... 21 22 63 15 ... 3 2 1 1 ... 12 13 0 0 一般處理過程： 在 i+1,i+2,...,n項中 ， 找出比 b[i,1]大的最長長度 m， 以及位置 K； 若 m0， 則 b[i,2]:=L+1。 某天 ， 雷達捕捉到敵國的導彈來襲 ， 由于該系統(tǒng)還在試用階段 。 例 一個 n行 m列迷宮 （ 1 ≤ n,m ≤ 50） ,入口位于左上角 ， 規(guī)定只能往下或往右走 。 子結(jié)構(gòu)劃分： 逐行掃描 。 現(xiàn)要將石子有序地合并成一堆 。醫(yī)師為了判斷他的資質(zhì)，給他出了一個難題?！? 如果你是辰辰，你能完成這個任務嗎？ 【 輸入文件 】 輸入文件 T（ 1 = T = 1000）和 M（ 1 = M = 100），用一個空格隔開， T代表總共能夠用來采藥的時間， M代表山洞里的草藥的數(shù)目。 。 【 輸出文件 】 輸出文件 ，這一行只包含一個整數(shù)，表示在規(guī)定的時間內(nèi)，可以采到的草藥的最大總價值。我會給你一段時間，在這段時間里，你可以采到一些草藥。 采藥 【 問題描述 】 辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫(yī)師。 [算法分析 ]： 變量的定義： Ai,j=迷宮第 i行第 j列的寶藏價值 ， 1表示障礙物； F i,j=走到第 i行第 j列所能收集大寶藏的最大價值 。 迷宮的某些地方里藏有不同價值的寶藏 。 輸入導彈依次飛來的高度 （ 雷達給出的高度不大于 30000的正整數(shù) ） 。 本題通過計算 ， 最終結(jié)果為： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 13 7 9 16 38 24 37 18 44 19 21 22 63 15 7 8 7 6 3 4 3 5 2 4 3 2 1 1 4 3 4 8 9 7 9 10 13 11 12 13 0 0 源程序分析 題例 、 某國為了防御敵國的導彈襲擊 ， 發(fā)展出一種導彈攔截系統(tǒng) 。 同樣再從倒數(shù)第 3項開始 ， 其后有兩項 ， 因此必須在最后 2項中找出最長的作為連接項 。 [解法分析 ]： 數(shù)據(jù)結(jié)構(gòu)：假設(shè)有 N個數(shù)的數(shù)列 ， 設(shè)定數(shù)組為 N行 3 列的整型數(shù)組 b。若 j的值比原先多 1則向右，否則向下。 同理，求從 11出發(fā)到底端的最大路徑問題可以轉(zhuǎn)化為從 12出發(fā)和從 7出發(fā)的最大路徑問題。 3） 動態(tài)規(guī)劃求解：動態(tài)規(guī)劃求解問題的過程歸納為： 自頂向下分析，自底向上計算 。 解析： 1）用窮舉法：從根結(jié)點開始，將所有可能的路徑求和，找出最大值，但算法時間復雜度使問題成為不可能。其和為 AB， BC， CD的最短路徑之和，將其作為整個問題的最短路徑，且其解法為最優(yōu)解。 4）尋找終止條件：給出的狀態(tài)轉(zhuǎn)移方程是一個遞推式，必須有一個遞推的終止條件。 動態(tài)規(guī)劃算法 動態(tài)規(guī)劃算法的一般模式： 1）劃分階段：按照問題的時間或空間特征，把問題分為若干個階段。在實際生活中，有這樣的一類問題，它們的活動過程可以分為若干個階段，而且在任意一個階段 x，過程在階段 x以后的行為，僅依賴于x階段的過程狀態(tài)，而與 x之前過程如何達到這種狀態(tài)的方式無關(guān)，這樣的過程就構(gòu)成一個多階段決策過程。 分治法 ：假設(shè)取 AB的中點作為出租車 X載甲的下車點，計算結(jié)果若甲先到達 B，則實驗點用折半方法往出發(fā)點靠，反之若乙丙先到達 B則甲的下車點要向 B靠，即在接近 B的一半求新的實驗點。從 A地出發(fā)時， A地有 X、 Y兩種出租車可供利用，已知三人步性速度都為 V1，出租車 Y速度為 V2，并僅能載一人，出租車 X的速度為 V3，能載兩人。 采用二分查找，其時間復雜度為 O(long2n)。同時每一個子問題又可以按照上述二分法分解下去，直至每個組中僅有 2個運動員時為止。這樣可以將運動員分成兩組： 1,2,…,n/2 和 n/2+1,n/2+2,…,n 。試為這 n個運動員安排一個比賽日程，使得每個運動員每天只能進行一場比賽，且整個比賽在 n1天內(nèi)結(jié)束。 若分組后元素個數(shù)還大于 2，則再次分組，直至組內(nèi)元素小于等于 2?？梢灾苯? 進行比較。 使用分治策略的問題常常要借助遞歸的結(jié)構(gòu)，逐層求解，當問題規(guī)模達到某個簡單情況時，解容易直接得出，而不必繼續(xù)分解。當 n=2時的分治法又稱二分法。其中第（（ 1=i