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

1、2020/9/3,1,ACM 程序競賽入門 開課號：85019 授課教師：王英姿,2020/9/3,2,第二講,數(shù)學問題,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ù)？ 階乘怎么存儲？ 一定要算出階乘嗎？ n!的位數(shù)： (int) log10(n!)+1 (int)(log10(1)+log10(2)+log10(3)+log10(n)+1,2020/9/3,6,代碼怎么寫？ 超時問題怎么解決？ 能不能降低計算量？ 有沒有更簡便的公式？,2020/9/3,7

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

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

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

7、事件。大家都想在自己住的這一層停下（因為電梯在上升的過程中只能停下一次，之后就只能返回到地下車庫了）。爭吵給保安帶來了麻煩，所以保安想請你編個程序。當人們每次進入電梯，統(tǒng)計一下人數(shù)，再統(tǒng)計一下到每層的人數(shù)就計算出電梯到哪一層停最合理（當人從高往低走時，走一層要花3點力量，而從低往高走時，走一層要花4點力量，當所有人們花的力量總和最小時，停那一層就是最合理的）。,2020/9/3,15,Input:每行的第一個數(shù)是n（1=n=50），表示這幢樓有幾層，接下來有n個數(shù)，分別表示1到n層各層的人數(shù)。到各層的人數(shù)不超過100個。大家都是從地下車庫坐電梯上來的。當n為0，則結束。 Output:每行輸出

8、最合理的那一層，當有好幾層都是合理的，那就都輸出來，并且每個數(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ù)問題,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,分析：,準確的說，此問

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

14、道石子總數(shù)的情況下，小明想快速知道每次的輸贏情況。,2020/9/3,25,分析：,各取一次共有三種情況： 共取走2顆石子 共取走4顆石子 共取走6顆石子 設有石子S.方案取了N1次，方案取了N2次，方案取了N3次后，還剩下K個石子。 S=2*N1+4*N2+6*N3+K K的取值有三種情況：0，1，3。 K=1,3則先取方勝。反之，另一方勝。 當S為偶數(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、某一項是否能被3 整除 是否需要把某一項的值求出來，進行整除判斷？ 能被3整除的整數(shù)的特點？ 關于能否被3整除，這樣的項在排列上是否有規(guī)律？ （找出規(guī)律） 第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項整除.,2020/9/3,28,Hdoj_1021程序清單：,#include int main() long n; while(scanf(%ld, ,2020/9/3,29,這個問題主要在于找出規(guī)律； 程序編寫很簡單； 考查的是分析問題的能力。,2020/9/

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

18、 Output:對于每個n，輸出其第n年的母牛數(shù)，每個結果對應一行輸出。,2020/9/3,35,如何得出遞推公式？,列出前面幾個數(shù)據(jù)： 1 1 1 2 3 4 6 假設規(guī)模小于N的情況已經得到解決 重點分析：當規(guī)模擴大到N時，如何枚舉出所有的情況，并且要確保對于每一種子情況都能用已經得到的數(shù)據(jù)解決。 f(n）=f(n-1)+f(n-3) (n-3年存在的牛在n年均可以生出一頭小牛）,2020/9/3,36,再來看難一點的問題,2020/9/3,37,2050：折線分割平面,2020/9/3,38,這個問題其實屬于遞推問題，你們比我更擅長，呵呵,2020/9/3,39,先看直線分割平面問題,經

19、典結論：平面內有n條直線，任何兩條不平行，任何三條不過同一點；這n條直線可以把平面分成 n(n+1) /2 +1個部分。 可用數(shù)學歸納法證明。,2020/9/3,40,公式的推導,F(1)=2; F(n) = F(n-1)+n; (第n條直線與n-1條相交，將增加n個區(qū)域） F(n)=n+n-1+n-2+.+2+f(1) =n(n+1)/2+1,2020/9/3,41,回到折線問題：,一個折線可以看成兩條直線相交，并去掉角的一邊 ；可推出公式： 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, 內容已經不少了來幾個思考題,2020/9/3,44,思考(1)：1358,雖然題目采用故事性描述 本質上就是求相交圓的面積 純數(shù)學問題,別問我，這類問題我不擅長.,2020/9/3,45,思考（2） HDOJ 1465: 不容易系列之一(遞推求解),某人寫了n封信和n個信封，如果所有的信都裝錯了信封。求所有的信都裝錯信封,共有多少種不同情況。,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