【正文】 eof(a))的最用是把數(shù)組 a清 0，在 ，很方便！ ? 代碼很規(guī)范 ！ 2020/9/16 57 對于字符串輸入的處理： ? C語法： char buf[20]。Z39。A39。 ? else ? { ? for(i=0。 ? int i。 2020/9/16 51 【 輸出 】 ? 對每一個測試數(shù)據(jù)只會有一行輸出。 一個單獨的測試數(shù)據(jù)包括三個部分： 1. 開始行：單獨的一行 “ START” 。（比如，假如那個字母是 ‘ 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 密文中只有字母被切換了，非字母的字符應該保持不變，所有的字母都是大寫的。這個加密方法聽起來是這樣的令人難以置信，沒有一個人可以指出它（的原文）除非知道它怎樣工作。 + + + = + + + = + + = + = L 2020/9/16 45 通用分治遞推式 大小為 n的原問題分成若干個大小為 n/b的子問題，其中 a個子問題需要求解，而 k是合并各個子問題的解需要的工作量。 3. 輸出 n 。 優(yōu)點：表達能力強，抽象性強，容易理解 2020/9/16 42 1. r = m % n。 r=m % 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ù)： ? 復雜度： 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í)行第 ② 步 。 【 例 1】 交換 i和 j的內(nèi)容。 2020/9/16 31 圖 T(n)與規(guī)模 n的函數(shù)關(guān)系 2020/9/16 32 ? Temp=i； i=j； j=temp； ? 以上三條單個語句的頻度均為 1，該算法段的執(zhí)行時間是一個與問題規(guī)模 n無關(guān)的常數(shù)。k=n。++i) for(j=1。 2020/9/16 28 再看看這個代碼： 對較復雜的算法計算算法的運行時間 ,經(jīng)常從算法中選取一種對于所研究的問題來說是 基本 (或者說是主要 ) 的原操作 ,以該基本操作在算法中重復執(zhí)行的次數(shù)作為算法運行時間的衡量準則 。k=n。 2020/9/16 27 ? 一個算法中 所有語句的頻度之和 構(gòu)成了該算法的運行時間。ACM程序設計 東北林業(yè)大學 陳宇 2020/9/16 2 第一講 算法原理和 ACM入門 (Introduction to ACM) 2020/9/16 3 我校的 ACM在線評測系統(tǒng) ? ? 課件下載地址： ? 2020/9/16 4 開課目的 ? 為林大 ACM代表隊培養(yǎng)后備人才 ? 提高分析問題和應用計算機編程解決問題的能力 ? 培養(yǎng)必要的自學能力 ? 培養(yǎng)學生的協(xié)調(diào)和溝通能力 ? 體會學習的快樂 2020/9/16 5 ACM/ICPC in China 中國大陸高校從 1996年開始參加 ACM/ICPC—— ? 前六屆中國賽區(qū)設在上海，由上海大學承辦； ? 2020年 ： 清華和西安交大； ? 2020年 ： 清華和中山 ； ? 2020年 ： 北大和上海交大 ； ? 2020年 ： 川大、北大和浙大 ； ? 2020年 ： 上海大學、清華和西電 ； ? 2020年：北航、南航、吉大、西華 ； ? 2020年：哈工程、北交、中科大、 杭電 、西南民大 ； ? 2020年：哈工 大 、中科大、 NIT、武大 、 東華； ? 2020年：天大、福大、川大、哈工程、浙江理工； 2020/9/16 6 ACM in NEFU ? 2020年 9月，第一次參加此類比賽（黑龍江省賽） ? 2020～ 2020，每年 5月 —— 黑龍江省第 1～ 5屆大學生程序設計競賽 ? 2020～ 2020，每年 6月 —— 東北地區(qū)第 1～ 4屆大學生程序設計競賽 2020～ 2020，每年 9月 —— 11月 第 29～ 34屆 ACM國際大學生程序設計競賽亞洲區(qū)預選賽 2020/9/16 7 預期賽事（今后每年） ? 3~4月，舉行校內(nèi)大賽（暨選拔賽） ? 4月， ACM全國邀請賽 ? 5月，參加黑龍江省大學生程序設計大賽 ? 6月，參加東北 4省大學生程序設計大賽 ? 10~11月，參加 ACM/ICPC亞洲區(qū)比賽（至少參加 4～5個賽區(qū) 的比賽） ? 另外，每學期至少有三次月賽以及適當?shù)木毩曎? 2020/9/16 8 2020年的風采 2020/9/16 9 2020/9/16 10 2020/9/16 11 2020/9/16 12 2020/9/16 13 2020/9/16 14 2020/9/16 15 2020/9/16 16 2020/9/16 17 2020/9/16 18 2020/9/16 19 2020/9/16 20 2020/9/16 21 2020/9/16 22 2020/9/16 23 第一部分 算法概述 算法分析的目的： ? 設計算法 —— 設計出復雜性盡可能低的算法 ? 選擇算法 —— 在多種算法中選擇其中復雜性最低者 算法分析（ Algorithm Analysis）：對算法所需要的兩種計算機資源 —— 時間和空間進行估算 ? 時間復雜性（ Time Complexity） ? 空間復雜性（ Space Complexity） 2020/9/16 24 評價算法 ? 評價算法的三條主要 標準 是： ? (1) 算法實現(xiàn)所耗費的 時間 ； ? (2) 算法實現(xiàn)所所耗費的存儲 空間 ，其中 ? 主要考慮輔助存儲空間； ? (3) 算法應易于 理解 ，易于編碼，易于調(diào) ? 試等等。 Ο是數(shù)量級的符號。++j) ? for(k=1。 ? 算法運行時間為： 3*n2+2n+2。i=n。