1、2020/9/3,1,ACM 程序競(jìng)賽入門(mén) 開(kāi)課號(hào)：85019 授課教師：王英姿,2020/9/3,2,第二講,數(shù)學(xué)問(wèn)題,2020/9/3,3,引例：本校OJ 1207 （相似題）杭電1018，求n！的位數(shù) ,In many applications very large integers numbers are required. Some of these applications are using keys for secure transmission of data, encryption, etc. In this problem you are given a number,

2、you have to determine the number of digits in the factorial of the number.,2020/9/3,4,Input Input consists of several lines of integer numbers. The first line contains an integer n, which is the number of cases to be tested, followed by n lines, one integer 1 m 107 on each line Output The output con

3、tains the number of digits in the factorial of the integers appearing in the input.,Sample Input 2 10 20,Sample Output 7 19,2020/9/3,5,如何求位數(shù)？,算出階乘，循環(huán)求位數(shù)？ 階乘怎么存儲(chǔ)？ 一定要算出階乘嗎？ n!的位數(shù)： (int) log10(n!)+1 (int)(log10(1)+log10(2)+log10(3)+log10(n)+1,2020/9/3,6,代碼怎么寫(xiě)？ 超時(shí)問(wèn)題怎么解決？ 能不能降低計(jì)算量？ 有沒(méi)有更簡(jiǎn)便的公式？,2020/9/3,7

4、,計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)中給出了另一個(gè)公式 n! = sqrt(2*n) * (n/e)n) * (1 + 1/(12*n) + 1/(288*n*n) + O(1/n3) = acos(-1) e = exp(1) 兩邊對(duì)10取對(duì)數(shù) 忽略 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),2020/9/3,8,如果不知道高效的計(jì)算公式？,(int)(log10(1)+log10(2)+log10(3)+log10(n)

5、 對(duì)于每個(gè)輸入的數(shù)都要按上述公式計(jì)算 如何避免重復(fù)計(jì)算？ 先算小數(shù)的位數(shù)，在此基礎(chǔ)上再算大數(shù)。 （1） 每次找最小值？需要存儲(chǔ)數(shù)據(jù)和位數(shù)的計(jì)算 （2）先把算出的log10存儲(chǔ)？,2020/9/3,9,數(shù)學(xué)問(wèn)題的特點(diǎn)：,題意容易理解； 數(shù)學(xué)關(guān)聯(lián)性一般比較大； 語(yǔ)言的關(guān)聯(lián)性相對(duì)較??；但有時(shí)需要相關(guān)策略來(lái)規(guī)避過(guò)高的復(fù)雜度。 要注意復(fù)雜度問(wèn)題； 適合ACM/ICPC入門(mén)練習(xí)。 每次競(jìng)賽一般會(huì)有1-2個(gè)數(shù)學(xué)問(wèn)題。,2020/9/3,10,常用單詞： 1、integer 整數(shù)（不一定就是32位的） 2、positive 正的 3、negative (adj)負(fù)的; (n)負(fù)數(shù) 4、factorial (n

6、)階乘; (adj)因子的，階乘的 5、digital (n)數(shù)字; (adj)數(shù)字的 6、multiple 倍數(shù) 7、multiplication 乘法運(yùn)算,2020/9/3,11,常用單詞： （ 圖形相關(guān)） 1、vertex ( vertices ) 頂點(diǎn) 2、polygon 多邊形 3、convex 凸的 4、concave 凹的 5、segment (線)段（n）;分割（v）,2020/9/3,12,數(shù)學(xué)問(wèn)題（分類分析）,2020/9/3,13,第一類,簡(jiǎn)單問(wèn)題,2020/9/3,14,1288 電梯,不管在什么事情上，總是想方設(shè)法給自己帶來(lái)方便。于是在一幢古老樓房的電梯里就發(fā)生了爭(zhēng)吵

7、事件。大家都想在自己住的這一層停下（因?yàn)殡娞菰谏仙倪^(guò)程中只能停下一次，之后就只能返回到地下車(chē)庫(kù)了）。爭(zhēng)吵給保安帶來(lái)了麻煩，所以保安想請(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í)，停那一層就是最合理的）。,2020/9/3,15,Input:每行的第一個(gè)數(shù)是n（1=n=50），表示這幢樓有幾層，接下來(lái)有n個(gè)數(shù)，分別表示1到n層各層的人數(shù)。到各層的人數(shù)不超過(guò)100個(gè)。大家都是從地下車(chē)庫(kù)坐電梯上來(lái)的。當(dāng)n為0，則結(jié)束。 Output:每行輸出

