北京大学程序设计实习课程.ppt

《北京大学程序设计实习课程.ppt》由会员分享，可在线阅读，更多相关《北京大学程序设计实习课程.ppt（72页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、程序设计实习课程(C+ProgrammingPractice)程序设计实习第六讲输入输出流和枚举主讲教师：田永鸿http:/ 允许指定输入终止的字符(默认是换行字符)。在读取完成后，从读取的内容中删除该终止字符。cin.getline(char*str,intm,charcEnd);cin.getline(char*str,intm);/charcEnd=n12北京大学程序设计实习课程/73例2#include#includevoidmain()chartest11001,test21001,test31001;cin.getline(test1,1000,a);scanf(%s,test2)

2、;cin.getline(test3,1000,a);couttest1:test1endl;couttest2:test2;coutendl;couttest3:test3endl;输入：qweabgdfdda13北京大学程序设计实习课程/73例2输出oVisualStudio.Net/GCC/部分VisualC+6.0环境输出test1:qwetest2:bgtest3:dfddPressanykeytocontinueo部分VisualC+6.0环境输出test1:qwetest2:dfdtest3:bgdPressanykeytocontinue原因：混用cin和scanf造成的错误1

3、4北京大学程序设计实习课程/73例3#include#includevoidmain()chartest110001,test21001,test31001;cin.getline(test1,10,a);scanf(%c,&(test20);cin.getline(test3,1000,a);couttest1:test1;printf(test2:%c,test20);coutendl;couttest3:test3endl;输入：qwertabbbccccacbb15北京大学程序设计实习课程/73例3输出oVisualStudio.Net/GCC/部分VisualC+6.0环境输出tes

4、t1:qwerttest2:btest3:bbccccPressanykeytocontinueo部分VisualC+6.0环境输出test2:ctest1:qwerttest3:bbbPressanykeytocontinue结论：不要混用iosteam和stdio的输入输出函数。原因：混用cin和scanf、cout和printf造成的错误16程序设计实习课程(C+ProgrammingPractice)枚举的思想北京大学程序设计实习课程/73枚举o一种解决问题的方法。例如：求小于N的最大素数n找不到一个数学公式，使得我们根据N就可以计算出这个素数nN-1是素数吗？N-2是素数吗？N-K是

5、素数的充分必要条件是：N-K不能被任何一个大于1、小于N-K的素数整除。n判断N-K是否是素数的问题又成了求小于N-K的全部素数n解决方法：p2是素数，记为PRIM0p根据PRIM0、PRIM1、PRIMk，寻找比PRIMk大的最小素数PRIMk+1。如果PRIMk+1大于N，则PRIMk是我们需要找的素数，否则继续寻找18北京大学程序设计实习课程/73枚举的思想o列出所有可能的情况，逐一检查是否是问题的解o关键：n可能的情况是什么n有序地枚举，不漏掉情况n尽早发现不是解的情况o根据所知道的知识知识，给一个猜测的答案。2是素数o判断猜测的答案是否正确。2是小于N的最大素数吗？o进行新新的猜测：

6、有两个关键因素要注意n猜测的结果必须是前面的猜测中没有出现过的。每次猜测是素数一定比已经找到的素数大n猜测的过程中要及早排除错误的答案。除2之外，只有奇数才可能是素数19北京大学程序设计实习课程/73枚举的思想o枚举过程的三个关键问题n建立简洁的数学模型：模型中变量数尽可能少，它们之间相互独立减小问题解的搜索空间的维度！代码中循环嵌套的层数就少！p例：“求小于N的最大素数”中的条件是“n不能被2,n)中任意一个素数整除”，而不是“n不能被2,n)中任意一个整数整除”n减少搜索的空间：利用知识缩小模型中各变量的取值范围，避免不必要的计算减少代码中循环体执行次数！p除2之外，只有奇数才可能是素数，

