《算法設(shè)計(jì)與分析》模擬試卷三.doc

算法設(shè)計(jì)與分析模擬試卷三考試形式：閉卷 考試時(shí)間：120分鐘 站點(diǎn)：_ 姓名：_ 學(xué)號(hào)：_ 成績(jī)：_ 1到商場(chǎng)購(gòu)買(mǎi)商品需要找零錢(qián)。假設(shè)有四種面值分別為14角、5角、2角和1角的硬幣可以找零，售貨員希望找零的硬幣數(shù)目最少。也就是，優(yōu)化目標(biāo)是找零的硬幣數(shù)目最少，限制條件是所選擇的硬幣的總面值等于要找的零錢(qián)數(shù)。1）假設(shè)要找的零錢(qián)數(shù)分別是13角，21角和41角；(貪婪策略：每一次選擇應(yīng)該使硬幣的面值最大), 給出相應(yīng)的解。2）假設(shè)要找的零錢(qián)數(shù)是n角，請(qǐng)用C語(yǔ)言或偽代碼描述算法。2 對(duì)于二分圖覆蓋問(wèn)題設(shè)計(jì)一種貪婪啟發(fā)算法，貪婪準(zhǔn)則是：如果B中某一個(gè)頂點(diǎn)被A中一個(gè)頂點(diǎn)覆蓋，選擇A中這個(gè)頂點(diǎn)；否則，從A中選擇一個(gè)頂點(diǎn)，使得它所覆蓋的未被覆蓋的頂點(diǎn)數(shù)目最多。給出這種貪婪算法的偽代碼。3有n（=2 k）個(gè)硬幣，其中1個(gè)是假幣，且假幣和真幣的重量不同。請(qǐng)用分而治之方法設(shè)計(jì)一個(gè)找出假幣的算法，并用偽代碼描述你的算法。4請(qǐng)用分治法設(shè)計(jì)算法：在一個(gè)整數(shù)組A1.n 中，同時(shí)尋找最大值和最小值。假設(shè) n 為 2 的方冪。請(qǐng)用偽代碼描述你的算法并分析算法的時(shí)間復(fù)雜度。5定義0/1/2背包問(wèn)題為：。限制條件為：，且。設(shè)f(i , y)表示剩余容量為y，剩余物品為：i，i+1，n時(shí)的最優(yōu)解的值。1） 給出f(i , y)的遞推表達(dá)式；2） 請(qǐng)?jiān)O(shè)計(jì)求解f(i , y)的算法，并用偽代碼描述你的算法；3） 設(shè)W=10,20,15,30，P=6,10,15,18,c=48，請(qǐng)用你的算法求解。6請(qǐng)?jiān)O(shè)計(jì)一個(gè)有效的算法，可以進(jìn)行兩個(gè)n位（n=2k）十進(jìn)制大整數(shù)的乘法運(yùn)算。7子集和問(wèn)題：對(duì)于集合S=1，2 ，6，8，求子集，要求該子集的元素之和d=9。1） 畫(huà)出子集和問(wèn)題的解空間樹(shù)；2） 該樹(shù)運(yùn)用回溯算法，寫(xiě)出依回溯算法遍歷節(jié)點(diǎn)的順序；3） 如果S中有n個(gè)元素，指定d，用偽代碼描述求解子集和問(wèn)題的回溯算法。參考答案1. 1) 13角：2個(gè)5角 + 1個(gè)2角 + 1個(gè)1角； 21角：1個(gè)14角+1個(gè)5角 + 1個(gè)2角； 41角：2個(gè)14角 + 2個(gè)5角 + 1個(gè)2角+ 1個(gè)1角；2) 當(dāng)要找的錢(qián)數(shù)是n 角時(shí)，用偽代碼描述此貪婪算法如下： float exchange(int fund , int coin , int x) int n=coin.length, opt=fund; Sort(coin); /從大到小 for (int i = 0; i 0) xj=opt/coinj; opt=opt%coinj; return x ; 2 貪婪算法的偽代碼為m=0 / 當(dāng)前覆蓋的大小對(duì)于A 中的所有 i, Outi=outdegreei;對(duì)于 B 中的所有 i, Ini=indegreei;對(duì)于B 中的所有i, Covi=false;for (對(duì)于B 中所有入度為 1 的頂點(diǎn) i) 設(shè) v 是鄰接于Bi的頂點(diǎn) Cm+=v; for (所有鄰接于v 的頂點(diǎn) j) if (! Covj) Covj=true; 對(duì)于所有鄰接于j 的頂點(diǎn)，使其 Outk 減 1 while (對(duì)于A 中的某些 i, Outi0) 設(shè) v 是具有最大Outi 的頂點(diǎn) Cm+=v; for (所有鄰接于v 的頂點(diǎn) j) if (!Covj) Covj=true; 對(duì)于所有鄰接于j的頂點(diǎn)，使其 Outk 減1 if (有些頂點(diǎn)未被覆蓋) 失敗else 找到一個(gè)覆蓋3. Feit_money(low, high) / 假定偽幣較真幣輕 if high-low=1 thenif AlowAhigh return Ahigh;else mid=(low+high)/2; sum1=sum(low, mid); sum2=sum(mid+1, high); if sum1sum2 then Feit_money(low, mid); else Feit_money(mid+1, high); end if end if return 0;4. min_max(low, high) if high-low=1 then if AlowAhigh then return (Alow, Ahigh);else return (Ahigh, Alow);end if elsemid=(low+high)/2;(x1, y1)=min_max(low, mid);(x2, y2)=min_max(mid+1, high);x=min(x1, x2);y=max(y1, y2);return (x, y); end if5. 2) void knapsack(int v , int w , int c, int m ) int n=v.length-1; int jMax=min(wn-1,c); for( int j=0; j=jMax; j+) mnj=0; for( int j=wn; j=2*wn-1; j+) mnj=vn;for( int j=2*wn; j1; i-) jMax=min(wi-1,c); for( int j=0; j=jMax; j+) mij=mi+1j; for(int j=wi; j=2*wi; j+) mij=max(mi+1j, mi+1j-wi+vi); for(int j=2*wi; j=2*w1)m1c=max(m1c, m2c-w1+v1, m2c-2*w1+2*v1); else if (c=w1) m1c=max(m1c, m2c-w1+v1);3) 設(shè) w=10, 20, 15, 30, p=6, 10, 15, 18, c=48, 用上述算法求解如下n=4, f(4, 48)=18; f(3, 18)=max(f(4, 18), f(4, 3)+15)=