老少皆宜数学题课件市公开课获奖课件省名师优质课赛课一等奖课件.ppt

单击此处编辑母版样式,单击此处编辑幻灯片母版样式,第二层,第三层,第四层,第五层,*,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考!,ACM 程序设计,计算机学院 刘春英,1/51,10/6/,1,今天，,你 了吗？,AC,2/51,10/6/,2,每七天一星（1）：,06050016wuxingling,3/51,10/6/,3,关于期末考评补充：,平时成绩30,-分数组成,（2（1012）其它）,期末考试70（5个题目）,-分数组成（25-15-15-10-5）,4/51,10/6/,4,开胃羹（1）,几个惯用单词：,1、vertex(vertices)顶点,2、polygon 多边形,3、convex 凸,4、concave 凹,5、segment (线)段（n）;分割（v）,5/51,10/6/,5,开胃羹（2）,再来几个：,1、integer 整数,2、positive 正,3、negative (adj)负;(n)负数,4、factorial (n)阶乘;(adj)因子，阶乘,5、digital (n)数字;(adj)数字,6/51,10/6/,6,第三讲,老少皆宜之数学题,7/51,10/6/,7,ACM数学题特点分析:,题意轻易了解,算法相对简单（有些极难！）,编程比较轻易ACM/ICPC入门练习好选择,下面，分类介绍：,8/51,10/6/,8,从首届“舜宇”杯说起,9/51,10/6/,9,比赛背景,因为前一年邀请赛很多学校没有做出一道题，所以，这次比赛特意准备了几道简单题目，目标就是让大多数学校都能拿个气球回去，也好有个交待，于是有,10/51,10/6/,10,第一类,弱 智 型,11/51,10/6/,11,Problem A:Let the Balloon Rise,12/51,10/6/,12,题目评述：,1.一个让你看到后兴奋题目,2.只要懂点C或者C+，就可处理该问题。,13/51,10/6/,13,1004题目分析：,该题算法思想比较简单，就是对输入字符串进行比较和统计。值得注意一点是：,假如用C语言来写，要注意可能会把第一个数字后“回车符”误认为是第一个串，字符串比较也要用函数和循环语句。,而C+则在处理字符串方面较为方便。,14/51,10/6/,14,Problem E:Elevator,15/51,10/6/,15,实际上，这是此次比赛最简单一题，浙大、浙工大等当初训练水平相对较高学校基本上10分钟之内处理该题，这也是一个没有算法题目。,这种题目大家不会错过,题目评述：,16/51,10/6/,16,不要分析了吧,17/51,10/6/,17,第二类 基 本 型,18/51,10/6/,18,Problem F:FatMouse Trade,19/51,10/6/,19,题目特点：,这个题目比前面两个题目稍难，不过属于能一眼看出处理方法题目。只要静下心，还是比较轻易处理。,20/51,10/6/,20,1009算法分析：,输入（J,F 放入数组）,对数组排序（按效益，降序）,输出（按效益高低有序交易）,21/51,10/6/,21,第三类 技 巧 型,22/51,10/6/,22,先来看一个简单题目铺垫一下:,23/51,10/6/,23,1021 Fibonacci Again,24/51,10/6/,24,题目分析：,能被3整除整数特点？,还要看程序吗？,假如两个数和能被3整除，这两个数有什么特点？,关于能否被3整除，这两个数一共有多少种组合？,25/51,10/6/,25,Hdoj_1021程序清单：,#include,int main(),long n;,while(scanf(%ld,&n)!=EOF),if(n%8=2|n%8=6),printf(yesn);,else,printf(non);,return 0;,26/51,10/6/,26,回到正题,27/51,10/6/,27,Problem B:Number Sequence,28/51,10/6/,28,题目特点：,这个题目是一个比较经典ACM竞赛题，尽管在真正大赛中这个题目可能算比较简单，但在此次比赛中，本题难度属于中等，能够说，能做出本题队伍基本都有二等奖以上。,但假如不认真分析，有可能会掉入陷阱。,29/51,10/6/,29,Question:,暴力能处理问题吗？,30/51,10/6/,30,Why?,31/51,10/6/,31,题目分析：,对于这种题目，千万不能蛮干！实际上，有经验同学看到本题目标数据规模，很快就能知道：这类题目有规律可循。,32/51,10/6/,32,现在对这题有什么想法,?,33/51,10/6/,33,第四类 纸老虎型,34/51,10/6/,34,HDOJ_1071 The Area,35/51,10/6/,35,第一眼：傻了,36/51,10/6/,36,再一看,37/51,10/6/,37,抛物线公式：y=ax2+bx+c,已知三点 -a、b、c 系数,公式已知 -怎样求面积？,会简单积分吗？,38/51,10/6/,38,该你思索了,感觉怎么样？,39/51,10/6/,39,思索题(1)：,（Ural Collegiate Programming Contest 1998）,contains two integer numbers M and N in the range from 1 to 1000000000 separated with space(s).,Output,Output should contain the length of the shortest route.,Sample Input,6 12,Sample Output,3,41/51,10/6/,41,思索：,要输出结果和哪些原因相关？,请发表看法。,42/51,10/6/,42,思索题(2)：,（3月4日HDOJ练习赛题目）,43/51,10/6/,43,关键点分析：,1、暴力复杂度是多少？,2、哪些陷阱？,3、关键在哪？,4、顺利应该多长时间？,44/51,10/6/,44,数学公式:,1、这个大家都会：1+2+3+4+n=n(n+1)/2,2、这个有些同学忘记了：,1*1+2*2+3*3+n*n=n(n+1)(2n+1)/6,3、合并后得到n(n+1)(n2)/3,45/51,10/6/,45,Any question?,46/51,10/6/,46,课后作业（简单数学题）,47/51,10/6/,47,HDOJ作业：,一、DIY在线作业(2):,ACM ProgrammingExercise（2）by LCY,二、常规练习（包含以上作业）,1004、1005、1008、1009,10121014、10191021,1049、1060、1061、1066,1071、1178、1108、1030,1597,48/51,10/6/,48,下次课内容：,递推求解,49/51,10/6/,49,课后一定要练习！,50/51,10/6/,50,See you next week.,Thank you!,51/51,10/6/,51,