算法分析作業(yè)

1、算法分析練習(xí)題（一）、選擇題1、二分搜索算法是利用（A ）實(shí)現(xiàn)的算法。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法2、下列不是動(dòng)態(tài)規(guī)劃算法基本步驟的是（ A ）。A、找出最優(yōu)解的性質(zhì)B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、定義最優(yōu)解3下列算法中通常以自底向上的方式求解最優(yōu)解的是（B ）。A、備忘錄法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法4、衡量一個(gè)算法好壞的標(biāo)準(zhǔn)是（ C ）。A 運(yùn)行速度快 B 占用空間少 C 時(shí)間復(fù)雜度低 D 代碼短5、以下不可以使用分治法求解的是（ D ）。A 棋盤(pán)覆蓋問(wèn)題 B 選擇問(wèn)題 C 歸并排序 D 0/1 背包問(wèn)題6. 實(shí)現(xiàn)循環(huán)賽日程表利用的算法是（ A ）。A、分治策略B、

2、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法7. 備忘錄方法是那種算法的變形。 （B ）A、分治法 B動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法8最長(zhǎng)公共子序列算法利用的算法是（B ）。A、分支界限法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法9實(shí)現(xiàn)棋盤(pán)覆蓋算法利用的算法是（A ）。A、分治法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法10、矩陣連乘問(wèn)題的算法可由（B設(shè)計(jì)實(shí)現(xiàn)。A、分支界限算法B、動(dòng)態(tài)規(guī)劃算法C、貪心算法D、回溯算法11、 Strassen矩陣乘法是利用（A ）實(shí)現(xiàn)的算法。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法12、使用分治法求解不需要滿(mǎn)足的條件是（ A ）。A 子問(wèn)題必須是一樣的B 子問(wèn)題不能夠重復(fù)C 子問(wèn)題的解

3、可以合并D 原問(wèn)題和子問(wèn)題使用相同的方法解13、下列算法中不能解決0/1背包問(wèn)題的是（A ）A貪心法B動(dòng)態(tài)規(guī)劃C回溯法D分支限界法14 實(shí)現(xiàn)合并排序利用的算法是（A ）。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法15.下列是動(dòng)態(tài)規(guī)劃算法基本要素的是（D)°A、定義最優(yōu)解B、構(gòu)造最優(yōu)解C、算出最優(yōu)解D、子問(wèn)題重疊性質(zhì)16下列算法中通常以自底向下的方式求解最優(yōu)解的是（ B ）。A、分治法B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法17、合并排序算法是利用（ A ）實(shí)現(xiàn)的算法。A、分治策略 B、動(dòng)態(tài)規(guī)劃法 C、貪心法D、回溯法18 實(shí)現(xiàn)大整數(shù)的乘法是利用的算法（C ）。A、貪心法B、動(dòng)態(tài)規(guī)劃法C

4、、分治策略D、回溯法19. 實(shí)現(xiàn)最大子段和利用的算法是（B ）。A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心法D、回溯法20. 一個(gè)問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征是問(wèn)題的（B ）。A、重疊子問(wèn)題B、最優(yōu)子結(jié)構(gòu)性質(zhì)21. 實(shí)現(xiàn)最長(zhǎng)公共子序列利用的算法是（A、分治策略B、動(dòng)態(tài)規(guī)劃法C、貪心選擇性質(zhì)D、定義最優(yōu)解B ）。C、貪心法D、回溯法0二、填空題1算法的復(fù)雜性有 時(shí)間復(fù)雜性和 空間 復(fù)雜性之分2、程序是 算法 用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。3、算法的 確定性”指的是組成算法的每條 指令 是清晰的，無(wú)歧義的。4矩陣連乘問(wèn)題的算法可由動(dòng)態(tài)規(guī)劃 設(shè)計(jì)實(shí)現(xiàn)。5、算法是指解決問(wèn)題的 一種方法或一個(gè)過(guò)

