計算機算法設(shè)計與分析練習(xí)題

1、計算機算法設(shè)計與分析練習(xí)題一 最大子段和問題：給定整數(shù)序列 ，求該序列形如的子段和的最大值： 1. 一個簡單算法如下：int Maxsum(int n,int a,int& besti,int& bestj) int sum = 0; for(int i=1;i=n;i+) int suma = 0;for(int j=i;j sum) sum = suma; besti = i; bestj = j; return sum;試分析該算法的時間復(fù)雜性。2. 試用分治算法解最大子段和問題，并分析算法的時間復(fù)雜性。3. 試說明最大子段和問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，并設(shè)計一個動態(tài)規(guī)劃算法解最大子段和問題

2、。分析算法的時間復(fù)雜度。二設(shè)是個互不相同的元素，每個元素有一個正實數(shù)權(quán)值，且滿足。個元素的帶權(quán)的中位數(shù)是滿足下面不等式的元素： (1)1). 證明的（不帶權(quán)的）中位數(shù)是帶權(quán) （ ）的帶權(quán)中位數(shù)（不帶權(quán)的中位數(shù)是指按照大小排在中間位置的數(shù)，如果有兩個，則取小者）。2). 說明如何通過排序，在最壞情況下用時間求出個元素的帶權(quán)中位數(shù)。3). 說明如何利用一個線性時間選擇算法，在最壞情況下用時間求出個元素的帶權(quán)中位數(shù)。4). 郵局位置問題是：已知個點以及與它們相了解的權(quán)，要求確定一點（未必是輸入的點），使和式達到最小，其中表示與之間的距離。試論證帶權(quán)的中位數(shù)是一維郵局問題的最優(yōu)解，此時。三設(shè)是準備存放

3、到長為L的磁帶上的n個程序，程序需要的帶長為。設(shè)，要求選取一個能放在帶上的程序的最大子集合（即其中含有最多個數(shù)的程序）。構(gòu)造的一種貪心策略是按的非降次序?qū)⒊绦蛴嬋爰稀?1). 證明這一策略總能找到最大子集，使得。 2). 設(shè)是使用上述貪心算法得到的子集合，磁帶的利用率可以小到何種程度？3). 試說明1)中提到的設(shè)計策略不一定得到使取最大值的子集合。四 電路布線問題：在一塊電路板的上、下兩段分別有個接線柱，如下圖。根據(jù)電路設(shè)計，要求用導(dǎo)線將上端接線柱與下端接線柱相連，1012654389710126543897導(dǎo)線稱為電路板上的第條連線。對于任何連線相交的充分必要條件是。在整理電路板時，要求將

4、這條連線分布到若干個絕緣層上，使得在同一層上的連線不相交。電路布線問題就是要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。該問題等價于確定布線集的最大不相交子集。如果記，的最大不相交子集為，試證明電路布線問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。構(gòu)造一個動態(tài)規(guī)劃算法解電路布線問題（寫出算法的基本步驟即可），并說明你的算法的時間復(fù)雜度。五 給定件物品和一個背包，物品的重量是，體積是，價值是；背包的容量為，容積為。一件物品只能整個放進背包中或不放進背包中，也不允許重復(fù)放入。試設(shè)計一個求解此問題的算法，并計算其時間復(fù)雜度。六 設(shè)計一個時間的算法，找出個數(shù)組成的序列的最長單調(diào)遞增子序列。七 字符出現(xiàn)的頻率恰

5、好是前8個Fibonacci數(shù)，它們的Huffman編碼是什么？將結(jié)果推廣到個字符的頻率恰好是前個Fibonacci數(shù)的情形。Fibonacci數(shù)的定義為：。八 （雙機調(diào)度問題）用兩臺處理機A和B處理個作業(yè)。設(shè)第個作業(yè)交給機器A處理時所需要的時間是，若由機器B來處理，則所需要的時間是?，F(xiàn)在要求每個作業(yè)只能由一臺機器處理，每臺機器都不能同時處理兩個作業(yè)。設(shè)計一個動態(tài)規(guī)劃算法，使得這兩臺機器處理完這個作業(yè)的時間最短（從任何一臺機器開工到最后一臺機器停工的總的時間）。以下面的例子說明你的算法： 九 考慮下面特殊的整數(shù)線性規(guī)劃問題試設(shè)計一個解此問題的動態(tài)規(guī)劃算法，并分析算法的時間復(fù)雜度。十 考慮下列問

6、題i. 在一個由元素組成的表中，出現(xiàn)次數(shù)最多的元素稱為眾數(shù)。試寫出一個求眾數(shù)的算法，并分析其時間復(fù)雜性。ii. 主元素問題：數(shù)組中的元素稱為該數(shù)組的主元素，如果該數(shù)組中有多于一半的元素等于，即。主元素問題是確定已知數(shù)組中是否存在主元素。設(shè)計一個線性時間算法求解主元素問題。十一 分派問題一般陳述為：給個人分派件工作，把工作分派給第個人的成本為。設(shè)計一個回溯算法，在給每個人分派一件不同工作的情況下，使得總成本最小。十二 已知一個無向連通圖用它的鄰接矩陣表示，試設(shè)計一個回溯算法HamiltonCycle，判定該圖是否有Hanmilton圈，如果有將所有不同的Hanmilton圈都打印出來。十三 設(shè)和

