【正文】 fib:=fib(n2)+fib(n1)。 begin writeln(‘input n=’)。 if n0 then writeln(‘data error!’) else writeln(‘fib=‘,fib(n))。編程序計算上 n層臺階共有多少種走法？ 遞推式 ： F(n)= { 1, n=2 3, n=3 F(n1)+F(n2), n3。設(shè)有一個背包，可以防如入的重量為 s。從 n件物品中挑選若干件，使得放入背包的重量之和正好為 s. [ 算法分析 ]：用 snap(s,n)代表這一問題。而選中的 tn還要看后續(xù)的問題 snap(stn,n1)是否有解 ， 無解的話說明先取的 tn不合適 ， 就要放棄 tn,在剩余物品中重新開始挑選 ， 即有 snap(s,n)? snap(s,n1)。 在 2） 、 3） 中就出現(xiàn)了遞歸定義 ， 而 1） 是有解時遞歸結(jié)束的條件；如果無解時 ， 只有當(dāng) 2） 、 3） 中所剩的物品不夠的話問題就不能繼續(xù)執(zhí)行 ， 這也是遞歸結(jié)束的條件 。對于解決這樣的問題，可以通過使用徹底的搜索方法來解決。徹底的搜索，要進(jìn)行大量的比較，大量的舍棄，以大量的運(yùn)算，大量的時間為代價。例如，迷宮問題，八皇后問題，騎士周游世界問題。實際上是廣度與深度搜索結(jié)合的搜索，深度搜索過程中碰到條件不滿足，則退回上一層，在每一層上也進(jìn)行全面的搜索。 求解八皇后問題： 在 n*n個方塊排成 n行 n列的棋盤上，如果兩個皇后位于同一行、同一列或同一對角線上，則稱它們互相攻擊。 列號：（ 8， 2， 4， 1， 7， 5， 3， 6） 分析 ： 為了找出互不攻擊的布局，需要對n*n個方案進(jìn)行檢查，將有攻擊的布局剔除掉。但這種方法對于較大的 n，其工作量會急劇的增大，而逐一例舉是沒有必要的。首先將每一行上安置一個皇后，并假設(shè)第 i個皇后在第 i行上，用一個一維數(shù)組 queen[1..n]用于記錄安放皇后的過程中隨時記錄第 i行上的皇后所在的列號。因此，在安置每一行上的皇后時，只需考慮每兩個皇后不能在同一列或同一對角線上的可能性。 設(shè)前 i1行上的皇后已布局好 ， 即它們互不攻擊 。 為了實現(xiàn)這一點(diǎn) ， 可以從第 i行皇后的當(dāng)前位置開始向右搜索 。 在同一右對角線上 ， ij是常量 。 第 i行第 j列上放皇后在第 ij條右對角線和第 i+j條左對角線上 。 數(shù)組 queen存放各行皇后所在的列號 。給定一個 n*n的方陣，共有 n2個區(qū)域，有一個國際象棋的馬置于一個區(qū)域上，要求找到一條路徑，使馬按國際象棋的規(guī)則，從開始區(qū)域出發(fā)，不重復(fù)地把 n2個區(qū)域都恰好經(jīng)過一次。設(shè)馬所在區(qū)域坐標(biāo)為（ i,j） ,則下一步能達(dá)到的 8個位置的坐標(biāo)如下： (i2,j1) （ 3） (i2,j+1) （ 2） (i1,j2) （ 4） (i1,j+2) （ 1） （ i,j） (j+1,j2) （ 5） (i+1,j+2)（ 8） (i+2,j1) （ 6） (i+2,j1)（ 7） 分析 2： 馬從初始位置（ i,j）開始，按 8個方向（從（ 1） ?（ 8） ）走，如下一位置在方陣中而且未到過，則馬跳到該位置，繼續(xù)走；如果 8個方向的位置都不能落腳，則退一步，上一步為當(dāng)前步，再按下一個方向繼續(xù)試跳。 if 工作未完成 then 退棧； {原來的上一層更換為下一選擇，回溯，上層橫向走 } until 全部工作完成； 輸出； end 。k=‘a(chǎn)’,計算機(jī)先下 ). 輸出 :游戲過程 .一行表示一步 :現(xiàn)有棋子數(shù) ,被抓走的棋子數(shù) .最后一行為贏方的名字 . 這個問題的 算法核心 是 :要置對方于死地 ,必須使余下的棋子是1+2=3的整數(shù)倍 .因此 ,當(dāng)甲方處在棋子數(shù)是 3的倍數(shù)時要小心等待 .一旦對方錯一步 ,趕緊控制余下棋子數(shù)為 3 的倍數(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。b:=1+x。 輸出乙方贏 。 end else begin n:=nb。 K:=‘a(chǎn)’ End。 if a0 then {若剩余棋子數(shù)為 3的整數(shù)倍 ,則調(diào)整每次抓的棋數(shù) } else x:=random(2)。 if na=0 then begin 輸出現(xiàn)有 0枚棋子 ,甲方抓走 n 枚棋子 。 break。 輸出現(xiàn)有 n枚棋子 ,甲方抓走 a枚棋子 。 End。 End。先讓甲規(guī)定石子總數(shù) N以及每次最多取多少顆數(shù) k（ n=2*k+1），甲每次取 a顆 , （ N,k,a均為隨機(jī)數(shù)），乙怎樣取贏的可能性最大？設(shè)甲為計算機(jī)產(chǎn)生的隨機(jī)數(shù)，乙為由你編的計算機(jī)程序。人默想一個四位數(shù)，由計算機(jī)來猜。計算機(jī)一次又一次地猜，直到猜對為止。屏幕顯示格式為： 第二行顯示計算機(jī)所猜的四位數(shù)。最后給出結(jié)束信息，其他由編程者自定。屏幕顯示格式為： 第一行顯示人所默想的數(shù)，用“ xxxx”. 第二行至第五行同問題 1，只不過末尾數(shù)字不再由鍵盤輸入，而是計算機(jī)判斷后自動顯示。 算法分析： 計算機(jī)隨機(jī)產(chǎn)生一個猜數(shù) 設(shè) m當(dāng)前的猜數(shù)集合。 t:integer。若 m集合為空（ t=0）時還未猜中，則游戲以失敗告終。 begin if t0 then get_next:=m[random(t)+1] else get_next:=1。{get_next} 計算機(jī)產(chǎn)生的猜數(shù)必須與 m集合中的每一個四位數(shù)比較，以確定其中哪些四位數(shù)與猜數(shù)默想一方的應(yīng)答信息相符。設(shè)： n—由計算機(jī)產(chǎn)生的猜數(shù)，即 n:=get_next。 轉(zhuǎn)化過程如下： procedure put (n:integer,var now:nowtype)。n:=n div 10。{for} end。根據(jù)這一信息，我們將 m集合中的每一個元素與 now 比較，由比較結(jié)果確定哪些元素應(yīng)從 m集合中去除。 Now—計算機(jī)產(chǎn)生的猜數(shù)，其數(shù)據(jù)類型亦為 nowtype 。 var h,i,j:integer。{now和 key間有重復(fù)數(shù)字的標(biāo)志。{mark初始化 } h:=0。 if j=3 then begin mark[j]:=true。 end。{for} test1:=h。{test1} Function test2(key,now:nowtype):integer。 begin h:=0。 Test:=h。{test2} 我們通過 test2(key,now)函數(shù)計算 key中有多少數(shù)字曾在 now中出現(xiàn)且位置一一對應(yīng)： 當(dāng)默想數(shù)為 key、計算機(jī)產(chǎn)生的猜數(shù)為 now時，我們可以通過調(diào)用上述兩個函數(shù)猜出猜對的數(shù)字個數(shù)t1[t1:=test1(key,now)]和猜對的數(shù)字中位置也對的數(shù)字個數(shù)t2[t2。 put(m[i],key)。 Until It。這一計算過程由子程序 delete(now)完成： procedure delete(now:nowtype)。 repeat I:=I+1。 if (test1(key,now)t1) or (test2(key,now)t2) then begin m[i]:=m[t]。 I:=I1。{then} Until It。{delete} 算法流程： 問題（ 1）的算法。 t:=9000。 Repeat n:=get_next。 end。 Delete(now)。 問題 2的算法。 step:=0。put(n,now)。t2:=test2(key,now)。 Step:=step+1。 Until(t1=4) and (t2=4)。 For k:=0 to 19 do begin 執(zhí)行問題 2的算法； Total:total+step。{for} 輸出猜中 20個數(shù)所需的總步數(shù) total。 但是這種攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度 ， 但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度 。 所以一套系統(tǒng)有可能不能攔截所有的導(dǎo)彈 。 計算要攔截所有的 導(dǎo)彈最少需配備多少套這種導(dǎo)彈攔截系統(tǒng) 。 貪心法 貪心法 是從問題的某一個初始解出發(fā) ,向給定的目標(biāo)推進(jìn) .但不同的是 ,推進(jìn)的每一步不是依據(jù)某一固定的遞推式 ,而是做一個當(dāng)時看似最佳的貪心選擇 ,不斷地將問題實例歸納為更小的相似的子問題 ,并期望通過所做的局部最優(yōu)選擇產(chǎn)生出一個全局最優(yōu)解 . 算法分析 : k—當(dāng)前配備的系統(tǒng)數(shù) . L[k]—被第 k套系統(tǒng)攔截的最后一枚導(dǎo)彈的高度 ,簡稱系統(tǒng) k的最低高度 .(1=k=n)。L[k]:=導(dǎo)彈 1的高度 ).然后依次分析導(dǎo)彈 2,3….. 導(dǎo)彈 n的高度 : i的高度高于所有系統(tǒng)的最低高度 ,則斷定導(dǎo)彈 i不能被這些系統(tǒng)所攔截 ,應(yīng)增設(shè)一套系統(tǒng)來攔截導(dǎo)彈 i(k:=k+1。究竟選擇哪個系統(tǒng)攔截可使得配備的系統(tǒng)數(shù)最少。這樣，可以使得被一套系統(tǒng)攔截的導(dǎo)彈數(shù)盡可能增多。 此時得出的 k便為應(yīng)配備的最少系統(tǒng)數(shù)。L[1]:=導(dǎo)彈 1的高度； For I:=2 to n do begin p:=0。 If p=0 then begin k:=k+1。 輸