程序设计实习讲义5.ppt

《程序设计实习讲义5.ppt》由会员分享，可在线阅读，更多相关《程序设计实习讲义5.ppt（37页珍藏版）》请在优知文库上搜索。

1、程序设计实习第 五讲内容提要内容提要l枚举的基本思想l程序设计练习l作业枚举枚举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关键：l可能的情况是什么l有序地枚举，不漏掉情况l尽早发现不是解的情况例例1：完美立方：完美立方 (POJ1543)l问题描述： a3 = b3 + c3 + d3为完美立方等式。例如123 = 63 + 83 + 103 。编写一个程序，对任给的正整数N (N100)，寻找所有的四元组(a, b, c, d)，使得a3 = b3 + c3 + d3，其中1a, b, c, d N。l输入：正整数N (N100)l输出：每行输出一个完美立方，按照a的值，从小到大依次输出。当两个完美立方等式中a的值相同，则依次按照b、c、d进行非降序排列输出，即b值小的先输出、然后c值

3、小的先输出、然后d值小的先输出。l样例输入：24l样例输出：Cube = 6, Triple = (3,4,5) Cube = 12, Triple = (6,8,10) Cube = 18, Triple = (2,12,16) Cube = 18, Triple = (9,12,15) Cube = 19, Triple = (3,10,18) Cube = 20, Triple = (7,14,17) Cube = 24, Triple = (12,16,20) l逐一枚举a,b,c,d,#include void main() int n; scanf(%d,&n); int I, c

4、ube101; for(i=0;i=100;i+) cubei=i*i*i; int a,b,c,d; for(a=2;a=n;a+) for(b=2;ba;b+) for(c=b;ca;c+) for(d=c;da;d+) if(cubea = cubeb+cubec+cubed) printf(Cube = %d, Triple = (%d,%d,%d)n,a,b,c,d); 例例2：熄灯问题（：熄灯问题（POJ1222）l问题描述：有一个由按钮组成的矩阵，其中每行有6个按钮，共5行。每个按钮的位置上有一盏灯。当按下一个按钮后，该按钮以及周围位置(上边、下边、左边、右边)的灯都会改变一次。

5、即，如果灯原来是点亮的，就会被熄灭；如果灯原来是熄灭的，则会被点亮。l在矩阵角上的按钮改变3盏灯的状态l在矩阵边上的按钮改变4盏灯的状态l其他的按钮改变5盏灯的状态l在上图中，左边矩阵中用X标记的按钮表示被按下，右边的矩阵表示灯状态的改变l对矩阵中的每盏灯设置一个初始状态。请你按按钮，直至每一盏等都熄灭。与一盏灯毗邻的多个按钮被按下时，一个操作会抵消另一次操作的结果。在下图中，第2行第3、5列的按钮都被按下，因此第2行、第4列的灯的状态就不改变l请你写一个程序，确定需要按下哪些按钮，恰好使得所有的灯都熄灭。根据上面的规则，我们知道l第2次按下同一个按钮时，将抵消第1次按下时所产生的结果。因此，

6、每个按钮最多只需要按下一次。l各个按钮被按下的顺序对最终的结果没有影响l对第1行中每盏点亮的灯，按下第2行对应的按钮，就可以熄灭第1行的全部灯。如此重复下去，可以熄灭第1、2、3、4行的全部灯。同样，按下第1、2、3、4、5列的按钮，可以熄灭前5列的灯。l输入：第一行是一个正整数N，表示需要解决的案例数。每个案例由5行组成，每一行包括6个数字。这些数字以空格隔开，可以是0或1。0表示灯的初始状态是熄灭的，1表示灯的初始状态是点亮的。l输出：对每个案例，首先输出一行，输出字符串“PUZZLE #m”，其中m是该案例的序号。接着按照该案例的输入格式输出5行，其中的1表示需要把对应的按钮按下，0则表

7、示不需要按对应的按钮。每个数字以一个空格隔开。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 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 解题思路解题思

8、路既然按钮按下的顺序不影响最后的结果，不妨假设从第一行往下一行一行按按钮按第二行按钮时必须把第一行灯全部熄灭，否则第三行以后的按钮再也不能改变第一行的灯这样只要枚举第一行的按钮组合情况，就可以判断所有灯的熄灭情况。第一行共有2的6次方种情况。源程序 1222.cpp例例3：poj1054问题问题l稻田问题问题l青蛙从外面跳入稻田，踩过一些禾苗，后，跳出稻田。问题问题l蛙路：一个方向，等间距，大于等于3个点 l不同蛙路：可以方向不同，间距不同问题问题l许多青蛙跳过稻田，形成多条蛙路，不同蛙路可以踩过同一作物。问题问题l青蛙每天早上踩坏稻田，早上人们发现稻田有若干株作物被踩坏，但不知多少青蛙来过。

