《程序设计实习讲义5.ppt》由会员分享，可在线阅读，更多相关《程序设计实习讲义5.ppt（37页珍藏版）》请在课桌文档上搜索。
1、程序设计实习第 五讲,内容提要,枚举的基本思想程序设计练习作业,枚举,一种解决问题的方法。例如：求小于N的最大素数找不到一个数学公式，使得我们根据N就可以计算出这个素数N-1是素数吗？N-2是素数吗？N-K是素数的充分必要条件是：N-K不能被任何一个大于1、小于N-K的素数整除。判断N-K是否是素数的问题又成了求小于N-K的全部素数解决方法：2是素数，记为PRIM0根据PRIM0、PRIM1、PRIMk，寻找比PRIMk大的最小素数PRIMk+1。如果PRIMk+1大于N，则PRIMk是我们需要找的素数，否则继续寻找,枚举的思想：,列出所有可能的情况，逐一检查是否是问题的解关键：可能的情况是什
2、么有序地枚举，不漏掉情况尽早发现不是解的情况,例1：完美立方(POJ1543),问题描述：a3=b3+c3+d3为完美立方等式。例如123=63+83+103。编写一个程序，对任给的正整数N(N100)，寻找所有的四元组(a,b,c,d)，使得a3=b3+c3+d3，其中1a,b,c,d N。输入：正整数N(N100)输出：每行输出一个完美立方，按照a的值，从小到大依次输出。当两个完美立方等式中a的值相同，则依次按照b、c、d进行非降序排列输出，即b值小的先输出、然后c值小的先输出、然后d值小的先输出。,样例输入：24样例输出：Cube=6,Triple=(3,4,5)Cube=12,Trip
3、le=(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),逐一枚举a,b,c,d,#include void main()int n;scanf(%d,例2：熄灯问题（POJ1222）,问题描述：有一个由按钮组成的矩阵，其中每行有6个按钮，共5行。每个按钮的位置上有一盏灯。当按下一个按钮后，该按钮以及周围位置(上边、下边、左边、右边)的灯都会改变一次。即，如果灯原来是点亮的，就会被熄灭；如
4、果灯原来是熄灭的，则会被点亮。在矩阵角上的按钮改变3盏灯的状态在矩阵边上的按钮改变4盏灯的状态其他的按钮改变5盏灯的状态,在上图中，左边矩阵中用X标记的按钮表示被按下，右边的矩阵表示灯状态的改变对矩阵中的每盏灯设置一个初始状态。请你按按钮，直至每一盏等都熄灭。与一盏灯毗邻的多个按钮被按下时，一个操作会抵消另一次操作的结果。在下图中，第2行第3、5列的按钮都被按下，因此第2行、第4列的灯的状态就不改变,请你写一个程序，确定需要按下哪些按钮，恰好使得所有的灯都熄灭。根据上面的规则，我们知道第2次按下同一个按钮时，将抵消第1次按下时所产生的结果。因此，每个按钮最多只需要按下一次。各个按钮被按下的顺序
5、对最终的结果没有影响对第1行中每盏点亮的灯，按下第2行对应的按钮，就可以熄灭第1行的全部灯。如此重复下去，可以熄灭第1、2、3、4行的全部灯。同样，按下第1、2、3、4、5列的按钮，可以熄灭前5列的灯。,输入：第一行是一个正整数N，表示需要解决的案例数。每个案例由5行组成，每一行包括6个数字。这些数字以空格隔开，可以是0或1。0表示灯的初始状态是熄灭的，1表示灯的初始状态是点亮的。输出：对每个案例，首先输出一行，输出字符串“PUZZLE#m”，其中m是该案例的序号。接着按照该案例的输入格式输出5行，其中的1表示需要把对应的按钮按下，0则表示不需要按对应的按钮。每个数字以一个空格隔开。,样例输入
6、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,样例输出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,解题思路,既然按钮按下的顺序不影响最后的结果，不妨假设从第一行往下一行一行按
7、按钮按第二行按钮时必须把第一行灯全部熄灭，否则第三行以后的按钮再也不能改变第一行的灯这样只要枚举第一行的按钮组合情况，就可以判断所有灯的熄灭情况。第一行共有2的6次方种情况。源程序 1222.cpp,例3：poj1054问题,稻田,问题,青蛙从外面跳入稻田，踩过一些禾苗，后，跳出稻田。,问题,蛙路：一个方向，等间距，大于等于3个点 不同蛙路：可以方向不同，间距不同,问题,许多青蛙跳过稻田，形成多条蛙路，不同蛙路可以踩过同一作物。,问题,青蛙每天早上踩坏稻田，早上人们发现稻田有若干株作物被踩坏，但不知多少青蛙来过。也有不在蛙路上的被踩坏的作物。,问题,问，给定一块被踩坏的稻田，求可能的最长的蛙路
8、上被踩坏的作物的数目。,输入,第一行整数R和C，稻田的行数和列数第二行整数N，表示被踩坏的作物总数。后续N行，每行两个整数i,j为被踩坏的作物的行和列的位置:1=i=R,1，1=j=C。每个被踩坏的作物只出现一次。,输出,单个整数-表示最长可能蛙路上踩坏的作物数目,样例,Figure-4,解题思路,每条青蛙行走路径中至少有3棵水稻假设一只青蛙进入稻田后踩踏的前两棵水稻分别是(X1，Y1)、(X2，Y2)。那么：青蛙每一跳在X方向上的步长dX=X2-X1、在 Y方向上的步长dY=Y2-Y1(X1-dX，Y1-dY)需要落在稻田之外当青蛙踩在水稻(X，Y)上时，下一跳踩踏的水稻是(X+dX，Y+d
9、Y)将路径上的最后一棵水稻记作(XK，YK)，(XK+dX，YK+dY)需要落在稻田之外,解题思路：枚举每一条可能路径,枚举的办法需要保证：每条可能的路径都能够被检测到从输入的水稻中任取两棵，作为一只青蛙进入稻田后踩踏的前两棵水稻，看能否形成一条穿越稻田的行走路径检测的过程需要尽快排除错误的答案：假设(X1，Y1)、(X2，Y2)就是所要寻找的行走路径上的前两棵水稻。当下列条件之一满足时，这个猜测就不成立青蛙不能经过一跳从稻田外跳到(X1，Y1)上按照(X1，Y1)、(X2，Y2)确定的步长，从出发，青蛙最多经过(MAXSTEPS-1)步，就会跳到稻田之外。MAXSTEPS是当前以找到的最好答
10、案,选择合适的数据结构,选择合适的数据结构：采用的数据结构需要与问题描述中的概念对应方案1：struct int x,y;plants5000;方案2：int plantsRow5000,plantsCol5000;显然方案1更符合问题本身的描述,设计的算法要简洁,尽量使用C提供的函数完成计算的任务：猜测一条行走路径时，需要从当前位置(X，Y)出发上时，看看(X+dX，Y+dY)位置的水稻水稻是否被踩踏方案1：自己写一段代码，看看(X+dX，Y+dY)是否在数组plants中;方案2：先用QSORT对plants中的元素排序，然后用BSEARCH从中查找元素(X+dX，Y+dY)显然基于方案2
11、设计的算法更简洁、更容易实现、更不容易出错误通常，所选用的数据结构对算法的设计有很大影响,参考程序,#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()int i,j,dX,dY,pX,pY,steps,max=2;scanf(%d%d,for(i=0;i=1,int myCompare(co
12、nst 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,课堂练习1：画家问题(POJ1681),问题描述：有一个正方形的墙，由NN个正方形
13、的砖组成，其中一些砖是白色的，另外一些砖是黄色的。Bob是个画家，想把全部的砖都涂成黄色。但他的画笔不好使。当他用画笔涂画第(i,j)个位置的砖时，位置(i-1,j)、(i+1,j)、(i,j-1)、(i,j+1)上的砖都会改变颜色。请你帮助Bob计算出最少需要涂画多少块砖，才能使所有砖的颜色都变成黄色。,输入：第一行是个整数t(1t 20)，表示要测试的案例数。然后是t个案例。每个案例的首行是一个整数n(1n 15)，表示墙的大小。接下来的n行表示墙的初始状态。每一行包含n个字符。第i行的第j个字符表示位于位置(i,j)上的砖的颜色。“w”表示白砖，“y”表示黄砖。输出：每个案例输出一行。如
14、果Bob能够将所有的砖都涂成黄色，则输出最少需要涂画的砖数，否则输出“inf”,样例输入2 3 yyy yyy yyy 5wwwww wwwww wwwww wwwww wwwww,样例输出0 15,1681bitop.cpp,作业：POJ1166,问题描述：有9个时钟，排成一个33的矩阵。现在需要用最少的移动，将9个时钟的指针都拨到12点的位置。共允许有9种不同的移动。如右表所示，每个移动会将若干个时钟的指针沿顺时针方向拨动90度。输入：从标准输入设备读入9个整数，表示各时钟指针的起始位置。1=12点、1=3点、2=6点、3=9点。输出：输出一个最短的移动序列，使得9个时钟的指针都指向12点。按照移动的序号大小，输出结果,样例输入3 3 0 2 2 2 2 1 2 样例输出4 5 8 9,
