華中師范大學(xué)網(wǎng)絡(luò)教育學(xué)院《算法設(shè)計與分析》練習(xí)題庫及答案

《算法設(shè)計與分析》練習(xí)題庫及答案(加粗紅色字體為2013下新增題目)概念題：請解釋下列術(shù)語。1．?dāng)?shù)據(jù)類型2．隊列3．多項式復(fù)雜度4．滿二叉樹5．NP-難度6．算法7．SIMD(并行算法)8．連通圖9．抽象數(shù)據(jù)類型10．指數(shù)復(fù)雜度11．遞歸12．完全二叉樹13．狀態(tài)空間樹14．NP-完全的15．算法與過程16．有向圖與無向圖17．樹18．P類問題19.確定的算法20.NP問題21.最小生成樹22.動態(tài)規(guī)劃23.數(shù)據(jù)結(jié)構(gòu)24.排序二、填空題1.簡單遞選分類過程中所需進行移動存儲的操作次數(shù)較少，其最大值為___________。2.一組有序的n個數(shù)，采用逐個查找算法查找一給定的數(shù)是否出現(xiàn)在序列中，其算法復(fù)雜性為_____________。3.動態(tài)規(guī)劃實際上是研究一類__________________的算法，其應(yīng)用非常廣泛。4.BFS算法的中文名稱是______________________算法。5.一棵樹中定義為該樹的高度或深度。6.二分檢索樹要求樹中所有結(jié)點中的元素滿足。7.比較樹的結(jié)點由稱為和的兩種結(jié)點組成。8.外結(jié)點用一個結(jié)點表示，在二分檢索算法中它表示不成功檢索的一種情況。9.由根到所有內(nèi)部結(jié)點的距離之和稱為;由根到所有外部結(jié)點的距離之和稱為.10．max和min被看成是兩個內(nèi)部函數(shù)，它們分別求取兩個元素的大者和小者，并認為每次調(diào)用其中的一個函數(shù)都只需作次元素比較。11．如果用分治策略來設(shè)計分類算法，則可使最壞情況時間變?yōu)閛(nlogn)。這樣的算法稱為。12.貪心算法可行的第一個基本要素是。13.當(dāng)一個問題的最優(yōu)解包含著它的子問題的最優(yōu)解時，稱此問題具有性質(zhì)。14.二路歸并模式可以用樹來表示。15.kruskal算法對于每一個無向連通圖g產(chǎn)生一棵。16．因為如果有環(huán)，則可去掉這個環(huán)且不增加這條路徑的長度(不含有負長度的環(huán))。如果k是這條最短路徑上的一個中間結(jié)點，那么—由i到k和由k到j(luò)的這兩條子路徑應(yīng)分為別是由i到k和．由k到j(luò)的最短路徑。否則，這條由i到j(luò)的路徑就不是具有最小長度的路徑。于是，原理成立。17.為了把動態(tài)規(guī)劃應(yīng)用于得到一棵最優(yōu)二分檢索樹的問題，需要把構(gòu)造這樣的一棵樹看成是一系列決策的結(jié)果，而且要能列出求取序列的遞推式.18.所謂可靠性設(shè)計最優(yōu)化問題是在的約束下，如何使系統(tǒng)的可靠性達到最優(yōu)的問題。19.貨郎擔(dān)問題是求取具有的周游路線問題。20.一個算法就是一個有窮規(guī)則的集合，其中之規(guī)則規(guī)定了解決某一特殊類型問題的一系列運算，此外，算法還應(yīng)具有以下五個重要特性：__________，__________，__________，__________，__________。21.算法的復(fù)雜性有_____________和___________之分，衡量一個算法好壞的標準是___________。22.某一問題可用動態(tài)規(guī)劃算法求解的顯著特征是_____________________。23.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，請給出序列X和Y的一個最長公共子序列_____________________________。三、程序填空題。1．對二叉樹的先根次序周游算法遞歸表示為：procedurePREORDER(T)//T是一棵二元樹。T中每個結(jié)點有三個信息段：ICHILD，，DATA，RCHILD//ifT≠0thencallVISIT(T)__________(1)_____________________(2)___________endifendPREORDER2．遞歸求取最大和最小元素procedureMAXMIN(i．j.fmax，fmin)//A(1：n)是含有n個元素的數(shù)組，參數(shù)i，j是整數(shù)，1≤i，j≤n////該過程把A(i，j)中的最大和最小元素分別賦給fmax和fmin//integeri，j；globaln，A(1：n)case ：i=j：fmax?fmin?A(i) ：i=j-1：ifA(i)<A(j)thenfmax?A(j)；fmin?A(i)elsefmax?A(i)；fmin?A(j)endif:else:mid?___________(1)_________________________(2)______________ fmax?max(gmax，hmax)fmin?min(gmin，hmin)endcaseendMAXMIN3．用回溯法求子集和數(shù)問題的遞歸回溯算法procedureSUMOFSUB<s，k，r)//找W(1：n)中和數(shù)為M的所有子集，進入此過程時X(1)，…，X(k-1)的值已確定。。這些對Ｗ(j)按非降次序排列。假定W(1)≤M.//globalintegerM，n;globalrealW(1：n)；globalBooleanX(1：n)realr,s；integerk，j//生成左兒子。注意，由于，因此s+W(k)≤M// X(k)?1 ifs+W(k)=Mthen//子集找到／／ print(X(j),j?1tok)elseifs+W(k)+W(k+1)<=Mthen//B=yrue//______________(1)__________________endif//生成右兒子和計算B的值//endif ifs+r-W(k)≥Mands+W(k+1)≤M／／B＝true／／thenX(k)?0_______________(2)_________________ endifendSUMOFSUB4．用回溯法求n-皇后問題的所有解procedureNQUEENS(n)//此過程使用回溯法求出在一個n*n棋盤上放置n個皇后，使其不能互相攻擊的所有可能位置//integerk，n，X(1:n)X(1)?0；k?1//k是當(dāng)前行；X(k)是當(dāng)前列//whilek>0do//對所有的行執(zhí)行以下語句//X(k)?X(k)+1//移到下一列//whileX(k)≤nandnotPLACE(k)do//此處能放這個皇后嗎//____________(1)___________repeatifX(k)≤n//找到一個位置//thenifk＝n//是一個完整的解嗎//thenprint(X)//是，打印這個數(shù)組//else_______(2)_______；_______(3)_______；//轉(zhuǎn)向下一行//endifelse_______(4)_______//回溯//endifrepeatendNQUEENS5.二分查找算法procedurebinsrch1(a，n，x，j)//除n>0外，其余說明與binsrch同//integerlow，high，mid，j，n;low?1;high?(1)//high總比可能的取值大1//whilelow<(2)domid?ifx<a(mid)//在循環(huán)中只比較一次//then(3)else(4)//x≥a(mid)//endifrepeatifx=a(low)thenj?low//x出現(xiàn)//elsej?o//x不出現(xiàn)//endif；endbinsrch16.求圖中每對頂點之間的最短路徑。procedureall—Paths(cost，a,n)／／cost(n，n)是n結(jié)點圖的成本鄰接矩陣；a(i，j)是結(jié)點vi到vj的最短路徑的成本；cost(i，j)＝0，1≤i≤n／／integeri，j，k，n；realcost(n，n)，a(n，n)fori?1tondoforj<--1tondoa(i，j)<--cost(i，j)repeatrepeat／／將cost(i，j)復(fù)制到a（i,j）／／fork<--1toondo／／對最高下標為k的結(jié)點的路徑//fori?-1tondo／／對于所有可能的結(jié)點對／／fori<--1tondoa(i，j)<--min{(1)，(2)}repeatrepeatrepeatendall—Paths7.簡單的合并與查找運算procedureu(i，j)//根為i和j的兩個不相交集合用它們的并來取代//integeri，jParent(i)<--j;enduproceduref(i)//找包含元素i的樹的根//integeri，jj<--i;while⑴do//若此結(jié)點是根，則Parent(j)<--0//⑵;repeatreturn(j)endf8.插入分類procedureinsertionsort(a，n)／／將a(1：n)中的元素按非降次序分類，n≥1//a(0)?-∞／／開始時生成一個虛擬值//forj?⑴tondo／／a(1:j-1)已分類//item?a(j)；i?⑵whileitem<a(i)do／／0≤i<j／／a(i+1)?a(i)；i?i-1repeata(i+1)?-itemrepeatendinsertionsort9.歸并分類proceduremergesort(low,high)／／a(low:high)是一個全程數(shù)組，它含有high-low+1≥0個待分類的元素//integerlow,high；iflow<high；thenmid?//求這個集合的分割點//call⑴／/將一個子集合分類／／call⑵／／將另一個子集合分類／／call⑶／／歸并兩個已分類的子集合//endifendmergesort10.使用鏈接表歸并已分類的集合proceduremerge1(q，r，p)／／q和r是全程數(shù)組link(1:n)中兩個表的指針。這兩個表可用來獲得全程數(shù)組a(1：n)中已分類元素的子集合。此算法執(zhí)行后構(gòu)造出一個由p所指示的新表，利用此表可以得到按非降次序把a中元素分好類的元素表，同時q和r所指示的表隨之消失。假定link(0)被定義,且假定表由0所結(jié)束／／globaln,a(1:n),link(0:n)localintegeri，j，ki?q；j?r；k?0／／新表在link(0)處開始//while⑴and⑵do//當(dāng)兩表皆非空時作//ifa(i)≤a(j)／／找較小的關(guān)鍵字／／thenlink(k)?i;k?i；i?link(i)／／加一個新關(guān)鍵字到此表//else⑶endifrepeatifi=0then⑷elselink(k)?iendifp?link(0)endmergel11.作業(yè)排序算法的概略描述proceduregreedy-job(d，j，n)／／作業(yè)按p1≥p：≥…≥Pn的次序輸入，它們的期限值d(i)≥1,1≤i≤n,n≥1.j是在它們的截止期限前完成的作業(yè)的集合／／

