算法分析若干實例問題解析要點

1、最小長度電路板排列問題問題描述 小長度電路板排列問題是大規(guī)模電子系統(tǒng)設計中提出的實際問題。該問題的提法是：將n塊電路板以最佳排列方案插入帶有n個插槽的機箱中。n塊電路板的不同的排列方式對 應于不同的電路板插入方案。 設8=1,2,，n 是n塊電路板的集合。集合l= n1 , n2 ,，nm 是n塊電路板的m個連接塊。其中每個連接塊 ni是b的一個子集，且 ni中 的電路板用同一根導線連 接在一起。連接塊的長度是指該連接塊中第1塊電路板到最后1塊電路板之間的距離。試設計一個分支限界法找出所給 n個電路板的最佳排列，使得 m個連接塊中最 大長度達到最小。例：如圖，設n=8, m=5,給定n塊電路板

2、及其 m 個連接塊：b=1,2, 3, 4, 5, 6, 7, 8, n1=4,5, 6, n2=2, 3, n3=1, 3, n4=3, 6,n5=7, 8;這8塊電路板兩個可能的排列如圖所示:板：21345678槽23456721塊電路板到最后1在最小長度電路板排列問題中，連接塊的長度是指該連接塊中第塊電路板之間的距離。例如在左圖示的電路板排列中，連接塊n4的第1塊電路板在插槽 3中，它的最后1塊電路板在插槽6中，因此n4的長度為3。同理n2的長度為2。圖中連接塊最大長度為3。試設計一個分支限界法找出所給n個電路板的最佳排列，使得 m個連接塊中最大長度達到最小。輸入數(shù)據：第一行有 2個正整

3、數(shù)n和m。接下來的n行中，每行有 m個數(shù)。第k行的 第j個數(shù)為0表示電路板k不在連接塊j中，1表示電路板k在連接塊j中。輸出數(shù)據為計 算出的電路板排列最小長度與相應的排列方式。sample input8 51 1 1 1 10 1 0 1 0 0 1 1 1 01 0 1 1 0 1 0 1 0 01 1 0 1 00 0 0 0 10 1 0 0 1sample output4可用策略電路板排列問題是np難問題，因此不大可能找到解此問題的多項式時間算法。首先考慮分治的方法，因為不同連接塊連接了不同的電路板，原問題很難分解成互不相關的子問題，所以不考慮分治法。其次考慮貪婪法，逐步滿足每個連接塊

