實(shí)驗(yàn)講義-算法指導(dǎo)

《算法設(shè)計(jì)與分析》實(shí)驗(yàn)指

實(shí)驗(yàn)單算法設(shè)用O,Ω,Θ估計(jì)。算法時(shí)間復(fù)雜性通過以下方法來估計(jì)：（1）計(jì)算迭代（循環(huán)）次數(shù)（2）計(jì)算基本運(yùn)算熟悉)輸入：輸入的第一行是一個(gè)正整m，表示測(cè)試?yán)齻€(gè)數(shù)。接下來幾m個(gè)測(cè)試?yán)臄?shù)據(jù)，每個(gè)測(cè)試?yán)臄?shù)據(jù)由兩行組成，其中第一行為一個(gè)正整數(shù)n(n<=500)，表示整數(shù)序列的長(zhǎng)971256438525311926 21123421786754.

264578965222376594321333(二)整數(shù)集合分輸入的第一行是一個(gè)正整數(shù)m，表示測(cè)試?yán)齻€(gè)數(shù)。接下來幾行是m個(gè)測(cè)試?yán)臄?shù)據(jù)，每個(gè)nn<=500)，表示原整數(shù)集合的長(zhǎng)度，第二行給出這n個(gè)整數(shù)序列，整數(shù)之間用一個(gè)空格隔開。268253416237395765721134782961739512043283485914324751426192452786523778517329726953723461213161720212934373943515768767822379142426282932374247485151525961626573784.實(shí)驗(yàn)二遞歸算法設(shè)計(jì)與應(yīng)四.例如：n=2時(shí)的碼為：{00,01,11,10}。個(gè)測(cè)試?yán)妮斎霐?shù)據(jù)由一行組成，用一個(gè)正整數(shù)n(n<=20)，表示碼的位數(shù)。55000000100110010011001110101010011001101111111101010101110011000000000000100011000100011000111001010010001100011010111101110010100101101001010001100011001110111101011110111111110111100101001101110110100101001110001100004.對(duì)于同一個(gè)輸入的正整數(shù)，不同的算法得到的碼可能會(huì)不同。長(zhǎng)度為n的碼可以由長(zhǎng)度為n-1的碼適當(dāng)變換而成?？梢杂脭?shù)組或字符串來碼。對(duì)于較大的正整數(shù)n，用數(shù)組容易引起死機(jī)。

實(shí)驗(yàn)三分治算法設(shè)計(jì)與應(yīng)分解→直接或遞歸求解子問 →組設(shè)B是一n×n棋盤，n=2k,(k=1,2,3,…)。用分治法設(shè)計(jì)一個(gè)算法，使得：用若干個(gè)L型條塊可以覆蓋住B除一個(gè)特殊方格外的所有方格。其中，一個(gè)L型條塊可以覆3方格。且任意兩個(gè)L型條塊不能覆蓋棋盤。例如：如n=2，則存4個(gè)方格，其中，除一個(gè)方格外，其3個(gè)方格可L型條n=4時(shí)，則存16個(gè)方格，其中，除一個(gè)方格外，其15個(gè)方5個(gè)L型條輸入一個(gè)正整數(shù)n，表示棋盤的大小是n*n的。輸出一個(gè)被L型條塊覆蓋的n*n棋盤。該棋盤除一個(gè)方格外，其余各方格都被L型條塊覆蓋住。為區(qū)別出各個(gè)方格是被哪個(gè)L型條塊所覆蓋，每個(gè)L型條塊用不同的數(shù)字或顏色、標(biāo)記表示。4.mm個(gè)測(cè)試?yán)臄?shù)據(jù)，輸出：對(duì)于每個(gè)測(cè)試?yán)敵鲆籯個(gè)整數(shù)組成，表示輸n整數(shù)中k說明：限于Acm平臺(tái)，要求輸出數(shù)據(jù)按從小到大排序。算法的時(shí)間復(fù)雜性也相應(yīng)地放2954637811273 88332817515749351125 232545162223373567811.耗費(fèi)時(shí)間為O(nlogn),超出要求；如果運(yùn)行算法SELECTk次，耗費(fèi)Θ(kn)=O(n2),因k不是常量，因此不能簡(jiǎn)單地運(yùn)行算法SELECTk次。由于Acm平臺(tái)的限制，輸出數(shù)據(jù)應(yīng)按升序排列，估時(shí)間復(fù)雜性也相應(yīng)地放寬要求。本Acm平臺(tái)1764題實(shí)驗(yàn)四動(dòng)態(tài)規(guī)劃算法設(shè)序列中非連續(xù)的數(shù)按照原序列順序排列而成的。最長(zhǎng)遞增子序列是其遞增子序列中長(zhǎng)度輸入：輸入的第一行是一個(gè)正整n，表示測(cè)試?yán)齻€(gè)數(shù)。接下來幾n個(gè)測(cè)試?yán)臄?shù)據(jù)，每個(gè)測(cè)試?yán)臄?shù)據(jù)由兩行組成，其中第一行為一個(gè)正整數(shù)k(k<=500)，表示整數(shù)序列的長(zhǎng)25331241354.第1700題。mm個(gè)測(cè)試?yán)?nx1y1x2,y2,…xn,ynn個(gè)頂點(diǎn)的坐標(biāo)值(xi,yi)i=1,2,…,n，整數(shù)之間用一個(gè)空格隔開。剖分的n-3條弦的長(zhǎng)度之和。兩個(gè)測(cè)試?yán)妮敵鰯?shù)據(jù)之間用一個(gè)空行隔開。61221.520.51000.50題的關(guān)鍵，注意遞歸方程的參數(shù)的設(shè)置。本題是Acm平臺(tái)上第1701題。一．基本原理的

