西北工業(yè)大學軟件工程專業(yè)算法總復習

《西北工業(yè)大學軟件工程專業(yè)算法總復習》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、一.簡答題1.寫出回溯算法的一般模式。a)用回溯算法搜索子集樹的一般模式voidsearch(intm){if(m>n)//遞歸結束條件output();//相應的處理(輸出結果)else{a[m]=0;//設置狀態(tài)：0表示不要該物品search(m+1);//遞歸搜索：繼續(xù)確定下一個物品a[m]=1;//設置狀態(tài)：1表示要該物品search(m+1);//遞歸搜索：繼續(xù)確定下一個物品}}b)用回溯算法搜索子集樹的一般模式voidsearch(intm){if(m>n)//遞歸結束條件output();//相應的處理(輸出結果)elsefor(i=m;i<=n;i++){swap(m,i);

2、//交換a[m]和a[i]if()if(canplace(m))//如果m處可放置search(m+1);//搜索下一層swpa(m,i);//交換a[m]和a[i](換回來)}}2.分治算法的基本思想是什么？分治法的基本思想是將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解這些子問題，然后將各個子問題的解合并得到原問題的解。它的一般的算法設計模式如下：divide-and-conquer(P){if(

3、P

4、<=n0)adhoc(P);dividePintosmallersubinstancesP1,P2,...,Pk;for(i=1;i<=k;i+

5、+)yi=divide-and-conquer(Pi);returnmerge(y1,...,yk);}其中，

6、P

7、表示問題P的規(guī)模。n0為一閥值，表示當問題P的規(guī)模不超過n0時，問題已容易解出，不必再繼續(xù)分解。adhoc(P)是該分治法中的基本子算法，用于直接解小規(guī)模的問題P。當P的規(guī)模不超過n0時，直接算法adhoc(P)求解。算法merge(y1,y2,...,yk)是該分治法中的合并子算法，用于將P的子問題P1,P2,...,Pk的解y1,y2,...,yk合并為P的解。3.什么是最優(yōu)子結構性質？1）重疊子問題2）最優(yōu)子結構我們在這里討論的最優(yōu)子結構性質2）最優(yōu)子結構：如果問題的最優(yōu)

8、解所包含的子問題的解也是最優(yōu)的，我們就稱該問題具有最優(yōu)子結構性質（即滿足最優(yōu)化原理）。最優(yōu)子結構性質為動態(tài)規(guī)劃算法解決問題提供了重要線索。例如，最短路徑問題有以下最優(yōu)子結構性質：如果一個節(jié)點x是到源節(jié)點ü的最短路徑，同時又是到目的節(jié)點V的最短路徑，則最短路徑從u到v是結合最短路徑：u到x和x到v。解決任意兩點間的最短路徑的算法的Floyd-Warshall算法和貝爾曼-福特是動態(tài)規(guī)劃的典型例子。1.分支限界法的基本思想。2.簡述分治法與動態(tài)規(guī)劃算法的區(qū)別于聯(lián)系？一.算法設計（1、2兩題任選一題）1.矩陣連乘問題。2.最長公共子序列問題。#include#include

9、ring.h>intlcs_length(charx[],chary[]);intmain(){charx[100],y[100];intlen;while(1){scanf("%s%s",x,y);if(x[0]=='0')//約定第一個字符串以‘0’開始表示結束break;len=lcs_length(x,y);printf("%d",len);}}intlcs_length(charx[],chary[]){intm,n,i,j,l[100][100];m=strlen(x);n=strlen(y);for(i=0;i

10、;j++)l[0][j]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++)if(x[i-1]==y[j-1])//i,j從1開始，但字符串是從0開始l[i][j]=l[i-1][j-1]+1;elseif(l[i][j-1]>l[i-1][j])l[i][j]=l[i][j-1];elsel[i][j]=l[i-1][j];returnl[m][n];}由于每個數(shù)組單元的計算耗費Ο(1)時間，算法lcs_length耗時Ο(mn)。一.應用題（3、4選一題3易4難）1.用優(yōu)先隊列式分支限界法解決。2.寫出對下面的序列進行合并排序的過程（從小到大）。3.63149982

11、3481570（舉例）privatestaticvoidMerge(T[]array,intlo,intmid,inthi){inti=lo,j=mid+1;//把元素拷貝到輔助數(shù)組中for(intk=lo;k<=hi;k++){aux[k]=array[k];}//然后按照規(guī)則將數(shù)據(jù)從輔助數(shù)組中拷貝回原始的array中for(intk=lo;k<=hi;k++){//如果左邊元素沒了，直接將右邊的剩余元素都