算法題-計算機算法設計與分析期末試題4套(含答案)

xxx公司文件編號：文件日期：修訂次數(shù)：第1.0次更改批準審核制定方案設計，管理制度（1）用計算機求解問題的步驟：1、問題分析2、數(shù)學模型建立3、算法設計與選擇4、算法指標5、算法分析6、算法實現(xiàn)7、程序調試8、結果整理文檔編制（2）算法定義：算法是指在解決問題時，按照某種機械步驟一定可以得到問題結果的處理過程（3）算法的三要素1、操作2、控制結構3、數(shù)據結構算法具有以下5個屬性：有窮性：一個算法必須總是在執(zhí)行有窮步之后結束，且每一步都在有窮時間內完成。確定性：算法中每一條指令必須有確切的含義。不存在二義性。只有一個入口和一個出口可行性：一個算法是可行的就是算法描述的操作是可以通過已經實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。輸入：一個算法有零個或多個輸入，這些輸入取自于某個特定對象的集合。輸出：一個算法有一個或多個輸出，這些輸出同輸入有著某些特定關系的量。算法設計的質量指標：正確性：算法應滿足具體問題的需求；可讀性：算法應該好讀，以有利于讀者對程序的理解；健壯性：算法應具有容錯處理，當輸入為非法數(shù)據時，算法應對其作出反應，而不是產生莫名其妙的輸出結果。效率與存儲量需求：效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。一般這兩者與問題的規(guī)模有關。經常采用的算法主要有迭代法、分而治之法、貪婪法、動態(tài)規(guī)劃法、回溯法、分支限界法迭代法也稱“輾轉法”，是一種不斷用變量的舊值遞推出新值的解決問題的方法。利用迭代算法解決問題，需要做好以下三個方面的工作：一、確定迭代模型。在可以用迭代算法解決的問題中，至少存在一個直接或間接地不斷由舊值遞推出新值的變量，這個變量就是迭代變量。二、建立迭代關系式。所謂迭代關系式，指如何從變量的前一個值推出其下一個值的公式（或關系）。迭代關系式的建立是解決迭代問題的關鍵，通?？梢允褂眠f推或倒推的方法來完成。三、對迭代過程進行控制。在什么時候結束迭代過程這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地重復執(zhí)行下去。迭代過程的控制通?？煞譃閮煞N情況：一種是所需的迭代次數(shù)是個確定的值，可以計算出來；另一種是所需的迭代次數(shù)無法確定。對于前一種情況，可以構建一個固定次數(shù)的循環(huán)來實現(xiàn)對迭代過程的控制；對于后一種情況，需要進一步分析出用來結束迭代過程的條件。編寫計算斐波那契（Fibonacci）數(shù)列的第n項函數(shù)fib（n）。斐波那契數(shù)列為：0、1、1、2、3、……，即：fib(0)=0;fib(1)=1;fib(n)=fib(n-1)+fib(n-2)（當n>1時）。寫成遞歸函數(shù)有：intfib(intn){if(n==0)return0;if(n==1)return1;if(n>1)returnfib(n-1)+fib(n-2);}一個飼養(yǎng)場引進一只剛出生的新品種兔子，這種兔子從出生的下一個月開始，每月新生一只兔子，新生的兔子也如此繁殖。如果所有的兔子都不死去，問到第12個月時，該飼養(yǎng)場共有兔子多少只分析：這是一個典型的遞推問題。我們不妨假設第1個月時兔子的只數(shù)為u1，第2個月時兔子的只數(shù)為u2，第3個月時兔子的只數(shù)為u3，……根據題意，“這種兔子從出生的下一個月開始，每月新生一只兔子”，則有u1＝1，u2＝u1＋u1×1＝2，u3＝u2＋u2×1＝4，……根據這個規(guī)律，可以歸納出下面的遞推公式：un＝un－1×2(n≥2)對應un和un－1，定義兩個迭代變量y和x，可將上面的遞推公式轉換成如下迭代關系：y=x*2x=y讓計算機對這個迭代關系重復執(zhí)行11次，就可以算出第12個月時的兔子數(shù)。參考程序如下：clsx=1fori=2to12y=x*2x=ynextiprintyend分而治之法1、分治法的基本思想任何一個可以用計算機求解的問題所需的計算時間都與其規(guī)模N有關。問題的規(guī)模越小，越容易直接求解，解題所需的計算時間也越少。例如，對于n個元素的排序問題，當n=1時，不需任何計算；n=2時，只要作一次比較即可排好序；n=3時只要作3次比較即可，…。而當n較大時，問題就不那么容易處理了。要想直接解決一個規(guī)模較大的問題，有時是相當困難的。分治法的設計思想是，將一個難以直接解決的大問題，分割成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。分治法所能解決的問題一般具有以下幾個特征：（1）該問題的規(guī)?？s小到一定的程度就可以容易地解決；（2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結構性質；（3）利用該問題分解出的子問題的解可以合并為該問題的解；（4）該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。3、分治法的基本步驟分治法在每一層遞歸上都有三個步驟：（1）分解：將原問題分解為若干個規(guī)模較小，相互獨立，與原問題形式相同的子問題；（2）解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個子問題；（3）合并：將各個子問題的解合并為原問題的解?？焖倥判蛟谶@種方法中，n個元素被分成三段（組）：左段left，右段right和中段middle。中段僅包含一個元素。左段中各元素都小于等于中段元素，右段中各元素都大于等于中段元素。因此left和right中的元素可以獨立排序，并且不必對left和right的排序結果進行合并。middle中的元素被稱為支點(pivot)。圖14-9中給出了快速排序的偽代碼。//使用快速排序方法對a[0:n-1]排序從a[0:n-1]中選擇一個元素作為middle，該元素為支點把余下的元素分割為兩段left和right，使得left中的元素都小于等于支點，而right中的元素都大于等于支點遞歸地使用快速排序方法對left進行排序遞歸地使用快速排序方法對right進行排序所得結果為left+middle+right考察元素序列[4,8,3,7,1,5,6,2]。假設選擇元素6作為支點，則6位于middle；4，3，1，5，2位于left；8，7位于right。當left排好序后，所得結果為1，2，3，4，5；當right排好序后，所得結果為7，8。把right中的元素放在支點元素之后，left中的元素放在支點元素之前，即可得到最終的結果[1,2,3,4,5,6,7,8]。把元素序列劃分為left、middle和right可以就地進行（見程序14-6）。在程序14-6中，支點總是取位置1中的元素。也可以采用其他選擇方式來提高排序性能，本章稍后部分將給出這樣一種選擇。程序14-6快速排序template<classT>voidQuickSort(T*a,intn){對fn+1(xn+1)初始化;