5、程 。&從分治法的一般設(shè)計(jì)模式可以看出， 用它設(shè)計(jì)出的程序一般是 涕歸算法7、矩陣連乘問(wèn)題的算法可由動(dòng)態(tài)規(guī)劃設(shè)計(jì)實(shí)現(xiàn)。8. 動(dòng)態(tài)規(guī)劃算法的基本思想是將待求解問(wèn)題分解成若干子問(wèn)題,先求解 子問(wèn)題，然后從這些 子問(wèn)題的解得到原問(wèn)題的解。9. 算法是由若干條指令組成的有窮序列，且要滿(mǎn)足輸入、輸出確定性和有限性 四條性質(zhì)。10. 大整數(shù)乘積算法是用分治法 來(lái)設(shè)計(jì)的。11快速排序算法是基于分治策略 的一種排序算法。12. 動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本要素是. 性質(zhì)和性質(zhì)。13. 任何可用計(jì)算機(jī)求解的問(wèn)題所需的時(shí)間都與其規(guī)模 有關(guān)。14. 快速排序算法的性能取決于劃分的對(duì)稱(chēng)性o15、出自于“平衡子問(wèn)題”

6、的思想，通常分治法在分割原問(wèn)題，形成若干子問(wèn)題時(shí)，這些子問(wèn)題的規(guī)模都大致相同。16、使用二分搜索算法在n個(gè)有序元素表中搜索一個(gè)特定元素，在最佳情況下， 搜索的時(shí)間復(fù)雜性為O ()，在最壞情況下，搜索的時(shí)間復(fù)雜性為 O ( logn )o17、已知一個(gè)分治算法耗費(fèi)的計(jì)算時(shí)間 T(n), T(n)滿(mǎn)足如下遞歸方程：T(n)0(1)n 22T(n /2)0(n) n 2解得此遞歸方可得T(n)= 0(nlogn)18、 動(dòng)態(tài)規(guī)劃算法有一個(gè)變形方法備忘錄方法。這種方法不同于動(dòng)態(tài)規(guī)劃算法“自底向上”的填充方向，而是“自頂向下”的遞歸方向，為每個(gè)解 過(guò)的子問(wèn)題建立了備忘錄以備需要時(shí)查看，同樣也可避免相同子

7、問(wèn)題的重復(fù)求解。19、 遞歸的二分查找算法在divide階段所花的時(shí)間是 0(1)，conquer階段所花的時(shí)間是 T( n/2)，算法的時(shí)間復(fù)雜度是O( log n)。20、 用動(dòng)態(tài)規(guī)劃算法計(jì)算矩陣連乘問(wèn)題的最優(yōu)值所花的時(shí)間是O(n3)，子冋題空間大小是O(n 2)。21、一個(gè)算法的優(yōu)劣可以用(時(shí)間復(fù)雜度)與(空間復(fù)雜度)與來(lái)衡量。22、直接或間接地調(diào)用自身的算法稱(chēng)為(遞歸算法)。23、記號(hào)在算法復(fù)雜性的表示法中表示(漸進(jìn)確界或緊致界)。24、在分治法中，使子問(wèn)題規(guī)模大致相等的做法是出自一種(平衡子問(wèn)題)的思 想。25、動(dòng)態(tài)規(guī)劃算法適用于解(具有某種最優(yōu)性質(zhì))問(wèn)題。26、 最優(yōu)子結(jié)構(gòu)性質(zhì)的含

