ACM入门教程-数学问题.ppt

ACM程序设计竞赛入门,浙江工业大学田贤忠txz,2019/11/25,1,2019/11/25,2,第二讲,数学问题,2019/11/25,3,引例：本校OJ1207,Inmanyapplicationsverylargeintegersnumbersarerequired.Someoftheseapplicationsareusingkeysforsecuretransmissionofdata,encryption,etc.Inthisproblemyouaregivenanumber,youhavetodeterminethenumberofdigitsinthefactorialofthenumber.,2019/11/25,4,InputInputconsistsofseverallinesofintegernumbers.Thefirstlinecontainsanintegern,whichisthenumberofcasestobetested,followedbynlines,oneinteger1m107oneachlineOutputTheoutputcontainsthenumberofdigitsinthefactorialoftheintegersappearingintheinput.,SampleInput21020,SampleOutput719,2019/11/25,5,如何求位数？,算出阶乘，循环求位数？阶乘怎么存储？一定要算出阶乘吗？n!的位数：(int)log10(n!)+1(int)(log10(1)+log10(2)+log10(3)+log10(n)+1,2019/11/25,6,代码怎么写？超时问题怎么解决？能不能降低计算量？有没有更简便的公式？,2019/11/25,7,如果不知道高效的计算公式？,(int)(log10(1)+log10(2)+log10(3)+log10(n)对于每个输入的数都要按上述公式计算如何避免重复计算？先算小数的位数，在此基础上再算大数。（1）每次找最小值？需要存储数据和位数的计算（2）先把算出的log10存储？,2019/11/25,8,计算机程序设计艺术中给出了另一个公式n!=sqrt(2*n)*(n/e)n)*(1+1/(12*n)+1/(288*n*n)+O(1/n3)=acos(-1)e=exp(1)两边对10取对数忽略log10(1+1/(12*n)+1/(288*n*n)+O(1/n3)log10(1)=0得到公式log10(n!)=log10(sqrt(2*pi*n)+n*log10(n/e),2019/11/25,9,数学问题的特点：,题意容易理解；数学关联性一般比较大；语言的关联性相对较小；但有时需要相关策略来规避过高的复杂度。要注意复杂度问题；适合ACM/ICPC入门练习。每次竞赛一般会有1-2个数学问题。,2019/11/25,10,常用单词：1、integer整数（不一定就是32位的）2、positive正的3、negative(adj)负的;(n)负数4、factorial(n)阶乘;(adj)因子的，阶乘的5、digital(n)数字;(adj)数字的6、multiple倍数7、multiplication乘法运算,2019/11/25,11,常用单词：（图形相关）1、vertex(vertices)顶点2、polygon多边形3、convex凸的4、concave凹的5、segment(线)段（n）;分割（v）,2019/11/25,12,数学问题（分类分析）,2019/11/25,13,第一类,简单问题,HDOJ1004:LettheBalloonRise,HDOJ1004:LettheBalloonRise,题目描述：输入：第一行输入气球的个数n，以下n行输入n个气球的颜色，n为0时结束。输出：哪种颜色的气球数目最多,2019/11/25,15,HDOJ1004:LettheBalloonRise,SampleInput5greenredblueredred3pinkorangepink0,Sampleoutputredpink,2019/11/25,16,2019/11/25,17,题目评述：,1.一个让你看到后兴奋的题目,2.只要懂点C或者C+，就可解决该问题。,2019/11/25,18,1004题目分析：,该题算法思想比较简单，就是对输入的字符串进行比较和统计。值得注意的一点是：如果用C语言来写，要注意可能会把第一个数字后的“回车符”误认为是第一个串，字符串的比较也要用函数和循环语句。而C+则在处理字符串方面较为方便。,2019/11/25,19,Elevator,ProblemDescriptionThehighestbuildinginourcityhasonlyoneelevator.ArequestlistismadeupwithNpositivenumbers.Thenumbersdenoteatwhichfloorstheelevatorwillstop,inspecifiedorder.Itcosts6secondstomovetheelevatoruponefloor,and4secondstomovedownonefloor.Theelevatorwillstayfor5secondsateachstop.Foragivenrequestlist,youaretocomputethetotaltimespenttofulfilltherequestsonthelist.Theelevatorisonthe0thflooratthebeginninganddoesnothavetoreturntothegroundfloorwhentherequestsarefulfilled.,2019/11/25,20,InputTherearemultipletestcases.EachcasecontainsapositiveintegerN,followedbyNpositivenumbers.Allthenumbersintheinputarelessthan100.AtestcasewithN=0denotestheendofinput.Thistestcaseisnottobeprocessed.OutputPrintthetotaltimeonasinglelineforeachtestcase.SampleInput1232310SampleOutput1741,constintUP=6;constintDOWN=4;constintSTOP=5;intnCase,floor;while(cinnCase,2019/11/25,21,2019/11/25,22,第二类大数问题,2019/11/25,23,一、大数加法HDU1002：A+BProblemII,InputThefirstlineoftheinputcontainsanintegerT(1ab,2019/11/25,30,第三类注重分析的问题,2019/11/25,31,先看一个简单的题目:,2019/11/25,32,1331：取石子问题,Description:小明是个游戏迷，这不，今天他又和小刚一起玩“拿石子”的游戏。游戏规则是2个人轮流拿石子，一次可以拿1颗或3颗，规定谁取到最后一颗石子就是谁赢。小明和小刚商量后决定每次都是小明先取。小明与小刚都是游戏高手，该赢的局绝不会输。在知道石子总数的情况下，小明想快速知道每次的输赢情况。,2019/11/25,33,分析：,各取一次共有三种情况：共取走2颗石子共取走4颗石子共取走6颗石子设有石子S.方案取了N1次，方案取了N2次，方案取了N3次后，还剩下K个石子。S=2*N1+4*N2+6*N3+KK的取值有三种情况：0，1，3。K=1,3则先取方胜。反之，另一方胜。当S为偶数时，后取方胜，反之，先取方胜。,2019/11/25,34,杭电OJ：1021FibonacciAgain,ProblemDescriptionThereareanotherkindofFibonaccinumbers:F(0)=7,F(1)=11,F(n)=F(n-1)+F(n-2)(n=2).Input：Inputconsistsofasequenceoflines,eachcontaininganintegern.(n1,000,000).Output：Printthewordyesif3divideevenlyintoF(n).Printthewordnoifnot.,SampleInput012345,SampleOutputnonoyesnonono,2019/11/25,35,题目分析：,判断某一项是否能被3整除是否需要把某一项的值求出来，进行整除判断？能被3整除的整数的特点？关于能否被3整除，这样的项在排列上是否有规律？（找出规律）第0项除以3余1，第1项除以3余2，第2项整除，第3项除以3余2，第4项除以3余2，第5项除以3余1，第6项整除，第7项除以3余1，第8项除以3余1，第9项除以3余2，第7项整除.,2019/11/25,36,Hdoj_1021程序清单：,#includeintmain()longn;while(scanf(%ld,2019/11/25,37,这个问题主要在于找出规律；程序编写很简单；考查的是分析问题的能力。,2019/11/25,38,第四类公式型,HDOJ_1071TheArea,2019/11/25,40,抛物线公式：y=ax2+bx+c,已知三点-a、b、c系数,公式已知-如何求面积？,积分问题,2019/11/25,41,递推求解,还记得Fibonacci问题吧？F(0)=F(1)=1;F(n)=F(n-1)+F(n-2);,2019/11/25,42,1182：母牛问题,Description:假设单性繁殖成立，若一头母牛，从出生起第四个年头开始，每年生一头母牛，而生出的小母牛在之后的第四年也将具有生殖能力。按此规律，第n年时有多少头母牛？Input:输入数据中不多于50个整数（1n40）。Output:对于每个n，输出其第n年的母牛数，每个结果对应一行输出。,2019/11/25,43,如何得出递推公式？,列出前面几个数据：1112346假设规模小于N的情况已经得到解决重点分析：当规模扩大到N时，如何枚举出所有的情况，并且要确保对于每一种子情况都能用已经得到的数据解决。f(n）=f(n-1)+f(n-3)(n-3年存在的牛在n年均可以生出一头小牛）,2019/11/25,44,再来看难一点的问题,2019/11/25,45,2050：折线分割平面,2019/11/25,46,这个问题其实属于递推问题，你们比我更擅长，呵呵,2019/11/25,47,先看直线分割平面问题,经典结论：平面内有n条直线，任何两条不平行，任何三条不过同一点；这n条直线可以把平面分成n(n+1)/2+1个部分。可用数学归纳法证明。,2019/11/25,48,公式的推导,F(1)=2;F(n)=F(n-1)+n;(第n条直线与n-1条相交，将增加n个区域）F(n)=n+n-1+n-2+.+2+f(1)=n(n+1)/2+1,2019/11/25,49,回到折线问题：,一个折线可以看成两条直线相交，并去掉角的一边；可推出公式：f(n)=f(n-1)+(2n-1)+2n-2,2019/11/25,50,f(n)=f(n-1)+(2n-1)+2n-2f(1)=2F(n)=2n+2n-1+2n-2+2n-3+.+4+3-2*(n-1)+f(1)=2n-1+2n-2+.+4+3+2+1+1=2n*(2n-1)/2+1=2n(n-1)+1=2*n2-n+1注意：两直线直接带入公式：n(n+1)/2+1,2019/11/25,51,Ok,内容已经不少了来几个思考题,2019/11/25,52,思考（1）HDOJ1465:不容易系列之一(递推求解),某人写了n封信和n个信封，如果所有的信都装错了信封。求所有的信都装错信封,共有多少种不同情况。,分析,总和就是(n-1)*(f(n-1)+f(n-2),2019/11/25,53,#includeintmain()intn;_int64i,a21=0;a2=1;a3=2;for(i=4;i=20;i+)ai=(i-1)*(ai-1+ai-2);while(scanf(%d,2019/11/25,54,2019/11/25,55,思考（2）HDOJ1030:Delta-wave,ThetravellerneedstogofromthecellwithnumberMtothecellwithnumberN.Thetravellerisabletoenterthecellthroughcelledgesonly,hecannottravelfromcelltocellthroughvertices.Thenumberofedgesthetravellerpassesmakesthelengthofthetravellersroute.WritetheprogramtodeterminethelengthoftheshortestrouteconnectingcellswithnumbersNandM.,题目大意：,InputInputcontainstwointegernumbersMandNintherangefrom1to1000000000separatedwithspace(s).OutputOutputshouldcontainthelen