9、也有不在蛙路上的被踩坏的作物。问题问题l问，给定一块被踩坏的稻田，求可能的最长的蛙路上被踩坏的作物的数目。输入输入l第一行整数R和C，稻田的行数和列数l第二行整数N，表示被踩坏的作物总数。l后续N行，每行两个整数i,j为被踩坏的作物的行和列的位置:1=i=R,1，1=j=C。l每个被踩坏的作物只出现一次。输出输出l单个整数- 表示最长可能蛙路上踩坏的作物数目样例样例lFigure- 4解题思路解题思路l每条青蛙行走路径中至少有3棵水稻l假设一只青蛙进入稻田后踩踏的前两棵水稻分别是(X1，Y1)、 (X2，Y2)。那么：l青蛙每一跳在X方向上的步长dX = X2 - X1 、在 Y方向上的步长d

10、Y = Y2 - Y1 l(X1 - dX，Y1 - dY)需要落在稻田之外l当青蛙踩在水稻(X，Y)上时，下一跳踩踏的水稻是(X + dX，Y + dY)l将路径上的最后一棵水稻记作(XK，YK)，(XK + dX，YK + dY)需要落在稻田之外解题思路：枚举每一条可能路径解题思路：枚举每一条可能路径l枚举的办法需要保证：每条可能的路径都能够被检测到l从输入的水稻中任取两棵，作为一只青蛙进入稻田后踩踏的前两棵水稻，看能否形成一条穿越稻田的行走路径l检测的过程需要尽快排除错误的答案：假设(X1，Y1)、 (X2，Y2)就是所要寻找的行走路径上的前两棵水稻。当下列条件之一满足时，这个猜测就不成

11、立l青蛙不能经过一跳从稻田外跳到(X1，Y1)上l按照(X1，Y1)、 (X2，Y2)确定的步长，从出发，青蛙最多经过(MAXSTEPS - 1)步，就会跳到稻田之外。 MAXSTEPS是当前以找到的最好答案选择合适的数据结构选择合适的数据结构l选择合适的数据结构：采用的数据结构需要与问题描述中的概念对应l方案1：struct int x, y; plants5000;l方案2：int plantsRow5000, plantsCol5000;l显然方案1更符合问题本身的描述设计的算法要简洁设计的算法要简洁l尽量使用C提供的函数完成计算的任务：猜测一条行走路径时，需要从当前位置(X，Y)出发上

12、时，看看(X + dX，Y + dY)位置的水稻水稻是否被踩踏l方案1：自己写一段代码，看看(X + dX，Y + dY) 是否在数组plants中;l方案2：先用QSORT对plants中的元素排序，然后用BSEARCH从中查找元素(X + dX，Y + dY)l显然基于方案2设计的算法更简洁、更容易实现、更不容易出错误l通常，所选用的数据结构对算法的设计有很大影响参考程序参考程序#include #include int r, c, n;struct PLANT int x, y;PLANT plants5001;PLANT plant;int myCompare( const void

13、*ele1, const void *ele2 )；int searchPath(PLANT secPlant, int dX, int dY) void main()int i,j, dX, dY, pX, pY, steps, max = 2;scanf(%d%d, &r, &c);scanf(%d, &n);for (i = 0; i n; i+)scanf(%d%d, &plantsi.x, &plantsi.y);qsort(plants, n, sizeof(PLANT), myCompare);for (i = 0; i n - 2; i+)for (j = i + 1; j n

14、 - 1; j+) dX = plantsj.x - plantsi.x; dY = plantsj.y - plantsi.y; pX = plantsi.x - dX; pY = plantsi.y - dY; if (pX = 1 & pY = 1)continue; if (plantsi.x + (max - 1) * dX r)break; pY = plantsi.y + (max - 1) * dY; if ( pY c | pY max) max = steps; if ( max = 2 ) max = 0;printf(%dn, max);int myCompare( c

15、onst 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 );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 &

16、 plant.y = 1) if (!bsearch(&plant, plants, n, sizeof(PLANT), myCompare) steps = 0;break;plant.x += dX; plant.y += dY;steps+;return(steps);课堂练习课堂练习1：画家问题：画家问题(POJ1681)l问题描述：有一个正方形的墙，由NN个正方形的砖组成，其中一些砖是白色的，另外一些砖是黄色的。Bob是个画家，想把全部的砖都涂成黄色。但他的画笔不好使。当他用画笔涂画第(i, j)个位置的砖时， 位置(i-1, j)、 (i+1, j)、 (i, j-1)、 (i, j+1)上的砖都会改变颜色。请你帮助Bob计算出最少需要涂画多少块砖，才能使所有砖的颜色都变成黄色。l输入：第一行是个整数t(1t 20)，表示要测试的案例数。然后是t个案例。每个案例的首行是一个整数n (1n 15)，表示墙的大小。接下来的n行表示墙的初始状态。每一行包含n个字符。第i行的第j个字符表示位于位置(i,j)上的砖的颜色。“w”表示白砖，“y”表示黄砖。l输出：每个案例输出一行。如果