j?{1}

for⑴tondo

ifj∪{i}所有作業(yè)都能在它們的截止期限前完成then⑵endifrepeatendgreedy—job12.生成二元歸并樹算法lineproceduretree(l，n)／／l是n個單結(jié)點二元樹的表//fori?1ton-1docallgetnode(t)／／用于歸并兩棵樹／／lchild(t)<--least(l)／／最小的長度／rchild(t)<--least(l)weight(t)<--⑴callinsert(l，t)repeat⑵／／留在l中的樹是歸并樹"endtreekruskal算法lineprocedurekruskal(e,cost，n，t,mincost)／／g有n個結(jié)點，e是g的邊集。cost(u，v)是邊(u，v)的成本。t是最小成本生成樹的邊集。mincost是它的成本"realmincost，cost(1:n，1:n)；integerParent(1:n)，t(1：n-1，2)，n；以邊成本為元素構(gòu)造一個min—堆Parent?1／／每個結(jié)點都在不同的集合中礦i?mincost?0whilei<n一1and堆非空do從堆中刪去最小成本邊(u，v)并重新構(gòu)造堆j?find(u)；k?find(v)ifj≠kthen⑴t(i，1)<—ut(i，2)?vmincost<—⑵callunion(i，k)endif

repeat

ifi≠n-1thenprint(‘nospanningtree’)endif

