算法分析與設(shè)計作業(yè)及參考答案樣本

《算法分析與設(shè)計》作業(yè)（一）本課程作業(yè)由兩某些構(gòu)成。第一某些為“客觀題某些”，由15個選取題構(gòu)成，每題1分，共15分。第二某些為“主觀題某些”，由簡答題和闡述題構(gòu)成，共15分。作業(yè)總分30分，將作為平時成績記入課程總成績?？陀^題某些：選取題（每題1分，共15題）1、遞歸算法：（C）A、直接調(diào)用自身B、間接調(diào)用自身C、直接或間接調(diào)用自身D、不調(diào)用自身2、分治法基本思想是將一種規(guī)模為n問題分解為k個規(guī)模較小字問題，這些子問題：（D）A、互相獨立B、與原問題相似C、互相依賴D、互相獨立且與原問題相似3、備忘錄辦法遞歸方式是：（C）A、自頂向下B、自底向上C、和動態(tài)規(guī)劃算法相似D、非遞歸4、回溯法求解目的是找出解空間中滿足約束條件：（A）A、所有解B、某些解C、極大解D、極小解5、貪心算法和動態(tài)規(guī)劃算法共有特點是：（A）A、最優(yōu)子構(gòu)造B、重疊子問題C、貪心選取D、形函數(shù)6、哈夫曼編碼是：（B）A、定長編碼B、變長編碼C、隨機(jī)編碼D、定長或變長編碼7、多機(jī)調(diào)度貪心方略是：（A）A、最長解決時間作業(yè)優(yōu)先B、最短解決時間作業(yè)優(yōu)先C、隨機(jī)調(diào)度D、最優(yōu)調(diào)度8、程序可以不滿足如下性質(zhì)：（D）A、零個或各種外部輸入B、至少一種輸出C、指令擬定性D、指令有限性9、用分治法設(shè)計出程序普通是：（A）A、遞歸算法B、動態(tài)規(guī)劃算法C、貪心算法D、回溯法10、采用動態(tài)規(guī)劃算法分解得到子問題：（C）A、互相獨立B、與原問題相似C、互相依賴D、互相獨立且與原問題相似11、回溯法搜索解空間辦法是：（A）A、深度優(yōu)先B、廣度優(yōu)先C、最小耗費優(yōu)先D、隨機(jī)搜索12、拉斯維加斯算法一種明顯特性是它所做隨機(jī)選性決策有也許導(dǎo)致算法：（C）A、所需時間變化B、一定找到解C、找不到所需解D、性能變差13、貪心算法能得到：（C）A、全局最優(yōu)解B、0-1背包問題解C、背包問題解D、無解14、能求解單源最短途徑問題算法是：（A）A、分支限界法B、動態(tài)規(guī)劃C、線形規(guī)劃D、蒙特卡羅算法15、迅速排序算法和線性時間選取算法隨機(jī)化版本是：（A）A、舍伍德算法B、蒙特卡羅算法C、拉斯維加斯算法D、數(shù)值隨機(jī)化算法主觀題某些：寫出下列程序答案（每題2.5分，共2題）1、請寫出批解決作業(yè)調(diào)度回溯算法。#include<iostream>#include<algorithm>usingnamespacestd;classFlowing{friendintFlow(int**,int,int[]);private: //intBound(inti); voidBacktrack(intt); int**M;// int*x;//當(dāng)前解 int*bestx;// int*f2;// intf1;// intf;// intbestf;// intn;//};voidFlowing::Backtrack(inti){ if(i>n){ for(intj=1;j<=n;j++) bestx[j]=x[j]; bestf=f; } else for(intj=i;j<=n;j++){ f1+=M[x[j]][1]; f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2]; f+=f2[i]; if(f<bestf){ swap(x[i],x[j]); Backtrack(i+1); swap(x[i],x[j]); } f1-=M[x[j]][1]; f-=f2[i]; }}intFlow(int**M,intn,intbestx[]){ intub=INT_MAX; FlowingX; X.x=newint[n+1]; X.f2=newint[n+1]; X.M=M; X.n=n; X.bestx=bestx; X.bestf=ub; X.f1=0; X.f=0; for(inti=0;i<=n;i++) X.f2[i]=0,X.x[i]=i; X.Backtrack(1); delete[]X.x; delete[]X.f2; returnX.bestf;}voidmain(){ int**M; intn; int*bestx; cout<<"請輸入作業(yè)數(shù):"; cin>>n; M=newint*[n+1]; cout<<"請輸入各作業(yè)解決時間:"<<endl; for(inti=1;i<=n;i++) M[i]=newint[2]; for(intk=1;k<=n;k++) for(intj=1;j<3;j++) cin>>M[k][j]; bestx=newint[n+1]; for(i=1;i<=n;i++) bestx[i]=0; cout<<"最優(yōu)完畢時間:"<<Flow(M,n,bestx)<<endl; cout<<"最優(yōu)方案:"; for(i=1;i<=n;i++) cout<<"作業(yè)"<<bestx[i]<<""; cout<<endl;}2、函數(shù)漸進(jìn)階對于下列各組函數(shù)f(n)和g(n)，擬定f(n)=O(g(n))或f(n)=或f(n)=，并簡述理由。(1)f(n)=logn2；g(n)=logn+5;f(n)與g(n)同階，f(n)=(2)f(n)=logn2；g(n)=;當(dāng)n>=8時，f(n)<=g(n)，故f(n)=O(g(n))分析：此類題目不易直接看出階高低，可用幾種數(shù)字代入觀測成果。如依次用n=1，21，22，23，26，28，210(3)f(n)=n；g(n)=log2n;f(n)=(4)f(n)=nlogn+n；g(n)=logn;f(n)=(5)f(n)=10；g(n)=log10;f(n)=(6)f(n)=log2n；g(n)=logn;f(n)=(7)f(n)=2n；g(n)=100n2;f(n)=(8)f(n)=2n；g(n)=3n;f(n)=O(g(n))三、寫出下列題目程序（每題5分，共2題）1、請寫出背包問題貪心算法。procedureGREEDY-KNAPSACK(P，W，M，X，n)X←0//將解向量初始化為零//cu←M//cu是背包剩余容量//fori←1tondoifW(i)≤cuthenexitendifX(i)←1；cu←cu-W(i)；repeat；ifi≤nthenX(i)←cu/W(i)；endifendGREEDY-KNAPSACK2、字符串比較問題問題描述：對于長度相似2個字符串A和B，其距離定義為相應(yīng)位置字符距離之和。2個非空格字符距離是它們ASCII碼之差絕對值?？崭衽c空格距離為0，空格與其他字符距離為一定值k。在普通狀況下，字符串A和B長度不一定相似。字符串A擴(kuò)展是在A中插入若干空格字符所產(chǎn)生字符串。在字符串A和B所有長度相似擴(kuò)展中，有一對距離最小擴(kuò)展，該距離稱為字符串A和B擴(kuò)展距離。對于給定字符串A和B，試設(shè)計一種算法，計算其擴(kuò)展距離。編程任務(wù)：對于給定字符串A和B，編程計算其擴(kuò)展距離。數(shù)據(jù)輸入：由文獻(xiàn)input.txt給出輸入數(shù)據(jù)。第1行是字符串A，第2行是字符串B，第3行是空格與其他字符距離定值k。成果輸出：將計算出字符串A和B擴(kuò)展距離輸出到文獻(xiàn)output.txt。輸入文獻(xiàn)示例輸出文獻(xiàn)示例input.txtoutput.txtcmc10snmn2解答：設(shè)字符串A和B字串A[1...i]和B[1...j]擴(kuò)展距離是val(i，j)；依題意，字符串A和B有三種也許狀況：1）A串最后一種字符是空格，B串最后一種字符是字母，則val(i，j)=val(i-1，j)+k；2）A串最后一種字符時字母，B串最后一種字符時空格，則val(i，j)=val(i，j-1)+k；3）A串和B串最后一種字符均是字母，則val(i，j)=val(i-1，j-1)+dist(ai，bi)；由上可知，val(i，j)具備最優(yōu)子構(gòu)造性質(zhì)，且滿足如下遞推式：val(i，j)=min{val(i-1，j)+k，val(i，j)+k，val(i-1，j-1)+dist(ai，bi)}（使用動態(tài)規(guī)劃算法，自底向上計算各個子問題并運用每次計算成果，避免重復(fù)運算，從而減少算法復(fù)雜度。）從動態(tài)規(guī)劃遞歸式可知，算法時間復(fù)雜度為O（mn），m和n分別是字符串A和B長度。代碼如下：#include<iostream>#include<cmath>#defineMAX100000//標(biāo)記最大也許整數(shù)intval[300][300];std::stringstra；//字符串Astd::stringstrb；//字符串Bintk；//定值k//返回字符a與bASCII碼差絕對值intdist(chara，charb){returnabs(a-b)；}intcomp(){intlen1，len2;inttmp;val[0][0]=0;len1=stra.length();len2=strb.length();for(inti=0；i<=len1；i++)//字符串A和B有效下標(biāo)是o1~len,下標(biāo)0表達(dá)空字符串{//i或j是0表達(dá)A或B串為空串for(intj=0；j<=len2；j++){if(i+j)//i和j至少一種不不大于0{val[i][j]=MAX；tmp=val[i-1][j]+k;if(i&&(tmp<val[i][j]))//i不不大于0val[i][j]=tmp；tmp=val[i][j-1]+k;if(j&&(tmp<val[i][j]))//j不不大于0val[i][j]=tmp；