【正文】 出應(yīng)配備的最少系統(tǒng)數(shù) k. 旅行家問(wèn)題 一個(gè)旅行家想駕駛汽車以最少的費(fèi)用從一個(gè)城市到另一個(gè)城市（假設(shè)出發(fā)時(shí)油箱是空的）。如果無(wú)法到達(dá)目的地，則輸出 “ No solution”. 輸入： D1 ,C, D2, P, N 以下含 n行。當(dāng)我們處理大規(guī)模問(wèn)題時(shí)，求解可能比較困難，對(duì)于這類問(wèn)題，我們可以將原問(wèn)題分解成規(guī)模較小而結(jié)構(gòu)與原問(wèn)題相似的子問(wèn)題，然后遞歸地解決這些子問(wèn)題，最后由這些小問(wèn)題的解構(gòu)造出原問(wèn)題的解。遞歸地解決這些子問(wèn)題，然后合并其結(jié)果就得到原問(wèn)題的解。 分治策略一般分為三個(gè)步驟： 分解：將要解決的問(wèn)題劃分成若干個(gè)規(guī)模較小的同類問(wèn)題。 合并：按原問(wèn)題的要求，將子問(wèn)題的解逐層合并成原問(wèn)題的解。其過(guò)程大致如下： 分 治 策 略 If 問(wèn)題不可分 then begin 直接求解； 返回問(wèn)題的解； else begin 從原問(wèn)題中劃分出含 1/n運(yùn)算對(duì)象的子問(wèn)題 1； 遞歸調(diào)用分治法過(guò)程，求出解 1； 從原問(wèn)題中劃分出含 1/n運(yùn)算對(duì)象的子問(wèn)題 2； 遞歸調(diào)用分治法過(guò)程，求出解 2； …… 從原問(wèn)題中劃分出含 1/n運(yùn)算對(duì)象的子問(wèn)題 n； 遞歸調(diào)用分治法過(guò)程，求出解 n； 將解 解 …… 解 n組合成整個(gè)問(wèn)題的解； end。 [算法分析 ]：假設(shè)數(shù)據(jù)個(gè)數(shù)為 n，存放在數(shù)組 A[1..n]中。 min:=a[1]。 for i:=2 to n do if a[i]max then max:=a[i] else if a[i]min then min:=a[i] 使用分治策略：把 n(n2)個(gè)數(shù)據(jù)先分成兩組，分別求最大值、最小值，然后分別將這兩組的最大值和最小值進(jìn)行比較，求出全部元素的最大值和最小值。 使用這一算法 ， 比較次數(shù)為 2（ n1） 。 源程序 例 賽程問(wèn)題 有 n個(gè)編號(hào)為 1到 n的運(yùn)動(dòng)員參加某項(xiàng)運(yùn)動(dòng)的單循環(huán)比賽，即每個(gè)運(yùn)動(dòng)員要和所有其他運(yùn)動(dòng)員進(jìn)行一次比賽。 輸入數(shù)據(jù)：運(yùn)動(dòng)員人數(shù) n(n=10000)。 [算法分析 ] 由于 n個(gè)運(yùn)動(dòng)員要進(jìn)行單循環(huán)比賽，且在 n1天內(nèi)要結(jié)束全部比賽，經(jīng)過(guò)分析，當(dāng)且僅當(dāng) n為 2的整數(shù)次冪時(shí)，問(wèn)題才有解，當(dāng)然解是唯一的。給第一組運(yùn)動(dòng)員安排一個(gè)比賽日程，得到一個(gè) n/2階的方陣A1；同時(shí)給第二組的運(yùn)動(dòng)員安排一個(gè)比賽日程，同樣得到一個(gè) n/2階的方陣 A2。因此原問(wèn)題的解可以由分解后的兩個(gè)子問(wèn)題的解合并起來(lái)。 源程序 例 設(shè)有 20名學(xué)生的姓名、數(shù)學(xué)成績(jī)，按照字典順序存放學(xué)生姓名及其相對(duì)應(yīng)的成績(jī)于數(shù)組中，現(xiàn)從鍵盤輸入一個(gè)學(xué)生的姓名，編程查找該學(xué)生是否在這 20個(gè)學(xué)生中，如果在，請(qǐng)輸出他的姓名及數(shù)學(xué)成績(jī)，否則輸出“ NO FOUND” [解析 ]： 根據(jù)題意，其數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)為記錄型數(shù)組，有兩個(gè)域：姓名域、數(shù)學(xué)成績(jī)域。 查找一個(gè)學(xué)生的姓名及相應(yīng)成績(jī)：可以用順序查找，即從第一個(gè)學(xué)生姓名開(kāi)始，順次查找到所需要的學(xué)生姓名，其時(shí)間復(fù)雜度為 O(n)。算法如下 ： 首先看將要查找學(xué)生的姓名與中間位置的 a[mid].name是否相同，若相同則查找成功，輸出該學(xué)生姓名和成績(jī)； 若查找學(xué)生姓名順序大于中間位置學(xué)生姓名，則余下查找在數(shù)據(jù)序列的后半部分查找； 若查找學(xué)生姓名順序小于中間位置學(xué)生姓名，則余下查找在數(shù)據(jù)序列的前半部分查找； 重復(fù)以上三步操作，直到查找到或查無(wú)此人為止。 例 AB兩地的距離為 S公里，甲、乙、丙三人從 A地到 B地共同完成任務(wù)。問(wèn)題是從 A出發(fā)時(shí) X只能載一人，回頭接人時(shí)才能載兩人，試問(wèn)怎樣安排行程，才能使甲、乙、丙三人盡快同時(shí)到達(dá) B地后共同完成任務(wù)（已知 V1V2V3）。 由此可以看出：甲乘車到 C，從 C步行到 B；乙乘 Y車到 E，然后步行到 D，再?gòu)?D乘 X車到達(dá) B地；丙步行到 G點(diǎn)，被出租車Y接到 D點(diǎn)會(huì)同乙乘出租車 X到達(dá) B地。這里設(shè)出發(fā)點(diǎn)到甲下車點(diǎn)的距離為 k 當(dāng)確定甲下車點(diǎn) C后，接著用同樣方法測(cè)試 D點(diǎn)位置，此時(shí)測(cè)試區(qū)域?yàn)?AC，確定點(diǎn)為 D。 源程序 動(dòng)態(tài)規(guī)劃是對(duì)最優(yōu)化問(wèn)題的一種新的算法設(shè)計(jì)方法。由此提出了解決這類問(wèn)題的“最優(yōu)化原理”，創(chuàng)建了最優(yōu)化問(wèn)題的一種新的算法設(shè)計(jì)方法 動(dòng)態(tài)規(guī)劃。它適用的原則是優(yōu)化原則，它可以將整體優(yōu)化分解為若干個(gè)局部?jī)?yōu)化。在劃分階段時(shí)，注意有序或可排序。 3）確定決策并寫出狀態(tài)轉(zhuǎn)移方程：一般是根據(jù)相鄰兩個(gè)階段各狀態(tài)之間的關(guān)系來(lái)確定決策。 5）編寫程序。 通過(guò)三段路程的最短路徑可以用各自的最短路徑，求他們 的和。 [算法分析 ]：窮舉法：時(shí)間復(fù)雜度： n1*n2*n3, 貪心法：時(shí)間復(fù)雜度： n1+n2+n3,可行 。從頂點(diǎn)出發(fā)，可以向左走或向右走，如圖： 從根結(jié)點(diǎn) 13出發(fā)向左、向右的路徑長(zhǎng)度可以是： 13117147，其和為 52 1311121413，其和為 63 若要求從根結(jié)點(diǎn)開(kāi)始，找出一條路徑，使路徑之和最大，若存在多條請(qǐng)輸出任意一條。當(dāng) N=1， P=1 N=2， P=2 N=3， P=4 …… N=k,P=2k1。 2）用貪心法：本題若用貪心法則： 1311121413，其和為 63，實(shí)際上存在另一條路徑： 138261524，其和為 86；貪心法問(wèn)題所在：眼光短淺?；痉椒ǎ? 劃分階段：按三角形的行，劃分階段，若有 n行，則有 n1個(gè)階段，找到問(wèn)題求解的最優(yōu)途徑。 C、 if xy then 選擇 x 且取得最大和為 13+x else 選擇 y 且取得最大和為 13+y 這樣，原先求根結(jié)點(diǎn)到底端的最大路徑問(wèn)題，變?yōu)閺?11出發(fā)和和從 8出發(fā)求路徑和的子問(wèn)題。 [決策：路徑和最大 ] [狀態(tài)轉(zhuǎn)移方程： Fi=max(Fi1(左 ), Fi1(右 ))] A、當(dāng)?shù)降箶?shù)第二層時(shí)，每個(gè)結(jié)點(diǎn)其后繼僅有兩個(gè)結(jié)點(diǎn)，可以直接比較，選擇最大值為前進(jìn)方向，從而求得從根結(jié)點(diǎn)開(kāi)始到底端的最大路徑。 C、算法：數(shù)組初始化，輸入每個(gè)結(jié)點(diǎn)值以及初始的最大路徑、前進(jìn)方向 0；從倒數(shù)第二層開(kāi)始向上一層求最大路徑，共循環(huán) n1次；從頂向下，輸出路徑：關(guān)鍵是 j的值，由于行逐漸遞增，表示向下，究竟是向下還是向右取決于列的值。 源程序分析 例 求一組數(shù)列的最長(zhǎng)不下降序列 。 在一個(gè)數(shù)列中可能有多個(gè)不下降序列 ， 輸出最長(zhǎng)的序列 。 b[i,1]表示第 i個(gè)數(shù)的數(shù)值本身； b[i,2]表示第 i項(xiàng)到最后一項(xiàng)最長(zhǎng)不下降序列的長(zhǎng)度； b[i,3]表示最長(zhǎng)不下降序列經(jīng)過(guò)此項(xiàng)之后 ， 后面繼續(xù) 的項(xiàng) ， 若 b[i,3] =0則表示后面沒(méi)有連接的數(shù) 。 從倒數(shù)第二項(xiàng)開(kāi)始計(jì)算 ， 由于在其后僅有一個(gè)數(shù)據(jù)項(xiàng) ， 所以計(jì)算機(jī)做一次比較后保存最大數(shù) 。 用表格表示所構(gòu)造出的 b[1..n,1..3]初始表如下： 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 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 b[i,1] b[i,2] b[i,3] 求解過(guò)程 ： 從倒數(shù)第二項(xiàng)開(kāi)始計(jì)算 ， 由于后面僅有 1項(xiàng) ， 所以做一次比較 ， 因 6315， 不符合問(wèn)題要求 ， 不作任何鏈接 ， 長(zhǎng)度仍為 1。b[i,3]:=k。 但是這種攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度 ， 但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度 。 所以一套系統(tǒng)有可能不能攔截所有的導(dǎo)彈 。 計(jì)算一套導(dǎo)彈攔截系統(tǒng)最多能夠攔截多少枚導(dǎo)彈 。 迷宮中存在一些障礙物無(wú)法通過(guò) 。 求所能收集的寶藏的最大價(jià)值 。 考慮迷宮某一點(diǎn) ， 要求走到這一點(diǎn)所 能收集的寶藏的最大價(jià)值 ， 先求出走到它在邊和 上邊所能收集的寶藏的最大價(jià)值 。 狀態(tài)轉(zhuǎn)移方程 ： Fi,j=max{Fi,j1|j1, Fi1,j |i1}+ Ai,j 邊界條件： F1,1 = A1， 1 answer= Fn,m 源程序 在一個(gè)操場(chǎng)上擺放著一行共 n堆石子 。 規(guī)定每次只能選相鄰的兩堆合并成新的一堆 ， 并將新的一堆石子數(shù)記為該次合并的得分 ， 請(qǐng)編程計(jì)算出將 n堆石子合并成一堆的最小得分 。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師把他帶到一個(gè)到處都是草藥的山洞里對(duì)他說(shuō)：“孩子，這個(gè)山洞里有一些不同的草藥，采每一株都需要一些時(shí)間，每一株也有它自身的價(jià)值。如果你是一個(gè)聰明的孩子，你應(yīng)該可以讓采到的草藥的總價(jià)值最大。接下來(lái)的 M行每行包括兩個(gè)在 1到 100之間（包括 1和100）的整數(shù)，分別表示采摘某株草藥的時(shí)間和這株草藥的價(jià)值。 【 數(shù)據(jù)規(guī)模 】 對(duì)于 30%的數(shù)據(jù) ， M = 10； 對(duì)于全部的數(shù)據(jù) ， M =