8、義是(問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解)。27、按照符號(hào) 0 的定義 O(f)+O(g等于 O(maxf(n),g(n)。28、二分搜索技術(shù)是運(yùn)用(分治)策略的典型例子。29、動(dòng)態(tài)規(guī)劃算法中，通常不同子問(wèn)題的個(gè)數(shù)隨問(wèn)題規(guī)模呈(多項(xiàng)式)級(jí)增長(zhǎng)。30、 (最優(yōu)子結(jié)構(gòu)性質(zhì))和(子問(wèn)題重疊性質(zhì))是采用動(dòng)態(tài)規(guī)劃算法的兩個(gè)基本 要素。三、算法填空1. 最大子段和：動(dòng)態(tài)規(guī)劃算法int MaxSum(int n, int a)int sum=0, b=0 ； 速排序template<class Typevoid Quicksort (Type a, int p, int r)if (p<r) in

9、t q=Partiti on( a,p,r);Quicksort ( a ， p ，q-1);2n 3n log n n! n log n n2 nn 103參考解答：io" Y log和Y “l(fā)og”Y丁 Yh Y”！ Y"”最長(zhǎng)上升子序列問(wèn)題】一一提示：此題可采用動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)對(duì)于給定的一個(gè)序列(ai,a2丄Rn)，1 N 1000。我們可以得到一些遞增上升的子序列(叭印2丄，ax)，這里1 h i2 L h N。比如，對(duì)于序列(1, 7, 3,5, 9, 4, 8),有它的一些上升子序列，如(1,7), (3, 4, 8等等。這些子序列中最長(zhǎng)的 長(zhǎng)度是4,比如子序列

10、(1,3, 5, 8占你的任務(wù)：就是對(duì)于給定的序列，求出最長(zhǎng)上 升子序列的長(zhǎng)度。要求寫(xiě)出你設(shè)計(jì)的算法思想及遞推函數(shù)的公式表達(dá)。參考解算：設(shè)r(I)a示:從左向右韌描過(guò)耒直到朕住卩兀沽姑尾的序鳳,獲得的 晟歩上升子序和的長(zhǎng)廈且子序利也含叫門(mén)死考(i£f】)rIi = i/(O = max/(j) + l;W J< 0 i >1141： W(l< ><r>t<=«/即,/是從/(I) - /(I) 到/(*-!)中找廈犬的一個(gè)值-再加I,或舟就 是1,主姿是看迢iiX*無(wú)索能否加入舅之諦己蛭獲擇杓暈.喪上舟子序列.如罷能加 入，.是之前

11、已衣荷的歳氏上片卜序列氏廢加一；曲社不能削入*就膽工眞后一個(gè)元擊 作為一令單拽子序死.悅曳為I展看,聽(tīng)譬求的螯個(gè)序列的載掘公兵子序Jl'itS-jS maifrti): 1<=i<=n倒如、吋于序罰：2 63152iI234§7& rray42631r 521122132評(píng)分準(zhǔn)則：B 答列使用動(dòng)態(tài)規(guī)劃算法-井且摳導(dǎo)出動(dòng)態(tài)規(guī)劃算法的適推函戟公式表達(dá)，邊 界迂毛満附，本題典叮得満辦；I閥基廿仃細(xì)石注推公式晁達(dá).公式及達(dá)含發(fā) 正踴即可.囲共表達(dá)弟式可能不唯一丨2) 銳明使用動(dòng)態(tài)規(guī)劃算法r但寸遞捲禹救農(nóng)達(dá)諾演或舍糊、扣2介以上； 3并它椅況酌情耆慮"2.

12、 【Gray碼構(gòu)造問(wèn)題】一一 提示：此題可采用分治遞歸算法實(shí)現(xiàn)問(wèn)題描述：“格雷碼”是一個(gè)長(zhǎng)度為2n的序列，滿(mǎn)足：(a) 每個(gè)元素都是長(zhǎng)度為n比特的串(b) 序列中無(wú)相同元素(c) 連續(xù)的兩個(gè)元素恰好只有1個(gè)比特不同例如：n=2時(shí)，格雷碼為00, 01，11，10。Gray碼是一種編碼，這種編碼可以避免在讀取時(shí)，因各數(shù)據(jù)位時(shí)序上的差 異造成的誤讀。格雷碼在工程上有廣泛應(yīng)用。但格雷碼不便于運(yùn)算，請(qǐng)你設(shè)計(jì) 種構(gòu)造方法，輸入長(zhǎng)度序列n,輸出格雷碼(你只要做出一種構(gòu)造方案即可，格 雷碼并不唯一)。星考解答： 此世叩同仝勞也醉決.雪n=l時(shí)一輸去格番也;山L；當(dāng)n>l時(shí)，胳需嗎的卡屋溝才，即共有邪個(gè)

13、碼序列。此時(shí)*捋問(wèn)迎一兮詢(xún)二,別上半部分和下半劑分.上半部分匠髙位誼翔0,下半部分最奇位法砌1_,別下ml位 的格雷碼的構(gòu)造采用遢隣的思路3.現(xiàn)在有8位運(yùn)動(dòng)員要進(jìn)行網(wǎng)球循環(huán)賽，要設(shè)計(jì)一個(gè)滿(mǎn)足以下要求的比賽日程表：(1)每個(gè)選手必須與其他選手各賽一次;(2)每個(gè)選手一天只能賽次；(3)循環(huán)賽一共進(jìn)行n -1天。請(qǐng)利用分治法的思想，給這8位運(yùn)動(dòng)員設(shè)計(jì)一個(gè)合理的比賽日程。1234567821436587341278b6432187C5567812346587214318563412876543214. 對(duì)于矩陣連乘所需最少數(shù)乘次數(shù)問(wèn)題，其遞歸關(guān)系式為:mi, j0imin mi,k mk 1,jpP

14、kPj ii k j其中mi, j為計(jì)算矩陣連乘Ai-Aj所需的最少數(shù)乘次數(shù)，pi-i為矩陣Ai的行，口為矩陣Ai的列?，F(xiàn)有四個(gè)矩陣，其中各矩陣維數(shù)分別為:AiA2A3A4501010 4040 3030 5p 0 p 1p 1 p 2p 2 p 3p 3p 4請(qǐng)根據(jù)以上的遞歸關(guān)系，計(jì)算出矩陣連乘積 A1A2A3A4所需要的最少數(shù)乘次數(shù)。舉舟解答;就 11"24 + 鳳円丹一+ m 5 10500初l4 = inij創(chuàng)12十創(chuàng)34|十規(guī)總口 =20000-珀00十50 40. 5 = 36000 卸13 + 蟲(chóng)44 + 必沖曲=27000 + 0 + 50. 30. 5 = 3450

15、0-105005. 有這樣一類(lèi)特殊0-1背包問(wèn)題：可選物品 重量越輕的物品價(jià)值越高n=6, c=20, P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。其中n為物品個(gè)數(shù)，c為背包載重量，P表示物品的價(jià)值，W表示物品的重 量。請(qǐng)問(wèn)對(duì)于此0-1背包問(wèn)題，應(yīng)如何選擇放進(jìn)去的物品，才能使到放進(jìn)背包的 物品總價(jià)值最大，能獲得的最大總價(jià)值多少?lài)?guó)均該問(wèn)題比牧特廩廠(chǎng)碼號(hào)重量魅輕的涵品價(jià)值越髙.所漢比 丸取車(chē)量輕的物品就遠(yuǎn)背包臼最終可以把重量分別為2. 3. 4. 5的三個(gè)粉品疲進(jìn)背包. 礙到的金值和腳15 *日* 6十4 = 3玄為員尢粗.6. 歸并排序算法對(duì)下列實(shí)例排序，寫(xiě)出算法執(zhí)行過(guò)程

16、。A=（48,12,61,3,5,19,32,7）5.48,12, 61, 348,1212,48£ 13?61,3336148? 615, 19,32, 75,195. 1932(77, 325, 7, 19, 327, L2t 19,32t 48, 817.規(guī)則證明：O(f(n )+O(g( n) = O(maxf( n),g( n)對(duì)于任意fn) =t存在正常數(shù)燈和自然數(shù)q,使得對(duì)所電血g有h(n) M o類(lèi)似地，對(duì)于任意a(n) - O(g(n),存在正常數(shù)q和自然數(shù)煦，使得對(duì) 所有金“有g(shù)(n) < cg(n) P- 令Gj-maxlc Cjf n3nf h(n) m

17、ax"門(mén)),g(r?) <,則對(duì)所有的n>nv有< ©Re) + CgSln) Cg(n) + g(n)玄學(xué) maxRn),g0) 2c3h(n)=0(e自刈R(shí)n),g(Q).8.給定已按升序排好序的n個(gè)元素a0:n-1，現(xiàn)要在這n個(gè)元素中找出一特定元素x,返回其在數(shù)組中的位置，如果未找到返回-1。寫(xiě)出二分搜索的算法，并分析其時(shí)間復(fù)雜度。L tTyp&£uL B inaiy Scar eJi (Typeconsi TypdL xt Ini n)17在aO:nk, tplx時(shí)返回其在販組巾的她.否則軀回-LInt left=t> int tightiiLVhilc (lefl<=ritihL)4"int iDiddle=(lefl light)/2;if (xainiiicile) return inLddle；if (x>amiddle) leftmiddleH: else 上 1 ftl=oiitldlt-1:Re Luxti 1.;