4、的局部最優(yōu)解，很容易 想出并不能得到全局最優(yōu)解。使用動態(tài)規(guī)劃方法也沒有辦法解答這個問題?？捎盟惴ㄓ谢厮莘ê头种藿绶?。采用回溯法予以解答。算法設計 考慮采用回溯法系統(tǒng)的搜索問題解空間的排列樹，找出電路板的最佳排列。設 用數(shù)組b表示輸入。bij的值為1當且僅當電路板i在連接塊nj中。設lowi表示第i塊 連接塊中最左邊的電路板的下標，highi表示第i快連接塊中最右邊的電路板的下標?；厮莘ㄋ阉髋帕袠涞乃惴ㄒ话憧梢悦枋鋈缦拢簐oid backtrack(int t) if (t > n)output(x);elsefor (int i = t; i < n; i+) swap(xt,

5、xi);if (constraint(t) && bound(t) backtrack(t + 1);swap(xt, xi); 在這個問題中，output(x),即所有已經排列好，更新最優(yōu)排列。當 i<n時，電路板排列 尚未完成。x1： i的是當前擴展結點所相應的部分排列，highi- lowi表示相應的部分最大長度，在當前部分排列之后加入一塊未排定的電路板，擴展當前部分排列產生當前擴展結點的一個兒子結點。對于這個兒子結點，計算新的最大長度。僅當 len<bestd時候，算法搜索 相應的子樹，否則該子樹被剪去。按上述回溯搜索策略設計的算法如下：實例/執(zhí)行結果1.

6、using namespace std;2. class minboard3. public :4. minboard( int n, int m, int *b);5. int * getbestx() return bestx;6. int getminl() return minl;7. private :8. intminl;/最優(yōu)最大長度9. intnowl;/當前最大長度10. int*low;/lowi 表示第i塊連接塊中最左邊的電路板的下標11. int *high; /highi 表示第i快連接塊中最右邊的電路板的下標12. int *x; /當前解向量13. int *be

7、stx; /當前最優(yōu)解向量14. int *b; /bij = 1 表示第i個電路板在第j個連接塊中15. intn;/電路板數(shù)量16. intm;/連接塊數(shù)量17. intt;/遞歸深度18. void backtrack( int t); / 回溯遞歸函數(shù)19. intcanowl( int t); /計算當前排列的最大長度20. ;21. minboard:minboard( int n, int m, int *b)9.50

8、.51.52.53.this ->b = b;this ->n = n;this ->m = m;this ->t=1;minl = 0x7fffffff;nowl = 0;x = new int n + 1;bestx = new int n + 1;for ( int i = 1;i <= n; +i)xi = i;low = new int m + 1;high = new int m + 1;this ->backtrack(t);int minboard:canowl( int t)for ( int i = 1;i <= m; +i)low

9、i = n + 1;highi = 0;for (i = 1;i <= t; +i)for ( int j = 1;j <= m; +j)if (b(m + 1)*xi+j)if (lowj > i)lowj = i;if (highj < i)highj = i;54. 55. int maxt = 0;56. for ( int j = 1;j <= m; +j)57. 58.if (highj - lowj > maxt &&lowj <= n)59. 60. maxt = highj - lowj;61. 62. 63. ret

10、urn maxt;64.65. 66. void minboard:backtrack( int t)67. if (t > n) /若能夠達到說明滿足條件nowl < mini68. 69. /更新最優(yōu)解70. for ( int j = 1; j <= n; +j)71. 72. bestxj = xj;73. 74. mini =nowl;0.91.92.else for ( int i = t; i <= n; +i)/產生下一個排列swap(xt,xi);/記錄原始no

11、wl當前最大長度用于恢復 int renowl = nowl;/計算當前組合的最大長度nowl = canowl(t);if (nowl < minl)backtrack(t+1);/回溯恢復狀態(tài)swap(xi,xt);nowl = renowl;93. 94. int main()95. int n,m;96. in >>n>>m;97.int *b =new int (m + 1)*(n + 1);98.for ( inti = 1; i <= n; +i)99.100.for(int j = 1; j <= m; +j)101.102.in &g

12、t;>bi*(m+1) + j;103.104. 105. minboard minb(n,m,b);106.107. out <<"case #" <<case<< ": " <<minb.getminl()<<endl;108. for (i = 1; i <= n; +i)109. 110. out <<minb.getbestx()i<< ""111. 112. out <<endl;113. 114. return 0

13、;115. 輸入：8 51 1 1 1 10 1 0 1 00 1 1 1 01 0 1 1 01 0 1 0 01 1 0 1 00 0 0 0 10 1 0 0 1 輸出45 4 3 1 6 2 8 7算法分析該問題用回溯法求解，搜索一棵樹列樹。最壞情況下有n!個節(jié)點，對于剪枝函數(shù)canowl復雜度為o(mn)。n為電路板數(shù)量，m為連接塊數(shù)量。所以此問題的總復雜度為 o(mn*n!)。中位數(shù)中位數(shù)1 .問題描述 給定一個由n個互不相同的數(shù)組成的集合 s,及一個正整數(shù)kwn, 試設計一個o(n)時間算法找出s中最接近s的中位數(shù)的k個數(shù)。2 .設計思路s -k s k( , 1)可用策略 對數(shù)

14、組排序，然后取 22 范圍內的k個數(shù)。2)選用策略1 .找中位數(shù)x;2 .計算s中各個數(shù)與該中位數(shù)x的差值：|six|,組成新的非負數(shù)集合s; '3 .查找s中k個小的數(shù)對應于集合s中的兀素。3.算法設計/描述1 .找中位數(shù)x; 一一 . . 一 '2 .計算s中各個數(shù)與該中位數(shù)x的差值：|s-x|,組成新的非負數(shù)集合s;3 .查找s中第k小的數(shù)，記為人；4 .查找s'中所有小于等于xk的數(shù)；5 .根據第4步查找的結果找出在集合 s中對應的數(shù)即為s中最接近s的中 位數(shù)的k個數(shù)。關于第三步，求數(shù)組中第k小的數(shù)，線性時間復雜度的具體算法描述如下：基于快排序思想，步驟如下：1

