资源描述
程序设计实习课程(C+ProgrammingPractice)程序设计实习第六讲输入输出流和枚举北京大学程序设计实习课程/732内容提要o输入输出缓冲区o枚举o作业程序设计实习课程(C+ProgrammingPractice)关于输入输出缓冲区的问题北京大学程序设计实习课程/734数据以二进制形式输入计算机北京大学程序设计实习课程/735标准输入流1100011010键盘操作系统键盘缓冲区被不同程序读出北京大学程序设计实习课程/736标准输入流o键盘上的输入被持续不断地读入操作系统缓冲区,与该缓冲区相连的流缓冲区从操作系统缓冲区读入数据(以行为单位)o如果一个流缓冲区读入的行中包含其它流需要的信息,就会造成错误。北京大学程序设计实习课程/737标准输入流10键盘操作系统键盘缓冲区stdin11000110cinscanf,gets,getcharcina,cin.getline,cin.gets北京大学程序设计实习课程/738例1#includevoidmain()chartest11001,test21001;cin.getline(test1,1000,a);couttest1;cin.getline(test2,1000,a);couttest2;coutendl;输入:qweraddass北京大学程序设计实习课程/739例1输出qwerddPressanykeytocontinuecin.getline允许从输入流中读取多个字符,并且 允许指定输入终止的字符(默认是换行字符)。在读取完成后,从读取的内容中删除该终止字符。cin.getline(char*str,intm,charcEnd);cin.getline(char*str,intm);/charcEnd=n北京大学程序设计实习课程/7310例2#include#includevoidmain()chartest11001,test21001,test31001;cin.getline(test1,1000,a);scanf(%s,test2);cin.getline(test3,1000,a);couttest1:test1endl;couttest2:test2;coutendl;couttest3:test3endl;输入:qweabgdfdda北京大学程序设计实习课程/7311例2输出oVisualStudio.Net/GCC/部分VisualC+6.0环境输出test1:qwetest2:bgtest3:dfddPressanykeytocontinueo部分VisualC+6.0环境输出test1:qwetest2:dfdtest3:bgdPressanykeytocontinue原因:混用cin和scanf造成的错误北京大学程序设计实习课程/7312例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;输入:qwertabbbccccacbb北京大学程序设计实习课程/7313例3输出oVisualStudio.Net/GCC/部分VisualC+6.0环境输出test1:qwerttest2:btest3:bbccccPressanykeytocontinueo部分VisualC+6.0环境输出test2:ctest1:qwerttest3:bbbPressanykeytocontinue结论:不要混用iosteam和stdio的输入输出函数。原因:混用cin和scanf、cout和printf造成的错误程序设计实习课程(C+ProgrammingPractice)枚举的思想北京大学程序设计实习课程/7315枚举o一种解决问题的方法。例如:求小于N的最大素数n找不到一个数学公式,使得我们根据N就可以计算出这个素数nN-1是素数吗?N-2是素数吗?N-K是素数的充分必要条件是:N-K不能被任何一个大于1、小于N-K的素数整除。n判断N-K是否是素数的问题又成了求小于N-K的全部素数n解决方法:p2是素数,记为PRIM0p根据PRIM0、PRIM1、PRIMk,寻找比PRIMk大的最小素数PRIMk+1。如果PRIMk+1大于N,则PRIMk是我们需要找的素数,否则继续寻找北京大学程序设计实习课程/7316枚举的思想o列出所有可能的情况,逐一检查是否是问题的解o关键:n可能的情况是什么n有序地枚举,不漏掉情况n尽早发现不是解的情况o根据所知道的知识知识,给一个猜测的答案。2是素数o判断猜测的答案是否正确。2是小于N的最大素数吗?o进行新新的猜测:有两个关键因素要注意n猜测的结果必须是前面的猜测中没有出现过的。每次猜测是素数一定比已经找到的素数大n猜测的过程中要及早排除错误的答案。除2之外,只有奇数才可能是素数北京大学程序设计实习课程/7317枚举的思想o枚举过程的三个关键问题n建立简洁的数学模型:模型中变量数尽可能少,它们之间相互独立减小问题解的搜索空间的维度!代码中循环嵌套的层数就少!p例:“求小于N的最大素数”中的条件是“n不能被2,n)中任意一个素数整除”,而不是“n不能被2,n)中任意一个整数整除”n减少搜索的空间:利用知识缩小模型中各变量的取值范围,避免不必要的计算减少代码中循环体执行次数!p除2之外,只有奇数才可能是素数,2,2*i+1|1=i,2*i+1nn采用合适的搜索顺序:搜索空间的遍历顺序要与模型中条件表达式一致p对2,2*i+1|1=i,2*i+1n按照从小到大的顺序北京大学程序设计实习课程/7318例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进行非降升序排列输出,即b值小的先输出、然后c值小的先输出、然后d值小的先输出。北京大学程序设计实习课程/7319o样例输入: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)北京大学程序设计实习课程/7320问题o如何利用枚举来求解问题?n数组定义n初始化n枚举过程及判断o逐一枚举a,b,c,d,#includevoidmain()intn;scanf(%d,&n);intI,cube101;for(i=0;i=n;i+)cubei=i*i*i;inta,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);北京大学程序设计实习课程/7322例2:熄灯问题(POJ1222)o问题描述:有一个由按钮组成的矩阵,其中每行有6个按钮,共5行。每个按钮的位置上有一盏灯。当按下一个按钮后,该按钮以及周围位置(上边、下边、左边、右边)的灯都会改变一次。即,如果灯原来是点亮的,就会被熄灭;如果灯原来是熄灭的,则会被点亮。n在矩阵角上的按钮改变3盏灯的状态n在矩阵边上的按钮改变4盏灯的状态n其他的按钮改变5盏灯的状态北京大学程序设计实习课程/7323o在上图中,左边矩阵中用X标记的按钮表示被按下,右边的矩阵表示灯状态的改变o对矩阵中的每盏灯设置一个初始状态。请你按按钮,直至每一盏等都熄灭。与一盏灯毗邻的多个按钮被按下时,一个操作会抵消另一次操作的结果。在下图中,第2行第3、5列的按钮都被按下,因此第2行、第4列的灯的状态就不改变北京大学程序设计实习课程/7324o请你写一个程序,确定需要按下哪些按钮,恰好使得所有的灯都熄灭。根据上面的规则,我们知道n第2次按下同一个按钮时,将抵消第1次按下时所产生的结果。因此,每个按钮最多只需要按下一次。n各个按钮被按下的顺序对最终的结果没有影响n对第1行中每盏点亮的灯,按下第2行对应的按钮,就可以熄灭第1行的全部灯。如此重复下去,可以熄灭第1、2、3、4行的全部灯。同样,按下第2、3、4、5、6列的按钮,可以熄灭前5列的灯。北京大学程序设计实习课程/7325o输入:n第一行是一个正整数N,表示需要解决的案例数。n每个案例由5行组成,每一行包括6个数字。这些数字以空格隔开,可以是0或1。0表示灯的初始状态是熄灭的,1表示灯的初始状态是点亮的。o输出:n对每个案例,首先输出一行,输出字符串“PUZZLE#m”,其中m是该案例的序号。n接着按照该案例的输入格式输出5行,其中的1表示需要把对应的按钮按下,0则表示不需要按对应的按钮。每个数字以一个空格隔开。北京大学程序设计实习课程/7326o样例输入2011010100111001001100101011100001010101011001011101100010100o样例输出PUZZLE#1101001110101001011100100010000PUZZLE#2100111110000000100110101101101北京大学程序设计实习课程/7327o第一想法:枚举所有可能的开关状态。对每个状态计算一下最后灯的情况,看是否都熄灭。每个开关有两种状态,一共有30个开关,那么状态数是230,太多,会超时。o如何减少枚举的状态数目呢?一个基本思路是,如果存在某个局部状态:一旦这个局部状态被确定,那么剩余其他部分的状态只能是确定的一种,或者不多的n种,那么就只需枚举这个局部状态就行了。解题思路北京大学程序设计实习课程/7328解题思路o本题是否存在这样的“局部”呢?n经过观察,发现第1行就是这样的一个“局部”。因为第1行的各开关状态确定的情况下,这些开关作用过后,将导致第1行某些灯是亮的,某些灯是灭的。n此时要熄灭第1行某个亮着的灯(假设位于第i列),那么唯一的办法就是按下第2行第i列的开关(因为第一行的开关已经用过了,而第3行及其后的开关不会影响到第1行)。o推理过程n为了使第1行的灯全部熄灭,第2行的合理开关状态就是唯一的。n第2行的开关起作用后,为了熄灭第二行的灯,第3行的合理开关状态就也是唯一的,以此类推,最后一行的开关状态也是唯一的。北京大学程序设计实习课程/7329o总之,只要第1行的状态定下来,比如叫A,那么剩余行的情况就是确定唯一的了。推算出最后一行的开关状态,然后看看最后一行的开关起作用后,最后一行的所有灯是否都熄灭,如果是,那么A就是一个解的状态。如果不是,那么A不是解的状态,第1行换个状态重新试试。o因此,只需枚举第一行的状态,状态数是26=64解题思路北京大学程序设计实习课程/7330具体实现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种可能取值北京大学程序设计实习课程/7331具体实现o根据上面的分析,对PRESS的第一行元素的各种取值进行枚举,依次考虑如下情况o对PRESS的第一行的每种取值,根据熄灯规则计算出PRESS的其他行的值,判断这个PRESS能否使得矩阵第五行的所有灯也恰好熄灭。北京大学程序设计实习课程/7332具体实现o因此需要定义两个函数o第一个函数enumate(),对PRESS的第一行元素的每种取值进行枚举n在每种取值情况下,看看是否找到答案;若找到,则返回;若没有,则尝试下一种取值的情况n问题1:如何进行枚举?如果每行开关数目是N那怎么办?o第二个函数guess():对PRESS的第一行的给定取值,根据熄灯规则计算出PRESS的其他行的值,判断这个PRESS能否使得矩阵第五行的所有灯也恰好熄灭。n问题2:如何计算出PRESS的其他行的值?n问题3:如何检查这个PRESS能否使得矩阵第五行的所有灯也恰好熄灭?北京大学程序设计实习课程/7333Press0里放着第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那怎么办?如何进行枚举?北京大学程序设计实习课程/7334如何进行枚举?o适用于一行有N个开关的办法:n一个6位二进制数的所有取值正好是64种,让该数的每一位对应于Press0里的一个元素(Press00对应最高位,Press01对应次高位.),那么这个二进制数的每个取值正好表示了第一行开关的一种状态。n二进制计数:每次从最低为+1,然后向高位开始依次处理进位问题n注意:若采用二进制表示,则要写一个从二进制数到状态的转换函数voidSwitchStatus(intn,int*pSwitchLine);n因此可以用int数组模拟二进制进位规则北京大学程序设计实习课程/7335如何计算出PRESS的其他行的值?o用一个68的数组来表示按钮矩阵:简化计算数组下一行的值的计算公式n第0行、第0列和第7列不属于PRESS矩阵范围,可全置0o给定PRESS的第一行取值,计算出PRESS的其他行的值nPressr+1c=(Puzzlerc+Pressrc-1+Pressrc+Pressrc+1+Pressr-1c)%2n0r5,0c7北京大学程序设计实习课程/7336参考程序#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)%2;for(c=1;c7;c+)if(press5c-1+press5c+press5c+1+press4c)%2!=puzzle5c)return(false);return(true);北京大学程序设计实习课程/7337void enumate()int c;bool success;for(c=1;c 1)press1c=0;c+;press1c+;return;void main()int cases,i,r,c;scanf(%d,&cases);for(r=0;r6;r+)pressr0=pressr7=0;for(c=1;c7;c+)press0c=0;for(i=0;icases;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);北京大学程序设计实习课程/7339例2:讨厌的青蛙(POJ1054)o问题描述:在韩国,有一种小的青蛙。每到晚上,这种青蛙会跳越稻田,从而踩踏稻子。农民在早上看到被踩踏的稻子,希望找到造成最大损害的那只青蛙经过的路径。n每只青蛙总是沿着一条直线跳越稻田,而且每次跳跃的距离都相同。n不同的青蛙有不同的跳跃距离,不同的跳跃方向。北京大学程序设计实习课程/7340o如下图所示,稻田里的稻子组成一个栅格,每棵稻子位于一个格点上。而青蛙总是从稻田的一侧跳进稻田,然后沿着某条直线穿越稻田,从另一侧跳出去北京大学程序设计实习课程/7341o如下图所示,可能会有多只青蛙从稻田穿越。青蛙的每一跳都恰好踩在一棵水稻上,将这棵水稻拍倒。有些水稻可能被多只青蛙踩踏。当然,农民所见到的是图4中的情形,并看不到图3中的直线,也见不到别人家田里被踩踏的水稻,。北京大学程序设计实习课程/7342o根据图4,农民能够构造出青蛙穿越稻田时的行走路径,并且只关心那些在穿越稻田时至少踩踏了3棵水稻的青蛙。因此,每条青蛙行走路径上至少包括3棵被踩踏的水稻。而在一条青蛙行走路径的直线上,也可能会有些被踩踏的水稻不属于该行走路径n不是一条行走路径:只有两棵被踩踏的水稻n是一条行走路径,但不包括(2,6)上的水道n不是一条行走路径:虽然有3棵被踩踏的水稻,但这三棵水稻之间的距离间隔不相等北京大学程序设计实习课程/7343问题o问,给定一块被踩坏的稻田,求可能的最长的蛙路上被踩坏的作物的数目。o例如,图4的答案是7,因为第6行上全部水稻恰好构成一条青蛙行走路径北京大学程序设计实习课程/7344输入o第一行整数R和C,1=R,C=5000,稻田的行数和列数o第二行整数N,3=N=5000,表示被踩坏的作物总数。o后续N行,每行两个整数i,j为被踩坏的作物的行和列的位置:1=i=R,1=j=C。o每个被踩坏的作物只出现一次。北京大学程序设计实习课程/7345输出o单个整数-表示最长可能蛙路上踩坏的作物数目北京大学程序设计实习课程/7346问题分析o这道题目也就是说,在给出的n个点中找出一些点的序列来n使得每一个点相对于上一个点的坐标都是一个相同的常量n“第一个点减去这个常量”和“最后一个点加上这个常量”后均落在方格的外面。北京大学程序设计实习课程/7347问题分析o我们先对这些点按照坐标排序。o然后依次循环出要求的序列中的第一个和第二个点,这样我们就知道后一个点相对于前一个点的坐标是多少了;o然后我们依次用第二个点加上这个坐标求出第三个点;o第三个点加上这个坐标得出第四个点等等。o当然,我们还需要判断一下这求出来的第三个、第四个点是否在给定的点内。北京大学程序设计实习课程/7348问题的解o需要注意的是,蛙路中的点数少于3个的时候是不考虑的。即每条青蛙行走路径中至少有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)需要落在稻田之外北京大学程序设计实习课程/7349解题思路:猜测一条路径o猜测的办法需要保证:每条可能的路径都能够被猜测到n从输入的水稻中任取两棵,作为一只青蛙进入稻田后踩踏的前两棵水稻,看能否形成一条穿越稻田的行走路径北京大学程序设计实习课程/7350解题思路:猜测一条路径o猜测的过程需要尽快排除错误的答案:猜测(X1,Y1)、(X2,Y2)就是所要寻找的行走路径上的前两棵水稻。当下列条件之一满足时,这个猜测就不成立n青蛙不能经过一跳从稻田外跳到(X1,Y1)上n按照(X1,Y1)、(X2,Y2)确定的步长,从(X2,Y2)出发,青蛙最多经过(MAXSTEPS-1)步,就会跳到稻田之外。MAXSTEPS是当前已经找到的最好答案北京大学程序设计实习课程/7351选择合适的数据结构o选择合适的数据结构:采用的数据结构需要与问题描述中的概念对应ostructintx,y;plants5000;北京大学程序设计实习课程/7352设计的算法要简洁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设计的算法更简洁、更容易实现、更不容易出错误北京大学程序设计实习课程/7353注意,一个有n个元素的数组,每次取两个元素,遍历所有取法的代码写法:for(inti=0;in1)for(intj=i+1;jmax,则记为maxo输出max(若max=2,则输出0)北京大学程序设计实习课程/7355参考程序#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);北京大学程序设计实习课程/7356具体实现o问题1:qsort中如何实现如何比较函数?nintmyCompare(constvoid*ele1,constvoid*ele2);o问题2:判断从secPlant点开始,步长为dx,dy,那么最多能走几步(利用bsearch定义函数)nintsearchPath(PLANTsecPlant,intdX,intdY);o问题3:如何测试第一点的前一点在稻田里?o问题4:如何判断x方向或y方向过早越界?北京大学程序设计实习课程/7357int 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);/判断从判断从 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;plant.x+=dX;plant.y+=dY;steps+;return(steps);北京大学程序设计实习课程/7359参考程序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+)/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(plants j.x+(max-1)*dX r)break;/x方向过早越界了。说明本次选的第二点不成立。方向过早越界了。说明本次选的第二点不成立。/如果换下一个点作为第二点,如果换下一个点作为第二点,x方向步长只会更大,更不成立,所以应该方向步长只会更大,更不成立,所以应该/认为本次选的第一点都是不成立的,那么取下一个点作为第一点再试认为本次选的第一点都是不成立的,那么取下一个点作为第一点再试 pY=plants j.y+(max-1)*dY;if(pY c|pY max)max=steps;if(max=2)max=0;printf(%dn,max);北京大学程序设计实习课程/7361作业1:画家问题(POJ1681)o有一个正方形的墙,由NN个正方形的砖组成,其中一些砖是白色的,另外一些砖是黄色的。oBob是个画家,想把全部的砖都涂成黄色。但他的画笔不好使。当他用画笔涂画第(i,j)个位置的砖时,位置(i-1,j)、(i+1,j)、(i,j-1)、(i,j+1)上的砖都会改变颜色。o请你帮助Bob计算出最少需要涂画多少块砖,才能使所有砖的颜色都变成黄色。北京大学程序设计实习课程/7362北京大学程序设计实习课程/7363o输入:第一行是个整数t(1t20),表示要测试的案例数。然后是t个案例。每个案例的首行是一个整数n(1n15),表示墙的大小。接下来的n行表示墙的初始状态。每一行包含n个字符。第i行的第j个字符表示位于位置(i,j)上的砖的颜色。“w”表示白砖,“y”表示黄砖。o输出:每个案例输出一行。如果Bob能够将所有的砖都涂成黄色,则输出最少需要涂画的砖数,否则输出“inf”北京大学程序设计实习课程/7364o样例输入23yyyyyyyyy5wwwwwwwwwwwwwwwwwwwwwwwwwo样例输出015北京大学程序设计实习课程/7365作业2:POJ1166o问题描述:有9个时钟,排成一个33的矩阵。现在需要用最少的移动,将9个时钟的指针都拨到12点的位置。共允许有9种不同的移动。如右表所示,每个移动会将若干个时钟的指针沿顺时针方向拨动90度。o输入:从标准输入设备读入9个整数,表示各时钟指针的起始位置。0=12点、1=3点、2=6点、3=9点。o输出:输出一个移动序列,使得9个时钟的指针都指向12点。按照移动的序号由小到大,输出结果移动影响的时钟1ABDE2ABC3BCEF4ADG5BDEFH6CFI7DEGH8GHI9EFHI北京大学程序设计实习课程/7367o样例输入330222212o样例输出4589
展开阅读全文