(hduacm2010版-09)筛选法及预处理
2019/4/20,1,第二讲,筛选法及预处理 （附-菜鸟的21个经典错误）,2019/4/20,2,例1-素数判断,题目描述： 给定一个N（1N100000），请判断N是否是素数，如果是素数，则请输出YES，否则输出NO。 Sample Input： 4 5 Sample Output: NO YES,2019/4/20,3,常见朴素算法,#include int main() int i,n; while(scanf(“%d“, ,2019/4/20,4,朴素算法优化版本,#include #include int main() int i,n,x; while(scanf(“%d“, ,2019/4/20,5,例2-求所有素数,题目描述： 给定一个N（1N100000），请按照递增次序输出所有小于等于N的素数。 Sample Input： 10 Sample Output: 2 3 5 7,2019/4/20,6,题目分析,题目特点：不是求一个素数，而是求一段素数（一种常见的情况就是求指定范围的所有的素数） 如果还用常规求素数方法，可能的问题是？,2019/4/20,7,筛选法求素数,基本思想：素数的倍数一定不是素数 实现方法：用一个长度为N+1的数组保存信息（0表示素数，1表示非素数），先假设所有的数都是素数（初始化为0），从第一个素数2开始，把2的倍数都标记为非素数（置为1），一直到大于N；然后进行下一趟，找到2后面的下一个素数3，进行同样的处理，直到最后，数组中依然为0的数即为素数。 说明：整数1特殊处理即可。,2019/4/20,8,效果演示,2019/4/20,9,效果演示,2019/4/20,10,效果演示,2019/4/20,11,效果演示,2019/4/20,12,效果演示,2019/4/20,13,效果演示,2019/4/20,14,效果演示,2019/4/20,15,效果演示,2019/4/20,16,效果演示,2019/4/20,17,参考代码（筛选法）,#include #include int a100001; int main() int i,j,n; while(scanf(“%d“, ,2019/4/20,18,例3-求素数个数,题目描述： 给定一个N（1N100000），请输出小于等于N的素数的个数。 测试数据有C组，（1C100000）. Sample Input： 10 Sample Output: 4,2019/4/20,19,常规筛选法代码,#include #include int a100001; int main() int i,j,n,count; while(scanf(“%d“, ,2019/4/20,20,题目分析(1),题目特点：数据量超大！ 分析：前面算法的瓶颈：每组数据都求素数. 如何改进以加快求解速度？ 可否一次筛选，多次查找？ 这就是预处理思想,2019/4/20,21,预处理参考代码,#include #include int a100001; int main() int i,j,n,count; for(i=2;i=100000;i+) if(ai=0) for(j=i+i;j=100000;j+=i) aj=1; while(scanf(“%d“, ,2019/4/20,22,题目分析(2),相对之前，算法有否改进； 但依然风险很大 哪个地方依然影响效率？ 如何改进？ 请自己完成,2019/4/20,23,筛选法思想的其他应用,1215 七夕节 题目大意：求一个数的真因子之和 Sample Input： 2 10 20 Sample Output： 8 22,2019/4/20,24,题目分析,本题特点同前例题：数据量很大（可达50万），每个数据也不小，同样可达50万。 常见方法：预处理筛法 思考：这个筛法和求素数的筛法细节区别在哪里？ 再思考：如果是求一个数的因子的数量，哪里需要变化？,2019/4/20,25,1215参考代码,略 :),2019/4/20,26,菜鸟的21个经典错误,2019/4/20,27,以1089 AB为例,Sample Input 1 5 10 20 Sample Output 6 30,2019/4/20,28,菜鸟之伤（1）,#include void main() int a,b; scanf(“%d%d”, ,2019/4/20,29,菜鸟之伤（1）,总结： 程序不能处理多组数据的问题是最常见的入门问题，只要掌握几种常见的类型，就可以轻松掌握了，具体处理方法曾在第一次课件有详细描述，这里省略了,2019/4/20,30,菜鸟之伤（2）,#include void main() int a,b; while(scanf(“%d%d”, ,2019/4/20,31,菜鸟之伤（2）,总结：文件结束符EOF的值是-1而不是0，所以while(scanf()!=0)常常会因为死循环而造成TLE，这个必须牢记。 说明：不仅仅菜鸟，很多老鸟也常常因为不注意这点而犯错误，而且还常常因为想不到会犯这种低级错误而想不到原因。,2019/4/20,32,菜鸟之伤（3）,#include void main() int a,b; while(scanf(“%d%d”, ,2019/4/20,33,菜鸟之伤（3）,总结：while 或者 for循环的条件外面误加了分号，编译不影响，但是结果循环体没有真正得到多次执行； 说明：菜鸟常犯的错误，往往因为编译能通过而不能迅速察觉，尤其比赛中 提醒：当你将scanf();语句加上while循环以处理多组数据问题的时候尤其注意因为之前有分号，很容易忘记去掉！,2019/4/20,34,菜鸟之伤（4）,#include void main() int a,b; while(scanf(“%d%d”, ,2019/4/20,35,菜鸟之伤（4）,总结： C语言中，赋值符号和判断是否相等的逻辑符号具有完全不同的含义，往往因为我们的习惯问题，在编程中误将判断是否相等的逻辑符号写成赋值符号。同样的，这种失误也会因为不影响编译而影响查错的时间。 说明：菜鸟常犯的错误，但是有过几次教训就会牢记了，呵呵,2019/4/20,36,以1001 Sum Problem为例,Sample Input 1 100 Sample Output 1 5050,2019/4/20,37,菜鸟之伤（5）,#include void main() int i,n,s; while(scanf(“%d”, ,2019/4/20,38,菜鸟之伤（5）,总结： 忘记变量的初始化是典型的菜鸟问题，不必紧张，多经历几次就牢记了 说明：普通变量的初始化还比较容易查找，而用来保存计算结果的数组的初始化更是容易忘记！,2019/4/20,39,菜鸟之伤（6）,#include void main() int i,n,s=0; while(scanf(“%d”, ,2019/4/20,40,菜鸟之伤（6）,总结：变量初始化放在循环外，是一个典型的ACM初级错误，因为ACM赛题的多组测试特性，如果不能在循环内初始化，将只能确保第一组数据没问题，而很多入门者习惯只测试一组数据，很容易忽略这个问题。 说明：菜鸟常犯的错误，关键是要理解为什么这样会有问题，真正理解后，修改也就不难了。,2019/4/20,41,菜鸟之伤（7）,#include void main() int i,n,s; while(scanf(“%d”, ,2019/4/20,42,菜鸟之伤（7）,总结： 数组越界还能在提交后收到Runtime Error的信息反馈，而运算中的数据溢出则往往只能收到Wrong Answer的错误提示，所以这种错误往往容易被误导成算法问题； 说明： 不仅菜鸟，就是大牛甚至大神，也常常犯这种错误，只是情况复杂些而已,2019/4/20,43,菜鸟之伤（8）,#include void main() int i,n,s; while(scanf(“%d”, ,2019/4/20,44,菜鸟之伤（8）,总结： 当两个整数进行运算的时候，运算结果一定还是整数，所以不要因为常规数学惯性思维的影响而认为结果可能为浮点数； 而不同数据类型一同运算的时候，运算结果的数据类型和相对复杂的类型一致（比如 整数+实数，结果类型是实数）,2019/4/20,45,菜鸟之伤（9）,#include void main() int i,n,s; while(scanf(“%d”, ,2019/4/20,46,菜鸟之伤（9）,总结： 写for或者while等任何循环语句的时候，不管循环体内有几个语句，务必养成都加上一对大括号的好习惯。 常常碰到的情况是这样的本来循环体内只有一条语句，确实不用大括号，但是在修改程序的过程中，循环体内增加了其他语句，而这时却忘记了添加大括号！ 所以说好习惯很重要！,2019/4/20,47,菜鸟之伤（10）,#include void main() int i,n,s; while(scanf(“%d”, ,2019/4/20,48,菜鸟之伤（10）,总结： 这也是一个经典错误，虽然为循环体加了大括号，但是并没有包含全部的信息，造成的后果是只有一次输出尽管对于每组数据都处理了，但是只输出最后一组结果。 由于很多同学习惯每次只测试一组数据，就更容易忽略这个错误了. 再次证明好习惯很重要！,2019/4/20,49,菜鸟之伤（11）,假设不会中间溢出，下面的程序是否有问题？ #include void main() int i,n,s; while(scanf(“%d”, ,2019/4/20,50,菜鸟之伤（11）,总结： 这也是受数学习惯影响而可能出现的一个错误，当然，这个错误很好检查，因为编译不能通过的 总结出这个只是因为确实会出现这个情况，而对于极度没有编程经验的同学来说，有时候也会带来困扰,2019/4/20,51,还是以AB为例,题目描述：计算AB的值，输入数据每行包含2个正整数，如果输入数据是两个负数，则结束输入。 Sample Input 1 5 -1 -1 Sample Output 6,2019/4/20,52,菜鸟之伤（12）,#include void main() int a,b; while(scanf(“%d%d”, ,2019/4/20,53,菜鸟之伤（12）,总结：正如判断相等要用“=”一样，C语言中进行逻辑与的运算也是需要两个字符“&&”，类似的逻辑或运算也是两个字符“|”，如果是单个的字符，含义就完全不同了,2019/4/20,54,菜鸟之伤（13）,上一个程序的改进版： #include void main() int a,b; while(scanf(“%d%d”, ,2019/4/20,55,菜鸟之伤（13）,总结：题目描述是负数结束输入，Sample Input最后给出的是-1，如果读题不仔细，很容易陷入思维定势，而会不加思索在程序中用-1判断，这样就真的会发生不幸的事件尽管我也认为这个陷阱有点阴，而且未必有很大意义，但是题目并没错，而你确实读题不仔细 说明：算是经典的小陷阱，现在很少出现了,2019/4/20,56,继续以AB为例,题目描述：给定2个整数A和B，如果A+B0，请输出”OK!”，否则请输出”No” Sample Input 1 5 1 -5 Sample Output OK! No,2019/4/20,57,菜鸟之伤（14）,#include void main() int a,b; while(scanf(“%d%d”, ,20