15、 .隨機選擇一個支點2 .將比支點大的數(shù)，放到數(shù)組左邊；將比支點小的數(shù)放到數(shù)組右邊；將支點 放到中間(屬于左部分)3 .設左部分的長度為l,當k < l時，遞歸地在左部分找第 k大的數(shù)當k > l時，遞歸地在有部分中找第(k - l次的數(shù)當k= l時，返回左右兩部分的分割點(即原來的支點)，就是要求的第k 大的數(shù)4 .實例/執(zhí)行結果輸入：s =9,6,4,2,1,5,7,3,8,18,32,14,13 , k = 5輸出：5,6,7,8,95 .分析 t(n)/s(n)1)策略1t(nx決于所采用的排序算法,根據已知的效率比較高的排序算法如歸并排序或者堆排序，t(n) = o(nl

16、gn) s(n) = o(1)2)策略2s(n) =o(n)第一步，t(n)=o(n)；第二步，一遍掃描即可，t(n)=o(n);第三步，采用stl中的nth_element算法，該算法的平均t(n)=o(n)；第四步，一遍掃描找出符合要求的數(shù)即可，因此 t(n)=o(n)。根據算法效率度量的加法規(guī)則，整個算法的t(n) =o(n) o二、帶權中位數(shù)一郵局選址問題1.問題描述 對分別具有正的權重w1,w2,wn且z wit的n個不同元素x1，x2，.，xn,帶權中位數(shù)是滿足如下條件的元素x wi <i 2xi <k乙=liwi wi -2xi xk2郵局選址問題(post-offi

17、ce location problem)定義如下：已知 n個點pl, p2,，pn及與它們相聯(lián)系的權重wi,w2,wn,要求希望確定一點p ( p不一定n是n個輸入之一)，使和式 工wid(p, r)達至i最小，其中，d(a,b)表示a與b之 i -間的距離。試論證帶權中位數(shù)是一維郵局問題的最優(yōu)解。止匕時d(a,b)=|a b|。2.證明思路 設p = pk是帶權中位數(shù)，對于任意一點x ,設 nnf(x)="wi* d(x, pi) =，wi*| x - pi |i4也。要證明f(p)是最小值，則只需要證明對于任意地 x, f(x)-f(pp0o3.證明過程 nnnf(x) - f

18、(p尸" wi*| x - r 1 wi*| p - r | = " wi *(| x- pi | - | p- p |) i li li l1. 當p <x時1 .當 p <x m pi : |x - pi |-1 p - pi |= pi -x-(pi - p) = p-x2 .當 p < pi ex :'.1 x-p 戶。且 | p pi |=|pi pl m x p |x-r|-|p-pil-|p-pil-p-x3 .當 pi e p <x|x- p|-|p- ip|=x-ip-( p-ip = x- p nf ( x)- f( p戶

19、 i w * bx i p- | 也 p | ) i -之 £ w*(px£ wi *(ep)p:pip _pi= (x p)e w -z wi )p _pip 印i1,x - p至0且z究工_且£ w+£ wi =1p ：p2p _pip :pi1wi 一p _pi2. f ( x) - f( p)- 0同理，當 xp 時，f(x) f(p)至0。問題得以證明，故帶權中位數(shù)為一維郵局選址位置的最優(yōu)解。參考文檔算法導論第九章：中位數(shù)和順序統(tǒng)計學尋找數(shù)組中第 k 小元素：http: 8158081 查找數(shù)組中第k個最小元素一對快排的改動 /item/ 47

20、cd21122d71c0731109b570stl 源碼分析 -nth_element() 使用與源碼分析 stl 源 碼 解 析- nth_element : 6580240 帶權中位數(shù)： 算法導論中位數(shù)與帶權中位數(shù)： 2011/11/032234482.html單機和多機最優(yōu)服務次序一.單機最優(yōu)服務次序1 .問題描述 設有n個顧客同時等待一項服務。顧客1需要的服務時間為 左，叱3£打。應如何安排h個顧客的服務次序才能使平均等待時間達到最小？平均樂待時間是汨個顧客等待服務時間的總和除以沿。2 .問題分析采用貪心算法，第一個被服務的顧客所需的等待時間為0,由于只有一個服務機，因此第二