7、，使用求定和子集問題的回溯算法找出中所有和數(shù)為的子集，并畫出所生成的部分狀態(tài)空間樹。十四 畫出優(yōu)先隊列式算法對于下列0/1背包問題實例所生成的部分狀態(tài)空間樹：十五 棧式分枝限界法將活結(jié)點表以后進先出(LIFO)的方式存儲于一個棧中。試設(shè)計一個解0/1背包問題的棧式分枝限界算法，并說明棧式分枝限界算法與回溯法的區(qū)別。部分問題提示：問題一1.3個for循環(huán)，時間復(fù)雜度為; 2. 將序列分成兩部分：和，此時有三種可能情況： (1) 的最大子段和與的最大子段和相同； (2) 的最大子段和與的最大子段和相同；(3) 的最大子段和為，其中；注意到上述三種情況，就可以設(shè)計出求最大子段和問題的分治算法。該算法

8、的時間復(fù)雜度函數(shù)滿足如下遞推關(guān)系式其中是一個固定正整數(shù)。直接推得可得時間復(fù)雜度為。3若記，所求的最大子段和為注意到 可以證明最大子段和問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，并且設(shè)計出求解該問題的動態(tài)規(guī)劃算法。該算法的時間復(fù)雜度為。問題二3.對線性選擇算法進行改進：首先同線性選擇算法一樣找到劃分子程序（Partition）所用的“標竿”（即用來作為標尺的數(shù)，比該數(shù)大的數(shù)向后移，比該數(shù)小的向前移，通過交換完成），在Partition程序中加一句：計算比的元素的權(quán)和；在線性選擇算法的遞歸過程中，將判斷改為，這樣就構(gòu)造出線性時間的求帶權(quán)中位數(shù)算法。4因為1維的郵局問題，所有的點都可以表示在一個實數(shù)軸上，假設(shè)的坐標為

9、，。不妨假定（不然，可以令），此時可以認為是的權(quán)。注意到其中，代表點的坐標。于是 (1)如果是帶權(quán)中位數(shù)，則 (2)直接推導(dǎo)可知，從而證明斷言。問題四記，對于固定的，分兩種情況討論（畫圖）：情況1，此時；情況2，此時；對于有，由此，可以說明電路布線問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，并設(shè)計出求該問題的動態(tài)規(guī)劃算法。其時間復(fù)雜度為。問題五設(shè)計動態(tài)規(guī)劃算法時，注意淹沒規(guī)則，因為此時不僅有容量約束還有容積約束。設(shè)和是兩個點偶，當(dāng)而且時，稱點耦淹沒點耦。其它部分同0/1背包問題的動態(tài)規(guī)劃算法。設(shè)計回溯算法和分枝限界算法時，同時注意到兩個約束即可。其余略。問題六 用記序列中最長單調(diào)遞增子序列的長度，為序列中所有長度

10、為的單調(diào)遞增子序列中最后元素最小的子序列的最后元素。則根據(jù)此遞推關(guān)系式，可以設(shè)計一個求最長單調(diào)遞增子序列的動態(tài)規(guī)劃算法，該算法時間復(fù)雜度為。問題八：假定個作業(yè)的集合為。則雙機處理作業(yè)問題相當(dāng)于確定的子集，使得中的作業(yè)在機器A上處理、其余作業(yè)在機器B上處理的安排是最省時的安排。此時所用時間為，即最優(yōu)安排所用時間應(yīng)為。若記，則有如下遞推關(guān)系： (4.1)令表示機器A需等待時間，且機器B需等待時間情況下安排作業(yè)集合在兩臺機器A、B上處理所需的最短時間，則對于任意作業(yè)， (4.2)個作業(yè)的雙機處理問題滿足： (4.3)(4.2)說明雙機調(diào)度問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，可以采用動態(tài)規(guī)劃算法。在(4.3)中，

11、如果，則作業(yè)安排在機器A上處理，否則安排在機器B上處理。若用表示第件作業(yè)在機器A上處理，表示第件作業(yè)在機器B上處理，則不等式就決定了的取值。根據(jù)以上分析不難給出雙機調(diào)度問題的動態(tài)規(guī)劃算法。注：此種方法能否推廣求解多機調(diào)度問題，比如求解3機調(diào)度問題？問題九：將每件物品用兩個和它完全一樣的物品來替代，構(gòu)造一個具有件物品的0/1背包問題。為寫出數(shù)學(xué)模型，可以把用于表示物品裝包情況的變量用兩個變量表示其被裝入背包的可能情況：表示物品沒有被裝進背包；則表示兩件物品有一件裝進背包，而則表示兩件物品都被裝進了背包。因而。 注：這種將整數(shù)規(guī)劃問題轉(zhuǎn)化成0/1規(guī)劃問題求解方法使得問題的規(guī)模增加過大，你能否設(shè)計一

