算法分析與設(shè)計(jì)復(fù)習(xí)題答案

算法的定義及五大特性？算法（Algorithm）：對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列。算法的五大特性：⑴輸入：一個(gè)算法有零個(gè)或多個(gè)輸入。⑵輸出：一個(gè)算法有一個(gè)或多個(gè)輸出。⑶有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。⑷確定性：算法中的每一條指令必須有確切的含義，對(duì)于相同的輸入只能得到相同的輸出。⑸可行性：算法描述的操作可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本操作執(zhí)行有限次來(lái)實(shí)現(xiàn)。最好最壞和平均情況。給定算法排序用大O記號(hào)。如果問(wèn)題規(guī)模相同，時(shí)間代價(jià)與輸入數(shù)據(jù)有關(guān)，則需要分析最好情況、最壞情況、平均情況。最好情況：出現(xiàn)概率較大時(shí)分析最差情況：實(shí)時(shí)系統(tǒng)平均情況：已知輸入數(shù)據(jù)是如何分布的，通常假設(shè)等概率分布畫(huà)出對(duì)三個(gè)數(shù)進(jìn)行排序的判定樹(shù)，并分析時(shí)間性能。aa1<a2a1<a2<a3是是是否否否a1<a3a2<a3a2<a1<a3a2<a3a3<a2<a1a2<a3<a1a1<a3a3<a1<a2a1<a3<a2否否是是n!=O(nn),全排序葉子結(jié)點(diǎn)至少有n!個(gè)，n個(gè)排序有n!多種情況，每個(gè)葉子對(duì)應(yīng)一種排序結(jié)果。舉例說(shuō)明n個(gè)NP完全問(wèn)題，解釋一下，寫(xiě)出三種以上。1．SAT問(wèn)題（BooleanSatisfiabilityProblem）2．最大團(tuán)問(wèn)題（MaximumCliqueProblem）3．圖著色問(wèn)題（GraphColoringProblem）4.哈密頓回路問(wèn)題（HamiltonianCycleProblem）5．TSP問(wèn)題（TravelingSalsmanProblem）6．頂點(diǎn)覆蓋問(wèn)題（VertexCoverProblem）7．最長(zhǎng)路徑問(wèn)題（LongestPathProblem）8．子集和問(wèn)題（SumofSubsetProblem）給定模式計(jì)算next值。KMPT＝“abaababc”next的值，前面重疊子串有多少。j=1時(shí)，next[1]=0；j=2時(shí)，next[2]=1；j=3時(shí)，t1≠t2，next[3]=1；j=4時(shí)，t1＝t3，next[4]=2；j=5時(shí)，t2≠t4，令k=next[2]=1，t1＝t4，next[5]=k+1=2；j=6時(shí)，t2＝t5，next[6]=3；j=7時(shí)，t3＝t6，next[7]=4；j=8時(shí)，t4≠t7，k=next[4]=2，t2＝t7，next[8]=k+1=3?？焖倥判虻姆种尾呗?。（1）劃分：選定一個(gè)記錄作為軸值，以軸值為基準(zhǔn)將整個(gè)序列劃分為兩個(gè)子序列r1…ri-1和ri+1…rn，前一個(gè)子序列中記錄的值均小于或等于軸值，后一個(gè)子序列中記錄的值均大于或等于軸值；（2）求解子問(wèn)題：分別對(duì)劃分后的每一個(gè)子序列遞歸處理；（3）合并：由于對(duì)子序列r1…ri-1和ri+1…rn的排序是就地進(jìn)行的，所以合并不需要執(zhí)行任何操作。簡(jiǎn)述最大子段和問(wèn)題的分治策略。（1）劃分：按照平衡子問(wèn)題的原則，將序列(a1,a2,…,an)劃分成長(zhǎng)度相同的兩個(gè)子序列(a1,…,a)和(a＋1,…,an)，則會(huì)出現(xiàn)以下三種情況：①a1,…,an的最大子段和＝a1,…,a的最大子段和；②a1,…,an的最大子段和＝a＋1,…,an的最大子段和；③a1,…,an的最大子段和＝，且（2）求解子問(wèn)題：對(duì)于劃分階段的情況①和②可遞歸求解，情況③需要分別計(jì)算則s1+s2為情況③的最大子段和（3）合并：比較在劃分階段的三種情況下的最大子段和，取三者之中的較大者為原問(wèn)題的解。寫(xiě)出最優(yōu)二叉查找樹(shù)的動(dòng)態(tài)規(guī)劃函數(shù)對(duì)于P54的查找集合，寫(xiě)出二維表C、R的最終狀態(tài)動(dòng)態(tài)規(guī)劃函數(shù)：C(i,i-1)=0(1≤i≤n+1)C(i,i)=pi(1≤i≤n)C(i,j)=min{C(i,k-1)+C(k+1,j)+}(1≤i≤j≤n,i≤k≤j)按對(duì)角線(xiàn)逐條計(jì)算每一個(gè)C(i,j)和R(i,j)，得到最終表。