7、2,2*i+1|1=i,2*i+1nn采用合适的搜索顺序：搜索空间的遍历顺序要与模型中条件表达式一致p对2,2*i+1|1=i,2*i+1n按照从小到大的顺序20北京大学程序设计实习课程/73例1：完美立方(POJ1543)o问题描述：a3=b3+c3+d3为完美立方等式。例如123=63+83+103。编写一个程序，对任给的正整数N(N100)，寻找所有的四元组(a,b,c,d)，使得a3=b3+c3+d3，其中1a,b,c,dN。o输入：正整数N(N100)o输出：每行输出一个完美立方，按照a的值，从小到大依次输出。当两个完美立方等式中a的值相同，则依次按照b、c、d进行非降升序排列输出，

8、即b值小的先输出、然后c值小的先输出、然后d值小的先输出。21北京大学程序设计实习课程/73o样例输入：24o样例输出：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)22北京大学程序设计实习课程/73问题o如何利用枚举来求解问题？n数组定义n初始化n枚举过程及判断23o逐一枚举a,b,c,d,#include vo

9、id main()int n;scanf(%d,&n);int I,cube101;for(i=0;i=n;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);24北京大学程序设计实习课程/73例2：熄灯问题（POJ1222）o问题描述：有一个由按钮组成的矩阵，其中每行有6个按钮，共5行。每个按钮的位置上有一盏灯。当按下一个按钮后，该按钮以及

10、周围位置(上边、下边、左边、右边)的灯都会改变一次。即，如果灯原来是点亮的，就会被熄灭；如果灯原来是熄灭的，则会被点亮。n在矩阵角上的按钮改变3盏灯的状态n在矩阵边上的按钮改变4盏灯的状态n其他的按钮改变5盏灯的状态25北京大学程序设计实习课程/73o在上图中，左边矩阵中用X标记的按钮表示被按下，右边的矩阵表示灯状态的改变o对矩阵中的每盏灯设置一个初始状态。请你按按钮，直至每一盏等都熄灭。与一盏灯毗邻的多个按钮被按下时，一个操作会抵消另一次操作的结果。在下图中，第2行第3、5列的按钮都被按下，因此第2行、第4列的灯的状态就不改变26北京大学程序设计实习课程/73o请你写一个程序，确定需要按下哪

11、些按钮，恰好使得所有的灯都熄灭。根据上面的规则，我们知道n第2次按下同一个按钮时，将抵消第1次按下时所产生的结果。因此，每个按钮最多只需要按下一次。n各个按钮被按下的顺序对最终的结果没有影响n对第1行中每盏点亮的灯，按下第2行对应的按钮，就可以熄灭第1行的全部灯。如此重复下去，可以熄灭第1、2、3、4行的全部灯。同样，按下第1、2、3、4、5列的按钮，可以熄灭前5列的灯。27北京大学程序设计实习课程/73o输入：n第一行是一个正整数N，表示需要解决的案例数。n每个案例由5行组成，每一行包括6个数字。这些数字以空格隔开，可以是0或1。0表示灯的初始状态是熄灭的，1表示灯的初始状态是点亮的。o输出

12、：n对每个案例，首先输出一行，输出字符串“PUZZLE#m”，其中m是该案例的序号。n接着按照该案例的输入格式输出5行，其中的1表示需要把对应的按钮按下，0则表示不需要按对应的按钮。每个数字以一个空格隔开。28北京大学程序设计实习课程/73o样例输入2011010100111001001100101011100001010101011001011101100010100o样例输出PUZZLE#1101001110101001011100100010000PUZZLE#210011111000000010011010110110129北京大学程序设计实习课程/73o第一想法：枚举所有可能的开关状

13、态。对每个状态计算一下最后灯的情况，看是否都熄灭。每个开关有两种状态，一共有30个开关，那么状态数是230，太多，会超时。o如何减少枚举的状态数目呢？一个基本思路是，如果存在某个局部状态：一旦这个局部状态被确定，那么剩余其他部分的状态只能是确定的一种，或者不多的n种，那么就只需枚举这个局部状态就行了。解题思路30北京大学程序设计实习课程/73解题思路o本题是否存在这样的“局部”呢？n经过观察，发现第1行就是这样的一个“局部”。因为第1行的各开关状态确定的情况下，这些开关作用过后，将导致第1行某些灯是亮的，某些灯是灭的。n此时要熄灭第1行某个亮着的灯（假设位于第i列），那么唯一的办法就是按下第2

