《ACM課件lecture老少皆宜數(shù)學(xué)題.ppt》由會員分享,可在線閱讀,更多相關(guān)《ACM課件lecture老少皆宜數(shù)學(xué)題.ppt(75頁珍藏版)》請在裝配圖網(wǎng)上搜索。
1、ACM程序設(shè)計,2020/6/11,2,第二講,老少皆宜之數(shù)學(xué)題,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ù)學(xué)題
2、特點分析:,題意容易理解算法相對簡單(有些很難的?。。┚幊瘫容^容易ACM/ICPC入門練習(xí)的好選擇下面,分類介紹:,2020/6/11,7,從首屆“舜宇”杯說起,2020/6/11,8,比賽背景,由于前一年的邀請賽很多學(xué)校沒有做出一道題,所以,這次的比賽特意準備了幾道簡單的題目,目的就是讓大多數(shù)的學(xué)校都能拿個氣球回去,也好有個交待,于是有…,,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ù)有什么特點?,關(guān)于能否被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)驗的同學(xué)看到本題目的數(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,問題一:科學(xué)計數(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,課后任務(wù):,1004、1005、1008、1009、10601012~1014、1019~1021、10611049、1178、1108、10301071、1597,2020/6/11,68,提示:關(guān)于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~,