01234100.10.41.11.72

00.20.81.43

00.41.04

00.35

0

012341

122332

2333

334

45

二維表C(b)二維表R最終表的狀態(tài)d=1d=2d=3d=1d=2d=3對(duì)于TSP問(wèn)題采用最近鄰點(diǎn)貪心策略，對(duì)于給定圖的代價(jià)矩陣，寫(xiě)出求解TSP問(wèn)題的過(guò)程。最近鄰點(diǎn)策略：從任意城市出發(fā)，每次在沒(méi)有到過(guò)的城市中選擇最近的一個(gè)，直到經(jīng)過(guò)了所有的城市，最后回到出發(fā)城市2525221543225221543232522154327363215432233215432(a)5城市的代價(jià)矩陣(b)城市1→城市4(c)城市4→城市3(d)城市3→城市5(e)城市5→城市2(f)城市2→城市1最近鄰點(diǎn)貪心策略求解TSP問(wèn)題的過(guò)程C=∞33263∞73237∞25232∞36253∞232∞36253∞寫(xiě)出由貪心法求解圖著色的算法P22第七章1．color[1]=1;//頂點(diǎn)1著顏色12．for(i=2;i<=n;i++)//其他所有頂點(diǎn)置未著色狀態(tài)color[i]=0;3．k=0;4．循環(huán)直到所有頂點(diǎn)均著色4.1k++;//取下一個(gè)顏色4.2for(i=2;i<=n;i++)//用顏色k為盡量多的頂點(diǎn)著色4.2.1若頂點(diǎn)i已著色，則轉(zhuǎn)步驟4.2，考慮下一個(gè)頂點(diǎn);4.2.2若圖中與頂點(diǎn)i鄰接的頂點(diǎn)著色與頂點(diǎn)i著顏色k不沖突，則color[i]=k;5．輸出k;寫(xiě)出用回溯法求解哈密頓回路的算法1．將頂點(diǎn)數(shù)組x[n]初始化為0，標(biāo)志數(shù)組visited[n]初始化為0；2．k=1;visited[1]=1;x[1]=1;從頂點(diǎn)1出發(fā)構(gòu)造哈密頓回路；3．while(k>=1)3.1x[k]=x[k]+1，搜索下一個(gè)頂點(diǎn);3.2若(n個(gè)頂點(diǎn)沒(méi)有被窮舉)執(zhí)行下列操作3.2.1若(頂點(diǎn)x[k]不在哈密頓回路上&&(x[k-1],x[k])∈E)，轉(zhuǎn)步驟3.3;3.2.2否則，x[k]=x[k]+1，搜索下一個(gè)頂點(diǎn)；3.3若數(shù)組x[n]已形成哈密頓路徑，則輸出數(shù)組x[n]，算法結(jié)束；3.4否則，3.4.1若數(shù)組x[n]構(gòu)成哈密頓路徑的部分解，則k=k+1，轉(zhuǎn)步驟3；3.4.2否則，重置x[k]，k=k-1，取消頂點(diǎn)x[k]的訪(fǎng)問(wèn)標(biāo)志，轉(zhuǎn)步驟3；用回溯法求解4皇后問(wèn)題的搜索過(guò)程。n皇后問(wèn)題，即在n×n的棋盤(pán)上擺放n個(gè)皇后，使任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線(xiàn)上。QQQ××QQ×Q×××××QQQQ×Q××××QQ×××QQQQQQQ××Q(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)QQ×Q寫(xiě)出用動(dòng)態(tài)規(guī)劃法求解近似串匹配的算法P65.第6章，并分析時(shí)間復(fù)雜度。大O記號(hào)表示。intASM(charP[],charT[],intm,intn,intK){for(j=1;j<=n;j++)//初始化第0行D[0][j]=0;for(i=0;i<=m;i++)//初始化第0列D[i][0]=i;for(j=1;j<=n;j++)//根據(jù)遞推式依次計(jì)算每一列{for(i=1;i<=m;i++){if(P[i]==T[j])D[i][j]=min(D[i-1][j-1