{邊界條件}fork:=ndownto1dofor每一個xk∈Xkdofor每一個uk∈Uk(xk)dobeginfk(xk):=一個極值;

{∞或－∞}xk+1:=Tk(xk,uk);

{狀態(tài)轉移方程}t:=φ(fk+1(xk+1),vk(xk,uk));

{基本方程(9)式}if

t比fk(xk)更優(yōu)thenfk(xk):=t;{計算fk(xk)的最優(yōu)值}end;t:=一個極值;

{∞或－∞}for每一個x1∈X1doiff1(x1)比t更優(yōu)thent:=f1(x1);

{按照10式求出最優(yōu)指標}輸出t;但是，實際應用當中經常不顯式地按照上面步驟設計動態(tài)規(guī)劃，而是按以下幾個步驟進行：（1）分析最優(yōu)解的性質，并刻劃其結構特征。（2）遞歸地定義最優(yōu)值。（3）以自底向上的方式或自頂向下的記憶化方法（備忘錄法）計算出最優(yōu)值。（4）根據計算最優(yōu)值時得到的信息，構造一個最優(yōu)解。步驟（1）～（3）是動態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟（4）可以省略，若需要求出問題的一個最優(yōu)解，則必須執(zhí)行步驟（4）。此時，在步驟（3）中計算最優(yōu)值時，通常需記錄更多的信息，以便在步驟（4）中，根據所記錄的信息，快速地構造出一個最優(yōu)解?？偨Y：動態(tài)規(guī)劃實際上就是最優(yōu)化的問題，是指將原問題的大實例等價于同一最優(yōu)化問題的較小實例，自底向上的求解最小實例，并將所求解存放起來，存放的結果就是為了準備數(shù)據。與遞歸相比，遞歸是不斷的調用子程序求解，是自頂向下的調用和求解?；厮莘?/p>

