算法題計(jì)算機(jī)算法設(shè)計(jì)與分析期末試題4套(含答案)

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