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

算法设计问题示例算法设计问题示例计算机科学的本质是算法计算机科学的本质是算法计算机硬件系统仅仅是依照特定的算法，计算机硬件系统仅仅是依照特定的算法，按照物理和电子学原理，采用特定的工艺流程生产的按照物理和电子学原理，采用特定的工艺流程生产的一种电子计算装置一种电子计算装置计算机程序设计语言是仅仅是程序员计算机程序设计语言是仅仅是程序员与计算机硬件系统进行沟通、交流的与计算机硬件系统进行沟通、交流的一种工具语言一种工具语言熟练掌握一种程序设计语言是成为一名优秀程序员的基础熟练掌握一种程序设计语言是成为一名优秀程序员的基础要成为一名优秀的、能够解决各类疑难问题的要成为一名优秀的、能够解决各类疑难问题的程序员程序员必须具有良好的算法设计的品质必须具有良好的算法设计的品质1.中国象棋中马的走法中国象棋中马的走法问题描述：问题描述：在在45的棋盘上已知马的起始坐标的棋盘上已知马的起始坐标(x,y)，求马，求马 能够返回到起始位置的不重复的所有不同走能够返回到起始位置的不重复的所有不同走法的总数。法的总数。回回 溯溯 法！法！马当前所在的位置是当前扩展结点！马当前所在的位置是当前扩展结点！每个活结点可能有八个孩子结点！每个活结点可能有八个孩子结点！如何记录马行走的路径？如何记录马行走的路径？152643class Horseprivate: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;i6;i+)for(int j=0;j5;j+)chessij=0;static long computer()count=0;if(sx0|sy=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&pi=0&pjj 1 i=jmij=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=(&xj=)|xi=&xj=)mij=min(mij,mi+1j-1);if(xi=(|xi=)mij=min(mij,mi+1j)+1;if(xj=)|xj=)mij=min(mij,mij-1)+1;for(int k=i;kj;k+)mij=min(mij,mik+mk+1j)return m1n;3.棋盘的最优分割棋盘的最优分割问题描述：问题描述：一个一个88的棋盘中每个格子里均有一个分值。对棋盘沿着任意的棋盘中每个格子里均有一个分值。对棋盘沿着任意一条格子线进行一次分割，将使棋盘成为两块矩形棋盘。给定一条格子线进行一次分割，将使棋盘成为两块矩形棋盘。给定n15，对原棋盘进行，对原棋盘进行n-1次分割，就把棋盘分割成了次分割，就把棋盘分割成了n块矩形棋盘。块矩形棋盘。一块矩形棋盘的总分是他的所有格子的分值之和。请设计算法，一块矩形棋盘的总分是他的所有格子的分值之和。请设计算法，给出把原棋盘分割成给出把原棋盘分割成n块矩形棋盘的方案，使得各矩形棋盘总分的块矩形棋盘的方案，使得各矩形棋盘总分的平方和平方和 最小。其中最小。其中xi是第是第i块棋盘的总分。块棋盘的总分。动态规划！动态规划！x1,y1x2,y2ab3.棋盘的最优分割棋盘的最优分割 假设左上角为假设左上角为(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),我们最终需要的是：我们最终需要的是：dn11884.多边形游戏多边形游戏问题描述：问题描述：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=513条直线是：条直线是：(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)64728351138467255.分离英文单词分离英文单词问题描述：问题描述：长度为长度为n的双重单词串是一个由小写英文字母组成的字的双重单词串是一个由小写英文字母组成的字符串，它至少存在两种分离单词的方法，每种方法都能形成一组正符串，它至少存在两种分离单词的方法，每种方法都能形成一组正确的单词排列，并且两种方法中不会出现相同的单词；同一单词不确的单词排列，并且两种方法中不会出现相同的单词；同一单词不会重复出现；一个单词在一种方法中的结束位置不会与某个单词在会重复出现；一个单词在一种方法中的结束位置不会与某个单词在另一种方法中的结束位置相同（单词串结束例外）。另一种方法中的结束位置相同（单词串结束例外）。给定包含给定包含m个单词的单词表个单词的单词表，是否能够从中选择出若干个单词，是否能够从中选择出若干个单词，组成一个长度为组成一个长度为n的双重单词串。的双重单词串。示例：示例：n=17,m=14n=17,m=14all,an,and,are,area,as,ask,at,data,last,or,read,real,taskall,an,and,are,area,as,ask,at,data,last,or,read,real,task双重单词串是：双重单词串是：andatareallastaskandatareallastask5.分离英文单词分离英文单词问题分析：问题分析：字母表字母表是否存在两个不相交的子集是否存在两个不相交的子集A和和B，他们中所，他们中所有单词的长度之和均等于有单词的长度之和均等于n？NoNo：不存在长度为不存在长度为n的双重单词串！的双重单词串！Why?Why?YesYes：的长度为的长度为n的双重单词串的构造算法。的双重单词串的构造算法。等量等量0-1背包问题背包问题分别由字母表分别由字母表的子集的子集A和和B中所有单词构造长度为中所有单词构造长度为n相同的两个字相同的两个字符串，该字符串就是符串，该字符串就是上的长度为上的长度为n的双重单词串！的双重单词串！030532085635230118an,ask,data,last,realan,ask,data,last,realas,at,and,all,are,taskas,at,and,all,are,taskananddataat arerealalllastas taskask6.会餐交友问题会餐交友问题问题描述：问题描述：某机构举行一次不超过某机构举行一次不超过500人参加的盛大餐会，以增进人参加的盛大餐会，以增进与会者之间的友谊。所以采取自助餐形式，客人可以自由走动、交与会者之间的友谊。所以采取自助餐形式，客人可以自由走动、交谈。由于客人中有些相互认识、有些相互不认识。为了让客人相互谈。由于客人中有些相互认识、有些相互不认识。为了让客人相互引见，使大家都能认识更多的朋友，举办方想控制中途离开的客人引见，使大家都能认识更多的朋友，举办方想控制中途离开的客人的人数。当客人离开太多时，就应该宣布餐会结束。问题是，最少的人数。当客人离开太多时，就应该宣布餐会结束。问题是，最少有多少客人离开后，剩下的客人两两彼此都不认识？有多少客人离开后，剩下的客人两两彼此都不认识？输入示例：输入示例：81,21,32,47,64,35,60,0输入数据：输入数据：n表示客人的个数，客人的编号依次是表示客人的个数，客人的编号依次是1,2,n。i,j表示客人表示客人i和和j相互认识；相互认识；i=0&j=0时输入数据结束。时输入数据结束。输出示例：输出示例：32,3,612365746.会餐交友问题的算法会餐交友问题的算法一个结点代表什么？一个结点代表什么？结点的度说明了什么？结点的度说明了什么？FIFO还是优先队列？还是优先队列？为什么按照结点的度由大到小排队？为什么按照结点的度由大到小排队？删除一个结点意味着什么？之后还需要做什么？删除一个结点意味着什么？之后还需要做什么？7.点在哪个图形内点在哪个图形内问题描述：问题描述：给定一组图形（矩形或者圆）和一组点，判断每个点落给定一组图形（矩形或者圆）和一组点，判断每个点落在哪个图形内。在哪个图形内。输入示例：输入示例：R 0.0 0.0 5.5 10.3C-5.0-5.0 3.7R 2.5 2.5 12.5 12.5*2.0 2.04.7 5.39999.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,y2x1=x=x2&y1=y=y2r(x-x0)2+(y-y0)2=r2x1,y18.最小半径圆最小半径圆问题描述：问题描述：给设平面上有给设平面上有n个点个点(0n1000)，第，第i个点的坐标是个点的坐标是(xi,yi)。约定。约定0 xi10000&0yi10000。求一个最小半径的圆，使。求一个最小半径的圆，使得得n个点均在圆内个点均在圆内(可以在圆上可以在圆上)。输入示例：输入示例：330 01 00 140 00 11 11 040 02 04 02 2输出示例：输出示例：0.50 0.50 0.710.50 0.50 0.712.00 0.00 2.00半径为0的圆以两点之间的直线为直径的圆以两条垂直平分线的交点为圆心的圆9.等高登山问题等高登山问题问题描述：问题描述：两个人在一山脉的两头处于同一水平位置。他们商定以两个人在一山脉的两头处于同一水平位置。他们商定以等高的方式同时登上山脉的最高顶。已知整个山脉中每个山顶和谷等高的方式同时登上山脉的最高顶。已知整个山脉中每个山顶和谷底的坐标。由于两个人要保持等高，所以他们的底的坐标。由于两个人要保持等高，所以他们的速度速度和上下方向完和上下方向完全不同。请写算法为他们计算出每次有人改变上下方向时，两个人全不同。请写算法为他们计算出每次有人改变上下方向时，两个人所处的位置坐标。所处的位置坐标。0123711131612359.等高登山问题等高登山问题输入示例输入示例60 02 23 17 511 113 316 0输出示例输出示例60.00 0.00 16.00 0.002.00 2.00 14.00 2.003.00 1.00 15.00 1.005.00 3.00 13.00 3.003.00 1.00 11.00 1.007.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 z10.模运算问题模运算问题int fmod(int a,int b,int c）if(!(1=a&ac)&(1=b&bc)&c=32768)return-1;int d=1;for(int i=1;i=b;i+)d=d*a mod c;fmod=d;return fmod;11.最短表面距离问题最短表面距离问题问题描述：问题描述：一个长方体一个长方体P=(x,y,z)|0 xL,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 71 702 503 304 405 406 307 201 41 73 43 55 76 70 0输出示例：输出示例：4 1602456这是一个什么问题？12.多花钱多卖鱼问题多花钱多卖鱼问题问题分析：问题分析：这个问题有一些约束条件：这个问题有一些约束条件：1.所买鱼的价格总和不能超过资金数所买鱼的价格总和不能超过资金数m；2.不能共存的鱼不能同时购买；不能共存的鱼不能同时购买；3.每种鱼最多买一条；每种鱼最多买一条；4.在满足上述条件的前提下，买尽可能多的鱼；在满足上述条件的前提下，买尽可能多的鱼；5.在满足上述条件的前提下，花尽可能多的买鱼钱。在满足上述条件的前提下，花尽可能多的买鱼钱。这是一个什么性是一个什么性质的的问题？输入示例：输入示例：170 71 702 503 304 405 406 307 201 41 73 43 55 76 70 017025033044054063072013.巧妙的剪纸问题巧妙的剪纸问题问题描述：问题描述：有一张正方形的纸，用笔和直尺把它等分成有一张正方形的纸，用笔和直尺把它等分成mm个小个小方格，用彩笔选择任一小方格作为起点，任意地一笔画一条正好经方格，用彩笔选择任一小方格作为起点，任意地一笔画一条正好经过了过了nn个小方格的彩线，把有彩线的小方格标记为个小方格的彩线，把有彩线的小方格标记为*。我们的问题。我们的问题是，你能够把所有标记为是，你能够把所有标记为*的小方格从纸上全部剪下来在一张纸片的小方格从纸上全部剪下来在一张纸片上上,然后再把它分剪成两片纸，使得这两片纸经过旋转、翻转或平移然后再把它分剪成两片纸，使得这两片纸经过旋转、翻转或平移后可以拼成一个后可以拼成一个nn的正方形。的正方形。*ABBABABBBB AAAAAAAAAAAAAAABBBBBBB13.巧妙的剪纸问题巧妙的剪纸问题问题分析：问题分析：我们需要解决两个问题：我们需要解决两个问题：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.21.月亮之眼问题月亮之眼问题问题描述：很早以前，在佛教圣地某庙宇的一根大立柱上，镶嵌很早以前，在佛教圣地某庙宇的一根大立柱上，镶嵌着一串用银白色和黛黑色各染一半的金线串接起来的、由着一串用银白色和黛黑色各染一半的金线串接起来的、由n颗珍珠颗珍珠组成的、谓之组成的、谓之“月亮之眼月亮之眼”的圣物。由于所有珍珠以及它们之间的的圣物。由于所有珍珠以及它们之间的金线在柱子上形成一条与地面垂直、与柱子平行的直线；可能会有金线在柱子上形成一条与地面垂直、与柱子平行的直线；可能会有两个珍珠镶嵌在同一地方；可能会有两根金线重叠摆放，所有使得两个珍珠镶嵌在同一地方；可能会有两根金线重叠摆放，所有使得圣物很美丽壮观。可是有一天，圣物突然脱落遗失，几千年后，一圣物很美丽壮观。可是有一天，圣物突然脱落遗失，几千年后，一个古董商人得到了圣物，他出于对佛的虔诚，把圣物送回圣地。圣个古董商人得到了圣物，他出于对佛的虔诚，把圣物送回圣地。圣地的僧人想恢复圣物的原状，可他们怎么都无法把圣物原样地镶嵌地的僧人想恢复圣物的原状，可他们怎么都无法把圣物原样地镶嵌在柱子上。你能帮助他们吗？在柱子上。你能帮助他们吗？递推递推问题示例：珍珠珍珠编号号 123456789白色金线 122455679黑色金线 237569788金线长度 35141113461237895451111443361237895411132222.22.丢失的正整数数列问题丢失的正整数数列问题问题描述：数学老师给全班同学写了一个包含数学老师给全班同学写了一个包含n个正整数个正整数的递增数列，要求大家回家后同样按照递增的次序，写出的递增数列，要求大家回家后同样按照递增的次序，写出所有的、任意两个数的和。有个同学很快就写完了作业。所有的、任意两个数的和。有个同学很快就写完了作业。可是他出去玩了一会，回来后发现老师给的原始数列丢失可是他出去玩了一会，回来后发现老师给的原始数列丢失了。你能帮他找回来吗？了。你能帮他找回来吗？递推递推22.22.丢失的正整数数列问题丢失的正整数数列问题问题分析：假设这个同学丢失的正整数递增数列是：假设这个同学丢失的正整数递增数列是：a1,a2,a3,a4,an他写出的结果包含了他写出的结果包含了n(n-1)/2个数，它们由小到大是：个数，它们由小到大是：k1,k2,k3,k4,!a1+a2=k1,a1+a3=k2a2+a3=?假设假设 a2+a3=kx,则解方程可得：则解方程可得：a1,a2,a3 依次递推计算写出每个依次递推计算写出每个ai 22.22.丢失的正整数数列问题丢失的正整数数列问题例题：假设假设K=4,5,7,10,11,12,13,13,14,19，求，求 a1,a2,a3,a4,解：因为解：因为 a1+a2=4,a1+a3=5a2+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.23.电气工程师的烦恼电气工程师的烦恼问题描述问题描述：电气工程师们刚为学校计算机大楼布好网线，电气工程师们刚为学校计算机大楼布好网线，结果发现，在入口处已经明确标记了各条网线的编号是结果发现，在入口处已经明确标记了各条网线的编号是1,2,3,n，但到了机房，这，但到了机房，这n条网线的顺序全乱了。为了条网线的顺序全乱了。为了知道这些网线的对应关系，他们测得网线中途有许多相互知道这些网线的对应关系，他们测得网线中途有许多相互交叉的现象，而且两条线最多交叉一次。你如果知道了所交叉的现象，而且两条线最多交叉一次。你如果知道了所有网线的交叉信息，能够帮他们找到这有网线的交叉信息，能够帮他们找到这n条网线在机房的条网线在机房的排列顺序吗？排列顺序吗？123451234523.23.电气工程师的烦恼电气工程师的烦恼问题分析问题分析：以各条网线的编号以各条网线的编号1,2,3,n为顶点构造一个为顶点构造一个有向图。若有向图。若 ij同时同时i与与j不相交，则画由不相交，则画由i到到j的有向边；的有向边；若若ij同时同时i与与j相交，则画由相交，则画由j到到i的有向边；的有向边；例如例如：12345每个顶点的入度就是它前面网线的条数！每个顶点的入度就是它前面网线的条数！入度为入度为0的顶点唯一！的顶点唯一！拓扑排序！拓扑排序！24.24.煎饼煎饼问题描述问题描述：锅里有一叠锅里有一叠n个煎饼，每个煎饼有唯一的一个个煎饼，每个煎饼有唯一的一个数字。厨师数字。厨师每次只能选择一个数每次只能选择一个数k，把从锅底开始数，第，把从锅底开始数，第k张以上的煎饼全部拿起，反过来又放在上面张以上的煎饼全部拿起，反过来又放在上面。在只能对煎。在只能对煎饼进行红色所描述的操作的前提下，请你帮厨师设计一个饼进行红色所描述的操作的前提下，请你帮厨师设计一个算法，使得所有煎饼由下到上、从小到大堆放。算法，使得所有煎饼由下到上、从小到大堆放。257648257648257648K=3K=125.25.士兵排队问题士兵排队问题问题描述问题描述：有有n个士兵分散在一个网格形的广场上。每个个士兵分散在一个网格形的广场上。每个网格的位置由整数坐标网格的位置由整数坐标(x,y)给出。士兵给出。士兵每步每步移动是在他的移动是在他的当前网格向上、下、左或者右移动一个网格。你作为指挥当前网格向上、下、左或者右移动一个网格。你作为指挥官，命令所有士兵集中到一个网格内，但要保证所有士兵官，命令所有士兵集中到一个网格内，但要保证所有士兵的移动步数之和最小。你向大家宣布的是哪个网格？的移动步数之和最小。你向大家宣布的是哪个网格？中位数原理中位数原理快速选择算法快速选择算法26.26.最小可靠交换问题最小可靠交换问题问题描述问题描述：有有n个整数寄存器个整数寄存器r1,r2,rn。比较。比较-交换交换指令指令：ce i,j /如果如果(ri)大于大于(rj)，则交换寄存器，则交换寄存器ri和和rj的内容。的内容。一个比较一个比较-交换交换程序程序是任意有限个比较是任意有限个比较-交换指令的序列。交换指令的序列。如果运行一个比较如果运行一个比较-交换程序之后，寄存器交换程序之后，寄存器r1的值总是所有的值总是所有寄存器的值中最小的，则这个比较寄存器的值中最小的，则这个比较-交换程序是一个交换程序是一个最小最小值查找值查找程序。如果从一个最小值查找程序中删除任意一条程序。如果从一个最小值查找程序中删除任意一条比较比较-交换指令后，它仍然是一个最小值查找程序，则它交换指令后，它仍然是一个最小值查找程序，则它是一个可靠的最小值查找程序。是一个可靠的最小值查找程序。给定一个最小值查找程序给定一个最小值查找程序P，最少在，最少在P的尾部添加几的尾部添加几条比较条比较-交换指令，才能使交换指令，才能使P变成可靠的最小值查找程序？变成可靠的最小值查找程序？例如例如：有有3个寄存器个寄存器r1,r2,r3。ce 1,2；ce 2,3；ce 1,2；是一个最小值查找程序。是一个最小值查找程序。ce 1,2；ce 2,3；ce 1,2；ce 1,3；ce 1,2；可靠的可靠的最小值查找最小值查找程序程序27.27.千年庆典千年庆典-赤道大篝火赤道大篝火问题描述问题描述：用涂满焦油的圆木撒上火药粉后铺满整个赤道。用涂满焦油的圆木撒上火药粉后铺满整个赤道。赤道上有赤道上有n个地方，地方个地方，地方i到地方到地方i+1的距离是的距离是si。选择其中。选择其中任意任意m个地方，在新千年的个地方，在新千年的t1,t2,tm分钟时，点燃圆木分钟时，点燃圆木。假设圆木点燃后，大火蔓延的速度是假设圆木点燃后，大火蔓延的速度是v公里公里/分；圆木一旦分；圆木一旦点燃，就可以燃烧足够长的时间。你能够告诉大家，赤道点燃，就可以燃烧足够长的时间。你能够告诉大家，赤道每个地方圆木的起火时间吗？每个地方圆木的起火时间吗？28.28.团伙团伙问题描述问题描述：某城市有某城市有n个人个人。任何两个。任何两个认识认识的人不是朋友的人不是朋友就是敌人，并且：就是敌人，并且：1.朋友的朋友是朋友，朋友的朋友是朋友，2.敌人的敌人是敌人的敌人是朋友。所有是朋友的人组成了一个团伙。现在已知关于这朋友。所有是朋友的人组成了一个团伙。现在已知关于这n个人的个人的m条信息条信息(i,j,t)，t=0表示表示i和和j是朋友；是朋友；t=1表示表示i和和j是敌人。请你计算出这个城市里所有的团伙及其构成。是敌人。请你计算出这个城市里所有的团伙及其构成。(i,j,0)：i和和j是朋友，合并是朋友，合并i和和j所在的朋友集合所在的朋友集合(i,j,1)：i和和j是是敌人，人，i的的敌人是集合人是集合ei将将i置入集合置入集合ej将将j置入集合置入集合ei集合的存储结构集合的存储结构树树29.29.方块消除游戏方块消除游戏问题描述问题描述：有颜色的方块排成一列，相邻的、相同颜色的有颜色的方块排成一列，相邻的、相同颜色的方块连成一个区域。游戏者可任选一个有方块连成一个区域。游戏者可任选一个有k个方块的区域个方块的区域进行消除，从而获得进行消除，从而获得k2的得分。方块消除后，其右边的所的得分。方块消除后，其右边的所有方块会自动向左平移，与被消除方块的左边相连。你能有方块会自动向左平移，与被消除方块的左边相连。你能够计算出一个方块消除游戏的最高得分及其游戏方法吗够计算出一个方块消除游戏的最高得分及其游戏方法吗？最高得分：最高得分：42+32+22=29一个方一个方块游游戏可以描述成：可以描述成：(c1,l1),(c2,l2),(cn,ln)(ci,li)表示第表示第i个区域的个区域的颜色色ci和方和方块个数个数li假假设fi,j,k是消除下列区域的最大得分：是消除下列区域的最大得分：(ci,li),(ci+1,li+1),(cj-1,lj-1),(cj,lj+k)则：0 ij fi,j,k=(li+k)2 i=j maxfi,j-1,0+(lj+k)2,fi,p,k+lj+fp+1,j-1,0 30.30.方块消除游戏方块消除游戏问题描述问题描述：有颜色的方块排成一列，相邻的、相同颜色的有颜色的方块排成一列，相邻的、相同颜色的方块连成一个区域。游戏者可任选一个有方块连成一个区域。游戏者可任选一个有k个方块的区域个方块的区域进行消除，从而获得进行消除，从而获得k2的得分。方块消除后，其右边的所的得分。方块消除后，其右边的所有方块会自动向左平移，与被消除方块的