return

endkruskal多段圖的向前處理算法lineprocedurefgraPh(e，k，n，P)／／輸入是按段的順序給結(jié)點編號的，有n個結(jié)點的k段圖。e是邊集，c(i，j)是邊<i，j>的成本。P(1:k)是最小成本路徑//realcost(n)，integerd(n一1)，P(k)，r，j，k，n⑴forj<--n一1to1by一1do／／計算cost(j)／／設(shè)r是一個這樣的結(jié)點，<j，r>∈e且使c(j,r)+cost(r)取最小值cost(j)+c(j，r)+cost(r)d(j)?rrepeat／／找一條最小成本路徑／／P(1)<一1；P(k)?nforj<--2to⑵do//找路徑上的第斗個結(jié)點／／P(j)<--d(P(j一1))repeatendfgraPh15．求最小元的并行算法proceduremimdmin(a(1)，a(2),...，a(n)，min)輸入；i＝{a(1)，a(2),…，a<n}}輸出：i中最小元min處理器個數(shù)；pifn>pthenforeachpi：1≤i≤ppardoforj＝i+ptonsteppdoif⑴thena(i)?a(j)endifrepeatendfork?pelsek?n；endifwhilek>ldoforeachpi：1≤i≤[k／2]pardoifa(k-i+1)<a(i)then⑵endifendfork?[k／2]repeatmin?a(1)endmimdmin16．0／1背包問題的回溯法求解。procedurebknaPl(m，n，w，P，fw，fp，x)／／m是背包容量。有n種物品，其重量與效益分別存在數(shù)組w(1：n)和P(1：n)中sp(i)/w(o≥P(i+1)／w(i+1)。fw是背包的最后重量，fp是背包取得的最大效益。x(1：n)中每個元素取0或1值。若物品k沒放人背包，則x(k)；0；否則x(k)＝1//