14、行第i列的开关（因为第一行的开关已经用过了，而第3行及其后的开关不会影响到第1行)。o推理过程n为了使第1行的灯全部熄灭，第2行的合理开关状态就是唯一的。n第2行的开关起作用后，为了熄灭第二行的灯，第3行的合理开关状态就也是唯一的，以此类推，最后一行的开关状态也是唯一的。31北京大学程序设计实习课程/73o总之，只要第1行的状态定下来，比如叫A，那么剩余行的情况就是确定唯一的了。推算出最后一行的开关状态，然后看看最后一行的开关起作用后，最后一行的所有灯是否都熄灭，如果是，那么A就是一个解的状态。如果不是，那么A不是解的状态，第1行换个状态重新试试。o因此，只需枚举第一行的状态，状态数是26=6

15、4解题思路32北京大学程序设计实习课程/73具体实现o用一个矩阵PUZZLE56表示灯的初始状态nPuzzleij=1：灯(i,j)初始时是被点亮的nPuzzleij=0：灯(i,j)初始时是熄灭的o用一个矩阵PRESS56表示要计算的结果nPressij=1：需要按下按钮(i,j)nPressij=0：不需要按下按钮(i,j)o有下列等式成立(0i5,0j6)nPuzzleij=(Pressij-1+Pressij+Pressij+1+Pressi-1j+Pressi+1j)%2oPress56共有230种可能取值33北京大学程序设计实习课程/73具体实现o根据上面的分析，第PRESS的第一

16、行元素的各种取值进行枚举，依次考虑如下情况o对PRESS的第一行的每种取值，根据熄灯规则计算出PRESS的其他行的值，判断这个PRESS能否使得矩阵第五行的所有灯也恰好熄灭。34北京大学程序设计实习课程/73具体实现o因此需要定义两个函数o第一个函数enumate()，对PRESS的第一行元素的每种取值进行枚举n在每种取值情况下，看看是否找到答案；若找到，则返回；若没有，则尝试下一种取值的情况n问题1：如何进行枚举？如果每行开关数目是N那怎么办?o第二个函数guess()：对PRESS的第一行的给定取值，根据熄灯规则计算出PRESS的其他行的值，判断这个PRESS能否使得矩阵第五行的所有灯也恰

17、好熄灭。n问题2：如何计算出PRESS的其他行的值？n问题3：如何检查这个PRESS能否使得矩阵第五行的所有灯也恰好熄灭？35北京大学程序设计实习课程/73Press0里放着第1行开关的状态，如何进行枚举呢？可以使用六重循环：for(inta0=0;a02;a0+)for(inta1=0;a12;a0+)for(inta2=0;a22;a0+)for(inta3=0;a32;a0+)for(inta4=0;a42;a0+)for(inta5=0;a52;a0+)Press00=a0;Press01=a1;Press02=a2;/如果每行开关数目是N那怎么办?如何进行枚举？36北京大学程序设计实

18、习课程/73如何进行枚举？o适用于一行有N个开关的办法：n一个6位二进制数的所有取值正好是64种，让该数的每一位对应于Press0里的一个元素（Press00对应最高位，Press01对应次高位.)，那么这个二进制数的每个取值正好表示了第一行开关的一种状态。n二进制计数：每次从最低为+1，然后向高位开始依次处理进位问题n注意：若采用二进制表示，则要写一个从二进制数到状态的转换函数voidSwitchStatus(intn,int*pSwitchLine);n因此可以用int数组模拟二进制进位规则37北京大学程序设计实习课程/73如何计算出PRESS的其他行的值？o用一个68的数组来表示按钮矩阵

