(HDUACM201303版_05)筛选法及预处理(附菜鸟的23个经典错误)

ACM程序设计,杭州电子科技大学刘春英acm,5/15/2020,2,每周一星（4）：,微风,5/15/2020,3,第五讲,筛选法及预处理（附-菜鸟的23个经典错误）,5/15/2020,4,例1-素数判断,题目描述：给定一个N（1N100000），请判断N是否是素数，如果是素数，则请输出YES，否则输出NO。SampleInput：45SampleOutput:NOYES,5/15/2020,5,常见朴素算法,#includeintmain()inti,n;while(scanf(%d,5/15/2020,6,朴素算法优化版本,#include#includeintmain()inti,n,x;while(scanf(%d,5/15/2020,7,例2-求所有素数,题目描述：给定一个N（1N100000），请按照递增次序输出所有小于等于N的素数。SampleInput：10SampleOutput:2357,5/15/2020,8,题目分析,题目特点：不是求一个素数，而是求一段素数（一种常见的情况就是求指定范围的所有的素数）如果还用常规求素数方法，可能的问题是？,5/15/2020,9,筛选法求素数,基本思想：素数的倍数一定不是素数实现方法：用一个长度为N+1的数组保存信息（0表示素数，1表示非素数），先假设所有的数都是素数（初始化为0），从第一个素数2开始，把2的倍数都标记为非素数（置为1），一直到大于N；然后进行下一趟，找到2后面的下一个素数3，进行同样的处理，直到最后，数组中依然为0的数即为素数。说明：整数1特殊处理即可。,5/15/2020,10,效果演示,5/15/2020,11,效果演示,5/15/2020,12,效果演示,5/15/2020,13,效果演示,5/15/2020,14,效果演示,5/15/2020,15,效果演示,5/15/2020,16,效果演示,5/15/2020,17,效果演示,5/15/2020,18,效果演示,5/15/2020,19,参考代码（筛选法）,#include#includeinta100001;intmain()inti,j,n;while(scanf(%d,5/15/2020,20,思考-常规筛选法的改进？,#include#includeinta100001;intmain()inti,j,n;while(scanf(%d,5/15/2020,21,例3-求素数个数,题目描述：给定一个N（1N100000），请输出小于等于N的素数的个数。测试数据有C组，（1C100000）.SampleInput：10SampleOutput:4,5/15/2020,22,常规筛选法代码,#include#includeinta100001;intmain()inti,j,n,count;while(scanf(%d,5/15/2020,23,题目分析(1),题目特点：数据量超大！分析：前面算法的瓶颈：每组数据都求素数.如何改进以加快求解速度？可否一次筛选，多次查找？这就是预处理思想,5/15/2020,24,预处理参考代码,#include#includeinta100001;intmain()inti,j,n,count;for(i=2;i=100000;i+)if(ai=0)for(j=i+i;j0，请输出”OK!”，否则请输出”No”SampleInput151-5SampleOutputOK!No,5/15/2020,60,菜鸟之伤（14）,#includevoidmain()inta,b;while(scanf(“%d%d”,5/15/2020,61,菜鸟之伤（14）,总结：字符串输出的大小写问题对于菜鸟需要特别注意，其实，不管是全大写、全小写，还是首字母大写，你尽管复制即可（没有电子版，另当别论），当然还要注意是否有标点符号等情况。说明：菜鸟常犯错误，稍有经验即可避免,5/15/2020,62,以1170BalloonComes!为例,SampleInput4+12-12*12/12,SampleOutput3-120.50,5/15/2020,63,菜鸟之伤（15）,intn,a,b,i;charp;scanf(%d,if(),5/15/2020,64,菜鸟之伤（15）,刚才程序的改进版:intn,a,b,i;charp;scanf(%d,if(.)是否还有问题？如何修改？,5/15/2020,65,菜鸟之伤（15）,总结：字符和数字的混合输入带来的问题，也是一个常常困扰使用C语言编程的同学的经典问题，关键就是程序未能及时接收回车符，而误将回车当作下一组数据的首字母，你可以通过添加一句getchar();轻松解决该问题。说明：菜鸟的经典错误，如果之前没有遇到过，很难一下子反应过来，当然，遇到一次以后就不成为问题了,5/15/2020,66,2007平方和与立方和,给定一段连续的整数，求出他们中所有偶数的平方和以及所有奇数的立方和。SampleInput1325SampleOutput42820152,5/15/2020,67,菜鸟之伤（16）,#includevoidmain()intm,n;while(scanf(“%d%d”,5/15/2020,68,菜鸟之伤（16）,总结：题目并没有保证数据是递增的，但人往往有思维定势，而很多题目的设计就是针对这一点！不要埋怨，这种训练能很好的培养我们审慎的思维习惯。说明：这种错误经历过以后还是比较容易牢记的，所以说有时候经验很重要。,5/15/2020,69,菜鸟之伤（17）,以下的程序输出什么？#include#includeintmain()intj=0;for(j=0;j5;j+)coutj=;printf(%dn,j);return0;,5/15/2020,70,菜鸟之伤（17）,期望输出：j=0j=1j=2j=3j=4,实际输出：?,5/15/2020,71,菜鸟之伤（17）,总结：在一个程序中同时使用C和C+的输出语句，很容易带来问题，原因就是输出机制不完全一样（一个不带缓冲，一个带缓冲），所以尽量避免C和C+输出语句混用。说明：这是传说中的经典错误，据说曾困扰某牛人于现场赛:-),5/15/2020,72,以2004成绩转换为例,题目描述：输入一个百分制的成绩t，将其转换成对应的等级，具体转换规则如下：90100为A;8089为B;7079为C;6069为D;059为E;输出描述：对于每组输入数据，输出一行。如果输入数据不在0100范围内，请输出一行：“Scoreiserror!”。,5/15/2020,73,菜鸟之伤（18）,#includeintmain()intt,a;while(scanf(%d,5/15/2020,74,菜鸟之伤（18）,总结：C语言中的case语句要求在每个case的处理后面都要跟break；（特殊需求除外），而如果因为不了解或者不小心而缺少部分break;则执行的效果也许会不符合你最初的设计。说明：C语言的基本功很重要,5/15/2020,75,以2046骨牌铺方格为例,题目描述：在2n的一个长方形方格中,用一个12的骨牌铺满方格,输入n,输出铺放方案的总数.输入描述：输入数据由多行组成，每行包含一个整数n,表示该测试实例的长方形方格的规格是2n(0n=50)。,5/15/2020,76,菜鸟之伤（19）,#includeintmain()inti;_int64a50=0,1,2;for(i=3;i=50;i+)ai=ai-1+ai-2;while(scanf(%d,5/15/2020,77,菜鸟之伤（19）,总结：数组下标越界是最常见的RuntimeError，也是菜鸟常犯的错误，除了需要扎实的C语言基本功，编程中的注意力集中也是需要的（很多时候不是不知道理论，而是不注意）说明：一般情况，你可以通过将数组开的大点而尽量避免这个问题,5/15/2020,78,以1425Sort为例,题目描述：给你n个整数，请按从大到小的顺序输出其中前m大的数。输入描述：每组测试数据有两行，第一行有两个数n,m(0n,m1000000)，第二行包含n个各不相同，且都处于区间-500000,500000的整数。,5/15/2020,79,菜鸟之伤（20）,#includevoidmain()intn,m,i,num1000000;while(scanf(“%d%d”,while(scanf(“%d%d”,5/15/2020,83,菜鸟之伤（21）,总结：不能把C语言中的幂运算和位运算符号混淆说明：菜鸟常犯错误，稍有经验即可避免,5/15/2020,84,以2039三角形为例,题目描述：给定三条边，请你判断一下能不能组成一个三角形。输入描述：输入数据第一行包含一个数M，接下有M行，每行一个实例，包含三个正数A,B,C。其中A,B,C1000;输出描述：对于每个测试实例，如果三条边长A,B,C能组成三角形的话，输出YES，否则NO。SampleInput2123222SampleOutputNOYES,5/15/2020,85,菜鸟之伤（22）,你中过此招吗？总结：样本是整数，不等于全部是整数！,5/15/2020,86,以3199HammingProblem为例,题目描述：Foreachthreeprimenumbersp1,p2andp3,letsdefineHammingsequenceHi(p1,p2,p3),i=1,.ascontaininginincreasingorderallthenaturalnumberswhoseonlyprimedivisorsarep1,p2orp3.Forexample,H(2,3,5)=2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,.SoH5(2,3,5)=6.输出描述：Theoutputfilemustcontainthesingleinteger-Hi(p1,p2,p3).Allnumbersininputandoutputarelessthan1018.,5/15/2020,87,菜鸟之伤（23）,典型错误没有仔细分析.也不敢尝试.直接被吓走了.,5/15/2020,88,菜鸟之伤（23）,总结：这个题目从本质上来说，和1058HumbleNumbers是