實(shí)驗(yàn)五貪心算法設(shè)計(jì)與應(yīng)不可取消 二．該類算法設(shè)計(jì)與實(shí)現(xiàn)的三．實(shí)驗(yàn)?zāi)康暮退模畬?shí)驗(yàn)(一)加油問題（ProblemSet1702問題描AB（設(shè)出發(fā)時(shí)油箱是空的。給定兩個(gè)城市之間要花最少的油費(fèi)從城市A到城市B，在每個(gè)應(yīng)加多少油，最少花費(fèi)為多少？具體要輸入的第一行是一個(gè)正整數(shù)k，表示測(cè)試?yán)齻€(gè)數(shù)。接下來幾行是k個(gè)測(cè)試?yán)臄?shù)據(jù)，每個(gè)距離d1、汽車油箱的容量c（以升為單位、每升能行駛的距離d2、沿途油站數(shù)n(1<=n<=200)n個(gè)實(shí)數(shù)d1d2dn，表示各油站離出發(fā)點(diǎn)的距離（d10第三行含n個(gè)實(shí)數(shù)p1,p2,…,pn，表示各油站每升的價(jià)格。同一行的數(shù)之間用一個(gè)SolutionSample2150050100300.0800.04.05.04.0100040100500.04.55.0SampleNo設(shè)計(jì)與實(shí)現(xiàn)的提擴(kuò)展內(nèi)TheExpressMail(ProblemSet(二)黑白點(diǎn)的匹配（ProblemSet1714問題描b（xb,ybw=(xwyw)xb>=xw和yb>=ywbw，則黑點(diǎn)bw可匹配（可形成一個(gè)匹配對(duì)。在一個(gè)黑點(diǎn)最多只能與一個(gè)白點(diǎn)匹配，一個(gè)白點(diǎn)最多只能與一個(gè)黑點(diǎn)匹配的前提下，求n個(gè)白點(diǎn)和n個(gè)黑點(diǎn)的最大匹配對(duì)數(shù)。具體要1n(n<16)2n個(gè)實(shí)數(shù)xb1,yb1,xb2,yb2,…,xbn,ybn，(xbi,ybi)，i=1,2,…,n表示n個(gè)黑點(diǎn)的坐標(biāo)；第三行含2n個(gè)實(shí)xw1yw1,xw2yw2xwnywn，(xwiywi)，i=1,2,…n表示n個(gè)白點(diǎn)的坐標(biāo)。n個(gè)白點(diǎn)和nSample135.03.05.0-1.04.02.03.52.02.0-2.0-Sample3擴(kuò)展內(nèi)實(shí)驗(yàn)六回溯算法設(shè)計(jì)與應(yīng)一．基本原理的直接回到其父結(jié)點(diǎn)，繼續(xù)DFS。三．實(shí)驗(yàn)?zāi)康暮退模畬?shí)驗(yàn)(一)尋寶問題（ProblemSet1417問題描可以走，當(dāng)然前提是在沒有的情況之下，其中可以分為單步走（onfoot）和跳步走（byjump）兩種情況，從起點(diǎn)Scount2。具體要Thelineoftheinputisanintegern(0<=n<=20),denotingthenumberoftestcases.Thefollowinglinesarethedataofntestcases.Thelineofeachtestcaseconsistsoftwointegerxandy(0<x<10,0<y<10).Thenextxlinesdescribethemazematrix,whichcontainsxrowsandycolumns.Inthematrix,'W'denotesthebarrier,'B'denotestheenterableposition,’S’denotesthestartingposition,and‘X’denotesthepositionoftheark.Therehaveandonlyhaveone‘S’andone‘X’inamazematrix.Foreachtestcase,outputoneline.Ifthereisasolutionfortheproblem,outputthenumbertheleaststepstofindtheArk.Otherwiseoutput“NOSample335432Sample22NO設(shè)計(jì)與實(shí)現(xiàn)的提擴(kuò)展內(nèi)(二)郵票問題（ProblemSet1746問題描n=3，m=32,3,5，則最大的具體要輸入的第一行是一個(gè)正整數(shù)n，表示測(cè)試?yán)齻€(gè)數(shù)。接下來幾行是n個(gè)測(cè)試?yán)臄?shù)據(jù)，每個(gè)nm1<=n,m<=10)n種郵票，每封信最多貼m張郵票；第二行含n個(gè)正整數(shù)，表示n種郵票的面值。同一行Sample232341412Sample21設(shè)計(jì)與實(shí)現(xiàn)的提擴(kuò)展內(nèi)一．基本原理的

實(shí)驗(yàn)七算法設(shè)計(jì)技術(shù)的應(yīng)二．該類算法設(shè)計(jì)與實(shí)現(xiàn)的三．實(shí)驗(yàn)?zāi)康暮退模畬?shí)驗(yàn)（一）旅行商問題（ProblemSet1747：?jiǎn)栴}描n個(gè)城市（頂點(diǎn)）G,nv1,v2,…,vn,G的鄰