《程序设计实习第五讲枚举》由会员分享，可在线阅读，更多相关《程序设计实习第五讲枚举（52页珍藏版）》请在金锄头文库上搜索。
1、程序设计实习第 五讲枚举枚举l一种解决问题的方法。例如：求小于N的最大素数l找不到一个数学公式，使得我们根据N就可以计算出这个素数lN-1是素数吗？N-2是素数吗？N-K是素数的充分必要条件是：N-K不能被任何一个大于1、小于N-K的素数整除。l判断N-K是否是素数的问题又成了求小于N-K的全部素数l解决方法：l2是素数，记为PRIM0l根据PRIM0、PRIM1、 、PRIMk ，寻找比PRIMk大的最小素数PRIMk+1。如果PRIMk+1大于N，则PRIMk是我们需要找的素数，否则继续寻找枚举的思想：猜测l根据所知道的知识知识，给一个猜测的答案。2是素数l判断猜测的答案是否正确。2是小于
2、N的最大素数吗？l进行新新的猜测：有两个关键因素要注意l猜测的结果必须是前面的猜测中没有出现过的。每次猜测是素数一定比已经找到的素数大l猜测的过程中要及早排除错误的答案。除2之外，只有奇数才可能是素数例题：例题：POJ1013POJ1013 称硬币称硬币问题描述问题描述 赛利有12枚银币。其中有11枚真币和1枚假币。假币看起来和真币没有区别，但是重量不同。但赛利不知道假币比真币轻还是重。于是他向朋友借了一架天平。朋友希望赛利称三次就能找出假币并且确定假币是轻是重。例如:如果赛利用天平称两枚硬币，发现天平平衡，说明两枚都是真的。如果赛利用一枚真币与另一枚银币比较，发现它比真币轻或重，说明它是假币
3、。经过精心安排每次的称量，赛利保证在称三次后确定假币。 输入输入 输入有三行，每行表示一次称量的结果。赛利事先将银币标号为A-L。每次称量的结果用三个以空格隔开的字符串表示：天平左边放置的硬币 天平右边放置的硬币 平衡状态。其中平衡状态用up, down, 或 even表示, 分别为右端高、右端低和平衡。天平左右的硬币数总是相等的。 输出输出 输出哪一个标号的银币是假币，并说明它比真币轻还是重。 例题：例题：POJ1013POJ1013 称硬币称硬币输入样例输入样例1 ABCD EFGH even ABCI EFJK up ABIJ EFGH even 输出样例输出样例K is the cou
4、nterfeit coin and it is light. 例题：例题：POJ1013POJ1013 称硬币称硬币例题：例题：POJ1013POJ1013 称硬币称硬币l问题分析 此题并非要求你给出如何称量的方案，而是数据已经保证三组称量后答案唯一。不是那道传统的智商测验题。 此题可以有多种解法，这里只介绍一种比较容易想到和理解的 逐一枚举法。例题：例题：POJ1013POJ1013 称硬币称硬币l总体构想 逐一试探法l对于每一枚硬币先假设它是轻的，看这样是否符合称量结果。如果符合，问题即解决。如果不符合，就假设它是重的，看是否符合称量结果。把所有硬币都试一遍，一定能找到特殊硬币例题：例题：
5、POJ1013POJ1013 称硬币称硬币l定义变量存储称量结果char left37,right37,result37;数组下标 3 代表3次称量；数组下标 7 代表每次左右至多6枚硬币，多出一个字符位置是为了放 0，以便使用字符串函数。例题：例题：POJ1013POJ1013 称硬币称硬币逐一枚举硬币的代码 for(char c=A; c=L;c+) if( isLight(c) ) cout c is the counterfeit coin and it is light.n; break; else if( isHeavy(c) ) cout c is the counterfeit
6、 coin and it is heavy.n; break; 例题：例题：POJ1013POJ1013 称硬币称硬币bool isLight(char x) / 判断硬币x是否为轻的代码 int i; for(i=0; i3; i+) / 判断是否与三次称量结果矛盾 switch( resulti0 ) case u: if( ! inRight(i,x) ) return false; break; case e: if(inRight(i,x) | inLeft(i,x) return false; break; case d: if(! inLeft(i,x) return false
7、; break; return true;例题：例题：POJ1013POJ1013 称硬币称硬币bool isHeavy(char x) /判断硬币x是否为重的代码 int i; for(i=0; i3; i+) / 判断是否与三次称量结果矛盾 switch( resulti0 ) case u: if( ! inLeft(i,x) ) return false; break; case e: if(inRight(i,x) | inLeft(i,x) return false; break; case d: if(! inRight(i,x) return false; break; ret
8、urn true;例题：例题：POJ1013POJ1013 称硬币称硬币bool inLeft(int i, char x) / 判断硬币x 是否在第i次称量左侧 return strchr( lefti,x);bool inRight(int i, char x)/ 判断硬币x 是否在第i次称量右侧return strchr(righti,x);例例1. 1. POJ1222POJ1222 熄灯问题（熄灯问题（P183P183）l问题描述：有一个由按钮组成的矩阵，其中每行有6个按钮，共5行。每个按钮的位置上有一盏灯。当按下一个按钮后，该按钮以及周围位置(上边、下边、左边、右边)的灯都会改变一
9、次。即，如果灯原来是点亮的，就会被熄灭；如果灯原来是熄灭的，则会被点亮。l在矩阵角上的按钮改变3盏灯的状态l在矩阵边上的按钮改变4盏灯的状态l其他的按钮改变5盏灯的状态l在上图中，左边矩阵中用X标记的按钮表示被按下，右边的矩阵表示灯状态的改变l对矩阵中的每盏灯设置一个初始状态。请你按按钮，直至每一盏等都熄灭。与一盏灯毗邻的多个按钮被按下时，一个操作会抵消另一次操作的结果。在下图中，第2行第3、5列的按钮都被按下，因此第2行、第4列的灯的状态就不改变 请你写一个程序，确定需要按下哪些按钮，恰好使得所有的灯都熄灭。l输入：第一行是一个正整数N，表示需要解决的案例数。每个案例由5行组成，每一行包括6
10、个数字。这些数字以空格隔开，可以是0或1。0表示灯的初始状态是熄灭的，1表示灯的初始状态是点亮的。l输出：对每个案例，首先输出一行，输出字符串“PUZZLE #m”，其中m是该案例的序号。接着按照该案例的输入格式输出5行，其中的1表示需要把对应的按钮按下，0则表示不需要按对应的按钮。每个数字以一个空格隔开。l样例输入2 0 1 1 0 1 01 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 l样例输出PUZZLE #1 1 0 1
11、 0 0 1 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 1 0 0 0 1 0 0 0 0PUZZLE #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 l第2次按下同一个按钮时，将抵消第1次按下时所产生的结果。因此，每个按钮最多只需要按下一次。l各个按钮被按下的顺序对最终的结果没有影响l对第1行中每盏点亮的灯，按下第2行对应的按钮，就可以熄灭第1行的全部灯。如此重复下去，可以熄灭第1、2、3、4行的全部灯。解题思路l第一想法：枚举所有可能的按钮（开关）状态，对每个状态计算一下最后灯的情况，看是否都熄
12、灭。每个按钮有两种状态(按下或不按下），一共有30个开关，那么状态数是230，太多，会超时。l如何减少枚举的状态数目呢？一个基本思路是，如果存在某个局部，一旦这个局部的状态被确定，那么剩余其他部分的状态只能是确定的一种，或者不多的n种，那么就只需枚举这个局部的状态就行了。解题思路l本题是否存在这样的“局部”呢？经过观察，发现第1行就是这样的一个“局部”。因为第1行的各开关状态确定的情况下，这些开关作用过后，将导致第1行某些灯是亮的，某些灯是灭的。此时要熄灭第1行某个亮着的灯（假设位于第i列），那么唯一的办法就是按下第2行第i列的开关（因为第一行的开关已经用过了，而第3行及其后的开关不会影响到第
13、1行)。因此，为了使第1行的灯全部熄灭,第2行的合理开关状态就是唯一的。解题思路l第2行的开关起作用后，为了熄灭第二行的灯，第3行的合理开关状态就也是唯一的，以此类推，最后一行的开关状态也是唯一的。l总之，只要第1行的状态定下来，比如叫A,那么剩余行的情况就是确定唯一的了。推算出最后一行的开关状态，然后看看最后一行的开关起作用后，最后一行的所有灯是否都熄灭，如果是，那么A就是一个解的状态。如果不是，那么A不是解的状态，第1行换个状态重新试试。l因此，只需枚举第一行的状态，状态数是26 = 64解题思路枚举第一列，状态数是25 = 32有没有状态数更少的做法？具体实现l用一个矩阵anPuzzle
14、 56表示灯的初始状态lanPuzzleij=1：灯(i, j)初始时是被点亮的lanPuzzle ij=0：灯(i, j)初始时是熄灭的l用一个矩阵anSwitch 56表示要计算的结果lanSwitchij=1：需要按下按钮(i, j)lanSwitchij=0：不需要按下按钮(i, j) anSwitch0里放着第1行开关的状态，如何进行枚举呢？可以使用六重循环：for( int a0 = 0; a0 2; a0 + ) for( int a1 = 0; a1 2; a0 + ) for( int a2 = 0; a2 2; a0 + ) for( int a3 = 0; a3 2; a
15、0 + ) for( int a4 = 0; a4 2; a0 + ) for( int a5 = 0; a5 2; a0 + ) anSwitch00 = a0; anSwitch01 = a1;anSwitch02 = a2; /如果每行灯很多，或每行开关数目是可变数N那怎么办? 适用于一行有N个开关的办法： 一个6位二进制数的所有取值正好是64种，让该数的每一位对应于anSwitch0里的一个元素（ anSwitch05 对应最高位，anSwitch04对应次高位. )，那么这个二进制数的每个取值正好表示了第一行开关的一种状态。 （如果一行有N个开关，那么就用一个N位二进制数） 比如，0
16、 的二进制表示形式是 00 0000，即代表所有开关都不按下63 的二进制表示形式是 11 1111，即代表所有开关都按下 5 的二进制表示形式是 00 00101，即代表右数第1，3个开关按下要写一个从二进制数到状态的转换函数：void SwitchStatus( int n, int * pSwitchLine);该函数将整数n( 0 =n64)的二进制表示形式对应到数组pSwitchLine里去（ pSwitchLIne i 对应第i位)void SwitchStatus( int n, int * pSwitch)for( i = 0;i i ) & 1; 要写一个让开关起作用的函数
17、void ApplySwitch( int * pLights, int * pNextLights, int * pSwitchs) ;pSwitchs 表示一行开关的状态pLights 表示与开关同一行的灯的状态pNextLights表示开关起作用后下一行的灯的状态本函数根据 pSwitchs 所代表的开关状态，计算这行开关起作用后，pLights行和pNextLights行的灯的状态不考虑开关的上一行的灯，是因为设定pSwitchs的值的时候，已经确保会使得上一行的灯变成全灭（或没有上一行）void ApplySwitch( int * pLights, int * pNextLight
18、s, int * pSwitchs) for( int i = 0;i 0 )pLightsi-1 = 1 - pLightsi-1;/开关所在位置的灯改变状态pLightsi = 1 - pLightsi;/开关右边的灯改变状态if( i 5) pLightsi+1 = 1 - pLightsi+1;/开关下边的灯改变状态pNextLightsi = 1 - pNextLightsi;#include #include #include using namespace std;int T; int anPuzzle66;int anOriPuzzle66;int anSwitch66; /开
19、关状态int i,j;void OutputResult(int t) /输出结果cout PUZZLE # t endl;for( int i = 0;i 5; i + ) for( int j = 0; j 6; j + ) cout anSwitchij;if( j 5 ) cout ;cout T;for( int t = 0; t T; t + ) for( i = 0;i 5; i + )for( j = 0; j anOriPuzzleij;for( int n = 0; n 64; n + ) /遍历首行开关的64种状态memcpy( anPuzzle,anOriPuzzle,
20、sizeof(anPuzzle);/算出n所代表的开关状态，放到anSwitch0SwitchStatus( n, anSwitch0);/下面逐行让开关起作用，并算出下一行开关应该是什么状态，再让它们起作用for( int k = 0; k 5; k + ) /算出第k行开关起作用后的结果ApplySwitch( anPuzzlek,anPuzzlek+1,anSwitchk);/第k+1行的开关状态应和第k行的灯状态一致memcpy( anSwitchk+1, anPuzzlek,sizeof(anPuzzlek); bool bOk = true; /记录最后一行灯是不是全灭/看最后一行
21、灯是不是全灭for( k = 0; k 6; k + ) if( anPuzzle4k ) bOk = false;break;if( bOk ) OutputResult(t+1); /输出解break; /找到解，就不用再试下一种状态了 / for( int n = 0; n 64; n + ) l问题描述：在韩国，有一种小的青蛙。每到晚上，这种青蛙会跳越稻田，从而踩踏稻子。农民在早上看到被踩踏的稻子，希望找到造成最大损害的那只青蛙经过的路径。每只青蛙总是沿着一条直线跳越稻田，而且每次跳跃的距离都相同。例题： POJ1054 讨厌的青蛙(P189)l如下图所示，稻田里的稻子组成一个栅格，每
22、棵稻子位于一个格点上。而青蛙总是从稻田的一侧跳进稻田，然后沿着某条直线穿越稻田，从另一侧跳出去l如下图所示，可能会有多只青蛙从稻田穿越。青蛙的每一跳都恰好踩在一棵水稻上，将这棵水稻拍倒。有些水稻可能被多只青蛙踩踏。当然，农民所见到的是图4中的情形，并看不到图3中的直线，也见不到别人家田里被踩踏的水稻，。l根据图4，农民能够构造出青蛙穿越稻田时的行走路径，并且只关心那些在穿越稻田时至少踩踏了3棵水稻的青蛙。因此，每条青蛙行走路径上至少包括3棵被踩踏的水稻。而在一条青蛙行走路径的直线上，也可能会有些被踩踏的水稻不属于该行走路径l不是一条行走路径：只有两棵被踩踏的水稻l是一条行走路径，但不包括（2，
23、6）上的水道l不是一条行走路径：虽然有3棵被踩踏的水稻，但这三棵水稻之间的距离间隔不相等l请你写一个程序，确定：在各条青蛙行走路径中，踩踏水稻最多的那一条上，有多少颗水稻被踩踏。例如，图4的答案是7，因为第6行上全部水稻恰好构成一条青蛙行走路径l程序输入：从标准输入设备上读入数据。第一行上两个整数R、C，分别表示稻田中水稻的行数和列数，1R、C5000。第二行是一个整数N，表示被踩踏的水稻数量， 3N5000。在剩下的N行中，每行有两个整数，分别是一颗被踩踏水稻的行号(1R)和列号(1C)，两个整数用一个空格隔开。而且，每棵被踩踏水稻只被列出一次。l程序输出：从标准输出设备上输出一个整数。如果
24、在稻田中存在青蛙行走路径，则输出包含最多水稻的青蛙行走路径中的水稻数量，否则输出0。l样例输入6 7 /6行7列1 4 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 l样例输出7解题思路 - 枚举l每条青蛙行走路径中至少有3棵水稻l假设一只青蛙进入稻田后踩踏的前两棵水稻分别是(X1，Y1)、 (X2，Y2)。那么：l青蛙每一跳在X方向上的步长dX = X2 - X1 、在 Y方向上的步长dY = Y2 - Y1 l(X1 - dX，Y1 - dY)需要落在稻田之外l当青蛙踩在水稻(X，Y)上时，下一跳踩踏的水稻是(X + dX，
25、Y + dY)l将路径上的最后一棵水稻记作(XK，YK)，(XK + dX，YK + dY)需要落在稻田之外枚举什么？枚举路径上的开始两点解题思路：猜测一条路径l猜测的办法需要保证：每条可能的路径都能够被猜测到l从输入的水稻中任取两棵，作为一只青蛙进入稻田后踩踏的前两棵水稻，看能否形成一条穿越稻田的行走路径解题思路：猜测一条路径l猜测的过程需要尽快排除错误的答案：猜测(X1，Y1)、 (X2，Y2)就是所要寻找的行走路径上的前两棵水稻。当下列条件之一满足时，这个猜测就不成立l青蛙不能经过一跳从稻田外跳到(X1，Y1)上l按照(X1，Y1)、 (X2，Y2)确定的步长，从(X1，Y1)出发，青蛙
26、最多经过(MAXSTEPS - 1)步，就会跳到稻田之外。 MAXSTEPS是当前已经找到的最好答案选择合适的数据结构选择合适的数据结构如何存放所有被踩踏水稻的位置?l选择合适的数据结构：采用的数据结构需要与问题描述中的概念对应l方案1：struct int x, y; plants5000;l方案2：int plantsRow5000, plantsCol5000;l显然方案1更符合问题本身的描述设计的算法要简洁设计的算法要简洁l尽量使用C+提供的函数完成计算的任务：猜测一条行走路径时，需要从当前位置(X，Y)出发上时，看看(X + dX，Y + dY)位置的水稻水稻是否被踩踏l方案1：自己
27、写一段代码，看看(X + dX，Y + dY) 是否在数组plants中;l方案2：先用QSORT对plants中的元素排序，然后用BSEARCH从中查找元素(X + dX，Y + dY)l显然基于方案2设计的算法更简洁、更容易实现、更不容易出错误l通常，所选用的数据结构对算法的设计有很大影响注意，一个有n个元素的数组，每次取两个元素，遍历所有取法的代码写法：for( int i = 0; i n 1 )for( int j = i + 1; j n; j + ) ai = ;aj = ;二分查找函数：void *bsearch(const void *key, const void *bas
28、e, size_t nelem, size_t width, int (_USERENTRY *fcmp)(const void *, const void *); 查到返回地址，查不到返回空指针参考程序参考程序#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) ;void main()in
29、t i,j, dX, dY, pX, pY, steps, max = 2;scanf(“%d%d”, &r, &c); /行数和列数, x方向是上下，y方向是左右scanf(%d, &n);for (i = 0; i n; i+)scanf(%d%d, &plantsi.x, &plantsi.y);/将水稻按x坐标从小到大排序，x坐标相同按y从小到大排序qsort(plants, n, sizeof(PLANT), myCompare);for (i = 0; i n - 2; i+) /plantsi是第一个点for ( j = i + 1; j n -1 ; j+) / plantsj
30、是第二个点 dX = plants j .x - plantsi.x; dY = plants j .y - plantsi.y; pX = plants i .x - dX; pY = plants i .y - dY; if (pX = 1 & pY = 1)continue; /第一点的前一点在稻田里，说明本次选的第 /二点导致的x方向步长不合理（太小)，取下一个点作为第二点 if (plants i .x + (max - 1) * dX r)break; /x方向过早越界了。说明本次选的第二点不成立。/如果换下一个点作为第二点，x方向步长只会更大，更不成立，所以应该/认为本次选的第一
31、点必然是不成立的，那么取下一个点作为第一点再试 pY = plants i .y + (max - 1) * dY; if ( pY c | pY max) max = steps; if ( max = 2 ) max = 0;printf(%dn, max); int myCompare( const void *ele1, const void *ele2 )PLANT *p1, *p2;p1 = (PLANT*) ele1;p2 = (PLANT*) ele2;if ( p1-x = p2-x ) return(p1-y - p2-y);return ( p1-x - p2-x );/
32、判断从 secPlant点开始，步长为dx,dy，那么最多能走几步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 & plant.y = 1) if (!bsearch(&plant, plants, n, sizeof(PLANT), myCompare) /每一步都必须踩倒水稻才算合理，否则这就不是一条行走路径steps = 0;break;p
33、lant.x += dX; plant.y += dY;steps+;return(steps);作业作业1 1：POJ1166POJ1166l问题描述：有9个时钟，排成一个33的矩阵。现在需要用最少的移动，将9个时钟的指针都拨到12点的位置。共允许有9种不同的移动。如右表所示，每个移动会将若干个时钟的指针沿顺时针方向拨动90度。l输入：从标准输入设备读入9个整数，表示各时钟指针的起始位置。1=12点、1=3点、2=6点、3=9点。l输出：输出一个最短的移动序列，使得9个时钟的指针都指向12点。按照移动的序号大小，输出结果移动 影响的时钟1ABDE2ABC3BCEF4ADG5BDEFH6CFI7DEGH8GHI9EFHIl样例输入3 3 0 2 2 2 2 1 2 l样例输出4 5 8 9 作业作业2 2：POJ1681 POJ1681 画家问题画家问题
