ACM課件(lecture02)老少皆宜數(shù)學(xué)題.ppt

上傳人:xin****828 文檔編號:15723123 上傳時間:2020-09-01 格式:PPT 頁數(shù):75 大?。?38KB
收藏 版權(quán)申訴 舉報 下載
ACM課件(lecture02)老少皆宜數(shù)學(xué)題.ppt_第1頁
第1頁 / 共75頁
ACM課件(lecture02)老少皆宜數(shù)學(xué)題.ppt_第2頁
第2頁 / 共75頁
ACM課件(lecture02)老少皆宜數(shù)學(xué)題.ppt_第3頁
第3頁 / 共75頁

下載文檔到電腦,查找使用更方便

14.9 積分

下載資源

還剩頁未讀,繼續(xù)閱讀

資源描述:

《ACM課件(lecture02)老少皆宜數(shù)學(xué)題.ppt》由會員分享,可在線閱讀,更多相關(guān)《ACM課件(lecture02)老少皆宜數(shù)學(xué)題.ppt(75頁珍藏版)》請在裝配圖網(wǎng)上搜索。

1、ACM程序設(shè)計,2020/9/1,2,第二講,老少皆宜之?dāng)?shù)學(xué)題,2020/9/1,3,今天,,你 了嗎?,AC,2020/9/1,4,開胃羹(1),幾個常用單詞: 1、vertex ( vertices ) 頂點(diǎn) 2、polygon 多邊形 3、convex 凸的 4、concave 凹的 5、segment (線)段(n);分割(v),2020/9/1,5,開胃羹(2),再來幾個: 1、integer 整數(shù) 2、positive 正的 3、negative (adj)負(fù)的; (n)負(fù)數(shù) 4、factorial (n)階乘;(adj)因子的,階乘的 5、digital (n)數(shù)字;(adj)