8、最合理的那一層，當(dāng)有好幾層都是合理的，那就都輸出來(lái)，并且每個(gè)數(shù)據(jù)之間空一格。,Sample Input: 3 1 1 1 5 6 6 8 2 1 0,Sample Output: 2 3,2020/9/3,16,Elevator,Problem Description The highest building in our city has only one elevator. A request list is made up with N positive numbers. The numbers denote at which floors the elevator will stop,

9、 in specified order. It costs 6 seconds to move the elevator up one floor, and 4 seconds to move down one floor. The elevator will stay for 5 seconds at each stop.For a given request list, you are to compute the total time spent to fulfill the requests on the list. The elevator is on the 0th floor a

10、t the beginning and does not have to return to the ground floor when the requests are fulfilled.,2020/9/3,17,Input There are multiple test cases. Each case contains a positive integer N, followed by N positive numbers. All the numbers in the input are less than 100. A test case with N = 0 denotes th

11、e end of input. This test case is not to be processed.Output Print the total time on a single line for each test case. Sample Input 1 2 3 2 3 1 0Sample Output 17 41,2020/9/3,18,第二類 大數(shù)問(wèn)題,2020/9/3,19,一、大數(shù)加法 HDU1002： A + B Problem II,Input The first line of the input contains an integer T(1=T=20) which

12、 means the number of test cases. Then T lines follow, each line consists of two positive integers, A and B. Notice that the integers are very large, that means you should not process them by using 32-bit integer. You may assume the length of each integer will not exceed 1000.,2020/9/3,20,分析：,準(zhǔn)確的說(shuō)，此問(wèn)

