ACM入門教程(2-數(shù)學(xué)問題)

2024/5/81ACM程序競(jìng)賽入門

開課號(hào)：85019

授課教師：王英姿2024/5/82第二講數(shù)學(xué)問題2024/5/83引例：本校OJ1207

〔相似題〕杭電1018，求n！的位數(shù)

Inmanyapplicationsverylargeintegersnumbersarerequired.Someoftheseapplicationsareusingkeysforsecuretransmissionofdata,encryption,etc.Inthisproblemyouaregivenanumber,youhavetodeterminethenumberofdigitsinthefactorialofthenumber.

2024/5/84InputInputconsistsofseverallinesofintegernumbers.Thefirstlinecontainsanintegern,whichisthenumberofcasestobetested,followedbynlines,oneinteger1≤m≤107oneachlineOutputTheoutputcontainsthenumberofdigitsinthefactorialoftheintegersappearingintheinput.SampleInput21020SampleOutput7192024/5/85如何求位數(shù)？算出階乘，循環(huán)求位數(shù)？階乘怎么存儲(chǔ)？一定要算出階乘嗎？

n!的位數(shù)：

(int)log10(n!)+1(int)(log10(1)+log10(2)+log10(3)+…+log10(n))+12024/5/86代碼怎么寫？超時(shí)問題怎么解決？能不能降低計(jì)算量？有沒有更簡(jiǎn)便的公式？2024/5/87《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》中給出了另一個(gè)公式

n!=sqrt(2*π*n)*((n/e)^n)*(1+1/(12*n)+1/(288*n*n)+O(1/n^3))

π=acos(-1)e=exp(1)兩邊對(duì)10取對(duì)數(shù)忽略log10(1+1/(12*n)+1/(288*n*n)+O(1/n^3))≈log10(1)=0

得到公式

log10(n!)=log10(sqrt(2*pi*n))+n*log10(n/e)2024/5/88如果不知道高效的計(jì)算公式？(int)(log10(1)+log10(2)+log10(3)+…+log10(n))對(duì)于每個(gè)輸入的數(shù)都要按上述公式計(jì)算如何防止重復(fù)計(jì)算？先算小數(shù)的位數(shù)，在此根底上再算大數(shù)?！?〕每次找最小值？需要存儲(chǔ)數(shù)據(jù)和位數(shù)的計(jì)算〔2〕先把算出的log10存儲(chǔ)？2024/5/89數(shù)學(xué)問題的特點(diǎn)：題意容易理解；數(shù)學(xué)關(guān)聯(lián)性一般比較大；語言的關(guān)聯(lián)性相對(duì)較??；但有時(shí)需要相關(guān)策略來躲避過高的復(fù)雜度。要注意復(fù)雜度問題；適合ACM/ICPC入門練習(xí)。每次競(jìng)賽一般會(huì)有1-2個(gè)數(shù)學(xué)問題。2024/5/810常用單詞：1、integer整數(shù)〔不一定就是32位的〕2、positive正的3、negative(adj)負(fù)的;(n)負(fù)數(shù)4、factorial(n)階乘;(adj)因子的，階乘的5、digital(n)數(shù)字;(adj)數(shù)字的6、multiple倍數(shù)7、multiplication乘法運(yùn)算2024/5/811常用單詞：〔圖形相關(guān)〕1、vertex(vertices)頂點(diǎn)2、polygon多邊形3、convex凸的4、concave凹的5、segment(線)段〔n〕;分割〔v〕2024/5/812數(shù)學(xué)問題

〔分類分析〕2024/5/813第一類簡(jiǎn)單問題2024/5/8141288電梯

不管在什么事情上，總是想方設(shè)法給自己帶來方便。于是在一幢古老樓房的電梯里就發(fā)生了爭(zhēng)吵事件。大家都想在自己住的這一層停下〔因?yàn)殡娞菰谏仙倪^程中只能停下一次，之后就只能返回到地下車庫(kù)了〕。爭(zhēng)吵給保安帶來了麻煩，所以保安想請(qǐng)你編個(gè)程序。當(dāng)人們每次進(jìn)入電梯，統(tǒng)計(jì)一下人數(shù)，再統(tǒng)計(jì)一下到每層的人數(shù)就計(jì)算出電梯到哪一層停最合理〔當(dāng)人從高往低走時(shí)，走一層要花3點(diǎn)力量，而從低往高走時(shí)，走一層要花4點(diǎn)力量，當(dāng)所有人們花的力量總和最小時(shí)，停那一層就是最合理的〕。2024/5/815Input:每行的第一個(gè)數(shù)是n〔1<=n<=50〕，表示這幢樓有幾層，接下來有n個(gè)數(shù)，分別表示1到n層各層的人數(shù)。到各層的人數(shù)不超過100個(gè)。大家都是從地下車庫(kù)坐電梯上來的。當(dāng)n為0，那么結(jié)束。Output:每行輸出最合理的那一層，當(dāng)有好幾層都是合理的，那就都輸出來，并且每個(gè)數(shù)據(jù)之間空一格。SampleInput:31115668210SampleOutput:232024/5/816Elevator