2、數(shù)字的,2020/9/1,6,ACM數(shù)學(xué)題特點(diǎn)分析:,題意容易理解 算法相對簡單(有些很難的?。。?編程比較容易 ACM/ICPC入門練習(xí)的好選擇 下面,分類介紹:,2020/9/1,7,從首屆“舜宇”杯說起,2020/9/1,8,比賽背景,由于前一年的邀請賽很多學(xué)校沒有做出一道題,所以,這次的比賽特意準(zhǔn)備了幾道簡單的題目,目的就是讓大多數(shù)的學(xué)校都能拿個氣球回去,也好有個交待,于是有,,2020/9/1,9,第一類,傻 瓜 型,2020/9/1,10,1004: Let the Balloon Rise,2020/9/1,11,Problem Description,Contest time

3、again! How excited it is to see balloons floating around. But to tell you a secret, the judges favorite time is guessing the most popular problem. When the contest is over, they will count the balloons of each color and find the result.This year, they decide to leave this lovely job to you.,2020/9/1

4、,12,Input,Input contains multiple test cases. Each test case starts with a number N (0 < N <= 1000) -- the total number of balloons distributed. The next N lines contain one color each. The color of a balloon is a string of up to 15 lower-case letters.A test case with N = 0 terminates the input and

5、this test case is not to be processed.,2020/9/1,13,Output,For each case, print the color of balloon for the most popular problem on a single line. It is guaranteed that there is a unique solution for each test case.,2020/9/1,14,Sample Input 5 green red blue red red 3 pink orange pink 0,Sample Output

6、 red pink,2020/9/1,15,題目評述:,1. 一個讓你看到后興奮的題目,2. 只要懂點(diǎn)C或者C++,就可解決該問題。,2020/9/1,16,1004題目分析:,該題算法思想比較簡單,就是對輸入的字符串進(jìn)行比較和統(tǒng)計。值得注意的一點(diǎn)是: 如果用C語言來寫,要注意可能會把第一個數(shù)字后的“回車符”誤認(rèn)為是第一個串,字符串的比較也要用函數(shù)和循環(huán)語句。,2020/9/1,17,1008: Elevator,2020/9/1,18,Problem Description,The highest building in our city has only one elevator. A r

7、equest list is made up with N positive numbers. The numbers denote at which floors the elevator will stop, 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 a

8、re to compute the total time spent to fulfill the requests on the list. The elevator is on the 0th floor at the beginning and does not have to return to the ground floor when the requests are fulfilled.,2020/9/1,19,Input,There are multiple test cases. Each case contains a positive integer N, followe

9、d by N positive numbers. All the numbers in the input are less than 100. A test case with N = 0 denotes the end of input. This test case is not to be processed.,2020/9/1,20,Output,Print the total time on a single line for each test case.,2020/9/1,21,Sample Input 1 2 3 2 3 1 0 Sample Output 17 41,202

10、0/9/1,22,實(shí)際上,這是本次比賽最簡單的一題,浙大、浙工大等當(dāng)時訓(xùn)練水平相對較高的學(xué)校基本上10分鐘之內(nèi)解決該題,這也是一個沒有算法的題目。 這種題目大家不會錯過的,題目評述:,不要分析了吧,2020/9/1,24,第二類,基 本 型,2020/9/1,25,1009: FatMouse Trade,2020/9/1,26,Problem Description,FatMouse prepared M pounds of cat food, ready to trade with the cats guarding the warehouse containing his favori

11、te food, JavaBean. The warehouse has N rooms. The i-th room contains Ji pounds of JavaBeans and requires Fi pounds of cat food. FatMouse does not have to trade for all the JavaBeans in the room, instead, he may get Ji* a% pounds of JavaBeans if he pays Fi* a% pounds of cat food. Here a is a real nu

12、mber. Now he is assigning this homework to you: tell him the maximum amount of JavaBeans he can obtain.,2020/9/1,27,Input,The input consists of multiple test cases. Each test case begins with a line containing two non-negative integers M and N. Then N lines follow, each contains two non-negative int

13、egers Ji and Fi respectively. The last test case is followed by two -1s. All integers are not greater than 1000.,2020/9/1,28,Output,For each test case, print in a single line a real number accurate up to 3 decimal places, which is the maximum amount of JavaBeans that FatMouse can obtain,2020/9/1,29,

14、,Sample Input 5 3 7 2 4 3 5 2 20 3 25 18 24 15 15 10 -1 -1,Sample Output 13.333 31.500,2020/9/1,30,題目特點(diǎn):,這個題目比前面兩個題目稍難,但是屬于能一眼看出解決辦法的題目。只要靜下心,還是比較容易解決的。,2020/9/1,31,1009算法分析:,輸入(J , F 放入數(shù)組) 對數(shù)組排序(按效益,降序) 輸出(按效益高低有序交易),2020/9/1,32,第三類,技 巧 型,2020/9/1,33,小錘摳縫,先來看一個簡單的題目鋪墊一下:,2020/9/1,34,1021 Fibonacci

15、Again,2020/9/1,35,Problem Description,There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n=2).,2020/9/1,36,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 t

16、he word no if not.,2020/9/1,37,Sample Input 0 1 2 3 4 5,Sample Output no no yes no no no,2020/9/1,38,題目分析:,能被3整除的整數(shù)的特點(diǎn)?,如果兩個數(shù)的和能被3整除,這兩個數(shù)有什么特點(diǎn)?,關(guān)于能否被3整除,這兩個數(shù)一共有多少種組合?,2020/9/1,39,Hdoj_1021程序清單:,#include int main() long n; while(scanf(%ld, ,2020/9/1,40,回到正題大錘搞定,,2020/9/1,41,1005: Number Sequence,20

17、20/9/1,42,A number sequence is defined as follows:f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.Given A, B, and n, you are to calculate the value of f(n).,Problem Description,2020/9/1,43,Input The input consists of multiple test cases. Each test case contains 3 integers A, B and n o

18、n a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed. Output For each test case, print the value of f(n) on a single line.,2020/9/1,44,Sample Input 1 1 3 1 2 10 0 0 0 Sample Output 2 5,2020/9/1,45,題目特點(diǎn):,這個題目是一個比較典型的

19、ACM競賽題,盡管在真正的大賽中這個題目可能算比較簡單的,但在本次比賽中,本題難度屬于中等,可以說,能做出本題的隊伍基本都有二等獎以上。 但如果不認(rèn)真分析,有可能會掉入陷阱。,2020/9/1,46,Question:,暴力能解決問題嗎?,2020/9/1,47,拒絕暴力,2020/9/1,48,題目分析:,對于這種題目,千萬不能蠻干!實(shí)際上,有經(jīng)驗(yàn)的同學(xué)看到本題目的數(shù)據(jù)規(guī)模,很快就能知道:這類題目有規(guī)律可循。,2020/9/1,49,現(xiàn)在對這題有什么想法,???,2020/9/1,50,第四類,紙老虎型,2020/9/1,51,HDOJ_1071 The Area,2020/9/1,52,S

