实验讲义-算法指导

《算法设计与分析》实验指

实验单算法设用O,Ω,Θ估计。算法时间复杂性通过以下方法来估计：（1）计算迭代（循环）次数（2）计算基本运算熟悉)输入：输入的第一行是一个正整m，表示测试例个数。接下来几m个测试例的数据，每个测试例的数据由两行组成，其中第一行为一个正整数n(n<=500)，表示整数序列的长971256438525311926 21123421786754.

264578965222376594321333(二)整数集合分输入的第一行是一个正整数m，表示测试例个数。接下来几行是m个测试例的数据，每个nn<=500)，表示原整数集合的长度，第二行给出这n个整数序列，整数之间用一个空格隔开。268253416237395765721134782961739512043283485914324751426192452786523778517329726953723461213161720212934373943515768767822379142426282932374247485151525961626573784.实验二递归算法设计与应四.例如：n=2时的码为：{00,01,11,10}。个测试例的输入数据由一行组成，用一个正整数n(n<=20)，表示码的位数。55000000100110010011001110101010011001101111111101010101110011000000000000100011000100011000111001010010001100011010111101110010100101101001010001100011001110111101011110111111110111100101001101110110100101001110001100004.对于同一个输入的正整数，不同的算法得到的码可能会不同。长度为n的码可以由长度为n-1的码适当变换而成。可以用数组或字符串来码。对于较大的正整数n，用数组容易引起死机。

实验三分治算法设计与应分解→直接或递归求解子问 →组设B是一n×n棋盘，n=2k,(k=1,2,3,…)。用分治法设计一个算法，使得：用若干个L型条块可以覆盖住B除一个特殊方格外的所有方格。其中，一个L型条块可以覆3方格。且任意两个L型条块不能覆盖棋盘。例如：如n=2，则存4个方格，其中，除一个方格外，其3个方格可L型条n=4时，则存16个方格，其中，除一个方格外，其15个方5个L型条输入一个正整数n，表示棋盘的大小是n*n的。输出一个被L型条块覆盖的n*n棋盘。该棋盘除一个方格外，其余各方格都被L型条块覆盖住。为区别出各个方格是被哪个L型条块所覆盖，每个L型条块用不同的数字或颜色、标记表示。4.mm个测试例的数据，输出：对于每个测试例输出一k个整数组成，表示输n整数中k说明：限于Acm平台，要求输出数据按从小到大排序。算法的时间复杂性也相应地放2954637811273 88332817515749351125 232545162223373567811.耗费时间为O(nlogn),超出要求；如果运行算法SELECTk次，耗费Θ(kn)=O(n2),因k不是常量，因此不能简单地运行算法SELECTk次。由于Acm平台的限制，输出数据应按升序排列，估时间复杂性也相应地放宽要求。本Acm平台1764题实验四动态规划算法设序列中非连续的数按照原序列顺序排列而成的。最长递增子序列是其递增子序列中长度输入：输入的第一行是一个正整n，表示测试例个数。接下来几n个测试例的数据，每个测试例的数据由两行组成，其中第一行为一个正整数k(k<=500)，表示整数序列的长25331241354.第1700题。mm个测试例的2nx1y1x2,y2,…xn,ynn个顶点的坐标值(xi,yi)i=1,2,…,n，整数之间用一个空格隔开。剖分的n-3条弦的长度之和。两个测试例的输出数据之间用一个空行隔开。61221.520.51000.50题的关键，注意递归方程的参数的设置。本题是Acm平台上第1701题。一．基本原理的

实验五贪心算法设计与应不可取消 二．该类算法设计与实现的三．实验目的和四．实验(一)加油问题（ProblemSet1702问题描AB（设出发时油箱是空的。给定两个城市之间要花最少的油费从城市A到城市B，在每个应加多少油，最少花费为多少？具体要输入的第一行是一个正整数k，表示测试例个数。接下来几行是k个测试例的数据，每个距离d1、汽车油箱的容量c（以升为单位、每升能行驶的距离d2、沿途油站数n(1<=n<=200)n个实数d1d2dn，表示各油站离出发点的距离（d10第三行含n个实数p1,p2,…,pn，表示各油站每升的价格。同一行的数之间用一个SolutionSample2150050100300.0800.04.05.04.0100040100500.04.55.0SampleNo设计与实现的提扩展内TheExpressMail(ProblemSet(二)黑白点的匹配（ProblemSet1714问题描b（xb,ybw=(xwyw)xb>=xw和yb>=ywbw，则黑点bw可匹配（可形成一个匹配对。在一个黑点最多只能与一个白点匹配，一个白点最多只能与一个黑点匹配的前提下，求n个白点和n个黑点的最大匹配对数。具体要1n(n<16)2n个实数xb1,yb1,xb2,yb2,…,xbn,ybn，(xbi,ybi)，i=1,2,…,n表示n个黑点的坐标；第三行含2n个实xw1yw1,xw2yw2xwnywn，(xwiywi)，i=1,2,…n表示n个白点的坐标。n个白点和nSample135.03.05.0-1.04.02.03.52.02.0-2.0-Sample3扩展内实验六回溯算法设计与应一．基本原理的直接回到其父结点，继续DFS。三．实验目的和四．实验(一)寻宝问题（ProblemSet1417问题描可以走，当然前提是在没有的情况之下，其中可以分为单步走（onfoot）和跳步走（byjump）两种情况，从起点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设计与实现的提扩展内(二)邮票问题（ProblemSet1746问题描n=3，m=32,3,5，则最大的具体要输入的第一行是一个正整数n，表示测试例个数。接下来几行是n个测试例的数据，每个nm1<=n,m<=10)n种邮票，每封信最多贴m张邮票；第二行含n个正整数，表示n种邮票的面值。同一行Sample232341412Sample21设计与实现的提扩展内一．基本原理的

实验七算法设计技术的应二．该类算法设计与实现的三．实验目的和四．实验（一）旅行商问题（ProblemSet1747：问题描n个城市（顶点）G,nv1,v2,…,vn,G的邻