ProblemDescriptionThehighestbuildinginourcityhasonlyoneelevator.ArequestlistismadeupwithNpositivenumbers.Thenumbersdenoteatwhichfloorstheelevatorwillstop,inspecifiedorder.Itcosts6secondstomovetheelevatoruponefloor,and4secondstomovedownonefloor.Theelevatorwillstayfor5secondsateachstop.

Foragivenrequestlist,youaretocomputethetotaltimespenttofulfilltherequestsonthelist.Theelevatorisonthe0thflooratthebeginninganddoesnothavetoreturntothegroundfloorwhentherequestsarefulfilled.

2024/5/817InputTherearemultipletestcases.EachcasecontainsapositiveintegerN,followedbyNpositivenumbers.Allthenumbersintheinputarelessthan100.AtestcasewithN=0denotestheendofinput.Thistestcaseisnottobeprocessed.

OutputPrintthetotaltimeonasinglelineforeachtestcase.

SampleInput1232310

SampleOutput17412024/5/818第二類

大數(shù)問題2024/5/819一、大數(shù)加法HDU1002：

A+BProblemIIInputThefirstlineoftheinputcontainsanintegerT(1<=T<=20)whichmeansthenumberoftestcases.ThenTlinesfollow,eachlineconsistsoftwopositiveintegers,AandB.Noticethattheintegersareverylarge,thatmeansyoushouldnotprocessthembyusing32-bitinteger.Youmayassumethelengthofeachintegerwillnotexceed1000.