回溯法也稱為試探法，該方法首先暫時放棄關于問題規(guī)模大小的限制，并將問題的候選解按某種順序逐一枚舉和檢驗。當發(fā)現(xiàn)當前候選解不可能是解時，就選擇下一個候選解；倘若當前候選解除了還不滿足問題規(guī)模要求外，滿足所有其他要求時，繼續(xù)擴大當前候選解的規(guī)模，并繼續(xù)試探。如果當前候選解滿足包括問題規(guī)模在內的所有要求時，該候選解就是問題的一個解。在回溯法中，放棄當前候選解，尋找下一個候選解的過程稱為回溯。擴大當前候選解的規(guī)模，以繼續(xù)試探的過程稱為向前試探。1、回溯法的一般描述可用回溯法求解的問題P，通常要能表達為：對于已知的由n元組（x1，x2，…，xn）組成的一個狀態(tài)空間E={（x1，x2，…，xn）∣xi∈Si，i=1，2，…，n}，給定關于n元組中的一個分量的一個約束集D，要求E中滿足D的全部約束條件的所有n元組。其中Si是分量xi的定義域，且|Si|有限，i=1，2，…，n。我們稱E中滿足D的全部約束條件的任一n元組為問題P的一個解。解問題P的最樸素的方法就是枚舉法，即對E中的所有n元組逐一地檢測其是否滿足D的全部約束，若滿足，則為問題P的一個解。但顯然，其計算量是相當大的。我們發(fā)現(xiàn)，對于許多問題，所給定的約束集D具有完備性，即i元組（x1，x2，…，xi）滿足D中僅涉及到x1，x2，…，xi的所有約束意味著j（j<i）元組（x1，x2，…，xj）一定也滿足D中僅涉及到x1，x2，…，xj的所有約束，i=1，2，…，n。換句話說，只要存在0≤j≤n-1，使得（x1，x2，…，xj）違反D中僅涉及到x1，x2，…，xj的約束之一，則以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）一定也違反D中僅涉及到x1，x2，…，xi的一個約束，n≥i>j。因此，對于約束集D具有完備性的問題P，一旦檢測斷定某個j元組（x1，x2，…，xj）違反D中僅涉及x1，x2，…，xj的一個約束，就可以肯定，以（x1，x2，…，xj）為前綴的任何n元組（x1，x2，…，xj，xj+1，…，xn）都不會是問題P的解，因而就不必去搜索它們、檢測它們。回溯法正是針對這類問題，利用這類問題的上述性質而提出來的比枚舉法效率更高的算法?；厮莘ㄊ紫葘栴}P的n元組的狀態(tài)空間E表示成一棵高為n的帶權有序樹T，把在E中求問題P的所有解轉化為在T中搜索問題P的所有解。樹T類似于檢索樹，它可以這樣構造：

設Si中的元素可排成xi(1)，xi(2)，…，xi(mi-1)，|Si|=mi，i=1，2，…，n。從根開始，讓T的第I層的每一個結點都有mi個兒子。這mi個兒子到它們的雙親的邊，按從左到右的次序，分別帶權xi+1(1)，xi+1(2)，…，xi+1(mi)，i=0，1，2，…，n-1。照這種構造方式，E中的一個n元組（x1，x2，…，xn）對應于T中的一個葉子結點，T的根到這個葉子結點的路徑上依次的n條邊的權分別為x1，x2，…，xn，反之亦然。另外，對于任意的0≤i≤n-1，E中n元組（x1，x2，…，xn）的一個前綴I元組（x1，x2，…，xi）對應于T中的一個非葉子結點，T的根到這個非葉子結點的路徑上依次的I條邊的權分別為x1，x2，…，xi，反之亦然。特別，E中的任意一個n元組的空前綴（），對應于T的根。

因而，在E中尋找問題P的一個解等價于在T中搜索一個葉子結點，要求從T的根到該葉子結點的路徑上依次的n條邊相應帶的n個權x1，x2，…，xn滿足約束集D的全部約束。在T中搜索所要求的葉子結點，很自然的一種方式是從根出發(fā)，按深度優(yōu)先的策略逐步深入，即依次搜索滿足約束條件的前綴1元組（x1i）、前綴2元組（x1，x2）、…，前綴I元組（x1，x2，…，xi），…，直到i=n為止。

