算法设计与分析五邑大学.ppt

算法设计问题示例,计算机科学的本质是算法,计算机硬件系统仅仅是依照特定的算法， 按照物理和电子学原理，采用特定的工艺流程生产的 一种电子计算装置,计算机程序设计语言是仅仅是程序员 与计算机硬件系统进行沟通、交流的 一种工具语言 熟练掌握一种程序设计语言是成为一名优秀程序员的基础,要成为一名优秀的、能够解决各类疑难问题的程序员 必须具有良好的算法设计的品质,1. 中国象棋中马的走法,问题描述：在45的棋盘上已知马的起始坐标(x,y)，求马 能够返回到起始位置的不重复的所有不同走法的总数。,回 溯 法！,马当前所在的位置是当前扩展结点！,每个活结点可能有八个孩子结点！,如何记录马行走的路径？,1,5,2,6,4,3,class Horse private: int chess56; int d28=(1,2,2,1-1,-2,-2,-1),(2,1,-1,-2,-2,-1,1,2); int sx,sy; int count; public: Horse(int x,int y) sx=x; sy=y; for(int i=0;i=6|sy=5) return ; backtrack(sx,sy); return count; Private static void backtrack(int p1,int p2); ;,Private static void Horse: backtrack(int p1,int p2) int pi,pj; for(int i=0;i=0,2. 合法的括号序列,问题描述：定义合法的括号序列： 1.空序列是合法的括号序列； 2.如果符号串S是合法的括号序列，则(S) 和S均是合法的括号序列； 3.如果符号串A和B是合法的括号序列，则AB也是合法的括号序列。 现有由(，)，组成的任意符号串X=x1x2xn，请添加尽可能少的四种括号，使其成为一个合法的括号序列。,动态规划！,分析：假设子问题Xij=xixi+1xkxk+1xj-1xj最少需要添加mij个括号，则： 0 ij 1 i=j mij= minmij, mi+1j-1 xi=(&sj=) | xi=&xj= minmij, mi+1j +1 xi=( | xi= minmij, mij-1 +1 xj=) | xj= minmij, mik+mk+1j （i=kj） 否则,public static int kh(char x) int n=x.length-1; int m=new int m+1n+1; for(int i=1; i=n; i+) mii-1=0; for(int i=1; i=n; i+) mii=1; for(int r=2; i=n; r+) for(int i=1; i=n-r+1; i+) int j=i+r-1; mij=MaxINT; if(xi=( ,3. 棋盘的最优分割,问题描述： 一个88的棋盘中每个格子里均有一个分值。对棋盘沿着任意一条格子线进行一次分割，将使棋盘成为两块矩形棋盘。给定n15，对原棋盘进行n-1次分割，就把棋盘分割成了n块矩形棋盘。一块矩形棋盘的总分是他的所有格子的分值之和。请设计算法，给出把原棋盘分割成n块矩形棋盘的方案，使得各矩形棋盘总分的平方和 最小。其中xi是第i块棋盘的总分。,动态规划！,x1,y1,x2,y2,a,b,3. 棋盘的最优分割,假设左上角为(x1,y1)、右下角为(x2,y2)的棋盘的总分为： sx1,y1,x2,y2， 被切割k次后得到的k+1块矩形的总分平方和的最小值是： dk,x1,y1,x2,y2,则： dk,x1,y1,x2,y2=min min dk-1, x1, y1, a, y2+ sa+1, y1, x2, y2, dk-1, a+1, y1, x2, y2+ sx1, y1, a, y2 (x1ax2) , min dk-1, x1, y1, x2, b+ sx1, b+1, x2, y2, dk-1, x1, b+1, x2, y2+ sx1, y1, x2, b (y1by2) ,我们最终需要的是： dn1188,4. 多边形游戏,问题描述：a任意画了一个凸n边形，并任意对其n个顶点进行1到n的编号。A又再这个多边形上画了m条不会相交于多边形内部的弦。现在a以(i, j)的方式把这n条边和m条弦告诉给b，让b说出n边形的n个顶点的编号顺序。其中(i, j)是编号为i、j的两个顶点之间的一条边或者弦。,问题分析： “m条不会相交与多边形内部的弦”表明：a画的n边形中至少有两个顶点不是任何弦的端点，而交于这个顶点的必定是多边形的边。这样的顶点的度为2！,算法： 1.求出所有度为2的顶点； 2.当存在度为2的取出一个度为2 的顶点s，以s为端点的边是(s,u)和(s,v)； 2.从边集中删除这两个边，并标记或补充补充标记虚边(u,v)；,示例： n=8,m=5 13条直线是： (1,5) (5,2) (2,7) (7,6) (6,4) (4,8) (8,3) (3,1) (2,3) (2,8) (7,4) (5,3) (2,4),6,4,7,2,8,3,5,1,5. 分离英文单词,问题描述：长度为n的双重单词串是一个由小写英文字母组成的字符串，它至少存在两种分离单词的方法，每种方法都能形成一组正确的单词排列，并且两种方法中不会出现相同的单词；同一单词不会重复出现；一个单词在一种方法中的结束位置不会与某个单词在另一种方法中的结束位置相同（单词串结束例外）。 给定包含m个单词的单词表，是否能够从中选择出若干个单词，组成一个长度为n的双重单词串。,示例：n=17, m=14 all,an,and,are,area,as,ask,at,data,last,or,read,real,task,双重单词串是： andatareallastask,5. 分离英文单词,问题分析：字母表是否存在两个不相交的子集A和B，他们中所有单词的长度之和均等于n？,No： 不存在长度为n的双重单词串！,Why?,Yes： 的长度为n的双重单词串的构造算法。,等量0-1背包问题,分别由字母表的子集A和B中所有单词构造长度为n相同的两个字符串，该字符串就是上的长度为n的双重单词串！,0,3,0,5,3,2,0,8,5,6,3,5,2,3,0,11,8,an,ask,data,last,real,as,at,and,all,are,task,an,and,data,at,are,real,all,last,as,task,ask,6. 会餐交友问题,问题描述：某机构举行一次不超过500人参加的盛大餐会，以增进与会者之间的友谊。所以采取自助餐形式，客人可以自由走动、交谈。由于客人中有些相互认识、有些相互不认识。为了让客人相互引见，使大家都能认识更多的朋友，举办方想控制中途离开的客人的人数。当客人离开太多时，就应该宣布餐会结束。问题是，最少有多少客人离开后，剩下的客人两两彼此都不认识？,输入示例： 8 1,2 1,3 2,4 7,6 4,3 5,6 0,0,输入数据：n表示客人的个数，客人的编号依次是1,2,n。 i,j表示客人i和j相互认识；i=0&j=0时输入数据结束。,输出示例： 3 2,3,6,1,2,3,6,5,7,4,6. 会餐交友问题的算法,一个结点代表什么？,结点的度说明了什么？,FIFO还是优先队列？,为什么按照结点的度由大到小排队？,删除一个结点意味着什么？之后还需要做什么？,7. 点在哪个图形内,问题描述：给定一组图形（矩形或者圆）和一组点，判断每个点落在哪个图形内。,输入示例： R 0.0 0.0 5.5 10.3 C -5.0 -5.0 3.7 R 2.5 2.5 12.5 12.5 * 2.0 2.0 4.7 5.3 9999.9 9999.9,输出示例： Point 1 is contained in figure 1. Point 2 is contained in figure 1. Point 2 is contained in figure 3.,x0,y0,x2,y2,x1=x=x2& y1=y=y2,r,(x-x0)2+(y-y0)2=r2,x1,y1,8. 最小半径圆,问题描述：给设平面上有n个点(0n1000)，第i个点的坐标是(xi,yi)。约定0xi10000&0yi10000。求一个最小半径的圆，使得n个点均在圆内(可以在圆上)。,输入示例： 3 3 0 0 1 0 0 1 4 0 0 0 1 1 1 1 0 4 0 0 2 0 4 0 2 2,输出示例： 0.50 0.50 0.71 0.50 0.50 0.71 2.00 0.00 2.00,半径为0的圆,以两点之间的直线为直径的圆,以两条垂直平分线的交点为圆心的圆,9. 等高登山问题,问题描述：两个人在一山脉的两头处于同一水平位置。他们商定以等高的方式同时登上山脉的最高顶。已知整个山脉中每个山顶和谷底的坐标。由于两个人要保持等高，所以他们的速度和上下方向完全不同。请写算法为他们计算出每次有人改变上下方向时，两个人所处的位置坐标。,0,1,2,3,7,11,13,16,1,2,3,5,9. 等高登山问题,输入示例 6 0 0 2 2 3 1 7 5 11 1 13 3 16 0,输出示例 6 0.00 0.00 16.00 0.00 2.00 2.00 14.00 2.00 3.00 1.00 15.00 1.00 5.00 3.00 13.00 3.00 3.00 1.00 11.00 1.00 7.00 5.00 7.00 5.00,算法？,联想？,速度,一维,动画,10. 模运算问题,问题描述：某美国麻省理工学院的三位教授发明了目前很流行的编码规则，称为RSA。这种编码规则的使用，要求有一个高效的模运算函数。请你帮他们设计一个这样的函数：对于三个正整数a,b,c(1a,bc32768)，计算 ab mod c,问题分析： 冪运算使得结果数据变大；我们面对的是 ab！ 模运算使得结果数据变小。 对乘积及时求莫，把一次莫运算变成多次模运算。,依据： xy mod z = x (y mod z)mod z,10. 模运算问题,int fmod(int a,int b,int c） if(!(1=a ,11. 最短表面距离问题,问题描述：一个长方体P=(x,y,z)|0xL,0yW,0zH的表面上有两个点A(x1,y1,z1)和B(x2,y2,z2)，求A与B之间的最短表面距离。,问题分析： 平面上两点之间的直线距离最短； 球面上两点之间的最短距离？,延伸： 此问题非平面亦非球面。 转化：将长方体表面上的两点转化成平面上的两点。,区分： 1.两点在长方体的同一表面上； 2.两点在长方体的两个相邻表面上； 3.两点在长方体的两个相对表面上。,11. 最短表面距离问题,1.A(x1,y1,z1)和B(x2,y2,z2)在长方体的同一表面上。 直接计算直线距离！,2.A(x1,y1,z1)和B(x2,y2,z2)在长方体的两个相邻表面上。 展开长方体；分三种情况；取小。,3.A(x1,y1,z1)和B(x2,y2,z2)在长方体的两个相对表面上。 展开长方体；分12种情况；取小。,12. 多花钱多卖鱼问题,问题描述：现有资金m，想去购买n种鱼中尽可能多的鱼，每种鱼只能购买一条。第i条鱼的价格是pi。如果第i条鱼与第j条鱼相互斗食而不能共存，则这两条鱼只能选择其一。写出能够计算出最佳买鱼方案的算法。,输入示例： 170 7 1 70 2 50 3 30 4 40 5 40 6 30 7 20 1 4 1 7 3 4 3 5 5 7 6 7 0 0,输出示例： 4 160 2 4 5 6,这是一个什么问题？,12. 多花钱多卖鱼问题,问题分析： 这个问题有一些约束条件： 1.所买鱼的价格总和不能超过资金数m； 2.不能共存的鱼不能同时购买； 3.每种鱼最多买一条； 4.在满足上述条件的前提下，买尽可能多的鱼； 5.在满足上述条件的前提下，花尽可能多的买鱼钱。,这是一个什么性质的问题？,输入示例： 170 7 1 70 2 50 3 30 4 40 5 40 6 30 7 20 1 4 1 7 3 4 3 5 5 7 6 7 0 0,170,250,330,440,540,630,720,13. 巧妙的剪纸问题,问题描述： 有一张正方形的纸，用笔和直尺把它等分成mm个小方格，用彩笔选择任一小方格作为起点，任意地一笔画一条正好经过了nn个小方格的彩线，把有彩线的小方格标记为*。我们的问题是，你能够把所有标记为*的小方格从纸上全部剪下来在一张纸片上,然后再把它分剪成两片纸，使得这两片纸经过旋转、翻转或平移后可以拼成一个nn的正方形。,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*,A,B,B,A,B,A,B,B,B,B,A,A,A,A,A,A,A,A,A,A,A,A,A,A,A,B,B,B,B,B,B,B,13.巧妙的剪纸问题,问题分析：我们需要解决两个问题： 1.如何巧妙地将所有带*的纸剪成两片纸？ 2.这两片纸如何拼接成一个正方形？,!所有的*是连通的。,剪掉所有的空白纸，并记录横向或者纵向上*连续个数大于n的直线坐标。,从左到右、从上到下找到第一个与空白纸相邻的*，从此开始，按照右手规则剪掉所有的空白纸。,! nn的正方形是由两片纸拼接成的。这两片纸中直线上有连续n个*的情形可以分为几种？,! 带*的纸片上连续超过n个*的直线是需要下剪子的。,13.巧妙的剪纸问题,!纸片的平移、旋转和翻转。,对两张纸片分别进行矢量化处理。若取左上角方格的坐标是(0,0)，则任意方格都有了相对坐标(x,y)。,旋转(逆时针90。)：(x,y)(-y,x)。,翻转(上下)：(x,y)(x,-y)。 (左右)：(x,y)(-x,y)。,平移：(x,y)(xd,yd)。,拼接：做一个nn的正方形模版。先把第一张纸片放进去，再将第二张纸片经过有限次平移、旋转和翻转后放进去，若成功，则结束。,14. 单轨砌积木问题,问题描述： 有n个边长为1的正方体积木，要堆砌在一个无限长、宽为1的水平轨道上，形成一个高度不超过m的积木堆： 1.水平方向上第一层积木之间不能分离； 2.积木的下面必须与轨道或另一个积木的上面完全接触； 3.若两种堆砌方案经翻转后形状一样，则认为他们是同一种方案。 试计算出所有的不同堆砌方案。,这又是一个什么问题？,这又是一个什么性质的问题？,15. 盒子里的气球问题,问题描述： 在一个长方体盒子里，有n个点。在任何一个点上放置一个半径为0的气球，它就会膨胀成一个以该点为球心的标准球体，直到接触到其他气球或盒子的边界。必须等到一个气球膨胀停止后才能放置下一个气球。按照什么样的顺序在这n个点上放置气球，能使得n个气球放置完毕后，所有气球的体积总和最大。,枚举法！,假设要放置的第i个气球的球心是(xi,yi,zi)，现在需要计算它膨胀停止后的半径Ri。,假定它最终接触到的气球是半径为Rj的第j个气球，则： Ri =min Dij=(xi-xj)2+(yi-yj)2+(zi-zj)2)1/2-Rj; (xi,yi,zi)到盒子每个面的距离,16. 钓鱼问题,问题描述： 某人有h小时的时间想钓到数量最多的鱼。这时他已经在一条路边，从他所在的地方开始，放眼望去，n个鱼场一字排开，编号依次是1,2,n。他已经知道，从鱼场i走到鱼场i+1需要花ti分钟；他在鱼场i钓鱼，第一个5分钟可钓到重fi的鱼；若他继续在鱼场i钓鱼，每过5分钟，鱼量将减少di。请你给他设计一个最佳钓鱼方案。,贪心算法！,？,？,17. 折纸留痕问题,问题描述： 给你一张大矩形纸，连续从右向左对折纸n次形成一个纸条。现在把这个纸条小心地沿着折痕连续打开，使得折痕连接的两个面保持垂直，这时从纸的一端沿着和纸面平行的方向看去，会看到一条美妙的画面。快写个程序把这样的画面绘制出来！,递归与分治算法！,？,？,18. 三色凸多边形问题,问题描述： 有一个凸n边形，用红、绿、蓝对它的所有顶点进行染色，使得相邻顶点不同色，而且三种颜色都用过。请给出这个多边形一种三角剖分方案，使得每个三角形的三个顶点都不同色。,递归与分治算法！,？,？,19. 超长数字串问题,问题描述： 给定一个数字串S:12345678910111213141516171819202122232425262728293031 它是由所有自然数从小到大依次排列起来的。任意一个数字串S1一定在S中出现无穷多次。请你计算S1在S中首次出现的位置。,递归与分治算法！,？,？,20. 彩球问题,问题描述： 有n个人，每个人任意从编号为1到n的n个彩球中拿走一个彩球，你知道剩下的那个彩球的编号吗？你有权利每次询问第i个人他的彩球编号的右数第j个二进制位dij是几，他会正确回答你的。你能用最少的询问次数来确定最后一个彩球的编号吗？,递归与分治算法！,？,？,21.月亮之眼问题,问题描述：很早以前，在佛教圣地某庙宇的一根大立柱上，镶嵌着一串用银白色和黛黑色各染一半的金线串接起来的、由n颗珍珠组成的、谓之“月亮之眼”的圣物。由于所有珍珠以及它们之间的金线在柱子上形成一条与地面垂直、与柱子平行的直线；可能会有两个珍珠镶嵌在同一地方；可能会有两根金线重叠摆放，所有使得圣物很美丽壮观。可是有一天，圣物突然脱落遗失，几千年后，一个古董商人得到了圣物，他出于对佛的虔诚，把圣物送回圣地。圣地的僧人想恢复圣物的原状，可他们怎么都无法把圣物原样地镶嵌在柱子上。你能帮助他们吗？,递推,问题示例：,6,1,2,3,7,8,9,5,4,5,1,1,1,1,4,4,3,3,6,1,2,3,7,8,9,5,4,1,1,1,3,2,2,22.丢失的正整数数列问题,问题描述：数学老师给全班同学写了一个包含n个正整数的递增数列，要求大家回家后同样按照递增的次序，写出所有的、任意两个数的和。有个同学很快就写完了作业。可是他出去玩了一会，回来后发现老师给的原始数列丢失了。你能帮他找回来吗？,递推,22.丢失的正整数数列问题,问题分析：假设这个同学丢失的正整数递增数列是： a1,a2,a3,a4,an 他写出的结果包含了n(n-1)/2个数，它们由小到大是： k1,k2,k3,k4,! a1+a2=k1, a1+a3=k2,a2+a3= ?,假设 a2+a3=kx , 则解方程可得：a1,a2,a3,依次递推计算写出每个ai,22.丢失的正整数数列问题,例题：假设K=4,5,7,10,11,12,13,13,14,19，求 a1,a2,a3,a4,解：因为 a1+a2=4, a1+a3=5,a2+a3 是K中的哪一个数呢？a1,a2,a3,因为只有a1+ai 可能比a2+a3小，所以a2+a3 是K中的序号一定在3到(n+3)之间！,由于a2+a3 (a1+ a2)+(a1+a3)=k1+k2，（据此可以提高枚举的速度！）所以 a2+a3=7.,于是 a1=1，a2=3，a3=4,从K中删掉这三个数的和有K=10,11,12,13,13,14,19 ，,于是，进一步递推有a1+a4=10, 所以a4=9。,从K中删掉由于a4产生的和有K=11,13,14,19 ，,同样进一步递推有a1+a5=11, 所以a5=10。,从K中删掉由于a5产生的和有K= ，所以 A=1,3,4,9,10 !,23.电气工程师的烦恼,问题描述：电气工程师们刚为学校计算机大楼布好网线，结果发现，在入口处已经明确标记了各条网线的编号是1,2,3,n，但到了机房，这n条网线的顺序全乱了。为了知道这些网线的对应关系，他们测得网线中途有许多相互交叉的现象，而且两条线最多交叉一次。你如果知道了所有网线的交叉信息，能够帮他们找到这n条网线在机房的排列顺序吗？,1,2,3,4,5,1,2,3,4,5,23.电气工程师的烦恼,问题分析：以各条网线的编号1,2,3,n为顶点构造一个有向图。若 ij同时i与j不相交，则画由i到j的有向边； 若ij同时i与j相交，则画由j到i的有向边；,例如：,1,2,3,4,5,每个顶点的入度就是它前面网线的条数！,入度为0的顶点唯一！,拓扑排序！,24.煎饼,问题描述：锅里有一叠n个煎饼，每个煎饼有唯一的一个数字。厨师每次只能选择一个数k，把从锅底开始数，第k张以上的煎饼全部拿起，反过来又放在上面。在只能对煎饼进行红色所描述的操作的前提下，请你帮厨师设计一个算法，使得所有煎饼由下到上、从小到大堆放。,2,5,7,6,4,8,2,5,7,6,4,8,2,5,7,6,4,8,K=3,K=1,25.士兵排队问题,问题描述：有n个士兵分散在一个网格形的广场上。每个网格的位置由整数坐标(x,y)给出。士兵每步移动是在他的当前网格向上、下、左或者右移动一个网格。你作为指挥官，命令所有士兵集中到一个网格内，但要保证所有士兵的移动步数之和最小。你向大家宣布的是哪个网格？,中位数原理,快速选择算法,26.最小可靠交换问题,问题描述：有n个整数寄存器r1,r2,rn。比较-交换指令：ce i, j /如果(ri)大于(rj)，则交换寄存器ri和rj的内容。 一个比较-交换程序是任意有限个比较-交换指令的序列。如果运行一个比较-交换程序之后，寄存器r1的值总是所有寄存器的值中最小的，则这个比较-交换程序是一个最小值查找程序。如果从一个最小值查找程序中删除任意一条比较-交换指令后，它仍然是一个最小值查找程序，则它是一个可靠的最小值查找程序。 给定一个最小值查找程序P，最少在P的尾部添加几条比较-交换指令，才能使P变成可靠的最小值查找程序？,例如：有3个寄存器r1,r2,r3。 ce 1, 2