19、：简化计算数组下一行的值的计算公式n第0行、第0列和第7列不属于PRESS矩阵范围，可全置0o给定PRESS的第一行取值，计算出PRESS的其他行的值nPressr+1c=(Puzzlerc+Pressrc-1+Pressrc+Pressrc+1+Pressr-1c)%2n0r5,0c738北京大学程序设计实习课程/73参考程序#include int puzzle68,press68;bool guess()int c,r;for(r=1;r5;r+)for(c=1;c7;c+)pressr+1c=(puzzlerc+pressrc+pressr-1c+pressrc-1+pressrc+1

20、)%2;for(c=1;c7;c+)if(press5c-1+press5c+press5c+1+press4c)%2!=puzzle5c)return(false);return(true);39北京大学程序设计实习课程/73void enumate()int c;bool success;for(c=1;c 1)press1c=0;c+;press1c+;return;40void main()int cases,i,r,c;scanf(%d,&cases);for(r=0;r6;r+)pressr0=pressr7=0;for(c=1;r7;r+)press0c=0;for(i=0;ic

21、ases;i+)for(r=1;r6;r+)for(c=1;c7;c+)scanf(%d,&puzzlerc);enumate();printf(PUZZLE#%dn,i+1);for(r=1;r6;r+)for(c=1;c7;c+)printf(%d,pressrc);printf(n);41北京大学程序设计实习课程/73例2：讨厌的青蛙（POJ1054）o问题描述：在韩国，有一种小的青蛙。每到晚上，这种青蛙会跳越稻田，从而踩踏稻子。农民在早上看到被踩踏的稻子，希望找到造成最大损害的那只青蛙经过的路径。n每只青蛙总是沿着一条直线跳越稻田，而且每次跳跃的距离都相同。n不同的青蛙有不同的跳跃距离

22、，不同的跳跃方向。42北京大学程序设计实习课程/73o如下图所示，稻田里的稻子组成一个栅格，每棵稻子位于一个格点上。而青蛙总是从稻田的一侧跳进稻田，然后沿着某条直线穿越稻田，从另一侧跳出去43北京大学程序设计实习课程/73o如下图所示，可能会有多只青蛙从稻田穿越。青蛙的每一跳都恰好踩在一棵水稻上，将这棵水稻拍倒。有些水稻可能被多只青蛙踩踏。当然，农民所见到的是图4中的情形，并看不到图3中的直线，也见不到别人家田里被踩踏的水稻，。44北京大学程序设计实习课程/73o根据图4，农民能够构造出青蛙穿越稻田时的行走路径，并且只关心那些在穿越稻田时至少踩踏了3棵水稻的青蛙。因此，每条青蛙行走路径上至少包

23、括3棵被踩踏的水稻。而在一条青蛙行走路径的直线上，也可能会有些被踩踏的水稻不属于该行走路径n不是一条行走路径：只有两棵被踩踏的水稻n是一条行走路径，但不包括（2，6）上的水道n不是一条行走路径：虽然有3棵被踩踏的水稻，但这三棵水稻之间的距离间隔不相等45北京大学程序设计实习课程/73问题o问，给定一块被踩坏的稻田，求可能的最长的蛙路上被踩坏的作物的数目。o例如，图4的答案是7，因为第6行上全部水稻恰好构成一条青蛙行走路径46北京大学程序设计实习课程/73输入o第一行整数R和C，稻田的行数和列数o第二行整数N，表示被踩坏的作物总数。o后续N行，每行两个整数i,j为被踩坏的作物的行和列的位置:1=

24、i=R,1=j=C。o每个被踩坏的作物只出现一次。47北京大学程序设计实习课程/73输出o单个整数-表示最长可能蛙路上踩坏的作物数目48北京大学程序设计实习课程/73问题分析o这道题目也就是说，在给出的n个点中找出一些点的序列来n使得每一个点相对于上一个点的坐标都是一个相同的常量n“第一个点减去这个常量”和“最后一个点加上这个常量”后均落在方格的外面。49北京大学程序设计实习课程/73问题分析o我们先对这些点按照坐标排序。o然后依次循环出要求的序列中的第一个和第二个点，这样我们就知道后一个点相对于前一个点的坐标是多少了；o然后我们依次用第二个点加上这个坐标求出第三个点；o第三个点加上这个坐标得

25、出第四个点等等。o当然，我们还需要判断一下这求出来的第三个、第四个点是否在给定的点内。50北京大学程序设计实习课程/73问题分析o由于每个点的上一个点/下一个点最多只能有n种选择，故一个点最多属于n条不同的蛙路。o这样，对于某个确定的点来说，它的所有可能的下一个需要判断的点至多有n个。这样因为判断一个点在不在给定的点内只需要O(1)的复杂度，所以我们只需要O(n2)的时间就可以得出问题的解答。o由于这个算法需要一个r*c的表来保存点在方格中的存在状态，故空间复杂度为O(n2)。51北京大学程序设计实习课程/73问题的解o需要注意的是，蛙路中的点数少于3个的时候是不考虑的。即每条青蛙行走路径中至

26、少有3棵水稻。所以这个时候的蛙路中的点数应该按照0来输出。o假设一只青蛙进入稻田后踩踏的前两棵水稻分别是(X1，Y1)、(X2，Y2)。那么：n青蛙每一跳在X方向上的步长dX=X2-X1、在Y方向上的步长dY=Y2-Y1n(X1-dX，Y1-dY)需要落在稻田之外n当青蛙踩在水稻(X，Y)上时，下一跳踩踏的水稻是(X+dX，Y+dY)n将路径上的最后一棵水稻记作(XK，YK)，(XK+dX，YK+dY)需要落在稻田之外52北京大学程序设计实习课程/73解题思路：猜测一条路径o猜测的办法需要保证：每条可能的路径都能够被猜测到n从输入的水稻中任取两棵，作为一只青蛙进入稻田后踩踏的前两棵水稻，看能否

27、形成一条穿越稻田的行走路径53北京大学程序设计实习课程/73解题思路：猜测一条路径o猜测的过程需要尽快排除错误的答案：猜测(X1，Y1)、(X2，Y2)就是所要寻找的行走路径上的前两棵水稻。当下列条件之一满足时，这个猜测就不成立n青蛙不能经过一跳从稻田外跳到(X1，Y1)上n按照(X1，Y1)、(X2，Y2)确定的步长，从(X1，Y1)出发，青蛙最多经过(MAXSTEPS-1)步，就会跳到稻田之外。MAXSTEPS是当前已经找到的最好答案54北京大学程序设计实习课程/73选择合适的数据结构o选择合适的数据结构：采用的数据结构需要与问题描述中的概念对应o方案1：structintx,y;plan

28、ts5000;o方案2：intplantsRow5000,plantsCol5000;o显然方案1更符合问题本身的描述55北京大学程序设计实习课程/73设计的算法要简洁o尽量使用C提供的函数完成计算的任务：猜测一条行走路径时，需要从当前位置(X，Y)出发上时，看看(X+dX，Y+dY)位置的水稻水稻是否被踩踏n方案1：自己写一段代码，看看(X+dX，Y+dY)是否在数组plants中;n方案2：先用QSORT对plants中的元素排序，然后用BSEARCH从中查找元素(X+dX，Y+dY)o显然基于方案2设计的算法更简洁、更容易实现、更不容易出错误o通常，所选用的数据结构对算法的设计有很大影响

29、56北京大学程序设计实习课程/73注意，一个有n个元素的数组，每次取两个元素，遍历所有取法的代码写法：for(inti=0;in1)for(intj=i+1;jmax，则记为maxo输出max（若max=2，则输出0）58北京大学程序设计实习课程/73参考程序#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);5

30、9北京大学程序设计实习课程/73具体实现o问题1：qsort中如何实现如何比较函数？nintmyCompare(constvoid*ele1,constvoid*ele2)；o问题2：判断从secPlant点开始，步长为dx,dy，那么最多能走几步（利用bsearch定义函数）nintsearchPath(PLANTsecPlant,intdX,intdY);o问题3：如何测试第一点的前一点在稻田里？o问题4：如何判断x方向或y方向过早越界？60北京大学程序设计实习课程/73int myCompare(const void*ele1,const void*ele2)PLANT*p1,*p2;p

31、1=(PLANT*)ele1;p2=(PLANT*)ele2;if(p1-x=p2-x)return(p1-y-p2-y);return(p1-x-p2-x);61/判断从判断从 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,pl

32、ants,n,sizeof(PLANT),myCompare)/每一步每一步都必须踩倒水稻才算合理，否则这就不是一条行走路径都必须踩倒水稻才算合理，否则这就不是一条行走路径steps=0;break;plant.x+=dX;plant.y+=dY;steps+;return(steps);62北京大学程序设计实习课程/73参考程序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(plant

33、s,n,sizeof(PLANT),myCompare);63for(i=0;i n-2;i+)/plantsi是第一个点是第一个点for(j=i+1;j n-1;j+)/plantsj是第二个点是第二个点 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;/第一点的前一点在稻田里，说明本次选的第第一点的前一点在稻田里，说明本次选的第 /二点导致的步长不合理，取下一个点作为第二点二点导致的步长不合理，取下一个点作为第二点 if(plant

34、s i.x+(max-1)*dX r)break;/x方向过早越界了。说明本次选的第二点不成立。方向过早越界了。说明本次选的第二点不成立。/如果换下一个点作为第二点，如果换下一个点作为第二点，x方向步长只会更大，更不成立，所以应该方向步长只会更大，更不成立，所以应该/认为本次选的第一点都是不成立的，那么取下一个点作为第一点再试认为本次选的第一点都是不成立的，那么取下一个点作为第一点再试 pY=plants i.y+(max-1)*dY;if(pY c|pY max)max=steps;if(max=2)max=0;printf(%dn,max);64北京大学程序设计实习课程/73作业1：画家问

35、题(POJ1681)o有一个正方形的墙，由NN个正方形的砖组成，其中一些砖是白色的，另外一些砖是黄色的。oBob是个画家，想把全部的砖都涂成黄色。但他的画笔不好使。当他用画笔涂画第(i,j)个位置的砖时，位置(i-1,j)、(i+1,j)、(i,j-1)、(i,j+1)上的砖都会改变颜色。o请你帮助Bob计算出最少需要涂画多少块砖，才能使所有砖的颜色都变成黄色。65北京大学程序设计实习课程/7366北京大学程序设计实习课程/73o输入：第一行是个整数t(1t20)，表示要测试的案例数。然后是t个案例。每个案例的首行是一个整数n(1n15)，表示墙的大小。接下来的n行表示墙的初始状态。每一行包含

36、n个字符。第i行的第j个字符表示位于位置(i,j)上的砖的颜色。“w”表示白砖，“y”表示黄砖。o输出：每个案例输出一行。如果Bob能够将所有的砖都涂成黄色，则输出最少需要涂画的砖数，否则输出“inf”67北京大学程序设计实习课程/73o样例输入23yyyyyyyyy5wwwwwwwwwwwwwwwwwwwwwwwwwo样例输出01568北京大学程序设计实习课程/73作业2：POJ1166o问题描述：有9个时钟，排成一个33的矩阵。现在需要用最少的移动，将9个时钟的指针都拨到12点的位置。共允许有9种不同的移动。如右表所示，每个移动会将若干个时钟的指针沿顺时针方向拨动90度。o输入：从标准输入设备读入9个整数，表示各时钟指针的起始位置。1=12点、1=3点、2=6点、3=9点。o输出：输出一个最短的移动序列，使得9个时钟的指针都指向12点。按照移动的序号大小，输出结果移动影响的时钟1ABDE2ABC3BCEF4ADG5BDEFH6CFI7DEGH8GHI9EFHI6970北京大学程序设计实习课程/73o样例输入330222212o样例输出458971北京大学程序设计实习课程/73做练习之前，认真阅读：“程序设计导引及在线实践”第八章72