integern，k，y(1：n)，i，x(1：n)；real，m，w(1：n)，P(1：n)，fw，fp，cw，cp；cw?cp?o；k?1；fp?l／／cw是背包當(dāng)前重量；cp是背包當(dāng)前取得的效益值//loopwhilek≤nand⑴≤mdo／／將物品、k放人背包／／cw?cw+w(k)；cp?cp+P(k)；y(k)?1；k?k+1repeatifk>nthenfp?cp；fw?cw；k?n；x?y／／修改解//else⑵／／超出m，物品k不適合／／endifwhilebound(cp、cw，k，m)≤fpdo//上面置了fp后，bound=fp//whilek0andy(k)1dok?k-1，//找最后放人背包的物品//repeatifk＝0thenreturnendif//找最后放人背包的物品//y(k)?0；cw?cw-w(k)；cp?cp—P(k)／／移掉第k項／／repeatk?k+1repeat

endbknaPl17.設(shè)計只求一個哈密頓環(huán)的回溯算法。ProcedureHamiltonian(n){k←1;x[k]←0;Whilek>0dox[k]←x[k]+1;whileB(k)=falseandx[k]≤ndo______eq\o\ac(○,1)________repeatIfx[k]≤nthenifk=nthen{printx;return}else{k←k+1;x[k]←0;}endifelse______eq\o\ac(○,2)________endifrepeatend}procedureB(k){G[x[k-1],x[k]]≠1thenreturnfalse;fori←1tok-1doifx[i]=x[k]thenreturnfalse;endifrepeatreturntrue;}18.設(shè)計一個算法在一個數(shù)組A中找出最大數(shù)和最小數(shù)的元素。Voidmaxmin(A,n)intA[];intn;{intmax,min,i;max=A[1];min=A[1];for(i=2;i<=n;i++)if(____eq\o\ac(○,1)___)max=A[i];elseif(A[i]<min)____eq\o\ac(○,2)____;printf(“max=%d,min=%d\n”,max,min);}19.選擇排序：設(shè)數(shù)組中有N個數(shù)，取I=1，2，3，??N-1，每次找出后N-I+1個數(shù)字中最小的與第I個數(shù)字交換位置。程序如下：uses

crt;

var

n:array[1..10]

of

integer;

i,j,k,t,min:integer;

begin

clrscr;

for

i:=1

to

10

do

read(n[i]);

for

i:=1

to

9

do

begin

min:=30000;

for

j:=i

to

10

do

begin

if

n[j]<min

then

begin

___eq\o\ac(○,1)____;

k:=j;

end;

end;

t:=n[i];

___eq\o\ac(○,2)____;

n[k]:=t;

end;

for

i:=1

to

10

do

write(n[i]:4);

