算法基礎(chǔ)ppt課件-閱讀頁(yè)
2025-05-14 03:26本頁(yè)面
【正文】 for Computing Machinery) 成立于計(jì)算機(jī)誕生次年，是目前計(jì)算機(jī)學(xué)界中歷史最悠久、最具權(quán)威性的組織，是推進(jìn)信息技術(shù)專業(yè)人員和學(xué)生提高技巧的主要力量。 ACM通過(guò)提供前沿技術(shù)信息和從理論到實(shí)踐的轉(zhuǎn)化，為其全球 成員服務(wù)，并已經(jīng)成為信息科技領(lǐng)域的一個(gè)基本信息來(lái)源。其宗旨是提供一個(gè)讓大學(xué)生向 IT界展示自己分析問(wèn)題和解決問(wèn)題的能力的絕好機(jī)會(huì)，并成為一個(gè)有效的途徑，讓下一代 IT天才可以接觸到其日后工作中將要用到的各種軟件。 4 ACM/ICPC in China 中國(guó)大陸高校從 1996年開始參加 ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽亞洲預(yù)賽。 ? 2022年由北京大學(xué)和上海交通大學(xué)承辦。 ? 2022年由上海大學(xué)、清華和西電承辦。 ? 2022年由哈爾濱工程大學(xué) 、北京交通大學(xué)、中國(guó)科學(xué)技術(shù)大學(xué) 、杭州電子科技大學(xué) 、西南民族大學(xué) 承辦 5 如何比賽 ？ ? 3人組隊(duì) ? 可以攜帶諸如書、手冊(cè)、 程序清單等參考資料；不能攜帶任何可用計(jì)算機(jī)處理的軟件或數(shù)據(jù)、不能攜帶任何類型的通訊工具； ? 可能收到的反饋信息包括： Compile Error 程序不能通過(guò)編譯。 Time Limit Exceeded ? 運(yùn)行超過(guò)時(shí)限還沒(méi)有得到輸出結(jié)果。 Presentation Error ? 輸出格式不對(duì)，可檢查空格、回車等等細(xì)節(jié)。 ? 如果多支隊(duì)伍解題數(shù)量相同，則根據(jù)總用時(shí)加上懲罰時(shí)間進(jìn)行排名。 ? 每道試題用時(shí)將從競(jìng)賽開始到試題解答被判定為正確為止，其間每一次錯(cuò)誤的運(yùn)行將被加罰20分鐘時(shí)間，未正確解答的試題不記時(shí)。 Allen Van Gelder ? 計(jì)算機(jī)程序設(shè)計(jì)藝術(shù) Donald Knuth ? Art of Programming Contest— C Programming, Data Structures, Algorithms 2nd Edition ? Programming Challenges ? …… 13 算法 ? 什么是算法？ ? 平時(shí)所說(shuō)的算法 算法就是解決問(wèn)題的方法或過(guò)程。 14 算法的基本特征 ? 有窮性 算法必須是可終止的。 ? 可行性 算法原則上能夠精確地運(yùn)行。 ? 輸出 一個(gè)算法有一個(gè)或多個(gè)輸出 15 時(shí)間復(fù)雜度和空間復(fù)雜度 ? 時(shí)間復(fù)雜度 對(duì)于一個(gè)規(guī)模為 n的輸入數(shù)據(jù)，我們希望知道算法要運(yùn)行多長(zhǎng)時(shí)間得到結(jié)果，也希望知道隨著 n的增長(zhǎng)，算法所需時(shí)間的增長(zhǎng)速度如何？ ? 空間復(fù)雜度 對(duì)于一定規(guī)模輸入數(shù)據(jù)，算法運(yùn)行所需空間的度量 16 基本漸進(jìn)記號(hào) ? 定義 設(shè) f和 g是兩個(gè)函數(shù)，如果存在 c1， c2，N0,使得當(dāng) nN時(shí)， ? 此時(shí)用 表示函數(shù)集合，其運(yùn)行時(shí)間用 來(lái)度量。 ? 如果存在正常數(shù) N和 c使得當(dāng) nN時(shí)，f(n)cg(n) ? 記為 。 for i: =1 to n do fact := fact * i。 for i :=1 to n do for j:=1 to n do sum := sum + a[i,j]。 for i := 1 to n do begin fact := 1。 sum := sum + fact。 for i := 1 to n1 do if a[i] a[i+1] then do_it。 for i:=1 to n do for j:=i to n do begin sum := 0。 if sum max then max := sum。 End。 for i:=1 to n do s[i] := s[i–1] + a[i]。 for i:=1 to n do for j:=i to n do if s[j] – s[i1] max then max := s[j] – s[i1]。 end。 for j :=1 to n do begin if s[j] – min_s max then max := s[j] – min_s。 end。在某臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)并完成該算法的時(shí)間為
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1