13、題不算是數(shù)學(xué)問(wèn)題； 由于數(shù)據(jù)特別大，用一般的整數(shù)類型不能存儲(chǔ)，怎么辦？ 字符串存儲(chǔ)？ 怎么處理？按位加，進(jìn)位？,2020/9/3,21,字符如何相加 ？(從最低位開(kāi)始相加） 不等長(zhǎng)怎么辦？ 發(fā)生進(jìn)位怎么辦？,2020/9/3,22,第三類 注重分析的問(wèn)題,2020/9/3,23,先看一個(gè)簡(jiǎn)單的題目:,2020/9/3,24,1331：取石子問(wèn)題,Description: 小明是個(gè)游戲迷，這不，今天他又和小剛一起玩“拿石子”的游戲。游戲規(guī)則是2個(gè)人輪流拿石子，一次可以拿1顆或3顆，規(guī)定誰(shuí)取到最后一顆石子就是誰(shuí)贏。小明和小剛商量后決定每次都是小明先取。小明與小剛都是游戲高手，該贏的局絕不會(huì)輸。在知

14、道石子總數(shù)的情況下，小明想快速知道每次的輸贏情況。,2020/9/3,25,分析：,各取一次共有三種情況： 共取走2顆石子 共取走4顆石子 共取走6顆石子 設(shè)有石子S.方案取了N1次，方案取了N2次，方案取了N3次后，還剩下K個(gè)石子。 S=2*N1+4*N2+6*N3+K K的取值有三種情況：0，1，3。 K=1,3則先取方勝。反之，另一方勝。 當(dāng)S為偶數(shù)時(shí)，后取方勝，反之，先取方勝。,2020/9/3,26,杭電OJ：1021 Fibonacci Again,Problem Description There are another kind of Fibonacci numbers: F(

15、0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n=2). Input ：Input consists of a sequence of lines, each containing an integer n. (n 1,000,000). Output：Print the word yes if 3 divide evenly into F(n). Print the word no if not.,Sample Input 0 1 2 3 4 5,Sample Output no no yes no no no,2020/9/3,27,題目分析：,判斷

16、某一項(xiàng)是否能被3 整除 是否需要把某一項(xiàng)的值求出來(lái)，進(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)整除.,2020/9/3,28,Hdoj_1021程序清單：,#include int main() long n; while(scanf(%ld, ,2020/9/3,29,這個(gè)問(wèn)題主要在于找出規(guī)律； 程序編寫(xiě)很簡(jiǎn)單； 考查的是分析問(wèn)題的能力。,2020/9/

17、3,30,第四類 公式型,HDOJ_1071 The Area,2020/9/3,32,拋物線公式：y=ax2+bx+c,已知三點(diǎn) -a、b、c 系數(shù),公式已知 - 如何求面積？,積分問(wèn)題 ,2020/9/3,33,遞推求解,還記得Fibonacci問(wèn)題吧？ F(0)=F(1)=1; F(n)=F(n-1)+F(n-2);,2020/9/3,34,1182：母牛問(wèn)題,Description: 假設(shè)單性繁殖成立，若一頭母牛，從出生起第四個(gè)年頭開(kāi)始，每年生一頭母牛，而生出的小母牛在之后的第四年也將具有生殖能力。按此規(guī)律，第n年時(shí)有多少頭母牛？ Input: 輸入數(shù)據(jù)中不多于50個(gè)整數(shù)（1n40）。

18、 Output:對(duì)于每個(gè)n，輸出其第n年的母牛數(shù)，每個(gè)結(jié)果對(duì)應(yīng)一行輸出。,2020/9/3,35,如何得出遞推公式？,列出前面幾個(gè)數(shù)據(jù)： 1 1 1 2 3 4 6 假設(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年均可以生出一頭小牛）,2020/9/3,36,再來(lái)看難一點(diǎn)的問(wèn)題,2020/9/3,37,2050：折線分割平面,2020/9/3,38,這個(gè)問(wèn)題其實(shí)屬于遞推問(wèn)題，你們比我更擅長(zhǎng)，呵呵,2020/9/3,39,先看直線分割平面問(wèn)題,經(jīng)

19、典結(jié)論：平面內(nèi)有n條直線，任何兩條不平行，任何三條不過(guò)同一點(diǎn)；這n條直線可以把平面分成 n(n+1) /2 +1個(gè)部分。 可用數(shù)學(xué)歸納法證明。,2020/9/3,40,公式的推導(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+1,2020/9/3,41,回到折線問(wèn)題：,一個(gè)折線可以看成兩條直線相交，并去掉角的一邊 ；可推出公式： f(n)=f(n-1)+(2n-1) +2n-2,2020/9/3,42,f(n)=f(n-1)+(2n-1) +2n-2 f(1)=2 F(n) =

20、 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,2020/9/3,43,Ok, 內(nèi)容已經(jīng)不少了來(lái)幾個(gè)思考題,2020/9/3,44,思考(1)：1358,雖然題目采用故事性描述 本質(zhì)上就是求相交圓的面積 純數(shù)學(xué)問(wèn)題,別問(wèn)我，這類問(wèn)題我不擅長(zhǎng).,2020/9/3,45,思考（2） HDOJ 1465: 不容易系列之一(遞推求解),某人寫(xiě)了n封信和n個(gè)信封，如果所有的信都裝錯(cuò)了信封。求所有的信都裝錯(cuò)信封,共有多少種不同情況。,2020/9/3,46,思考（3）HDOJ1030: Delta-wave ,The traveller needs to go from the cell with number M to the cell with number N. The traveller is able to enter the cell through cell edges only, he can not travel from cell to cell through vertices. The number of edges the travel