end.四．問答題1.算法的重要的5個特征是什么？2.什么是動態(tài)規(guī)劃？3．回溯程序的4種因素是什么？4．請解釋貪心法的基本思想，并用貪心法解決如下背包問題。背包問題：n=3,M=30,(p1,p2,p3)=(20,14,25),(w1,w2,w3)=(20,15,15)5．請解釋動態(tài)規(guī)劃的基本思想，并寫出用動態(tài)規(guī)劃解決0/1背包問題所采用的遞推方程式。6． 請解釋動態(tài)規(guī)劃的基本思想，并寫出用動態(tài)規(guī)劃解決多段圖問題所采用的遞推方程式。7．請解釋回溯法的基本思想，并寫出用回溯法解決子集和數(shù)問題的狀態(tài)空間樹。8．已知如下定義的數(shù)據(jù)結(jié)構(gòu)，請畫出它的邏輯示意圖，并說明它是何種類型的數(shù)據(jù)結(jié)構(gòu)。DS=<D,R,OP> D={1,2,3,4,5,6} R={<1,2>,<1,3>,<2,3>,<3,6>,<3,5>,<5,4>,<6,2>,<4,3>,<5,6>} 9．若將數(shù)據(jù)序列D={1,2,3}輸入堆棧，請給出所有可能的堆棧輸出。10.已知如下多段圖，請用動態(tài)規(guī)劃方法的向后處理法寫出求解此問題的遞推公式并完成對各結(jié)點的計算。11．請用Prim方法求下圖所示的最小生成樹。（請寫出該方法的基本思想和主要中間過程）。11235641030452520551540355012.最佳原理的基本思想是什么？13.利用分枝定界法求解流動推銷員問題。設(shè)給定5個城市的距離矩陣為D==(dij)5×514.將所給定序列a[1:n]分為長度相等的兩段a[1:n/2]和a[n/2+1:n]，分別求出這兩段的最大子段和，則a[1:n]的最大子段和有哪三種情形？ 15.由0——1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以對m（i,j）建立怎樣的遞歸式? 16. 對于下圖使用Dijkstra算法求由頂點a到頂點h的最短路徑?！端惴ㄔO(shè)計與分析》練習(xí)題庫參考答案概念題：請解釋下列術(shù)語。1．?dāng)?shù)據(jù)元素的集合。 2．隊列是一個線性表，限制為只能在固定的一端進行插入，在固定的另一端進行刪除。3．對于算法a，如果存在一多項式p()，使得對a的每個大小為n的輸入，a的計算時間為o(p(n))，則稱a具有多項式復(fù)雜度4．二叉樹的層數(shù)i與該層上的結(jié)點數(shù)n的關(guān)系為：n(i)=。5．如果可滿足性約化為一個問題L，則稱該問題為NP-難度的。6．算法就是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型問題的一系列運算。。7．多數(shù)據(jù)單指令流8．若圖的任意兩個節(jié)點間均存在路徑可達，則稱該圖為連通圖。9.是指一個數(shù)學(xué)模型以及定義在該模型上的一組操作。10．算法的復(fù)雜度只能用指數(shù)函數(shù)對其限界。11．函數(shù)或過程直接或間接調(diào)用它自己。12．和高度相同的滿二叉樹的每個對應(yīng)的頂點編號相同的樹13．由所有可行狀態(tài)所構(gòu)成的樹。14．如果L時NP難度的且L∈NP，則稱問題L是NP-完全的。15．算法是一個步驟的序列，滿足：有窮性、可行性、確定性、輸入、輸出；過程不需要滿足由窮性。16．有向圖的每條邊有起點與終點之分，且用箭頭指向邊的終點。無向圖的邊無起點和終點之分，邊無箭頭。17．樹(tree)是一個或多個結(jié)點的有限集合，，它使得：①有一個特別指定的稱作根(root)的結(jié)點；②剩下的結(jié)點被分成m≥0個不相交的集合tl，…，tm，這些集合的每一個都是一棵樹，并稱t1，…，tm為這根的子樹(subtree)。18．P是所有可在多項式時間內(nèi)用確定算法求解的判定問題的集合。19．運算結(jié)果是唯一確定的算法20.nP是所有可在多項式時間內(nèi)用不確定算法求解的判定問題的集合21．在一給定的無向圖G=(V,E)中，(u,v)代表連接頂點u與頂點v的邊（即），而w(u,v)代表此邊的權(quán)重，若存在T為E的子集（即）且為無循環(huán)圖，使得T中所有邊的權(quán)重之和w(T)最小，則此T為G的最小生成樹。22．動態(tài)規(guī)劃是一種在數(shù)學(xué)、計算機科學(xué)和經(jīng)濟學(xué)中使用的,通過把原問題分解為相對簡單的子問題的方式求解復(fù)雜問題的方法。23．?dāng)?shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。24．排序,就是要整理文件中的記錄,使之按關(guān)鍵字遞增(或遞減)次序排列起來的操作。二、填空題nO(n)最優(yōu)化問題寬度優(yōu)先搜索結(jié)點的最大級數(shù)互異內(nèi)結(jié)點和外結(jié)點方形內(nèi)部路徑長度、外部路徑長度一次歸并分類算法貪心選擇性質(zhì)最優(yōu)子結(jié)構(gòu)二元歸并最小成本生成樹最優(yōu)性最優(yōu)決策可容許最大成本c最小成本確定性有窮性可行性0個或多個輸入一個或多個輸出是的時間復(fù)雜性空間復(fù)雜性時間復(fù)雜度高低地方該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì){BABCD}或{CABCD}或{CADCD｝三、程序填空題。1．callPREORDER(LCHILD(T))callPREORDER(RCHILD(T))2．callMAXMIN(i，mid，gmax，gmin)callMAXMIN(mid+1,j,hmax,hmin)3．callSUMOFSUB(S+w(K),K+1,r-W(k))callSUMOFSUB(s，k+1，r—W(k))4．X(k)+X(k)+1k<-k+1；X(k)<-0k?k-15．（1）n+1(2)high-1(3)high?mid(4)low?mid6．(1)a(i，j)(2)a(i，k)+a(k，j)7.(1)Parent(i)>0(2)j<--Parent(j)8.(1)2(2)j-19.(1)mergesort(low，mid)(2)mergesort(mid+1，high)(3)merge(low，mid，high)10.(1)i≠0(2)j≠0(3)link(k)?j;k?j;j?link(j)(4)llnk(k)?j11.(1)i?2(2)j?j∪{i}12.(1)weight(lchild(t))+weight(rchild(t))(2)return(least(l))13.(1)i?i+1(2)mincost+cost(u，v)14.(1)cost(n)<--0(2)k一115．（1）a(j)<a(i)（2）a(i)?a(k-i+1)16．（1）cw+w(k)（2）y(k)?017. (1)x[k]←x[k]+1; (2)k←k-118. (1)A[i]>max (2)min=A[i]19.(1)min:=n[j] (2)n[i]:=n[k]四．問答題1.答:1)．確定性算法的每一種運算必須要有確切的定義，即每一種運算應(yīng)該執(zhí)行何種動作必須是相當(dāng)清楚的、無二義性的。在算法中不允許有諸如“計算5／0”或“將6或7與x相加”2)．能行性一個算法是能行的指的是算法中有待實現(xiàn)的運算都是基本的運算，每種運算至少在原理上能由人用紙和筆在有限的時間內(nèi)完成。整數(shù)算術(shù)運算是能行運算的一個例子，而實數(shù)算術(shù)運算則不是能行的，因為某些實數(shù)值只能由無限長的十進制數(shù)展開式來表示，像這樣的兩個數(shù)相加就違背能行性這一特性。3)．輸入一個算法有0個或多個輸入，這些輸入是在算法開始之前給出的量，這些輸入取自特定的對象集合。4)．輸出一個算法產(chǎn)生一個或多個輸出，這些輸出是同輸入有某種特定關(guān)系的量。5)．有窮性一個算法總是在執(zhí)行了有窮步的運算之后終止。2.答:在實際生活中，有這么一類問題，它們的活動過程可以分為若干個階段，而且在任一階段后的行為都僅依賴于i階段的過程狀態(tài)，而與i階段之前的過程如何達到這種狀態(tài)的方式無關(guān)，這樣的過程就構(gòu)成一個多階段決策過程。在50年代，貝爾曼(richardbellman)等人根據(jù)這類問題的多階段決策的特性，提出了解決這類問題的“最優(yōu)性原理”，從而創(chuàng)建了最優(yōu)化問題的一種新的算法設(shè)計方法——動態(tài)規(guī)劃。在多階段決策過程的每一階段，都可能有多種可供選擇的決策，但必須從中選取一種決策。一旦各個階段的決策選定之后，就構(gòu)成了解決這一問題的一個決策序列。決策序列不同，所導(dǎo)致的問題的結(jié)果也不同。動態(tài)規(guī)劃的目標就是要在所有容許選擇的決策序列中選取一個會獲得問題最優(yōu)解的決策序列，即最優(yōu)決策序列。顯然，用枚舉的方法從所有可能的決策序列中選取最優(yōu)決策序列是一種最笨拙的方法。貝爾曼認為，利用最優(yōu)性原理(Principleofoptimality)以及所獲得的遞推關(guān)系式去求取最優(yōu)決策序列可以使枚舉量急劇下降。這個原理指出，過程的最優(yōu)決策序列具有如下性質(zhì)：無論過程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對手初始決策所產(chǎn)生的狀態(tài)構(gòu)成一個最優(yōu)決策序列。如果所求解問題的最優(yōu)性原理成立，則說明用動態(tài)規(guī)劃方法有可能解決該問題。而解決問題的關(guān)鍵在于獲取各階段間的遞推關(guān)系式3．答:分治法的基本思想為：（1）分解問題為若干子問題；對子問題求解；組合各自問題的解?？焖倥判蜻^程為：procedurePARTITION(m，p)//在A(m)，A(m+1)，…，A(p-1)中的元素按如下方式重新排列：如果最初t=A(m)，則在重排完成之后，對于m和p-1之間的某個q，有A(q)=t，并使得對于m≤k<q，有A(k)≤t，而對于q<k<p，有A(k)≥t退出過程時，p帶著劃分元素所在的下標位置，即q的值返回。//integerm，p，i；globalA(m:p-1)v=A(m);i=m//A(m)是劃分元素//1ooploopi=i+1untilA(i)≥vrepeat//i由左向右移//loopp=p-1untilA(p)≤vrepeat//p由右向左移//ifi<pthencallINTERCHANGE(A(i),A(p))//A(i)和A(p)換位//elseexitendifrepeatA(m)=A(p)；A(p)=v／／劃分元素在位置p／／endPARTITIONprocedureQUICKSORT(p,q)//將全程數(shù)組A(1：n)中的元素A(p)，…，A（q）按遞增的方式分類。認為A(n+1)已被定義，且大于或等于A(p：q)的所有元素；即A(n+1)＝+∞//integerp，q；globaln，A(1:n)ifp<qthenj=q+1callPARTITION(p,j)callQUICKSORT(p,j-1)／／j是劃分元素的位置／／callQUICKSORT(j+1,q)endifendQUICKSORT 4．答:貪心法的基本思想為： （1）分析問題，求出最優(yōu)化評價標準； （2）按評價標準排序； （3）從序列中順序取元素； （4）若該元素符合要求，則放入結(jié)果表中；否則，刪除它。 背包算法為：procedureGREEDY-KNAPSACK(P，W，M，X，n)//P(1:n)和W(1:n)分別含有按P(i)／W(i)≥P(i+1)／W(i+1)排序的n件 物品的效益值和重量。M是背包的容量大小，而x(1:n)是解向量//realP(1:n)，W(1:n)，X(1:n)，M，cu；integeri，n；X=0//將解向量初始化為零//cu=M//cu是背包剩余容量//fori=1tondo ifW(i)>cuthenexitendif Xi=1 cu=cu-W(i)repeatifi≤nthenX（i）=cu／W(i)endifendGREEDY-KNAPSACK 5．答:動態(tài)規(guī)劃的基本思想為： （1）確定初始條件；（2）計算第一次結(jié)果；（3）用上一次的結(jié)果計算本次的結(jié)果；（4）若遞推到了最終結(jié)果，則算法結(jié)束；否則，轉(zhuǎn)（3）。 0/1背包問題的遞推公式為：6．答:動態(tài)規(guī)劃的基本思想為： （1）確定初始條件；（2）計算第一次結(jié)果；（3）用上一次的結(jié)果計算本次的結(jié)果；（4）若遞推到了最終結(jié)果，則算法結(jié)束；否則，轉(zhuǎn)（3）。 多段圖的遞推公式為： 7．答:回溯法的基本思想為： （1）分析問題，確定該問題的解空間及顯示條件與隱式條件； （2）確定求解問題的狀態(tài)空間樹； （3）對該狀態(tài)空間樹按深度優(yōu)先方法進行搜索； （4）對搜索的每一步，檢查該狀態(tài)是否為目標狀態(tài)； （5）若為目標狀態(tài)，則算法結(jié)束； （6）若不滿足隱式條件，則回到上一層； （7）選擇下一個孩子結(jié)點繼續(xù)搜索；若無下一個孩子可搜索，則回到上一層繼續(xù)； （8）若回到了最高層的上一層，則無解，算法結(jié)束。 子集和數(shù)問題的