acm程序設(shè)計算法原理和acm入門-文庫吧
2025-07-16 19:01 本頁面
【正文】 題規(guī)模 n的增加而增長，即使算法中有上千條語句 ,其執(zhí)行時間也不過是一個較大的常數(shù)。此類算法的時間復(fù)雜度是 Ο(1)。 【 例 1】 交換 i和 j的內(nèi)容。 2020/9/16 33 【 例 2】 變量計數(shù)之一。 ? (1) x=0； =0； ? (2) for(k1； =n； ++) ? (3) x++； ? (4) for(i=1； =n； ++) ? (5) for(j=1； j=n； ++) ? (6) y++； ? 該算法段的時間復(fù)雜度為 T(n)=Ο(n2)。 ? 當(dāng)有若干個循環(huán)語句時，算法的時間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的頻度 f(n)決定的 。 2020/9/16 34 【 例 3】 變量計數(shù)之二 ? (1) x=1； ? (2) for(i=1； i=n； i++) ? (3) for(j=1； j=i； j++) ? (4) for(k=1； k=j； k++) ? (5) x++； ? 該算法段中頻度最大的語句是 (5)，從內(nèi)層循環(huán)向外層分析語句 (5)的執(zhí)行次數(shù)： ? 復(fù)雜度： O(n3) 2020/9/16 35 算法的描述方法 ⑴ 自然語言 優(yōu)點：容易理解 缺點：冗長、二義性 使用方法：粗線條描述算法思想 注意事項：避免寫成自然段 2020/9/16 36 ① 輸入 m 和 n； ② 求 m除以 n的余數(shù) r； ③ 若 r等于 0， 則 n為最大公約數(shù) ， 算法結(jié)束； 否則執(zhí)行第 ④ 步； ④ 將 n的值放在 m中 ， 將 r的值放在 n中； ⑤ 重新執(zhí)行第 ② 步 。 歐幾里德算法 2020/9/16 37 ⑵ 流程圖 優(yōu)點：流程直觀 缺點：缺少嚴密性、靈活性 使用方法：描述簡單算法 注意事項：注意抽象層次 2020/9/16 38 N 開始 輸入 m和 n r=m % n r=0 m=n； n=r 輸出 n 結(jié)束 Y 歐幾里德算法 2020/9/16 39 ⑶ 程序設(shè)計語言 優(yōu)點：能由計算機執(zhí)行 缺點：抽象性差，對語言要求高 使用方法：算法需要驗證 注意事項：將算法寫成子函數(shù) 2020/9/16 40 include int CommonFactor(int m, int n) { int r=m % n。 while (r!=0) { m=n。 n=r。 r=m % n。 } return n。 } void main( ) { coutCommonFactor(63, 54)endl。 } 歐幾里德算法 2020/9/16 41 偽代碼 —— 算法語言 偽代碼（ Pseudocode）：介于自然語言和程序設(shè)計語言之間的方法，它采用某一程序設(shè)計語言的基本語法，操作指令可以結(jié)合自然語言來設(shè)計。 優(yōu)點：表達能力強，抽象性強，容易理解 2020/9/16 42 1. r = m % n。 2. 循環(huán)直到 r 等于 0 m = n。 n = r。 r = m % n。 3. 輸出 n 。 歐幾里德算法 2020/9/16 43 遞歸算法的分析 1. 猜測技術(shù) :對 遞推關(guān)系式估計一個上限 ，然后 （ 用數(shù)學(xué)歸納法 ） 證明它正確 。 ?關(guān)鍵：根據(jù)遞歸過程建立遞推關(guān)系式 ， 然后求解這個遞推關(guān)系式 。 2020/9/16 44 擴展遞歸技術(shù) 設(shè) n=2k ? ? ? + = = 1 5 ) 2 ( 2 1 7 ) ( 2 n n n T n n T ) ( 10 3 10 ) 2 1 2 ( 5 7 2 5 7 ) ( 2 2 2 1 2 1 0 n O n n n n n n2 n n T k k i i = ? = + = ? ? ? ? ? + = = ? 2 2 2 1 1 2 2 2 2 2 2 5 ) 2 ( 5 2 ) 2 ( 5 2 ) 1 ( 2 5 ) ) 2 ( 5 ) ) 4 ( 5 ) 8 ( 2 ( 2 ( 2 5 ) ) 2 ( 5 ) 4 ( 2 ( 2 5 ) 2 ( 2 ) ( n n n T n n n n T n n n T n n T n T k k k + 180。 + + + = + + + = + + = + = L 2020/9/16 45 通用分治遞推式 大小為 n的原問題分成若干個大小為 n/b的子問題，其中 a個子問題需要求解，而 k是合并各個子問題的解需要的工作量。 ? ? ? + = = 1 ) ( 1 ) ( n b n aT n c n T k ? ? ? ? ? = = k k k b k k a b a n O b a n n O b a n O n T b ) ( ) log ( ) ( ) ( log 2020/9/16 46 第二部分 編程基本知識 2020/9/16 47 先看這道題 ? The Hardest Problem Ever hdu1048 ? 第 60題 2020/9/16 48 【 問題描述 】 ? Julius Caesar生活在一個危險而又充斥著陰謀的時代。 Caesar面對的最難的情況關(guān)系著他的存亡。為了讓自己生存，他決心去創(chuàng)造第一種加密方法之一。這個加密方法聽起來是這樣的令人難以置信，沒有一個人可以指出它（的原文）除非知道它怎樣工作。 你是 Caesar軍隊的一個分隊長。你的工作是破譯 Caesar送來的信息并匯報給你的上級。 密碼很簡單，每一個字母對應(yīng)著一個明文，你將明文向右五步來得到安全的信息。（比如，假如那個字母是 ‘ A’，密文就是 ‘ F’） 2020/9/16 49 ? 加密文本 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 明文文本 V W X Y Z A B C D E F G H I J K L M N O P Q R S T U 密文中只有字母被切換了，非字母的字符應(yīng)該保持不變，所有的字母都是大寫的。 2020/9/16 50 【 輸入 】 ? 這個問題的輸入包括一系列（非空）最多 100個數(shù)據(jù)。每一個數(shù)據(jù)的格式會按照以下格式，并且在不同組數(shù)據(jù)間不會有空行分隔。所有的字符都是大寫的。 一個單獨的測試數(shù)據(jù)包括三個部分： 1. 開始行：單獨的一行 “ START” 。 2. 加密的信息：單獨的一行，由 1~200個字符組成來自 Caesar的一行
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1