20、ample Input 2 5.000000 5.000000 0.000000 0.000000 10.000000 0.000000 10.000000 10.000000 1.000000 1.000000 14.000000 8.222222 Sample Output 33.33 40.69,2020/9/1,53,第一眼:傻了,2020/9/1,54,再一看,,2020/9/1,55,拋物線公式:y=ax2+bx+c,已知三點(diǎn) -a、b、c 系數(shù),公式已知 - 如何求面積?,會簡單積分嗎?,分析過程:,該你思考了,感覺怎么樣?,2020/9/1,57,思考題:,1178 Herit

21、age from father,2020/9/1,58,Famous Harry Potter,who seemd to be a normal and poor boy,is actually a wizard.Everything changed when he had his birthday of ten years old.A huge man called Hagrid found Harry and lead him to a new world full of magic power. If youve read this story,you probably know tha

22、t Harrys parents had left him a lot of gold coins.Hagrid lead Harry to Gringotts(the bank hold up by Goblins). And they stepped into the room which stored the fortune from his father.Harry was astonishing ,coz there were piles of gold coins. The way of packing these coins by Goblins was really speci

23、al.Only one coin was on the top,and three coins consisted an triangle were on the next lower layer.The third layer has six coins which were also consisted an triangle,and so on.On the ith layer there was an triangle have i coins each edge(totally i*(i+1)/2).The whole heap seemed just like a pyramid.

24、Goblin still knew the total num of the layers,so its up you to help Harry to figure out the sum of all the coins.,Problem Description,2020/9/1,59,Input The input will consist of some cases,each case takes a line with only one integer N(0

25、算金幣的總數(shù)(保留三位有效數(shù)字),2020/9/1,60,Sample Input 1 3 0 Sample Output 1.00E0 1.00E1,2020/9/1,61,要點(diǎn)分析:,1、暴力的復(fù)雜度是多少? 2、哪些陷阱? 3、關(guān)鍵在哪? 4、順利應(yīng)該多長時間?,2020/9/1,62,數(shù)學(xué)公式:,1、這個大家都會:1+2+3+4+n=n(n+1)/2 2、這個有些同學(xué)忘記了: 1*1+2*2+3*3++n*n=n(n+1)(2n+1)/6 3、合并后得到n(n+1)(n+2)/3,,2020/9/1,63,問題一:科學(xué)計數(shù)法的格式,不知道? e E ,用%e : 用 %.2e,如何實(shí)現(xiàn)

26、格式要求?,2020/9/1,64,解決方案,方法一: 把輸出先輸出到字符串,再去掉e之后的0 a=(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,stri); for(i=6;stri!=0;i++) if(i==len-1|| stri!=0)printf(%c,stri); printf(n);,2020/9/1,65,方法二:尾數(shù)和指數(shù)分開控制格式 a=(1.0*n*n*n+3.0*n*n+2.0*n)/6.0; b=log10(a); p

27、rintf(%.2lf,a/pow(10,b)); printf(E%dn,b);,2020/9/1,66,Any question?,2020/9/1,67,課后任務(wù):,1004、1005、1008、1009 、1060 10121014、10191021 、1061 1049、1178、1108、1030 1071、1597,2020/9/1,68,提示:關(guān)于Presentation Error 的錯誤,2016 輸出n個數(shù),用空格隔開 常見錯誤:for(i=1;i<=n;i++) printf(“%d “,ai); printf(“n “); 最后一個數(shù)之后也有空格造成

28、 Presentation Error錯誤,2020/9/1,69,解決辦法,1、方法一 for(i=1;i

展開閱讀全文
溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號:ICP2024067431-1 川公網(wǎng)安備51140202000466號


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請立即通知裝配圖網(wǎng),我們立即給予刪除!

五月丁香婷婷狠狠色,亚洲日韩欧美精品久久久不卡,欧美日韩国产黄片三级,手机在线观看成人国产亚洲