12、個較好的方法，使問題規(guī)模的增大小些？第二部分：分析比較1 試比較復(fù)雜性函數(shù)的漸進性態(tài)與函數(shù)的區(qū)別和了解。2 假定復(fù)雜性函數(shù)都是定義在正整數(shù)集合上的正函數(shù)，那么關(guān)于漸進上界符號，如下運算性質(zhì)那些成立、那些不成立。成立則給出證明、不成立則舉出反例。(1) ；(2) ;(3) ;(4) ,其中是一個正的常數(shù)；(5) .3 何謂遞歸算法？就階矩陣相乘分別設(shè)計遞歸算法和迭代算法，并比較兩個算法的時間和空間復(fù)雜度。4 歸并排序和快速排序各自都強調(diào)了那方面的進程？5 試分析求最有生成樹的Prim算法和Kruskal算法的時間復(fù)雜性，看它們在何種情況下表現(xiàn)各自的優(yōu)越性。6 貪心算法和動態(tài)規(guī)劃算法有什么共同點和

13、區(qū)別？7 試比較回溯法與分枝限界算法，分別談?wù)勥@兩個算法比較適合的問題？8 確定性圖靈機模型與非確定性圖靈機模型的主要區(qū)別在那里？確定性圖靈機模型下算法的時間復(fù)雜度和空間復(fù)雜度指的是什么？9 什么是多項式時間算法？什么是NP類問題？10 已經(jīng)知道如何通過已知的NPC問題去證明另一個NP-問題也是NPC問題的方法，能否給出一個通過已知的P-問題證明另一個判定問題是P-問題？11 NP-困難問題與NPC問題是一類問題嗎？就旅行商最優(yōu)問題和旅行商判定問題談你的看法。12 下列問題那些是P-問題、那些是NPC-問題？那些是NP-困難問題？(1) 最優(yōu)生成樹的判定問題；例：給定一個賦權(quán)（權(quán)為正整數(shù)）連通

14、圖，一個正整數(shù)。問：是否存在的生成樹，其權(quán)值不超過？(2) 二維匹配問題例：給定一個二部圖，問：是否存在的完備匹配，即存在的子集滿足：中任何兩條邊沒有公共頂點，而且的端點集為？(3) 二元可滿足性問題例：給定邏輯語句，其子句定義在布爾變量上，而且每個子句的均由兩個文字構(gòu)成，。問：是否存在布爾變量的一個真值分配，使得語句取真值？(4) 三元可滿足性問題3SAT(3-Satisfiability)例：給定布爾變量的一個有限集合及定義于其上的邏輯語句，其中，。問：是否存在的一個真賦值，使得為真？(5) 圖的獨立集問題例：對于給定的無向圖和正整數(shù)問：是否包含一個獨立集，即是否存在一個子集，使得中的任何

15、兩個頂點在圖中都不相鄰。提示：考慮獨立集和團的關(guān)系：如果是圖的團，則是的補圖的獨立集；反之亦然。(6) 二部圖的獨立集問題例：給定一個二部圖二部圖，正整數(shù)問：是否含有一個不小于的獨立集？(7) 團問題（CLIQUE）例：給定一個無向圖和一個正整數(shù)。問：是否包含一個團？即是否存在，且對任意，有(8) 頂點覆蓋問題VERTEX-COVER例：給定無向圖和一個正整數(shù)問：是否有覆蓋，即是否存在，使得對任意，有。(9) 定和子集問題DSS例：給定非負整數(shù)集合S，正整數(shù)M問：是否存在子集,使得(10) 精確覆蓋問題XC例：已知有限集合的子集族問：是否包含一個精確覆蓋，即是否存在，使得中元素互不相交，且(1

16、1) 劃分問題PARTS例：已知一個有限集合，及對每個賦予的權(quán)值問：是否存在一個子集，使得(12) 0/1背包判定問題 KPS 例：給定一個有限集合，對于每個，對應(yīng)一個值和另一個值。另外給定一個約束值和目標 問：是否存在的一個子集，使得，而且(13) 0/1背包最優(yōu)問題(14) 旅行商判定問題例：待訪問城市的集合，每對城市之間的距離，以及一個界。問：在存在一個總長不超過的、通過所有城市的旅行路線嗎？(15) 旅行商最優(yōu)問題(16) 有向圖的有向Hamilton圈問題例：給定有向圖問：G是否有一個有向Hamilton圈，即長度為，而且恰好經(jīng)過每個頂點一次，然后回到起始頂點(17) 無向圖的Hamilton圈問題例：給定無向圖問：G是否有一個Hamilton圈，即長度為，而且恰好經(jīng)過每個頂點一次，然后回到起始頂點的圈。提示：將有向圖的（有向）Hamilton圈問題實例變換成無向圖的Hamilton問題實例：把已知有向圖的每個頂點換成欲構(gòu)造的無向圖的三個頂點：，并將頂點與頂點分別相連。如果在有向圖中有從頂點到頂點的有向邊（?。瑒t在無向圖中將頂點與頂點連接一條邊。(18) 區(qū)間排序問題（Sequencing within intervals）例：給定任務(wù)的有限集合，對于每個任務(wù)，相應(yīng)有一個開始時間和終止時間以及工作時間