ACM入门简单数学题.ppt

ACM程序设计,杭州电子科技大学刘春英acm,2020/4/28,2,今天，,你了吗？,AC,2020/4/28,3,每周一星（1）：,XS,2020/4/28,4,第二讲,基础数学题,2020/4/28,5,课前的一些问题：,一、关于课件二、关于教材三、关于选课,2020/4/28,6,“依然”从简单题说起：,SUM(n)=1+2+3+.+nYoumayassumetheresultwillbeintherangeof32-bitsignedinteger.Sampleinput:10Sampleoutput:55,2020/4/28,7,很常见的一种写法：,#includeintmain()intn,i,sum=0;scanf(%d,2020/4/28,8,其它方法？,SUM(n)=1+2+3+.+n=n*(n+1)/2什么风险？如何处理？,2020/4/28,9,OJ评测原理,2020/4/28,10,有什么问题呢？,享受今天的慢车旅程吧,2020/4/28,11,HDOJ_1008:Elevator,2020/4/28,12,这是2004浙江省赛最简单的一题，当时训练水平相对较高的学校基本上10分钟之内解决该题，这是一个没有算法的简单模拟题目。入门训练的好选择,题目评述：,2020/4/28,13,A+BforPolynomials,SampleInput212.403.2221.510.5SampleOutput321.512.903.2本题数据结构？（针对不同数据特点）本题注意事项？,2020/4/28,14,HDOJ_1108最小公倍数,给定两个正整数，计算这两个数的最小公倍数。Input：1014Output：70思考：如何求最小公倍数(LCM)？LCM=GCD,2020/4/28,15,GCD求解过程,x=2,2020/4/28,16,欧几里德算法,intgcd(intda,intxiao)inttemp;while(xiao!=0)temp=da%xiao;da=xiao;xiao=temp;return(da);,思考：递归的形式如何写？,2020/4/28,17,HDOJ_1061RightmostDigit,GivenapositiveintegerN,youshouldoutputthemostrightdigitofNN(1=N=1,000,000,000).3476,2020/4/28,18,HDOJ_1061RightmostDigit,数据规模很大暴力方法该打基本思路规律,2020/4/28,19,HDOJ_2035人见人爱AB,求AB的最后三位数表示的整数（1=A,B=10000）231268984,2020/4/28,20,HDOJ_2035人见人爱AB,最暴力的暴力？改进的暴力？如果：(1=A,B=100000000)怎么办？二分加速？,2020/4/28,21,1021FibonacciAgain,2020/4/28,22,题目分析：,能被3整除的整数的特点？,还要看程序吗？,如果两个数的和能被3整除，这两个数有什么特点？,关于“和”能否被3整除，这两个数一共有多少种组合？,会不会出现某连续两项和后面连续两项相等的情况？如果出现，能得到什么信息？,2020/4/28,23,Hdoj_1021程序清单：,#includeintmain()longn;scanf(%ld,2020/4/28,24,HDOJ_1005:NumberSequence,2020/4/28,25,Question:,暴力（Brute-Force）能解决问题吗？,2020/4/28,26,题目分析：,对于这种题目，千万不能蛮干！实际上，有经验的同学看到本题目的数据规模，很快就能知道：这类题目有规律可循。,2020/4/28,27,现在对这题有什么想法,?,2020/4/28,28,附：非典型数学题,HDOJ_1205吃糖果Gardon吃糖果时有个特殊的癖好，就是不喜欢将一样的糖果放在一起吃，喜欢先吃一种，下一次吃另一种；可是Gardon不知道是否存在一种吃糖果的顺序使得他能把所有糖果都吃完？请你写个程序帮忙计算一下对于每组数据，输出一行，包含一个Yes或者No。,2020/4/28,29,请自己仔细分析.,哪位同学做个陈述？,2020/4/28,30,课后任务：,完成在线练习：201309ACM程序设计作业（2）刘春英老师特别提醒：作业务必尽力完成（第一次的作业尚未完成的，一定要补上）作业密码：helloworld,2020/4/28,31,WelcometoHDOJ,ThankYou,