2024/5/820分析：準(zhǔn)確的說，此問題不算是數(shù)學(xué)問題；由于數(shù)據(jù)特別大，用一般的整數(shù)類型不能存儲(chǔ)，怎么辦？字符串存儲(chǔ)？怎么處理？按位加，進(jìn)位？2024/5/821‘1’‘2’‘3’…‘5’‘6’‘7’‘8’‘\0’‘2’‘3’‘5’‘6’‘7’‘8’‘\0’…..‘3’‘5’‘6’‘\0’字符如何相加？(從最低位開始相加〕不等長(zhǎng)怎么辦？發(fā)生進(jìn)位怎么辦？2024/5/822第三類

注重分析的問題2024/5/823先看一個(gè)簡(jiǎn)單的題目:2024/5/8241331：取石子問題

Description:小明是個(gè)游戲迷，這不，今天他又和小剛一起玩“拿石子”的游戲。游戲規(guī)那么是2個(gè)人輪流拿石子，一次可以拿1顆或3顆，規(guī)定誰取到最后一顆石子就是誰贏。小明和小剛商量后決定每次都是小明先取。小明與小剛都是游戲高手，該贏的局絕不會(huì)輸。在知道石子總數(shù)的情況下，小明想快速知道每次的輸贏情況。2024/5/825分析：各取一次共有三種情況：

①共取走2顆石子

②共取走4顆石子

③共取走6顆石子設(shè)有石子S.方案①取了N1次，方案②取了N2次，方案③取了N3次后，還剩下K個(gè)石子。S=2*N1+4*N2+6*N3+KK的取值有三種情況：0，1，3。K=1,3那么先取方勝。反之，另一方勝。當(dāng)S為偶數(shù)時(shí)，后取方勝，反之，先取方勝。

2024/5/826杭電OJ：1021FibonacciAgainProblemDescriptionThereareanotherkindofFibonaccinumbers:F(0)=7,F(1)=11,F(n)=F(n-1)+F(n-2)(n>=2).Input：Inputconsistsofasequenceoflines,eachcontaininganintegern.(n<1,000,000).Output：Printtheword"yes"if3divideevenlyintoF(n).

Printtheword"no"ifnot.

SampleInput012345SampleOutputnonoyesnonono2024/5/827題目分析：判斷某一項(xiàng)為哪一項(xiàng)否能被3整除是否需要把某一項(xiàng)的值求出來，進(jìn)行整除判斷？能被3整除的整數(shù)的特點(diǎn)？關(guān)于能否被3整除，這樣的項(xiàng)在排列上是否有規(guī)律？〔找出規(guī)律〕第0項(xiàng)除以3余1，第1項(xiàng)除以3余2，第2項(xiàng)整除，第3項(xiàng)除以3余2，第4項(xiàng)除以3余2，第5項(xiàng)除以3余1，第6項(xiàng)整除，第7項(xiàng)除以3余1，第8項(xiàng)除以3余1，第9項(xiàng)除以3余2，第7項(xiàng)整除…….2024/5/828Hdoj_1021程序清單：#include<stdio.h>intmain(){longn;while(scanf("%ld",&n)!=EOF) if(n%8==2||n%8==6) printf("yes\n"); else printf("no\n"); return0;}2024/5/829這個(gè)問題主要在于找出規(guī)律；程序編寫很簡(jiǎn)單；考查的是分析問題的能力。2024/5/830第四類

公式型HDOJ_1071TheArea

2024/5/832拋物線公式：y=ax^2+bx+c三點(diǎn)-〉a、b、c系數(shù)公式-〉如何求面積？積分問題

2024/5/833遞推求解……還記得Fibonacci問題吧？F(0)=F(1)=1;F(n)=F(n-1)+F(n-2);2024/5/8341182：母牛問題

Description:假設(shè)單性繁殖成立，假設(shè)一頭母牛，從出生起第四個(gè)年頭開始，每年生一頭母牛，而生出的小母牛在之后的第四年也將具有生殖能力。按此規(guī)律，第n年時(shí)有多少頭母牛？Input:輸入數(shù)據(jù)中不多于50個(gè)整數(shù)〔1≤n≤40〕。Output:對(duì)于每個(gè)n，輸出其第n年的母牛數(shù)，每個(gè)結(jié)果對(duì)應(yīng)一行輸出。2024/5/835如何得出遞推公式？列出前面幾個(gè)數(shù)據(jù)：1112346假設(shè)規(guī)模小于N的情況已經(jīng)得到解決重點(diǎn)分析：當(dāng)規(guī)模擴(kuò)大到N時(shí)，如何枚舉出所有的情況，并且要確保對(duì)于每一種子情況都能用已經(jīng)得到的數(shù)據(jù)解決。f(n〕=f(n-1)+f(n-3)(n-3年存在的牛在n年均可以生出一頭小?！?024/5/836再來看難一點(diǎn)的問題……2024/5/8372050：折線分割平面

2024/5/838

這個(gè)問題……

其實(shí)屬于遞推問題，

你們比我更擅長(zhǎng)，呵呵……2024/5/839先看直線分割平面問題經(jīng)典結(jié)論：平面內(nèi)有n條直線，任何兩條不平行，任何三條不過同一點(diǎn)；這n條直線可以把平面分成n(n+1)/2+1個(gè)局部?？捎脭?shù)學(xué)歸納法證明。2024/5/840公式的推導(dǎo)……F(1)=2;F(n)=F(n-1)+n;(第n條直線與n-1條相交，將增加n個(gè)區(qū)域〕F(n)=n+n-1+n-2+….+2+f(1)=n(n+1)/2+12024/5/841回到折線問題：一個(gè)折線可以看成兩條直線相交，并去掉角的一邊；可推出公式：

f(n)=f(n-1)+(2n-1)+2n-22024/5/842f(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*n^2-n+12024/5/843Ok,內(nèi)容已經(jīng)不少了……

來幾個(gè)思考題……2024/5/844思考(1)：1358

雖然題目采用故事性描述本質(zhì)上就是求相交圓的面積純數(shù)學(xué)問題別問我，這類問題我不擅長(zhǎng)…..

2024/5/845思考〔2〕

HDOJ1465:不容易系列之一(遞推求解)某人寫了n封信和n個(gè)信封，如果所有的信都裝錯(cuò)了信封。求所有的信都裝錯(cuò)信封,共有多少種不同情況。2024/5/846思考〔3〕HDOJ1030:Delta-wave

ThetravellerneedstogofromthecellwithnumberMtothecellwithnumberN.Thetravellerisabletoenterthecellthroughcelledgesonly,hecannottravelfromcelltocellthroughvertices.Thenumbe