算法作業(yè)講解

1、算法習(xí)題講解Sch1-1:設(shè)n個(gè)不同的整數(shù)排好序后存于T1.n中，若存在一個(gè)下標(biāo)i（1 i n），使得Ti=i。試設(shè)計(jì)一個(gè)有效算法找到這個(gè)下標(biāo)，要求算法在最壞情形下的計(jì)算時(shí)間為O(log n)。解答要點(diǎn)：采用二分查找，當(dāng)Tmidmid時(shí)，在前半部分尋找，當(dāng)Tmidmid時(shí)，在后半部分需找，相等時(shí)即找到。Sch1-2：在一個(gè)由n個(gè)元素組成的表中，出現(xiàn)次數(shù)最多的元素被稱為眾數(shù)。試寫一個(gè)尋找眾數(shù)及其重?cái)?shù)的有效算法，并分析其計(jì)算時(shí)間復(fù)雜性。解答要點(diǎn)：先排序，然后遍歷一遍找到重復(fù)次數(shù)最多的元素。注意：這里不一定能用計(jì)數(shù)排序，因?yàn)轭}目沒說明一定是整數(shù)。Sch1-3：設(shè)x=a+bi和y=c+di是兩個(gè)復(fù)數(shù)，

2、只要做4次乘法就能夠計(jì)算乘積xy=(ac-bd)+(ad+bc)i。試設(shè)計(jì)一個(gè)方法只用3次乘法計(jì)算乘積xy。解答要點(diǎn)：設(shè)法將ac、bd、ad和bc四次乘法變?yōu)橹挥?次乘法。保留ac、bd，于是(ad+bc)= (a+b)(c+d)-ac-bd只需計(jì)算ac、bd和(a+b)(c+d)三次乘法即可。15.2-1：對(duì)矩陣規(guī)模序列，求矩陣鏈最優(yōu)括號(hào)化方案。解答要點(diǎn)：遞歸求解公式為：15.4-5：設(shè)計(jì)一個(gè)O(n2)時(shí)間的算法，求一個(gè)n個(gè)數(shù)的序列的最長(zhǎng)單調(diào)遞增子序列。解答要點(diǎn)：方法一：轉(zhuǎn)化為求LCS對(duì)數(shù)組的一份拷貝進(jìn)行排序，然后去重，最后與原序列求LCS。方法二：直接采用動(dòng)態(tài)規(guī)劃法設(shè)Lj表示以aj結(jié)尾的數(shù)

3、組序列的最長(zhǎng)遞增子序列長(zhǎng)度，則Lj= max(Li)+1, ij且aiaj 注意：看清問題，題目要求的是單調(diào)遞增。15.4-6:設(shè)計(jì)一個(gè)O(nlgn)的算法，求一個(gè)n個(gè)數(shù)的序列的最長(zhǎng)單調(diào)遞增子序列。解答要點(diǎn)：設(shè)Lj保存當(dāng)前所有長(zhǎng)度為j的子序列中尾元素最小的元素下標(biāo)，對(duì)于第i個(gè)元素，由于aLi是非降的，可以使用二分查找找到最大的j，使得aLjai，記錄當(dāng)前以ai結(jié)尾的最長(zhǎng)子序列的前一個(gè)元素在a中的位置，以便輸出最長(zhǎng)子序列。15-5：編輯距離問題。（題目太長(zhǎng)，略）解答要點(diǎn): (a)遞歸求解公式為：(b): (1)如果xj=yj，1分；對(duì)應(yīng)的是copy操作； (2)如果xi!=yj并且兩者都不是空格

4、，-1分；對(duì)應(yīng)的是replace操作； (3)如果xj或者yj是空格，-2分，對(duì)應(yīng)的是insert和delete操作。i1j1cost(copy) i1j1cost(replace) i2j2cost(tw iddle),2, 1 m ini1j1cost(delete)alw ays 1cost(insert)alw ayscif x iyjcif x iyjcif ijx iyjc ijand xyc ijc ij16.1-4：假定有一組活動(dòng)，我們需要將他們安排到一些教室，任意活動(dòng)都可以在任意教室進(jìn)行，希望使用最少的教室完成所有活動(dòng)。設(shè)計(jì)一個(gè)高效的貪心算法求每個(gè)活動(dòng)應(yīng)該在哪個(gè)教室進(jìn)行。(區(qū)間圖著色問題)解答要點(diǎn)：構(gòu)造一個(gè)區(qū)間圖，頂點(diǎn)表示給定的活動(dòng)，邊連接表示不兼容的活動(dòng)，然后用最少的顏色對(duì)頂點(diǎn)進(jìn)行著色，使得所有相鄰頂點(diǎn)顏色均不相同。16.2-5：設(shè)計(jì)一個(gè)高效算法，對(duì)實(shí)數(shù)線上給定的一個(gè)點(diǎn)集x1,x2 xn，求一個(gè)單位長(zhǎng)度閉區(qū)間集合，包含所有給定的點(diǎn)，并要求此集合最小。證明你的算法是正確的。解答要點(diǎn)：對(duì)點(diǎn)集進(jìn)行排序得到y(tǒng)1,y2, yn，貪心的從左到右進(jìn)行選擇，比如選擇 y1,y1 +1區(qū)間，則屬于此區(qū)間內(nèi)的點(diǎn)均可消去。注意：要求是單位長(zhǎng)度閉區(qū)間集合。Sch2-1:作業(yè)分配問題，n個(gè)作業(yè)分配給n個(gè)人，使得總花