《ACM課件lecture老少皆宜數(shù)學題.ppt》由會員分享，可在線閱讀，更多相關《ACM課件lecture老少皆宜數(shù)學題.ppt（75頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、ACM程序設計,2020/6/11,2,第二講,老少皆宜之數(shù)學題,2020/6/11,3,今天，,你了嗎？,AC,2020/6/11,4,開胃羹（1）,幾個常用單詞：1、vertex(vertices)頂點2、polygon多邊形3、convex凸的4、concave凹的5、segment(線)段（n）;分割（v）,2020/6/11,5,開胃羹（2）,再來幾個：1、integer整數(shù)2、positive正的3、negative(adj)負的;(n)負數(shù)4、factorial(n)階乘;(adj)因子的，階乘的5、digital(n)數(shù)字;(adj)數(shù)字的,2020/6/11,6,ACM數(shù)學題
2、特點分析:,題意容易理解算法相對簡單（有些很難的?。。┚幊瘫容^容易ACM/ICPC入門練習的好選擇下面，分類介紹：,2020/6/11,7,從首屆“舜宇”杯說起,2020/6/11,8,比賽背景,由于前一年的邀請賽很多學校沒有做出一道題，所以，這次的比賽特意準備了幾道簡單的題目，目的就是讓大多數(shù)的學校都能拿個氣球回去，也好有個交待，于是有…,,2020/6/11,9,第一類,傻瓜型,2020/6/11,10,1004:LettheBalloonRise,2020/6/11,11,ProblemDescription,Contesttimeagain!Howexciteditistoseebal
3、loonsfloatingaround.Buttotellyouasecret,thejudgesfavoritetimeisguessingthemostpopularproblem.Whenthecontestisover,theywillcounttheballoonsofeachcolorandfindtheresult.Thisyear,theydecidetoleavethislovelyjobtoyou.,2020/6/11,12,Input,Inputcontainsmultipletestcases.EachtestcasestartswithanumberN(0
4、,2020/6/11,36,InputInputconsistsofasequenceoflines,eachcontaininganintegern.(n<1,000,000).OutputPrinttheword"yes"if3divideevenlyintoF(n).Printtheword"no"ifnot.,2020/6/11,37,SampleInput012345,SampleOutputnonoyesnonono,2020/6/11,38,題目分析：,能被3整除的整數(shù)的特點？,如果兩個數(shù)的和能被3整除，這兩個數(shù)有什么特點？,關于能否被3整除，這兩個數(shù)一共有多少種組合？,2020
5、/6/11,39,Hdoj_1021程序清單：,#includeintmain(){longn;while(scanf("%ld",},2020/6/11,40,回到正題——大錘搞定,,2020/6/11,41,1005:NumberSequence,2020/6/11,42,Anumbersequenceisdefinedasfollows:f(1)=1,f(2)=1,f(n)=(A*f(n-1)+B*f(n-2))mod7.GivenA,B,andn,youaretocalculatethevalueoff(n).,ProblemDescription,2020/6/11,43,Input
6、Theinputconsistsofmultipletestcases.Eachtestcasecontains3integersA,Bandnonasingleline(1<=A,B<=1000,1<=n<=100,000,000).Threezerossignaltheendofinputandthistestcaseisnottobeprocessed.OutputForeachtestcase,printthevalueoff(n)onasingleline.,2020/6/11,44,SampleInput1131210000SampleOutput25,2020/6/11,45,題
7、目特點：,這個題目是一個比較典型的ACM競賽題，盡管在真正的大賽中這個題目可能算比較簡單的，但在本次比賽中，本題難度屬于中等，可以說，能做出本題的隊伍基本都有二等獎以上。但如果不認真分析，有可能會掉入陷阱。,2020/6/11,46,Question:,暴力能解決問題嗎？,2020/6/11,47,拒絕暴力～,2020/6/11,48,題目分析：,對于這種題目，千萬不能蠻干！實際上，有經(jīng)驗的同學看到本題目的數(shù)據(jù)規(guī)模，很快就能知道：這類題目有規(guī)律可循。,2020/6/11,49,現(xiàn)在對這題有什么想法,???,2020/6/11,50,第四類,紙老虎型,2020/6/11,51,HDOJ_1071
8、TheArea,2020/6/11,52,SampleInput25.0000005.0000000.0000000.00000010.0000000.00000010.00000010.0000001.0000001.00000014.0000008.222222SampleOutput33.3340.69,2020/6/11,53,第一眼：傻了…,2020/6/11,54,再一看——,?,2020/6/11,55,拋物線公式：y=ax^2+bx+c,已知三點-〉a、b、c系數(shù),公式已知-〉如何求面積？,會簡單積分嗎？,分析過程：,該你思考了…,感覺怎么樣？,2020/6/11,57,思考題
9、：,1178Heritagefromfather,2020/6/11,58,FamousHarryPotter,whoseemdtobeanormalandpoorboy,isactuallyawizard.Everythingchangedwhenhehadhisbirthdayoftenyearsold.AhugemancalledHagridfoundHarryandleadhimtoanewworldfullofmagicpower.Ifyouvereadthisstory,youprobablyknowthatHarrysparentshadlefthimalotofgoldcoin
10、s.HagridleadHarrytoGringotts(thebankholdupbyGoblins).Andtheysteppedintotheroomwhichstoredthefortunefromhisfather.Harrywasastonishing,coztherewerepilesofgoldcoins.ThewayofpackingthesecoinsbyGoblinswasreallyspecial.Onlyonecoinwasonthetop,andthreecoinsconsistedantrianglewereonthenextlowerlayer.Thethird
11、layerhassixcoinswhichwerealsoconsistedantriangle,andsoon.Ontheithlayertherewasantrianglehaveicoinseachedge(totallyi*(i+1)/2).Thewholeheapseemedjustlikeapyramid.Goblinstillknewthetotalnumofthelayers,soitsupyoutohelpHarrytofigureoutthesumofallthecoins.,ProblemDescription,2020/6/11,59,InputTheinputwill
12、consistofsomecases,eachcasetakesalinewithonlyoneintegerN(0
13、1*1+2*2+3*3+…+n*n=n(n+1)(2n+1)/63、合并后得到n(n+1)(n+2)/3,,2020/6/11,63,問題一：科學計數(shù)法的格式,不知道？eE……,用%e:用%.2e,如何實現(xiàn)格式要求？,2020/6/11,64,解決方案,方法一：把輸出先輸出到字符串，再去掉e之后的0a=(1.0*n*n*n+3.0*n*n+2.0*n)/6.0;sprintf(str,"%.2E",a);len=strlen(str);for(i=0;i<=4;i++)printf("%c",str[i]);for(i=6;str[i]!=\0;i++)if(i==len-1||str[i]!
14、=0)printf("%c",str[i]);printf("\n");,2020/6/11,65,方法二：尾數(shù)和指數(shù)分開控制格式a=(1.0*n*n*n+3.0*n*n+2.0*n)/6.0;b=log10(a);printf("%.2lf",a/pow(10,b));printf("E%d\n",b);,2020/6/11,66,Anyquestion?,2020/6/11,67,課后任務：,1004、1005、1008、1009、10601012～1014、1019～1021、10611049、1178、1108、10301071、1597,2020/6/11,68,提示：關于Prese
15、ntationError的錯誤,2016輸出n個數(shù)，用空格隔開常見錯誤：for(i=1;i<=n;i++)printf(“%d“,a[i]);printf(“\n“);最后一個數(shù)之后也有空格造成PresentationError錯誤,2020/6/11,69,解決辦法,1、方法一for(i=1;i
16、ncludeintmain(){intm,n,t;inti,j;intflag;inta,b,c;flag=0;,不知道m(xù)到n有多少個水仙花數(shù)，怎么控制最后一個數(shù)后不空格？,2020/6/11,71,while(scanf("%d%d",,2020/6/11,72,if(i==j){printf("%d",i);flag=1;}},if(i==j){if(flag==1)printf("");printf("%d",i);flag=1;}},不知道m(xù)到n有多少個水仙花數(shù)，怎么控制最后一個數(shù)后不空格？,2020/6/11,73,if(flag==0)printf("no");printf("\n");}return0;},2020/6/11,74,下一講：,遞推求解,2020/6/11,75,ThankYou~,
ACM課件lecture老少皆宜數(shù)學題.ppt
