《枚举与递归.ppt》由会员分享，可在线阅读，更多相关《枚举与递归.ppt（53页珍藏版）》请在三一文库上搜索。
1、第七讲,枚举与递归,ACM算法与程序设计,什么是枚举,枚举是基于已有的知识进行答案猜测的一种问题求解策略。通常是根据建立的数学模型中的一组变量及其条件，在条件允许的范围内对变量依次取值，判断所取的值是否满足数学模型中的条件，直到找到(全部)符合条件的值为止。 使用时注意以下三方面的问题： 建立简洁的数学模型。数学模型中变量的数量要尽量少，它们之间相互独立。 减小搜索的空间。利用已有的知识，缩小数学模型中各个变量的取值范围，避免不必要的计算。 采用合适的搜索顺序。对搜索空间的遍历顺序要与数学模型中的条件表达式一致。,称硬币,1、链接地址 http:/ 2、问题描述 赛利有12枚银币。其中有11枚
2、真币和1枚假币。假币看起来和真币没有区别，但是重量不同。但赛利不知道假币比真币轻还是重。于是他向朋友借了一架天平。朋友希望赛利称三次就能找出假币并且确定假币是轻是重。 例如：如果赛利用天平称两枚硬币，发现天平平衡，说明两枚都是真的。如果赛利用一枚真币与另一枚银币比较，发现它比真币轻或重，说明它是假币。经过精心安排每次的称量，赛利保证在称三次后确定假币。,问题描述,输入格式 第一行有一个数字n，表示有n组测试用例。 对于每组测试用例：输入有三行，每行表示一次称量的结果。赛利事先将银币标号为A-L。每次称量的结果用三个以空格隔开的字符串表示：天平左边放置的硬币 天平右边放置的硬币 平衡状态。其中平
3、衡状态用”up”, “down”, 或”even”表示, 分别为右端高、右端低和平衡。天平左右的硬币数总是相等的。 输出要求 输出哪一个标号的银币是假币，并说明它比真币轻还是重(heavy or light)。,问题描述,输入样例 1 ABCD EFGH even ABCI EFJK up ABIJ EFGH even 输出样例 K is the counterfeit coin and it is light.,此题中赛利已经设计了正确的称量方案，保证从三组称量数据中能得到唯一的答案。答案可以用两个变量表示：x-假币的标号、w-假币是比真币轻还是比真币重。x共有12种猜测；w有2种猜测。根据
4、赛利设计的称量方案，(x，w)的24种猜测中，只有唯一的猜测与三组称量数据都不矛盾。因此，如果猜测(x，w )满足下列条件，这个猜测就是要找的答案： 在称量结果为“even 的天平两边，没有出现x ； 如果w表示假币比真币轻，则在称量结果为“up 的天平右边一定出现x、在称量结果为“down 的天平左边一定出现x； 如果w表示假币比真币重，则在称量结果为“up 的天平左边一定出现x、在称量结果为“down 的天平右边一定出现x。,3、解题思路,具体实现时，要注意两点： (1) 选择合适的算法 对于每一枚硬币x 逐个试探： x 比真币轻的猜测是否成立？猜测成立则进行输出。 x 比真币重的猜测是否
5、成立？猜测成立则进行输出。 (2) 选择合适的数据结构 以字符串数组存储称量的结果。每次称量时，天平左右最多有6 枚硬币。因此，字符串的长度需要为7，最后一位存储字符串的结束符0，便于程序代码中使用字符串操作函数。 char left37, right37, result37;,3、解题思路,4、参考程序,#include #include char left37, right37, result35; bool isHeavy(char x); bool isLight(char x); int main(void) int i,n; char c; scanf(“%d“, ,4、参考程序,
6、for ( c = A; c = L; c+ ) if ( isLight(c) ) printf(“%c is the counterfeit coin and it is light.n“, c); break; if ( isHeavy(c) ) printf(“%c is the counterfeit coin and it is heavy.n“, c); break; n-; return 0; ,4、参考程序,bool isLight( char x ) / 判断硬币x 是否为轻的代码 int i; for ( i = 0; i 3; i+ ) / 判断是否与三次称量结果矛盾
7、switch( resulti0 ) case u: if( strchr(righti, x) = NULL ) return false; break; case e: if(strchr(righti, x) != NULL | strchr(lefti, x) != NULL) return false; break; case d: if(strchr(lefti, x) = NULL) return false; break; return true; ,4、参考程序,bool isHeavy( char x ) /判断硬币x 是否为重的代码 int i; for ( i = 0;
8、 i 3; i+ ) / 判断是否与三次称量结果矛盾 switch( resulti0 ) case u: if( strchr(lefti, x) = NULL) return false; break; case e: if(strchr(righti, x) != NULL | strchr(lefti, x) != NULL) return false; break; case d: if(strchr(righti, x) = NULL) return false; break; return true; ,熄灯问题,1、链接地址 http:/ 2、问题描述 一个由按钮组成的矩阵，其
9、中每行有6个按钮，共5行。每个按钮的位置上有一盏灯。当按下一个按钮后，该按钮以及周围位置(上边、下边、左边、右边)的灯都会改变一次。即，如果灯原来是点亮的，就会被熄灭；如果灯原来是熄灭的，则会被点亮。在矩阵角上的按钮改变3盏灯的状态；在矩阵边上的按钮改变4盏灯的状态；其他的按钮改变5盏灯的状态。,问题描述,在上图中，左边矩阵中用X标记的按钮表示被按下，右边的矩阵表示灯状态的改变。对矩阵中的每盏灯设置一个初始状态。请你按按钮，直至每一盏灯都熄灭。与一盏灯毗邻的多个按钮被按下时，一个操作会抵消另一次操作的结果。在下图中，第2行第3、5列的按钮都被按下，因此第2行、第4列的灯的状态就不改变。,问题描
10、述,请你写一个程序，确定需要按下哪些按钮，恰好使得所有的灯都熄灭。根据上面的规则，我们知道： (1)第2次按下同一个按钮时，将抵消第1次按下时所产生的结果。因此，每个按钮最多只需要按下一次； (2)各个按钮被按下的顺序对最终的结果没有影响； (3)对第1行中每盏点亮的灯，按下第2行对应的按钮，就可以熄灭第1行的全部灯。如此重复下去，可以熄灭第1、2、3、4行的全部灯。同样，按下第1、2、3、4、5列的按钮，可以熄灭前5列的灯。,问题描述,输入数据 第一行是一个正整数N，表示需要解决的案例数。每个案例由5行组成，每一行包括6个数字。这些数字以空格隔开，可以是0或1。0表示灯的初始状态是熄灭的，1
11、表示灯的初始状态是点亮的。 输出要求 对每个案例，首先输出一行，输出字符串“PUZZLE #m”，其中m是该案例的序号。接着按照该案例的输入格式输出5行，其中的1表示需要把对应的按钮按下，0则表示不需要按对应的按钮。每个数字以一个空格隔开。,问题描述,输入样例 2 0 1 1 0 1 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 0 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 0 1 1 0 0 0 1 0 1 0 0,输出样例 PUZZLE #1 1 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0
12、1 1 1 0 0 1 0 0 0 1 0 0 0 0 PUZZLE #2 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 1 1 0 1 1 0 1,为了叙述方便，按下图所示，为按钮矩阵中的每个位置分别指定一个坐标。用数组元素puzzleij表示位置(i, j)上灯的初始状态：1 表示灯是被点亮的；0 表示灯是熄灭的。用数组元素pressij表示为了让全部的灯都熄灭，是否要按下位置(i, j)上的按钮：1 表示要按下；0 表示不用按下。 由于第0 行、第0 列和第7 列不属于按钮矩阵的范围，没有按钮，可以假设这些位置上的灯总是熄灭的、按钮也不用按下
13、。其它30 个位置上的按钮是否需要按下是未知的。 因此数组press 共有230种取值。从这么大的一个空间中直接搜索我们要找的答案，显然代价太大、不合适。要从熄灯的规则中，发现答案中的元素值之间的规律。不满足这个规律的数组press，就没有必要进行判断了。,3、解题思路,3、解题思路,3、解题思路,根据熄灯规则，如果矩阵press 是寻找的答案，那么按照press 的第一行对矩阵中的按钮操作之后，此时在矩阵的第一行上： 如果位置(1, j)上的灯是点亮的，则要按下位置(2, j)上按钮，即press2j一定取1； 如果位置(1, j)上的灯是熄灭的，则不能按位置(2, j)上按钮，即press
14、2j一定取0。 这样依据press 的第一、二行操作矩阵中的按钮，才能保证第一行的灯全部熄灭。而对矩阵中第三、四、五行的按钮无论进行什么样的操作，都不影响第一行各灯的状态。依此类推，可以确定press 第三、四、五行的值。 因此，一旦确定了press 第一行的值之后，为熄灭矩阵中第一至四行的灯，其他行的值也就随之确定了。press 的第一行共有26 种取值，分别对应唯一的一种press 取值，使得矩阵中前四行的灯都能熄灭。只要对这26 种情况进行判断就可以了：如果按照其中的某个press对矩阵中的按钮进行操作后，第五行的所有灯也恰好熄灭，则找到了答案。,3、解题思路,解决方案 (1)对pres
15、s 第一行的元素press11 press 16的各种取值情况进行枚举，依次考虑如下情况： 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 1 (2) 对press 第一行每一种取值，根据熄灯规则计算出press 的其他行的值。判断这个press 能否使得矩阵第五行的所有灯也恰好熄灭。,4、参考程序,int main(void) int cases,i,r,c; scanf(“%d“, ,4、参考程序,void enumate(void) int c; for (c=1;c1) press1c=0; c
16、+; press1c+; ,4、参考程序,#include int puzzle68,press68; bool guess(void) int c,r; for (r=1;r5;r+ ) for (c=1;c7;c+) pressr+1c=(puzzlerc+pressrc +pressr-1c+pressrc-1 +pressrc+1)%2; for(c=1;c7;c+) /判断最后一行是否熄灭 if (press5c-1+press5c+press5c+1 +press4c)%2!=puzzle5c) return(false); return true; ,讨厌的青蛙,1、链接地址 h
17、ttp:/ 2、问题描述 在韩国，有一种小的青蛙。每到晚上，这种青蛙会跳越稻田，从而踩踏稻子。农民在早上看到被踩踏的稻子，希望找到造成最大损害的那只青蛙经过的路径。每只青蛙总是沿着一条直线跳越稻田，而且每次跳跃的距离都相同，如图1所示。 稻田里的稻子组成一个栅格，每棵稻子位于一个格点上，如图2所示。而青蛙总是从稻田的一侧跳进稻田，然后沿着某条直线穿越稻田，从另一侧跳出去，如图3所示。,问题描述,问题描述,青蛙的每一跳都恰好踩在一棵水稻上，将这棵水稻拍倒。可能会有多只青蛙从稻田穿越，有些水稻被多只青蛙踩踏，如图4所示。当然，农民所见到的是图5中的情形，看不到图4中的直线。,问题描述,根据图5，农
18、民能够构造出青蛙穿越稻田时的行走路径，并且只关心那些在穿越稻田时至少踩踏了3 棵水稻的青蛙。因此，每条青蛙行走路径上至少包括3 棵被踩踏的水稻。而在一条青蛙行走路径的直线上，也可能会有些被踩踏的水稻不属于该行走路径。在图5中，格点(2, 1)、(6, 1)上的水稻可能是同一只青蛙踩踏的，但这条线上只有两棵被踩踏的水稻，因此不能作为一条青蛙行走路径；格点(2, 3)、(3, 4)、(6, 6)在同一条直线上，但它们的间距不等，因此不能作为一条青蛙行走路径；格点(2, 1)、(2, 3)、(2, 5)、(2, 7)是一条青蛙行走路径，该路径不包括格点(2, 6)。请你写一个程序，确定在所有的青蛙行
19、路径中，踩踏水稻棵数最多的路径上有多少棵水稻被踩踏。例如，图5的答案是7，因为第6 行上全部水稻恰好构成一条青蛙行走路径。,问题描述,输入数据 从标准输入设备上读入数据。第一行上两个整数R、C，分别表示稻田中水稻的行数和列数，1R、C5000。第二行是一个整数N，表示被踩踏的水稻数量， 3N5000。在剩下的N 行中，每行有两个整数，分别是一颗被踩踏水稻的行号(1R)和列号(1C)，两个整数用一个空格隔开。而且，每棵被踩踏水稻只被列出一次。 输出要求 从标准输出设备上输出一个整数。如果在稻田中存在青蛙行走路径，则输出包含最多水稻的青蛙行走路径中的水稻数量，否则输出0。,问题描述,输入样例 6
20、7 14 2 1 6 6 4 2 2 5 2 6 2 7 3 4 6 1 6 2 2 3 6 3 6 4 6 5 6 7,输出样例 7,这个问题看起来很复杂，其实目的很简单：帮助农民找到为害最大的青蛙。也就是要找到一条穿越稻田的青蛙路径，这个路径上被踩踏的水稻不少于其他任何青蛙路径上被踩踏的水稻数。当然，整个稻田中也可能根本就不存在青蛙路径。问题的关键是：找到穿越稻田的全部青蛙路径。任何一条穿越稻田的青蛙路径L，至少包括3 棵被踩踏的水稻。假设其中前两棵被踩踏的水稻分别是(X1，Y1)、(X2，Y2)，那么： 令dx=X2-X1、dy=Y2-Y1；X0=X1-dx、Y0=Y1- dy；X3=X
21、2 + dx、Y3=Y2 + dy (X0,Y0)位于稻田之外，青蛙从该位置经一跳后进入稻田、踩踏位置(X1,Y1)上的水稻,3、解题思路,Xi=X0 + idx、Yi=Y1 + idy(i3)，如果(Xi,Yi)位于稻田之内，则(Xi,Yi)上的水稻必被青蛙踩踏 根据上述规则，只要知道一条青蛙路径上的前两棵被踩踏的水稻，就可以找到该路径上其他的水稻。为了找到全部的青蛙路径，只要从被踩踏的水稻中，任取两棵水稻(X1,Y1)、(X2,Y2)，判断(X1,Y1)、(X2,Y2)是否能够作为一条青蛙路径上最先被踩踏的两颗水稻。 解决方案 这个问题的描述中，最基本的元素是被踩踏的水稻。在程序中要选择一
22、个合适的数据结构，来表达这个基本元素。这个数据结构是否合适的标准是：在程序中要表达这个元素时，能否用一个单词或者短语，即用一个变量来表示。,3、解题思路,struct PLANT /描述一棵被踩踏的水稻 int x; /水稻的行号 int y; /水稻的列号 这个问题的主要计算是：从被踩踏的水稻中选择两棵(X1,Y1)、(X2,Y2)。判断它们是否能够作为一条青蛙路径上最先被踩踏的两颗水稻。(X1,Y1)、(X2,Y2)唯一确定了蛙跳的方向和步长，从(X2,Y2)开始，沿着这个方向和步长在稻田内走。每走一步，判断所到达位置上(X,Y)的水稻是否被踩踏，直到走出稻田为止。如果在某一步上，(X,Y
23、)没有被踩踏，则表明(X1,Y1)、(X2,Y2)是一条青蛙路径上最先被踩踏的两颗水稻的假设不成立。这个判断的算法在问题求解过程中要反复使用，它的效率成为决定整个计算效率的关键。,3、解题思路,用一个PLANT 型的数组plants5001表示全部被踩踏的水稻 将plants 中的元素按照行/列序号的升序(或者降序)排列 采用二分法查找plants 中是否有值为(X,Y)的元素：将(X,Y)与plants 中间的元素比较，(1)相等，表明找到了元素；(2)比plants 中间元素的小，继续在plants 的前半部寻找；(3)比plants 中间元素的大，继续在plants 的后半部寻找。 采用
24、上述方法判断每走一步所到达位置上(X,Y)的水稻是否被踩踏，最多只要比较log2N，其中N 是稻田中被踩踏水稻的总量。,3、解题思路,4、参考程序,#include #include int r,c,n; struct PLANT int x,y; ; PLANT plants5001; PLANT plant; int myCompare(const void *ele1,const void *ele2); int searchPath(PLANT secPlant, int dX, int dY);,4、参考程序,int main(void) int i,j,dX,dY,pX,pY,st
25、eps,max=2; scanf(“%d%d“, /说明plantsi不是青蛙进入稻田的起始点,4、参考程序,if(plantsi.x+max*dXr) break;/随着j变化，dX只会增大 /说明在该路径上不会更多被踩踏，应该换起点 pY=plantsi.y+max*dY; if(pYc|pYmax) max=steps; if(max=2) max=0; printf(“%dn“,max); return (0); ,4、参考程序,int myCompare(const void *ele1,const void *ele2) PLANT *p1,*p2; p1=(PLANT*)ele1
26、; p2=(PLANT*)ele2; if(p1-x=p2-x) /优先竖向比较 return(p1-y-p2-y); return (p1-x-p2-x); ,4、参考程序,int searchPath(PLANT secPlant,int dX,int dY ) PLANT plant; int steps; plant.x=secPlant.x+dX; plant.y=secPlant.y+dY; steps=2; while(plant.x=1 ,递归的基本思想,先来看看n的阶乘，常见的有两种做法： 第一种做法，利用循环，直接求出： int n, m = 1; for(int i =
27、2; i = n; i+) m *= i; printf(“%d 的阶乘是%dn”, n, m); 这一种做法，需要了解n!的算法，它的优点是运算速度快。,递归的基本思想,第二种做法，利用公式n!=n*(n-1)!，使用递归函数求出： int factorial(int n) if(n 0) return(-1); if(n = 1 | n =0) return 1; else return n*factorial(n - 1); 该方法通过递推关系把原来问题缩小成一个更小规模的同类问题，并延续这一缩小规模的过程，直到在某一规模上，问题的解是已知的。这种解决问题的思想我们称为递归的思想。 递归
28、方法的总体思想是将待求解问题的解看作输入变量x 的函数f(x)，通过寻找函数g，使得f(x) = g(f(x-1)，并且已知f(0)的值，就可以通过f(0)和g 求出f(x)的值。这种思想也可以推广到多个输入变量x，y，z 等，x-1 也可以推广到 x - x1，只要递归朝着出口的方向走就可以了。,放苹果,1、链接地址 http:/ 2、问题描述 把 M 个同样的苹果放在N 个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K 表示）注意：5，1，1 和1，5，1 是同一种分法。,问题描述,输入数据 第一行是测试数据的数目t（0 = t = 20）。以下每行均包含两个整数M 和
29、N，以空格分开。1=M，N=10。 输出要求 对输入的每组数据M 和N，用一行输出相应的K。 输入样例 1 7 3 输出样例 8,所有不同的摆放方法可以分为两类：至少有一个盘子为空和所有盘子都不空。对于至少空着一个盘子的情况，则N 个盘子摆放M 个苹果的摆放方法数目与N-1 个盘子摆放M 个苹果的摆放方法数目相同。对于所有盘子都不空的情况，则N 个盘子摆放M 个苹果的摆放方法数目等于N 个盘子摆放M-N 个苹果的摆放方法数目。我们可以据此来用递归的方法求解这个问题。 设f(m, n) 为m 个苹果，n 个盘子的放法数目，则先对n 作讨论，如果nm，必定有n-m 个盘子永远空着，去掉它们对摆放苹
30、果方法数目不产生影响；即if(nm) f(m,n) =f(m,m)。当n = m 时，不同的放法可以分成两类：即有至少一个盘子空着或者所有盘子都有苹果，前一种情况相当于f(m , n) = f(m , n-1); 后一种情况可以从每个盘子中拿掉一个苹果，不影响不同放法的数目，即f(m , n) = f(m-n , n)。总的放苹果的放法数目等于两者的和，即 f(m,n) =f(m,n-1)+f(m-n,n) 。整个递归过程描述如下：,3、解题思路,3、解题思路,int f(int m , int n) if(n = 1 | m = 0) return 1; if(n m) return f (
31、m, m); return f (m , n-1)+f (m-n , n); 由上在知：当n=时，所有苹果都必须放在一个盘子里，所以返回；当没有苹果可放时，定义为种放法；递归的两条路，第一条n 会逐渐减少，终会到达出口n=1; 第二条m 会逐渐减少，因为nm 时，我们会return f(m , m) 所以终会到达出口m=0 注：苹果(相同或不同)放入盘子(相同或不同)的问题，在组合数学中有更多的论述，可参考卢开澄的组合数学(第2版)第2章中的Stirling数。,4、参考程序,#include int count(int x, int y) if(y = 1 | x = 0) return 1
32、; if(x y) return count(x, x); return count(x, y - 1) + count(x - y, y); int main(void) int t, m, n; scanf(“%d“, ,马的走法,1、问题描述,在一个45的棋盘上，马的起始位置坐标(纵，横)位置由键盘输入，求马能返回初始位置的所有不同走法的总数(马走过的位置不能重复，马走“日”字)。 输入输出样例：,2、问题分析,由于45的棋盘的问题规模比较小，用回溯法可以较好的解决问题。 如下图所示，如果从(1,1)出发，那么马首先从(1,1)点走向(3,2)点，再到(2,4)点，这样过程可以一步一步递
33、推下去，最后要么找到一条路径，要么进入“死胡同”，这时函数find(p1,p2)就不能递归调用自己了，因此实现了回溯。,为了避免走重复的位置，可以定义一个数组chess54表示棋盘，若chessij=1，则表示马已经走过，在递推时就不能走此位置，应该换一个方向。 对于马走的方向，可以定义数组d28，每列表示一个马可以走的方向。,3、参考代码,#include int chess54; int d28=-1,-1,-2,-2,2,2,1,1, 2,-2,1,-1,1,-1,2,-2; int sx,sy,tot; void find(int p1,int p2) int i,pi,pj; for
34、(i=0;i=0) ,int main(void) int i,j; while(scanf(“%d %d“, ,3、参考代码,课外练习,1、(除法) 输入正整数n，按从小到大的顺序输出所有形如abcde/fghij=n的表达式，其中 aj恰好为数字09的一个排列，2=n=79。 输例输入： 62 样例输出： 79546/01283=62 94736/01528=62 提示：只须枚举fghij。,2、(分数拆分) 输入正整数k，找到所有的正整数x=y，使得1/k=1/x+1/y。 样例输入： 2 12 样例输出： 2 1/2=1/6+1/3 1/2=1/4+1/4 8,1/12=1/156+1
35、/13 1/12=1/84+1/14 1/12=1/60+1/15 1/12=1/48+1/16 1/12=1/36+1/18 1/12=1/30+1/20 1/12=1/28+1/21 1/12=1/24+1/24 提示：找出y与k的关系，对y进行枚举。,课程成绩考核评定标准,一、成绩构成 1、平时成绩：50% 2、期末论文：50% 二、平时成绩构成： （禁止代码拷贝） 1、参与校赛与上机实践：30%（授课结束后安排上机） 2、平时OJ练题：10% 3、平时出勤：10% 三、期末论文类型及要求 稍后给出论文格式要求 需选择某一专题的深入研究 如：线段树、树状数组，网络流等，可以自己任意选择，题目范围涉及各个算法方面。 要求：要有该题目理论描述，自己完成的实际题目，并对题目给出解题分析和实现代码（需加注释），选题要有新意，有一定难度。,