在回溯法中，上述引入的樹被稱為問題P的狀態(tài)空間樹；樹T上任意一個結點被稱為問題P的狀態(tài)結點；樹T上的任意一個葉子結點被稱為問題P的一個解狀態(tài)結點；樹T上滿足約束集D的全部約束的任意一個葉子結點被稱為問題P的一個回答狀態(tài)結點，它對應于問題P的一個解。【問題】n皇后問題問題描述：求出在一個n×n的棋盤上，放置n個不能互相捕捉的國際象棋“皇后”的所有布局。這是來源于國際象棋的一個問題?；屎罂梢匝刂v橫和兩條斜線4個方向相互捕捉。如圖所示，一個皇后放在棋盤的第4行第3列位置上，則棋盤上凡打“×”的位置上的皇后就能與這個皇后相互捕捉。12345678××××××××××Q×××××××××××××××從圖中可以得到以下啟示：一個合適的解應是在每列、每行上只有一個皇后，且一條斜線上也只有一個皇后。求解過程從空配置開始。在第1列至第m列為合理配置的基礎上，再配置第m+1列，直至第n列配置也是合理時，就找到了一個解。接著改變第n列配置，希望獲得下一個解。另外，在任一列上，可能有n種配置。開始時配置在第1行，以后改變時，順次選擇第2行、第3行、…、直到第n行。當?shù)趎行配置也找不到一個合理的配置時，就要回溯，去改變前一列的配置。得到求解皇后問題的算法如下：{輸入棋盤大小值n；m=0;good=1;do{if(good)if(m==n){輸出解；改變之，形成下一個候選解;}else擴展當前候選接至下一列；else改變之，形成下一個候選解；good=檢查當前候選解的合理性；}while(m!=0);}在編寫程序之前，先確定邊式棋盤的數(shù)據結構。比較直觀的方法是采用一個二維數(shù)組，但仔細觀察就會發(fā)現(xiàn)，這種表示方法給調整候選解及檢查其合理性帶來困難。更好的方法乃是盡可能直接表示那些常用的信息。對于本題來說，“常用信息”并不是皇后的具體位置，而是“一個皇后是否已經在某行和某條斜線合理地安置好了”。因在某一列上恰好放一個皇后，引入一個一維數(shù)組（col[]），值col[i]表示在棋盤第i列、col[i]行有一個皇后。例如：col[3]=4，就表示在棋盤的第3列、第4行上有一個皇后。另外，為了使程序在找完了全部解后回溯到最初位置，設定col[0]的初值為0當回溯到第0列時，說明程序已求得全部解，結束程序運行。為使程序在檢查皇后配置的合理性方面簡易方便，引入以下三個工作數(shù)組：（1）數(shù)組a[]，a[k]表示第k行上還沒有皇后；（2）數(shù)組b[]，b[k]表示第k列右高左低斜線上沒有皇后；（3）數(shù)組c[]，c[k]表示第k列左高右低斜線上沒有皇后；棋盤中同一右高左低斜線上的方格，他們的行號與列號之和相同；同一左高右低斜線上的方格，他們的行號與列號之差均相同。初始時，所有行和斜線上均沒有皇后，從第1列的第1行配置第一個皇后開始，在第m列col[m]行放置了一個合理的皇后后，準備考察第m+1列時，在數(shù)組a[]、b[]和c[]中為第m列，col[m]行的位置設定有皇后標志；當從第m列回溯到第m-1列，并準備調整第m-1列的皇后配置時，清除在數(shù)組a[]、b[]和c[]中設置的關于第m-1列，col[m-1]行有皇后的標志。一個皇后在m列，col[m]行方格內配置是合理的，由數(shù)組a[]、b[]和c[]對應位置的值都為1來確定。細節(jié)見以下程序：【程序】#include#include#defineMAXN20intn,m,good;intcol[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];voidmain(){intj;charawn;printf(“Entern:“);scanf(“%d”,&n);for(j=0;j<=n;j++)a[j]=1;for(j=0;j<=2*n;j++)cb[j]=c[j]=1;m=1;col[1]=1;good=1;col[0]=0;do{if(good)if(m==n){printf(“列\(zhòng)t行”);for(j=1;j<=n;j++)printf(“%3d\t%d\n”,j,col[j]);printf(“Enteracharacter(Q/qforexit)!\n”);scanf(“%c”,&awn);if(awn==’Q’||awn==’q’)exit(0);while(col[m]==n){m--;a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;}col[m]++;}else{a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=0;col[++m]=1;}else{while(col[m]==n){m--;a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;}col[m]++;}good=a[col[m]]&&b[m+col[m]]&&c[n+m-col[m]];}while(m!=0);}試探法找解算法也常常被編寫成遞歸函數(shù)，下面兩程序中的函數(shù)queen_all()和函數(shù)queen_one()能分別用來解皇后問題的全部解和一個解?！境绦颉?include#include#defineMAXN20intn;intcol[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];voidmain(){intj;printf(“Entern:“);scanf(“%d”,&n);for(j=0;j<=n;j++)a[j]=1;for(j=0;j<=2*n;j++)cb[j]=c[j]=1;queen_all(1,n);}voidqueen_all(intk,intn){inti,j;charawn;for(i=1;i<=n;i++)if(a[i]&&b[k+i]&&c[n+k-i]){col[k]=i;a[i]=b[k+i]=c[n+k-i]=0;if(k==n){printf(“列\(zhòng)t行”);for(j=1;j<=n;j++)printf(“%3d\t%d\n”,j,col[j]);printf(“Enteracharacter(Q/qforexit)!\n”);scanf(“%c”,&awn);if(awn==’Q’||awn==’q’)exit(0);}queen_all(k+1,n);a[i]=b[k+i]=c[n+k-i];}}采用遞歸方法找一個解與找全部解稍有不同，在找一個解的算法中，遞歸算法要對當前候選解最終是否能成為解要有回答。當它成為最終解時，遞歸函數(shù)就不再遞歸試探，立即返回；若不能成為解，就得繼續(xù)試探。設函數(shù)queen_one()返回1表示找到解，返回0表示當前候選解不能成為解。細節(jié)見以下函數(shù)?！境绦颉?defineMAXN20intn;intcol[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];intqueen_one(intk,intn){inti,found;i=found=0;While(!found&&i{i++;if(a[i]&&b[k+i]&&c[n+k-i]){col[k]=i;a[i]=b[k+i]=c[n+k-i]=0;if(k==n)return1;elsefound=queen_one(k+1,n);a[i]=b[k+i]=c[n+k-i]=1;}}returnfound;}分支定界法：分支限界法：這是一種用于求解組合優(yōu)化問題的排除非解的搜索算法。類似于回溯法，分枝定界法在搜索解空間時，也經常使用樹形結構來組織解空間。然而與回溯法不同的是，回溯算法使用深度優(yōu)先方法搜索樹結構，而分枝定界一般用寬度優(yōu)先或最小耗費方法來搜索這些樹。因此，可以很容易比較回溯法與分枝定界法的異同。相對而言，分枝定界算法的解空間比回溯法大得多，因此當內存容量有限時，回溯法成功的可能性更大。算法思想：分枝定界（branchandbound）是另一種系統(tǒng)地搜索解空間的方法，它與回溯法的主要區(qū)別在于對E-節(jié)點的擴充方式。每個活節(jié)點有且僅有一次機會變成E-節(jié)點。當一個節(jié)點變?yōu)镋-節(jié)點時，則生成從該節(jié)點移動一步即可到達的所有新節(jié)點。在生成的節(jié)點中，拋棄那些不可能導出（最優(yōu)）可行解的節(jié)點，其余節(jié)點加入活節(jié)點表，然后從表中選擇一個節(jié)點作為下一個E-節(jié)點。從活節(jié)點表中取出所選擇的節(jié)點并進行擴充，直到找到解或活動表為空，擴充過程才結束。有兩種常用的方法可用來選擇下一個E-節(jié)點（雖然也可能存在其他的方法）：1)先進先出（FIFO）即從活節(jié)點表中取出節(jié)點的順序與加入節(jié)點的順序相同，因此活節(jié)點表的性質與隊列相同。2)最小耗費或最大收益法在這種模式中，每個節(jié)點都有一個對應的耗費或收益。如果查找一個具有最小耗費的解，則活節(jié)點表可用最小堆來建立，下一個E-節(jié)點就是具有最小耗費的活節(jié)點；如果希望搜索一個具有最大收益的解，則可用最大堆來構造活節(jié)點表，下一個E-節(jié)點是具有最大收益的活節(jié)點裝載問題用一個隊列Q來存放活結點表，Q中weight表示每個活結點所相應的當前載重量。當weight＝－1時，表示隊列已達到解空間樹同一層結點的尾部。算法首先檢測當前擴展結點的左兒子結點是否為可行結點。如果是則將其加入到活結點隊列中。然后將其右兒子結點加入到活結點隊列中(右兒子結點一定是可行結點)。2個兒子結點都產生后，當前擴展結點被舍棄?；罱Y點隊列中的隊首元素被取出作為當前擴展結點，由于隊列中每一層結點之后都有一個尾部標記-1，故在取隊首元素時，活結點隊列一定不空。當取出的元素是-1時，再判斷當前隊列是否為空。如果隊列非空，則將尾部標記-1加入活結點隊列，算法開始處理下一層的活結點。/*該版本只算出最優(yōu)解*/#include<>#include<>structQueue{intweight;structQueue*next;};intbestw=0;//目前的最優(yōu)值Queue*Q;//活結點隊列Queue*lq=NULL;Queue*fq=NULL;intAdd(intw){Queue*q;q=(Queue*)malloc(sizeof(Queue));if(q==NULL){

printf("沒有足夠的空間分配\n");

return1;}q->next=NULL;q->weight=w;if(Q->next==NULL){

Q->next=q;

fq=lq=Q->next;//一定要使元素放到鏈中}else{

lq->next=q;

lq=q;//

lq=q->next;}return0;}intIsEm