21、個顧客的等待時間取決于第一個顧客， 令1表示第*個顧 客的等待服務時間，&表示當前隊列長度為*時候的總服務時間，即& =*十1 = st 0根據上公式有s2 = fl,因此若要第二個顧客的等待時間小，則第一個顧客的 服務時間是最短的，那么我們首先將 機1按照升序進行排序，該順序即 為服務次序，由于在這個例子中貪心算法的局部最優(yōu)即使它的全局最優(yōu)，因此它的最優(yōu)服務次序即。的升序序列。其時間復雜度主要取決于排序算法的時間復雜 度，我采用的是冒泡排序，時間復雜度為 硒川）。3.問題求解1 . n個顧客，每個顧客服務時間為ti.2 .將所有顧客的服務時間存在數(shù)組 data口中3 .將da

22、ta口內所有數(shù)據從小到大進行排序4 .用數(shù)組sequence口存儲排序隊列5 .采用貪心算法依次選取data口中的元素放入sequence口中6 .最終sequence口的內容即為最優(yōu)服務次序 代碼如下：讀取文件類：readfileimport java.io.bufferedreader;import java.io.file;import java.io.filereader;import org.omg.corba.data_conversion;public class readfile private string filestring;private int num;private

23、 int data;private int servicenum;public readfile(string filepath) this.filestring=filepath;try file file=new file(filestring);filereader freader=new filereader(file);bufferedreader breader=new bufferedreader(freader); servicenum=integer.valueof(breader.readline();num=integer.valueof(breader.readline

24、();string datastring=breader.readline();data=new intnum;string datastring2=new stringnum;datastring2=datastring.split("");for(int i=0;i<num;i+)datai=integer.valueof(datastring2i);freader.close(); catch (exception e) / todo: handle exception system.out.println(e.tostring();public int get

25、num() return this.num;public int getdata() return this.data;public int getservicenum() return this.servicenum;public void showdata()system.out.println("讀入數(shù)據為：");system.out.println("服務機數(shù)量為："+this.servicenum);system.out.println("任務數(shù)量為："+this.num);system.out.println("

26、任務時間數(shù)據分別為："); for(int i=0;i<num;i+)system.out.print(datai+"");單機服務類：public class singleservice private int data口；private int num;private int sequence口；private double t;public singleservice(readfile rf) this.num=rf.getnum();data=new intnum;data=rf.getdata();sequence=new intnum;sort(

27、);setsequence();counttime();public void sort()for(int i=0;i<num;i+)for(int j=0;j<num;j+) if(datai<=dataj) int k=0;k=datai;datai=dataj; dataj=k;public void setsequence()for(int i=0;i<num;i+) sequencei=datai;public int getsequence()return this.sequence;public void counttime()int totaltime=

28、0;int time=new intnum;time0=0;totaltime +=time0;for(int i=1;i<num;i+)for(int j=0;j<i;j+) timei+=sequencej;totaltime +=timei;t=double.valueof(totaltime)/double.valueof(num);public void show()system.out.println();system.out.print("單機最優(yōu)次序為：");for(int i=0;i<num-1;i+)system.out.print(s

29、equencei+"->");system.out.println(sequencenum-1);system.out.println("平均等待時間為："+t);主函數(shù)代碼：publicindex public si:a±ic veld(st ring args.) (/ / tom auto-generated method stubst ri ng fllest r,ing="i nputl. t:其七 的 ;readfile rfile-nnim read fi le (fi lest ring ) jrf l1 q .

30、 showddit =()：豐 q-rvicq1 =ncw singrvic?(rf11. 寫 qpkizql一與hawo;fl llt-st riirl1g="ir1|pu fcl-txt." jrfilen同 readfilefilestring)1； pflie.&houdjt3();輸入格式為：1 .服務機數(shù)量2 .顧客數(shù)量3 .每一個顧客的服務時間工421010 20 15 26 6 9 23 12 34 2結果為：讀入效據為：_服棄機熱量為：1任皆救員為：ie 任烈寸河數(shù)據分別為：10 20 15 26 6 9 23 12 34 2單而航次厚為：2-&g

31、t;6->9->10->12 >15'>20->23->26'>34平均等待時宜為:：44.1二.多機最優(yōu)服務次序1 .問題描述設有咒個顧客同時等待服務，服務機數(shù)量為布。顧客;需要的服務時間為 心 1 <<小 應如何安排h個顧客的服務次序才能使平均等待時間達到最??？平均等待時間是啊個顧客等待服務時間的總和除以汨。2 .問題分析依舊采取貪心算法，首先還是將苗，打按照升序進行排序，由于本例子中服務機數(shù)量為加，因此前皿個顧客的等待時間均為0,第他-：個顧客 則選擇當前服務時間最短的那一個服務機進行等待，依次排序，從而貪心得

32、到最優(yōu)的服務次序，因此在本例中貪心算法的局部最優(yōu)也就是它的全局最 優(yōu)，因此得到的最優(yōu)序列即為全局最優(yōu)序列。其時間復雜度為： 洪舟。3 .問題求解1 .n個顧客，每個顧客服務時間為ti.2 .將所有顧客的服務時間存在數(shù)組data口中3 .將data口內所有數(shù)據從小到大進行排序4 .用數(shù)組arraylist<integer> sequence口 存儲m個服務排序隊列5 .采用貪心算6依次選取data口中的元素放入當前最短的sequence口中6 .最終arraylist<integer> sequence口 的內容即為最優(yōu)服務次序讀取文件的類和單機服務相同多機服務類：imp

33、ort java.util.arraylist;public class mutiservice private int num;private int servicenum;private int data口；private arraylist<integer> sequence口；private int timepersequence口；private double t;public mutiservice(readfile rfile)this.num=rfile.getnum();servicenum=rfile.getservicenum();data=new intnu

34、m;data=rfile.getdata();sequence=new arraylistservicenum;timepersequence=new intservicenum;for(int i=0;i<servicenum;i+)sequencei=new arraylist<integer>();timepersequencei=0;sort();setsequence();setaveragetime();public void sort()for(int i=0;i<num;i+)for(int j=0;j<num;j+)if(datai<=da

35、taj)int k=0;k=datai;datai=dataj;dataj=k;public void setsequence()for(int i=0;i<num;i+)int index=getminsequenceindex();sequenceindex.add(datai);timepersequenceindex+=datai;/system.out.println("第"+i+"個數(shù)："+"最小序列為："+index +"time:"+timepersequenceindex);public i

36、nt getminsequenceindex()int k=-1;int min=10000;for(int i=0;i<servicenum;i+)if(timepersequencei<=min) min=timepersequencei; k=i;return k;public void setaveragetime()int totaltime=0;for(int i=0;i<servicenum;i+)int tmptime=0;int time二new intsequencei.size();time0=0;tmptime+=time0;for(int j=1;j

37、<sequencei.size();j+)for(int k=0;k<j;k+)timej +=sequencei.get(k);tmptime +=timej;totaltime +=tmptime;t=double.valueof(totaltime)/double.valueof(num);public void show()system.out.println();system.out.println("多機最優(yōu)次序為：");for(int i=0;i<servicenum;i+)system.out.print("服務機"+i

38、+"次序為:");for(int j=0;j<sequencei.size()-1;j+)system.out.print(sequencei.get(j)+”->");system.out.print(sequencei.get(sequencei.size()-1);system.out.println();system.out.println("平均等待時間為："+t);主函數(shù)代碼：mutiservice service2=new mutiservice(rfile);service2.show();輸入格式為:1 .服務機數(shù)

39、量2 .顧客數(shù)量3.每一個顧客的服務時間10 2q 15 26 6 9 23 12 3 2 |舒里提粉朋希機置為：3仔若費里為：10任郎間勒耨分別為：10 20 15 26 6 9 23 12 m 2番機最優(yōu)次序為：質機密劃？為：9->15->26瞄機1：知？為：6-314>23廉務機2次序為：2>1g- >2g->34平+簿陸i同為：m3網格行走問題題目描述 給定一個m x n的矩形網格，設其左上角為起點 & 一輛汽車從起點s 出發(fā)駛向右下角終點 t。網格邊上的數(shù)字表示距離。在若干個網格點處設置了障礙，表示 該網格點不可到達。試設計一個算法，求出汽

40、車從起點s出發(fā)到終點t的一條行駛路程最短 的路線。下圖描述了一張4 x 4的道路網格，網格點（2, 2）處設置了一個障礙， 汽車無法到達該點。圖1網格行走問題樣例輸入2 2 202 2 3 32 2 33 3 5 44 2 210 10 5 510 10 1012 2樣例輸出18(1, 1)->(2, 1)->(3, 1)->(3, 2)->(3, 3)->(3, 4)->(4, 4)解題思路 以每個網格點為結點，可達網格點的網格邊為邊建圖，則可以建立無向有環(huán)圖。所以就將題目轉換成了無向有環(huán)圖上的兩點間最短路問題。而兩點間最短路問題的復雜度不會低于單源最短路

41、問題，所以就將題目轉換為無向有環(huán)圖上的單源最短路問題。無向有環(huán)圖上的最短路問題的經典算法有：dijkstra、bellman-ford、floyd-warshall。其中，dijkstra和bellman-ford可以求解單元最短路，bellman-ford可以求解帶負邊的最短路。 floyd-warshall可以求解任意兩點最短路。對于無負邊的情況，dijkstra算法的效率最高，若使用優(yōu)先隊列來優(yōu)化，時間復雜度可 以降為o(|e|log|v|)。故選擇dijkstra算法來求解。具體來說，dijkstra算法基于貪心思想，在求解過程中利用記憶化搜索(動規(guī))來輔助 求解?？紤]網格點(i,j)

42、的情況，假設從起點到(i, j)的最短路是d(i, j),那么可以由四個方向來 到 d(i, j),對應著 4 條入邊。所以有遞推關系d(i, j) = mind(k, l)|e(k,l), (i,j) c e。令s為已知最短路的結點的集合，則初始情況下s=s在dijkstra算法執(zhí)行時，考慮所有從s連出的邊e(u,v),取出d(v)最小的v。對于v,使用前述遞推式和結點v更新其余結點。也就是在這一步時，認為d(v)就是s到v的最短路。貪心證明：因為邊權為正，所以當 d(v)最小時不可能通過別的點到達v使得d(v)更小。當算法結束時，即可以求得所有點的最短路。最短路徑統(tǒng)計新開一個數(shù)組pa存儲每

43、個結點的前驅結點，在遞推式 du+e.cost < dv為真時更新pav = u。也可以在算出每一個結點的最短路后，利用du + e.cost = dv來找到結點v的前驅結點uo這里采用第一種方法。偽代碼q.add(new heapnode(0, s); /初始化，將起點加入優(yōu)先隊列while(!q.isempty)u = q.poll().u;if(doneu) continue;doneu = true;for(u吊所有出邊e(u, v) if(du+e.cost < dv) dv = du + e.cost; pav = u;q.add(new heapnode(dv, v)

44、; 算法實現(xiàn)import java.io.file;import java.io.filenotfoundexception;import java.io.ioexception;import java.util.arraylist;import java.util.arrays;import java.util.list;import java.util.priorityqueue;import java.util.queue;import java.util.scanner;class main class edge int from, to, cost;public edge(int f

45、rom, int to, int cost)this.from = from; this.to = to; this.cost = cost;class heapnode implements comparable<heapnode>int d, u;public heapnode(int d, int u)this.d = d; this.u = u;overridepublic int comparet o(heapnode o) return d-o.d;static int inf = integer.max_value;static int maxn = 10000;in

46、t n,m;int d = new intmaxn, pa = new intmaxn;boolean口 done = new booleanmaxn, obstacle = new booleanmaxn;list<edge> edges;list<list<integer>> g;void dijkstra()arrays.fill(d,0,n*m,inf);arrays.fill(done,0,n*m,false);arrays.fill(pa, 0, n*m, -1);d0 = 0;queue<heapnode> q = new prio

47、rityqueue<heapnode>();q.add(new heapnode(0, 0);while(!q.isempty()heapnode x = q.poll();int u = x.u;if(doneu) continue;doneu = true;for(int i=0; i<g.get(u).size(); i+)edge e = edges.get(g.get(u).get(i);if(obstaclee.to) continue;if(de.from + e.cost < de.to)pae.to = e.from;de.to = de.from +

48、 e.cost;q.add(new heapnode(de.to, e.to);void addedge(int u, int v, int cost)g.get(u).add(edges.size();edges.add(new edge(u,v,cost);g.get(v).add(edges.size(); edges.add(new edge(v,u,cost);boolean first = true;void print_path(int u)if(pau != -1) print_path(pau);if(first) first = false;else system.out.

49、print("->");system.out.printf("(%d, %d)", u/m + 1, u%m + 1);void solve() dijkstra();system.out.println(d(n-1)*m + (m-1);first = true; print_path(n-1)*m + (m-1); 一void begin() throws ioexception n = in.nextint(); m = in.nextint();int cost;g = new arraylist<list<integer>

50、;>();for(int i=0; i<n*m; i+)g.add(new arraylist<integer>();edges = new arraylist<edge>();for(int i=0; i<m-1; i+) cost = in.nextint(); addedge(i, i+1, cost);for(int i=0; i<n-1; i+) for(int j=0; j<m; j+) cost = in.nextint();addedge(i*m+j, (i+1)*m+j, cost);for(int j=0; j<m

51、-1; j+) cost =in.nextint(); addedge(i+1)*m+j, (i+1)*m+j+1,cost);int k = in.nextint(), u, v;arrays.fill(obstacle, 0, n*m, false); while(k- > 0)u = in.nextint(); v = in.nextint(); obstacle(u-1)*m+(v-1) = true; solve();public void close() throws ioexception in.close();scanner in;public main() throws

52、 filenotfoundexception in = new scanner(new file("in.txt");public static void main(string口 args) throws loexception main sssp = new main();sssp .begin();sssp .close();荷蘭國旗問題1 .原問題描述將亂序的紅白藍三色小球排列成有序的紅白藍三色的同顏色在一起的小球組。這個問題之所以叫荷蘭國旗，是因為可以將紅白藍三色小球想象成條狀物，有序排列后正好組成荷蘭國旗。要求算法的時間復雜度為o(n)。2 .設計思路可以將這個

53、問題視為一個數(shù)組排序問題，這個數(shù)組分為前部，中部和后部三個部分，每一個元素(紅白藍分別對應0、1、2)必屬于其中之一。由于紅、白、藍三色小球數(shù)量并不一定相同，所以這個三個區(qū)域不一定是等分的，也就是說如果我們將整個區(qū)域放在0,1的區(qū)域里，由于三色小球之間數(shù)量的比不同(此處假設1:2:2),可能前部為0,0.2),中部為0.2,0.6),后部為0.6,1。所有的排序方法都可以颼用:時間復雜度最小為oqm鳴川3 .算法設計首位置ib=1 ,尾位置ie=length 。loop 5 累計量 i=1 , length若i=ie退出loop 5若 nn(i)=0 , ib=ib+1 , i=i+1若舊wi

54、 nn(i)和nn(ib)互換;若 nn(i)=1 , i=i+1;若 nn(i)=2 , i=i+1 , ie=ie-1若 nn(ie)=1 , nn(i)和 nn(ie)互換；若 nn(ie)=0 , ib=ib+1若舊=i , nn(i)和nn(ie)互換；若 ibwj nt=nn(ib) , nn(舊戶nn(ie) , nn(ie尸nn(i) , nn(i)=nt ;若 nn(ie)=2 ,則進行 ie=ie-1 直到 nn(ie)豐l若 nn(ie)=1 , nn(i)和 nn(ie)互換；若 nn(ie)=0 , ib=ib+1若舊=i , nn(i)和nn(ie)互換；若 ibi nt=nn(ib) , nn(舊戶nn(ie) , nn(ie尸nn(i) , nn(i)=nt ;結束loop 54 .實例/執(zhí)行結果輸入數(shù)據nn (10,2):編號：1,2,3,4,5,6