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

...(1)用計算機求解問題的步驟：(2)算法定義：算法是指在解決問題時，按照某種機械步驟一定可以得到問題結果的處理(3)算法的三要素有窮性：一個算法必須總是在執(zhí)行有窮步之后結束，且每一步都在有窮時間完成?？诳尚行裕阂粋€算法是可行的就是算法描述的操作是可以通過已經實現(xiàn)的基本運算執(zhí)行有輸入：一個算法有零個或多個輸入，這些輸入取自于某個特定對象的集合。輸出：一個算法有一個或多個輸出，這些輸出同輸入有著某些特定關系的量。正確性：算法應滿足具體問題的需求；可讀性：算法應該好讀，以有利于讀者對程序的理解；。的最大存儲空間。一般這兩者與問題的規(guī)模有關。經常采用的算法主要有迭代法、分而治之法、貪婪法、動態(tài)規(guī)劃法、回溯法、分支限界法一個值的公式(或關系)。迭代關系式的建立是解決迭代問題的關鍵，通?？梢跃帉懹嬎沆巢瞧?Fibonacci)數(shù)列的第n項函數(shù)fib(n)。...bnnnbn}只兔子”，則有unun－1×2(n≥2)fori=2to12nextiprinty1、分治法的基本思想任何一個可以用計算機求解的問題所需的計算時間都與其規(guī)模規(guī)模越小，越容易直接求解，解題所需的計算時間也越少。例如，對于n=1時，不需任何計算；n=2時，只要作一次比較即可排好序；n=3時只要作3次比較即可，…。而當n較大時，問題就不那么容易處理了。要想直接解決一個規(guī)模較大的問題，有時是相當困難的。相同問題，以便各個擊破，分而治之。分治法所能解決的問題一般具有以下幾個特征：(1)該問題的規(guī)?？s小到一定的程度就可以容易地解決；(2)該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結...(3)利用該問題分解出的子問題的解可以合并為該問題的解；(4)該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共3、分治法的基本步驟分治法在每一層遞歸上都有三個步驟：(1)分解：將原問題分解為若干個規(guī)模較小，相互獨立，與原問題形式相同(2)解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個子(3)合并：將各個子問題的解合并為原問題的解?？焖倥判騨三段(組)：左段left，右段right和中段middle。中段僅包含一個元素。左段中各元素都小于等于中段元素，右段中各元素都大于等于t中給出了快速排序的偽代碼。//使用快速排序方法對a[0:n-1]排序從a[0:n-1]中選擇一個元素作為middle，該元素為支點right于等于支點遞歸地使用快速排序方法對left進行排序遞歸地使用快速排序方法對right進行排序所得結果為left+middle+right考察元素序列[4,8,3,7,1,5,6,2]。假設選擇元素6作為支點，則6ight3,4,5,6,7,8]。本章稍后部分將給出這樣一種選擇。template<classT>voidQuickSort(T*a,intn)an進行快速排序a[n]必需有最大關鍵值quickSort(a,0,n-1);template<classT>值if(l>=r)return;inti=l,//從左至右的游標j=r+1;//從右到左的游標Tpivot=a[l];pivot的元素進行交換while(true){do{//在左側尋找>=pivot的元素i=i+1;}while(a<pivot);do{//在右側尋找<=pivot的元素j=j-1;}while(a[j]>pivot);ifijbreak未發(fā)現(xiàn)交換對象Swap(a,a[j]);}a[l]=a[j];a[j]=pivot;quickSort(a,l,j-1);//對左段排序quickSort(a,j+1,r);//對右段排序}它采用逐步構造最優(yōu)解的思想，在問題求解的每一個階段，都作出一個在一定標準下看上去最優(yōu)的決策；決策一旦作出，就不可再更改。制定決策的依據稱為貪婪準則。前情況為基礎作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。#include<stdio.h>voidmain(){m,n,i,j,w[50],p[50],pl[50],b[50],s=0,max;printf("輸入背包容量m,物品種類n:");scanf("%d%d",&m,&n);for(i=1;i<=n;i=i+1){printf("輸入物品的重量W和價值P:");scanf("%d%d",&w[i],&p[i]);pl[i]=p[i];s=s+w[i];}fsm{printf("wholechoose\n");//return;}for(i=1;i<=n;i=i+1){max=1;for(j=2;j<=n;j=j+1)if(pl[j]/w[j]>pl[max]/w[max])max=j;pl[max]=0;b[i]=max;}for(i=1,s=0;s<m&&i<=n;i=i+1)s=s+w[b[i]];fsmw[b[i-1]]=m-w[b[i-1]];for(j=1;j<=i-1;j=j+1)printf("chooseweight%d\n",w[b[j]]);思想前文主要介紹了動態(tài)規(guī)劃的一些理論依據，我們將前文所說的具有明顯的階段劃分和狀態(tài)轉移方程的動態(tài)規(guī)劃稱為標準動態(tài)規(guī)劃，這種標準動態(tài)規(guī)劃是在研究多階段決策問題時推導出......小的子問題，并且原問題的最優(yōu)解中包含了子問題的最優(yōu)解(即滿足最優(yōu)子化原理)，則可以考慮用動態(tài)規(guī)劃解決。動態(tài)規(guī)劃的實質是分治思想和解決冗余，因此，動態(tài)規(guī)劃是一種將問題實例分解為更小的、子問題，并通過求解子問題產生一個全局最優(yōu)解。貪心法的當前選擇可能要依賴已經作出的所有選擇，但不依賴于有待于做出的選擇和子問題。因此貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個子問題是獨立的(即不包含公共的子問題)，因此一旦遞歸地求出各子問題的解后，便可自下而上地將子問題的解合并成問題的解。最能的解，每個解都有一個值，而動態(tài)規(guī)劃找出其中最優(yōu)(最大或最小)值的解。若存在若干子問題只解一次，并將結果保存起來，避免每次碰到時都要重復計算。解，并把答案保存起來，讓以后再遇到時直接引用，不必重新求解。3、動態(tài)規(guī)劃算法的基本步驟設計一個標準的動態(tài)規(guī)劃算法，通?？砂匆韵聨讉€步驟進行： (1)劃分階段：按照問題的時間或空間特征，把問題分為若干個階段。注意這若干個階段一定要是有序的或者是可排序的(即無后向性)，否則問題就無法用動態(tài)規(guī)劃求解。 (2)選擇狀態(tài)：將問題發(fā)展到各個階段時所處于的各種客觀情況用不同的狀態(tài)表示出來。當然，狀態(tài)的選擇要滿足無后效性。 (3)確定決策并寫出狀態(tài)轉移方程：之所以把這兩步放在一起，是因為決策和狀態(tài)轉移有我們確定了決策，狀態(tài)轉移方程也就寫出來了。但事實上，我們常常是反過來做，根據相鄰兩段的各狀態(tài)之間的關系來確定決策。(4)寫出規(guī)劃方程(包括邊界條件)：動態(tài)規(guī)劃的基本方程是規(guī)劃方程的通用形式化表達式。一般說來，只要階段、狀態(tài)、決策和狀態(tài)轉移確定了，這一步還是比較簡單的。動態(tài)規(guī)劃的方程可以直接遞歸計算最優(yōu)值，但是一般將其改為遞推計算，實現(xiàn)的大體上的框架如下：標準動態(tài)規(guī)劃的基本框架n+1n+1fork:=ndownto1dofor每一個x∈XdokkUxdokkkbeginf(x):=一個極值;kkk+1kkktkkkkt:=一個極值;for每一個x∈Xdo111111kk但是，實際應用當中經常不顯式地按照上面步驟設計動態(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)中，根據所記錄的信息，快速地構造的與遞歸相比，遞歸是不斷的調用子程序求解，是自頂向下的調用和求解。回溯法也稱為試探法，該方法首先暫時放棄關于問題規(guī)模大小的限制，并將問就是問題的一個解。在回溯法中，放棄當前候選解，尋找下一個候選解的過程稱為回溯。擴大當前候選解的規(guī)模，以繼續(xù)試探的過程稱為向前試探。1、回溯法的一般描述可用回溯法求解的問題P，通常要能表達為：對于已知的由n元組(x，x，…，x)組成的12n一個狀態(tài)空間E={(x，x，…，x)∣x∈S，i=1，2，…，n}，給定關于n元組中的一12nii個分量的一個約束集D，要求E中滿足D的全部約束條件的所有n元組。其中S是分量xiiP其計算量是相當大的。我們發(fā)現(xiàn)，對于許多問題，所給定的約束集D具有完備性，即i元組(x，x，…，x)滿12i足D中僅涉及到x，x，…，x的所有約束意味著j(j<i)元組(x，x，…，x)一定也12i12j滿足D中僅涉及到x，x，…，x的所有約束，i=1，2，…，n。換句話說，只要存在0≤j12j≤n-1，使得(x，x，…，x)違反D中僅涉及到x，x，…，x的約束之一，則以(x，12j12j1x，…，x)為前綴的任何n元組(x，x，…，x，x，…，x)一定也違反D中僅涉及到2j12jj+1nx，x，…，x的一個約束，n≥i>j。因此，對于約束集D具有完備性的問題P，一旦檢測12ixx12j12j以(x，x，…，x)為前綴的任何n元組(x，x，…，x，x，…，x)都不會是問題P12j12jj+1n...性質而提出來的比枚舉法效率更高的算法。根開始，讓T的第I層的每一個結點都有m個兒子。這m個兒子到它們的雙親的邊，按從ii左到右的次序，分別帶權x(1)，x(2)，…，x(mi)，i=0，1，2，…，n-1。照這種構造i+1i+1i+1方式，E中的一個n元組(x，x，…，x)對應于T中的一個葉子結點，T的根到這個葉子12n結點的路徑上依次的n條邊的權分別為x，x，…，x，反之亦然。另外，對于任意的0≤i12n≤n-1，E中n元組(x，x，…，x)的一個前綴I元組(x，x，…，x)對應于T中的一12n12i個非葉子結點，T的根到這個非葉子結點的路徑上依次的I條邊的權分別為x，x，…，x，12i的根到該葉子結點的路徑上依次的n條邊相應帶的n個權x，x，…，x滿足約束集D的全12n逐步深入，即依次搜索滿足約束條件的前綴1元組(x)、前綴2元組(x，x)、…，前綴1i12I元組(x，x，…，x)，…，直到i=n為止。12i在回溯法中，上述引入的樹被稱為問題P的狀態(tài)空間樹；樹T上任意一個結點問題描述：求出在一個n×n的棋盤上，放置n個不能互相捕捉的國際象棋“皇后”這是來源于國際象棋的一個問題?；屎罂梢匝刂v橫和兩條斜線4個方向相互捕捉。就能與這個皇后相互捕捉。123456××××××××××Q×××××××××7×8××斜線上也只有一個皇后。直至第n列配置也是合理時，就找到了一個解。接著改變第n列配置，希望獲得下一個解。......另外，在任一列上，可能有n種配置。開始時配置在第1行，以后改變時，順次選擇第2nn理的配置時，就要回溯，去改變前一列的配置。得到求解皇后問題的算法如下：m=0;good=1;do{if(good)if(m==n)改變之，形成下一個候選解;}else候選接至下一列；else改變之，形成下一個候選解；good前候選解的合理性；}while(m!=0);}而是“一個皇后是否已經在某行和某條斜線合理地安置好了”。因在某一列上恰好放一個皇后，引入一個一維數(shù)組(col[l為使程序在檢查皇后配置的合理性方面簡易方便，引入以下三個工作數(shù)組：(1)數(shù)組a[]，a[k]表示第k行上還沒有皇后；(2)數(shù)組b[]，b[k]表示第k列右高左低斜線上沒有皇后；(3)數(shù)組c[]，c[k]表示第k列左高右低斜線上沒有皇后；上的方格，他們的行號與列號之差均相同。abc【程序】#include...#include#defineMAXN20intn,m,good;intcol[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];voidmain()charawn;printfEntern);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)for(j=1;j<=n;j++)printf(“%3d\t%d\n”,j,col[j]);printf(“Enteracharacter(Q/qforexit)!\n”);scanf(“%c”,&awn);while(col[m]==n){m--;a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;}col[m]++;}{a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=0;col[++m]=1;}{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);}queen_one()能分別用來解皇后問題的全部解和一個解?！境绦颉?include#include#defineMAXN20intcol[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];voidmain()printfEntern);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)charawn;for(i=1;i<=n;i++)if(a[i]&&b[k+i]&&c[n+k-i])a[i]=b[k+i]=c[n+k-i]=0;if(k==n)for(j=1;j<=n;j++)printf(“%3d\t%d\n”,j,col[j]);printf(“Enteracharacter(Q/qforexit)!\n”);scanf(“%c”,&awn);}queen_all(k+1,n);a[i]=b[k+i]=c[n+k-i];}}當前候選解不能成為解。細節(jié)見以下函數(shù)?！境绦颉?defineMAXN20intcol[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];intqueen_one(intk,intn)foundi=found=0;While(!found&&i{i++;if(a[i]&&b[k+i]&&c[n+k-i])a[i]=b[k+i]=c[n+k-i]=0;if(k==n)return1;found=queen_one(k+1,n);a[i]=b[k+i]=c[n+k-i]=1;}}returnfound;}多，因此當存容量有限時，回溯法成功的可能性更大。算法思想：分枝定界(branchandbound)是另一種系統(tǒng)地搜索解空間的方法，它與回溯法的主要區(qū)別在于對E-節(jié)點的擴充方式。每個活節(jié)點有且僅有一次機會變成E-節(jié)點。當一個節(jié)點變?yōu)镋-節(jié)點時，則生成從該節(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é)點表示每個活結點所相應的當前載重量。當同一層結點的尾部。算法首先檢測當前擴展結點的左兒子結結點隊列中(右兒子結點一定是可行結點)。2個兒子結點都產生后，當前擴展結點被舍活結點隊列中的隊首元素被取出作為都有一個尾部標記-1，故在取隊首元素時，活結點隊列一定不空。當取出的元素是-1...開始處理下一層的活結點。/*該版本只算出最優(yōu)解*/#include<stdio.h>#include<malloc.h>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;//一定要使元中}{lq->next=q;lq=q;//lq=q->next;}return0;}intIsEmpty(){if(Q->next==NULL)return1;return0;}intDelete(int&w){Queue*tmp=NULL;/