1、BISTU1BISTU 第第 2 2 章章 算法基礎算法基礎 BISTU2 內容提要 1、算法的概念、算法的概念 2、算法設計、算法設計 3、算法的評價、算法的評價 BISTU3 1、算法的定義 l 簡單地說，算法（Algorithm）是用計算機 解決計算問題時所采取的一系列計算步驟 組成的序列。 l 嚴謹的定義：“算法就是任何明確定義的 計算過程，該過程取某個值或值的集合作 為輸入并產生某個值或值的集合作為輸出。 這樣，算法就是把輸入轉換成輸出把輸入轉換成輸出的計算計算 步驟的一個序列步驟的一個序列。” BISTU4 2、算法的特性 （1）有窮性有窮性：能在執行有限個步驟之后結束 （2）確定

2、性確定性：每一步驟都必須明確、無二義性。 （3）可行性可行性：算法的每一步都是可行的，即算法的每 一步都能被計算機所理解和執行，并且能得到正確的結 果。 （4）零個或多個輸入零個或多個輸入：輸入可以來自鍵盤、文件或網 絡。程序可以沒有輸入。 （5）至少一個輸出至少一個輸出：沒有輸出的算法沒有意義。 BISTU5 3、算法設計的要求 正確性正確性 可讀性可讀性 健壯性健壯性 時間效率高時間效率高 存儲量需求低存儲量需求低 BISTU6 正確性正確性的層次的層次 算法程序沒有語法錯誤; 算法程序對于合法的輸入數據能夠產生滿 足要求的輸出結果; 算法程序對于非法的輸入數據能夠得出滿 足規格說明的結果

3、; 算法程序對于精心選擇的，甚至刁難的測 試數據都有滿足要求的輸出結果。 BISTU7 可讀性可讀性 為了便于閱讀、理解和交流，可讀性要素： 增加算法文件名、子圖、子程序、算法樣本數 據文件名的可讀性； 在算法語句中增加注釋語句，說明重要變量、 決策語句的用途； 將算法有關的文檔整理在一個目錄中 BISTU8 健壯性健壯性 能對輸入數據不合法的情況做合適的處理 比如輸入的時間或者距離不應該是負數 算法的健壯性表現在當輸入數據不合法時，算 法也能做出相關處理，而不是產生異常或無法 解釋的結果 BISTU9 時間效率高和存儲量需求低時間效率高和存儲量需求低 對于同一個問題，如果有多個算法能夠達 到

4、同樣的問題解決標準，執行時間最短的 算法效率最高 存儲量需求指的是算法在執行過程中需要 的最大存儲空間，主要指算法程序運行時 所占用的內存或外部硬盤存儲空間，越少 越好 BISTU10 4、算法的描述 四種方式描述算法的方法： l 自然語言自然語言：直觀、易于理解，但易產生歧義。 l 流程圖流程圖：流程圖描述了算法所要執行的操作的順 序及執行操作的條件。流程圖直觀形象、易于理 解。 l 偽代碼偽代碼：偽代碼既類似于自然語言，又使用與程 序設計語言相似的方法描述算法。這使得偽代碼 即能夠清晰地表達算法的結構，又不必像程序那 樣在細節上非常嚴謹。 l 程序設計語言程序設計語言：算法的終極表示。能運

5、行并獲得 結果。 BISTU11 【例【例2-1】用自然語言寫出求兩個正整數a，b 的最大公約數的算法。 歐幾里德算法又稱輾轉相除法，用于計算 兩個正整數a,b的最大公約數。 其計算原理依賴于定理 gcd(a,b) = gcd(b, a mod b) ， 其中gcd(a,b)表示正整數a，b的最大公約數 a mod b表示a/b后的余數。 BISTU12 【例【例2-1】用自然語言寫出求兩個正整數a，b 的最大公約數的算法。 用自然語言描述該算法的思路： 步驟1：輸入a，b。 步驟2：如果a小于b，則對換a、b的值。 步驟3：a除以b得余數r。 步驟4：若r 等于0,則b為所求的最大公約數；

6、否則，以b為a、r為b,繼續步驟3。 BISTU13 【例【例2-2】從一組數（至少兩個）中找到最大 的數。 步驟1：輸入這一組數。 步驟2：將最大數置為第一個數。 步驟3：將下一個數和最大數進行比較，如 果該數大于最大數，將最大數置為該數， 反之保持最大數不變。 步驟4：重復步驟3，直至比較至最后一個 數，此時，將得到最大數。 BISTU14 流程圖 用圖框圖框表示各種操作，用流程線流程線表示操作的執行 順序。 流程圖描述了算法所要執行的操作的順序及執行 操作的條件。 流程圖直觀形象、易于理解。 美國國家標準化協會（American National Standard Institute ,

7、ANSI）規定了常用的程序流程圖符號 BISTU15 流程圖符號 常用的流程圖符號 起止框起止框判斷框判斷框處理框處理框輸入輸入/ /輸出框輸出框 注釋框注釋框流向線流向線 連接點連接點 BISTU16 算法的三種基本結構 三種基本結構： 順序結構 選擇結構 循環結構 任何算法都是上述三種結構的組合。 BISTU17 算法的三種基本結構 （a) 順序結構 (b) 選擇結構 (c1) 直到型 循環結構 (c2) 當型 循環結構 BISTU18 【例【例2-3】用流程圖描述求兩個正整數a，b的 最大公約數的算法。 采用歐幾里得 算法求兩個正 整數的最大公 約數。該算法 的流程圖如右 圖。 BIST

8、U19 【例【例2-4】從一組數（至少兩個）中找到最大 的數的算法。 右圖表示 的算法適 用于使用 數組來存 放輸入的 數據 BISTU20 【例【例2-4】從一組數（至少兩個）中找到最大 的數的算法 右圖表示的算 法適用于反復 使用一個變量 來存放輸入的 數據 BISTU21 基于流程圖的編程環境 為了幫助學生繞過編程語言來實現算法，出現了 多種基于流程圖的編程環境，其中開源軟件 Raptor就是一個優秀的流程圖工具。 Raptor 是一種基于流程圖的編程環境，不必記憶 復雜的編程語言語法，就可實現一個算法 Raptor中的用流程圖表示的算法可以直接執行， 并顯示執行結果。 上機實驗指導的第

9、2章，給出了幾個基于Raptor環 境的算法設計實驗，供同學們練習。 BISTU22 偽代碼（本部分內容僅要求理解） 使用偽代碼(Pseudocode)描述算法是一種常用 的方法。 偽代碼既類似于自然語言，又使用與程序設 計語言相似的方法描述算法。這使得偽代碼 即能夠清晰地表達算法的結構，又不必像程 序那樣在細節上非常嚴謹。 偽代碼沒有通用的語法標準 BISTU23 偽代碼規范的內容 我們采用了如下偽代碼規范： （1）變量 在偽代碼中，變量不需聲明，變量名是字母開頭、由字母數 字組成的符號串，用小寫表示，例如x、y、a1。 （2）表達式 表達式是由運算符將運算量（常量、變量或表達式）連接起 來

10、的式子，分為算術表達式、關系表達式、邏輯表達式。 BISTU24 運算符和表達式 算術運算符用 +、-、*、/、% 表示加、減、乘、除、求余 運算。 關系運算符用 、表示判斷“是否等 于”、“是否不等于”、“是否小于”、“是否大于”、 “是否小于等于”、“是否大于等于”。 邏輯表達式用 and、or、not表示“并且”、“或者”、“ 非”。 例子： b*b-4*a*c 是一個算術表達式； a+bc and b+ca and a+cb 是一個邏輯表達式，其中又 包括了三個關系表示式。 BISTU25 偽代碼規范的內容 （3）賦值 用“=”表示賦值，如x=e表示將e的值賦給x （4）注釋 用“/”

11、表示注釋開始，一直到該行的行尾。注釋是對偽代碼 的更詳細的解釋說明。 （5）選擇語句 IF （表達式C） THEN 語句塊S1 ELSE 語句塊S2 BISTU26 偽代碼規范的內容 （6）循環語句 這里給出兩種循環語句：當型循環(即WHILE循環)、FOR型循 環。 當型循環的基本形式： WHILE (表達式C) 語句塊S FOR循環的基本形式： FOR (i=begin TO end ) 語句塊S BISTU27 偽代碼規范的內容 （7）數組 用數組來表示一組相同類型的數據，其中每個數據稱為數組 元素。 用 aj 表示數組a的第j個元素。 a1. j表示含元素a1、 a2、 aj的數組，符

12、號“. ”用 來指示數組中下標取值的范圍。 BISTU28 【例【例2-5】用偽代碼寫出求兩個正整數a，b的最大公 約數的算法。 輸入：正整數a,b 輸出：a,b的最大公約數 GCD(a,b) 1 IF （ab） / 如果ab 2 THEN 3 c=a 4 a=b 5 b=c 6 r = a%b /求a除以b后的余數 7 WHILE （r0） 8 a=b 9 b=r / 實施“輾轉相除” 10 r = a%b 11 返回（b） BISTU29 【例【例2-6】用偽代碼寫出用偽代碼寫出從一組數（至少兩個）中找 到最大數的算法。 輸入：數組a1. n 輸出：最大值 MaxValue(a1. n)

13、1 max=a1 2 k=2 3 WHILE （kn） 4 IF （maxak） 5 THEN 6 max= ak 7 k=k+1 8 返回（max） BISTU30 程序設計語言 用程序設計語言描述算法是計算機算法的 終極表示。 設計算法的目標就是為了使算法能在計算 機上運行并獲得結果。 程序設計語言表示的算法恰恰實現了這一 目標。 一個算法可以用多種不同的程序設計語言 表示。 BISTU31 【例【例2-7】用用C語言實現語言實現求兩個整數的最大公 約數程序。 #include int main() int a , b , c , r ; printf(請輸入整數a,b: ); scanf

14、(%d%d, if(ab) c=a; a=b; b=c; r=a%b; while(r!=0) a=b; b=r; r=a%b; printf(result=%dn,b); return 0; BISTU32 三、 算法設計 l算法設計策略 l簡單排序算法 l簡單查找算法 BISTU33 （一）常用的算法設計策略 算法設計過程中，發現問題、分析問題及解決問 題的思路、步驟與其他學科中的方法是一致的， 就是尋找規律 計算機科學家在算法研究過程中總結了一些具有 普遍意義的算法策略和一些可循的規律，能夠幫 助我們較快地找到算法 BISTU34 （一）常用的算法設計策略 本節討論幾個常用的算法設計策略

15、： l窮舉法 l遞推法 l遞歸法 l分治法 l貪心法 BISTU35 1、窮舉法 n 也稱蠻力法，它是一種簡單而直接的問題求解方法 ，解題思路常常直接基于問題的描述，是計算機求 解最容易應用的方法，也是比較耗時的算法。 n 有很多問題，根據其描述和相關的知識，能確定一 個大概的解空間范圍大概的解空間范圍，在這個解空間范圍內，按照 某種順序一一枚舉一一枚舉和檢驗檢驗每個可能的值每個可能的值，直到找到 一個或全部符合條件的值（即問題的解），有時候 甚至可能無解可能無解。 BISTU36 窮舉法 采用窮舉法解題的基本思路： n 確定窮舉對象、窮舉范圍和判定條件； n 一一窮舉可能的解，驗證是否是問題

16、的解 在窮舉法中，窮舉對象的選擇對象的選擇也是非常重 要的，它直接影響著算法的時間復雜度， 選擇適當的窮舉對象可以獲得更高的效率 BISTU37 窮舉法 舉例 【例【例2-9】古典數學問題：百錢買百雞問題。 某人有一百元錢，要買一百只雞。其中 ，公雞五元一只，母雞三元一只，小雞一 元三只。問：如何用一百元錢正好買一百 只雞？ BISTU38 百錢買百雞問題 算法分析 n 第一步：先計算一下100元錢最多能買多少只公雞 和母雞： u經計算：100元錢最多最多能買20只公雞只公雞；100元錢最多最多能 買33只母雞只母雞；當然，雖然100元錢能買300只小雞，受 條件約束，小雞的數目必須在100以

17、內。這樣，就初步就初步 確定了此問題的解空間范圍。確定了此問題的解空間范圍。 n 第二步：檢驗公雞、母雞、小雞的數目哪種組合 能滿足總價錢為100元。 n設求出的解為公雞x只、母雞y只、小雞z只，則x、y、z 滿足條件是“5x+3y+z/3正好等于100”。 BISTU39 用偽代碼描述百千買百雞問題的算法 (注：算法中“/”表示對算法步驟的注釋) FOR( x =0 TO 20 ) /x取值范圍為取值范圍為020，判斷一次x值增加1。 FOR( y =0 TO 33 ) / y取值范圍為取值范圍為033，判斷一次y值加1 z = 100-x-y; /小雞最多100只，但根據x，y計算出小 /

18、雞的數目，這樣就縮小了窮舉范圍 IF (x*5+y*3+z/3 = 100) /判斷條件 THEN 輸出x,y,z的值 BISTU40 如果需要解決的問題規模不大 用窮舉法設計的算法其速度是可以接受的 BISTU41 分析：分析： 對對5 5本書從本書從1 1至至5 5編號，假設編號，假設a,ba,b兩個人分別借這兩個人分別借這5 5 本書中的本書中的1 1本。當本。當a=ia=i時，表示時，表示a a借了編號為借了編號為i i的書。的書。 則則a a、b b的取值范圍為：的取值范圍為：1 = 1 = a a、b= 5b= 5 當當2 2個人所借的書的編號不相同時（個人所借的書的編號不相同時（

19、a!=ba!=b） ，就，就 是滿足題意的一種借閱方法。是滿足題意的一種借閱方法。 問題：問題：小明有小明有5 5本新書，要借給、兩位小朋友，若本新書，要借給、兩位小朋友，若 每人每次只能借一本，則可有多少種不同的借法？每人每次只能借一本，則可有多少種不同的借法？ 算法：算法： 1.1.考察考察a a可能的范圍：可能的范圍：a=1a=1，2 2，3 3，4 4，5 5； 2.2.考察考察b b可能的范圍：可能的范圍：b=1b=1，2 2，3 3，4 4，5;5; 3.3.驗證驗證a,ba,b的所有取值，若的所有取值，若a!=ba!=b，則輸出，則輸出a,ba,b。 BISTU42 2、遞推法

20、遞推法是利用問題本身所具有的一種遞推 關系求解問題的一種方法 所謂遞推，是指從已知的初始條件出發，依據 某種遞推關系，逐次推出所要求的各中間結果 及最后結果 其中初始條件或是問題本身已經給定，或是通 過對問題的分析與化簡后確定 BISTU43 可遞推求解的問題特點 該類題目一般有以下二個特點： n問題可以劃分成多個狀態； n除初始狀態外，其它各個狀態都可以用固定的 遞推關系式來表示 在實際解題中，該類題目一般不會直接給 出遞推關系式，而是需要通過分析各種狀 態，找出遞推關系式 BISTU44 猴子吃桃問題 小猴子摘桃若干，立即吃了一半 還覺得不過癮，又多吃了一個； 第二天接著吃剩下桃子的一半，

21、仍 覺得不過癮又多吃了一個，以后小 猴子都是吃剩下的桃子一半多一個 ； 到第10天小猴子再去吃桃子的時候 ，看到只剩下一個桃子； 則小猴子第一天共摘了多少桃子？ BISTU45 遞推問題求解 由題意可以得到下表： 分析后可知，猴子吃桃問題遞推關系為： nSn=1 （當n=10時） nSn =2（Sn+1+1）（當1n10時） 在此基礎上，以第10天的桃數作為基數， 用以上歸納出來的遞推關系設計出一個循 環過程，將第1天的桃數推算出來 BISTU46 斐波那契數列 n斐波那契數列（Fibonacci）：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ， n數

22、列的規律：數列的規律：這個數列從第3項開始，每一 項都等于前兩項之和。 n第1項和第2項為初始項。即，f1=1，f2=1， nf3=f1+f2，fn=fn-1+fn-2 (當n3時)。逐步求 出所需要的斐波那契數列項。 n遞推關系式遞推關系式 fn=fn-1+fn-2 BISTU47 費波納切數列的奇妙性質 隨著數列項數的增加，前一項與 后一項之比越逼近黃金分割 0.6180339887，因此，斐波那契 數列也稱黃金分割數列。 斐波那契數列在物理學、化學、 經濟領域、生物學都有直接應用 。 它與自然界的許多現象也有很多 巧合，例如許多植物的花瓣數呈 現斐波那契數列特性。 BISTU48 用偽代

23、碼描述求斐波那契數列的算法 f1=1 f2=1 輸出f1,f2的值 FOR( i =2 TO 20 ) /本算法求費波納契的前20項 f3 = f1+f2; /后一項等于前兩項之和 輸出f3的值; f1=f2; / 為了得到新的f3更新f1 f2=f3; / 為了得到新的f3更新f2 BISTU49 3、遞歸法 能采用遞歸描述的算法通常有這樣的特征： 為求解規模為N的問題，設法將它分解分解成規模較 小的問題，然后從這些小問題的解方便地構造出 大問題的解。（分解時會利用遞推公式） 并且，這些規模較小的問題也能采用同樣的分解分解 和綜合綜合方法，分解成規模更小的問題，并從這些 更小問題的解構造出規

24、模較大問題的解。 特別地，當規模N=1時，能直接得解。 遞歸算法的執行過程分為問題分解分解和回歸回歸兩 個階段。 BISTU50 用遞歸法求費波納切數列 例如，編寫計算斐波那契數列的第n項函數 fib(n)。 實現該函數的核心偽代碼為： IF ( n=1 or n=2) THEN 得到函數值為 1 ELSE 計算 fib(n-1)+fib(n-2) 的值 BISTU51 4、分治法 分治法（分治法（Divide and Conquer）的基本思想是，將 一個較大規模的問題分解為若干個較小規模的子 問題，找出子問題的解，然后把各個子問題的解 合并,從而得到整個問題的解 分治法的分（Divide）

25、是指將較大的問題劃分 為若干個較小的問題，然后用遞歸法求解子問 題； 分治法的治（Conquer）是指從小問題的解來構 建大問題的解 BISTU52 4、分治法 分治法算法中至少包含有兩次遞歸過程，只有一 個遞歸過程的算法在嚴格意義上不能算作分治算 法 二分查找算法采用了分治法策略 分治法在每一層遞歸上都有三個步驟。 （1）分解：將原問題分解為若干個規模較小，相互獨立，與原問 題形式相同的子問題； （2）解決：若子問題規模較小而容易被解決則直接解，否則遞歸 地解各個子問題； （3）合并：將各個子問題的解合并合并為原問題的解。 BISTU53 二分查找算法中的分治法策略 計算n/2，得到序列的中

26、間位置值 mid，于是待查找的有序序列以 amid為界限，被分成個數大致相同的兩半。 原任務得到一次分解 。 判斷amid的值是否等于key。 若amid等于key，則在序列中找到指定元素，查找過程結束。 若amid小于key，則繼續在amid右側序列中查找指定元素（遞歸查找）。 若amid大于key，則繼續在amid左側序列中查找指定元素（遞歸查找）。 采用上述同樣的方法處理左右兩部分序列，直到找到滿足條件的 記錄，使查找成功；或直到無法在分出子序列為止，此時查找不 成功。 BISTU54 5、貪心法 貪心法是指，在對復雜問題求解時，總是做出在 當前看來最好的選擇（即局部最優）。 貪心法是一

27、種不追求最優解、只希望得到較為滿 意解的方法。 貪心法一般可以快速得到滿意的解，因為它省去 了為找最優解要窮盡所有可能而必須耗費的大量 時間。 貪心法以當前情況為基礎作最優選擇，而不考慮 各種可能的整體情況。 BISTU55 “數字三角形”問題 一個“數字三角形”如右圖所 示。 從三角形的頂點出發，向下行 走，到達最底層的某一個節點 ，稱為一條路徑。 每次向下層行走時，只能看到 其下接的兩個相鄰節點。 問：能否找到一條路徑，使得 路徑上節點值之和最大（稱為 最大權值路徑，每個節點的值 稱為“權”）？ BISTU56 用貪心法的求解數字三角形的過程 用貪心法的求解過程： 從第一層的節點5向下走，

28、使用貪心策略，選擇第 二層中的較大者（即節點4）。 繼續從第二層的節點4向下走，使用貪心策略，選 擇第三層中的較大者（即節點8）。 繼續按此方法向下行走，最終得到一條符合局部局部 最優的路徑最優的路徑 5 4 8 10 5（權值32）。 BISTU57 用貪心法最終得到一條符合局部最優的路徑局部最優的路徑 5 4 8 10 5（權值32）。 而實際上，數字三角形的最大權值路徑為而實際上，數字三角形的最大權值路徑為5 4 6 7 15（權值（權值37）。）。 用什么方法能求出最優解呢，用什么方法能求出最優解呢，-動態規劃法動態規劃法 感興趣的同學可查閱資料，了解此算法。感興趣的同學可查閱資料，了

29、解此算法。 BISTU58 6、迭代法 (選講) 迭代是數值計算中通過從一個初始估計出 發尋找一系列近似解來解決問題（一般是 解方程或者方程組）的過程 為實現這一過程所使用的方法統稱為迭代法（ Iterative Method） BISTU59 6、迭代法 一個簡單的代數方程 求上述方程根的 一種迭代法 令x0初始值為1，則代入上 式，可計算出x1 為2， 再次代入迭代式，得出x2為1.5，直到滿足條件： 新求出的值與上一次值相差不超過10-9 01 2 xx n n x x 1 1 1 BISTU60 （二）排序與查找算法 從浩瀚的數據中找到用戶所需的數據，是計算機 處理數據的基本操作之一。

30、 尤其是互聯網發達的今天，使用計算機的人經常 會用搜索引擎查找并下載自己所需的文字、圖片 等信息。 例如，我們使用搜索引擎（比如“百度”）查找 關鍵詞“算法”，搜索引擎就去從百度服務器的 “索引庫”中搜索出所有包含“算法”的頁面， 并顯示在瀏覽器窗口。 BISTU61 1、查找算法 從一系列數據中找到需要的數據，需要使用查找 算法，其中需要查找的數據稱為查找關鍵字（ Search Key）。 人們已經研究出了多種不同的查找算法，不同的 算法查找策略和效率不同。 本節只討論兩種簡單、常用的查找算法： 順序查找 二分查找。 BISTU62 （1）順序查找 順序查找，也稱線性查找， 其執行過程是：

31、從一組數據（也稱線性表）中的第一個數據元素開始， 依次查看每一個元素，將其與查找關鍵字進行比較， 若發現此元素的值與查找關鍵字相等，即找到所需的數 據元素，查找成功； 反之，若查到最后一個數據元素若查到最后一個數據元素，數據元素的值都不與 查找關鍵字相等，則表明線性表中沒有所找的元素，查 找失敗。 BISTU63 （1）順序查找 課堂練習：用一個“尋找秘密號碼”小游戲來模 擬順序查找算法。 然后請回答下列問題： 在一次游戲中，你最多花費的猜測次數是多少？你最 少花費的猜測次數是多少？ 在一次游戲中，你第一次就能猜對的概率是多少呢？ 在游戲中，平均花費多少次猜測能猜對呢？ 在一次游戲中，如果秘密

32、號碼卡片不在這些卡片中， 要猜多少次才能發現呢？ BISTU64 （1）順序查找 l 右圖為順序查找算法流程圖 l 輸入：n個數據組成的一個 序列，查找關鍵 字key。這里假定n的值已知 。 l 輸出：key在序列中的位置 ，或者key不在序列中的信 息。 l 提示：因為從第一個數據開 始比較，所以令k=1 BISTU65 （2）二分查找 二分查找，也稱折半查找， BinarySearch ， 它的基本思想是，將n個元素分成個數 大致相同的兩半（這里假設此數據序列按升序排 列），取an/2與欲查找的 key 作比較 如果key=an/2，則找到key，算法終止。 如果keyan/2，則只要在數

33、據序列的右半部繼續搜索key BISTU66 （2）二分查找 二分查找算法的自然語言描述： 輸入：n個數據組成的一個序列，查 找關鍵字key。這里假定n的值已知。 輸出：key在序列中的位置，或者key不在序列中 的信息（此算法中用0表示）。 BISTU67 （2）二分查找 二分查找算法的自然語言描述： 第一步：設查找區間初值，即設區間下界left=1,設區間上界 right=n； 第二步：如果 leftright 則 計算中間位置 mid=(left+right)/2; (除不盡時舍小數取整) 否則 查找失敗，算法結束。 第三步： 如果 keyamid 則 left=mid+1, 并繼續執行

34、第二步； 如果 key=amid 則 查找成功成功，返回目標元素位置位置mid。 BISTU68 （2）二分查找 二分查找算法的 流程圖描述： BISTU69 （2）二分查找 課堂練習： n設由10個元素組成的從小到大排列的有序序列 a1，a2，a3，a10為：1，5，8，9，12，14，15 ，18，20，25，要求查找元素18是否在序列中 。請寫出查找過程中變量left,right,mid的取值， 以及查找成功花費的查找次數查找成功花費的查找次數。 n請與順序查找算法做比較，查找同一個的數， 順序查找算法所需的查找次數。 n哪個算法效率高？ BISTU70 2、排序算法 在計算機科學中，排

35、序是研究最多的問題之一。通過排序 ，將一組無序的數據序列調整為按照元素關鍵字排序的有 序序列（這里，一個數據元素可能包含多個子項，其中參 與排序比較的子項稱為關鍵字）。 排序分為內部排序和外部排序。如果整個排序過程都在計 算機的內存里完成，稱為內部排序；如果排序的數據量非 常大，整個排序過程不可能在內存里完成，則稱為外部排 序。 本節只討論幾種常見的內部排序算法：選擇排序、冒泡排 序和插入排序。 BISTU71 （1）選擇排序 選擇排序算法的思路： 第一步：從所有數據中選一個最小數，作為已排 序的第一個數； 第二步：從剩下未排序數據中選最小的數，添加 到已排序數據的后面； 第三步：反復執行步驟

36、第二步，直到所有數據都 處理完畢。 把第二步的操作稱為一趟排序。n個元素的序列需 要n-1趟排序，就能變成有序序列。 BISTU72 （1）選擇排序 右圖演示了對數列 12，18，10，23，4， 30，25 進行選擇排序的過程 。有序區間用中括 號標出，其右側為 無序區間。 虛線表示數據互換 BISTU73 （1）選擇排序 課堂練習： 設由10個元素組成的無序序列 a1，a2，a3， a4，a5，a6， a7，a8，a9，a10 值為：12，8，15，3，4，2，1，18，20，25 ，按照選擇排序算法對該序列排序，要求寫 出每趟排序中的有序區和無序區區間。 BISTU74 （2）冒泡排序

37、冒泡排序的基本思想： 將全部數據元素分成兩部分：有序序列 和無序序列。無序序列的初始序列為，有序 序列的初始序列為空。 冒泡排序的基本操作是比較相鄰的元素， 如果第一個比第二個大，就交換他們兩個在序列中的位置，讓較小 的居前，較大者居后。 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對 。 最后的元素將是值最大的數據，將該元素加入到有序序列中，并令 無序序列的長度減1。 BISTU75 （2）冒泡排序 下圖演示了對數列12，18，10，23，4，30，25進行冒泡 排序的過程。 有序區間用中括號標出。 BISTU76 （2）冒泡排序 課堂練習： 設由10個元素組成的無序序列 a1，

38、a2，a3， a4，a5，a6， a7，a8，a9，a10 值為：12，8，15，3，4，2，1，18，20，25，按 照冒泡排序算法對該序列排序，要求寫出每趟排 序中的有序區和無序區區間。 與選擇排序進行對比，分別統計排序過程中進行 數據比較的次數。 BISTU77 （3）插入排序 插入排序的基本思想： 將全部數據元素分成兩部分： 有序序列和無序序列。 有序序列的初始序列為，無序序列的初始序列 為。 插入排序的基本操作：將無序序列中的一個數據插 入到已經排好序的有序序列中，并要求插入后的序 列仍然有序。進行n-1次插入并排序的操作后，將使 全部數據得到排序。 BISTU78 （3）插入排序

39、插入排序效率不高，但是容易實現。它借助了逐步 擴大成果的思想，使有序列表的長度逐漸增加，直 至其長度等于原列表的長度。 BISTU79 下圖演示了對數列12，18，10，23，4，30，25進行插入排 序的過程。有序區間用中括號標出，其右側為無序區間 圖中，將18 放入有序區 時不需要移 動數據，而 將10放入有 序區時則需 要移動數據， 為什么？ BISTU80 （3）插入排序 課堂練習： 設由10個元素組成的無序序列 a1，a2，a3， a4，a5，a6， a7，a8，a9，a10 值為：12，8，15，3，4，2，1，18，20，25 ，按照插入排序算法對該序列排序，要求寫 出每趟排序中

40、的有序區和無序區區間。 BISTU81 四、算法的評價 對同一個問題，可用不同的算法來解決， 執行這些算法所用的時間和存儲空間也各 不相同。 一個算法的質量優劣通常用時間復雜度時間復雜度和 空間復雜度空間復雜度來衡量。 BISTU82 1、時間復雜度 同一個算法在不同的軟硬件環境下，運行時間會有較 大差異。 因此，不能用算法的實際執行時間來衡量時間復雜度 通常是拋開計算機軟硬件環境，只對算法中的計算工 作量進行統計。 算法中語句執行次數越多，它花費的時間就越多。 只有順序結構和選擇結構的程序，其執行時間基本固 定 而循環結構的程序，其執行時間與問題的規模有關 BISTU83 例如，下述算法：

41、FOR( i =1 TO n ) / i的取值范圍為1n，此外層for語句執行次數為n FOR( j =1 TO n ) / j的取值范圍為1n，此for語句執行次數為n2 k = 100-i-j; /該步驟是基本操作，執行次數為 n2 IF (i*5+j*3+k/3 = 100) /該步驟是基本操作，執行次數為n2 THEN 輸出i,j,k的值 可見，這段用偽代碼描述的算法總的執行次數是：f(n) = 3n2+n。 BISTU84 1、時間復雜度 一般情況下，算法的基本操作重復執行的次數是 問題規模n的某一函數f(n)。 當問題的規模n趨向于無窮大時，如果f(n)的值增 長緩慢，則算法為優。

42、 一般用f(n)的數量級O來粗略的表示算法的時間復 雜度，即T(n) = O ( f(n) )。 上例中的時間復雜度可粗略地表示為 T(n) = O( n2 ) 。 BISTU85 2、空間復雜度 算法的空間復雜度是指執行這個算法所需要的內存空間算法的空間復雜度是指執行這個算法所需要的內存空間， 用S(n)表示，其中n表示問題的數據規模。 執行算法所需的內存空間其實包括兩部分：固定空間和可 變空間。 固定空間是算法執行時運行環境本身所占用的內存空間， 與問題規模無關，不屬于算法的空間復雜度考慮范圍內的 空間； 可變空間是存儲問題中的數據所占的空間。 一個算法所需的存儲空間用f(n)表示，算法的

43、空間復雜度 S(n) = O ( f(n) )。 在實際應用中，設計算法時，只要計算機的內存容量許可 ，一般都是用空間換時間。 BISTU8686 BISTU87 RAPTOR基本程序環境 基本界面 BISTU88 四種基本符號/語句 目的目的符號符號名稱名稱 說明說明 輸入 輸入語句輸 入 數 據 給 一個變量變量 處理 賦值語句使 用 各 類 運 算 來 更 改 的 變量變量的值 處理 過程調用執 行 一 組 在 命 名 過 程 中 定義的指令 輸出 輸出語句顯 示變 量變 量的 值。 BISTU89 變量 變量（variable）表示的是計算機內存中的 位置，用于保存數據值 在任何時候，

44、一個變量只能容納一個值 在程序執行過程中，變量的值可以改變 BISTU90 變量賦值過程 說明說明X的值的值程序程序 當程序開始時，沒有 任何變量存在 未定義 第一個賦值語句，X32， 分配數據值32給變量X 32 下一個賦值語句， XX +1，檢索到當前X的 值為32，給它加1，并把 結果33給變量X 33 下一個賦值語句，XX * 2，檢索到X當前值為33， 乘以2，并把結果66給變 量X 66 BISTU91 RAPTOR變量值的設置 基本原則： 任何變量在被引用前必須存在并被賦值 變量的類型由最初的賦值語句所給的數據決定 設置方法 通過輸入語句賦值 通過賦值語句的中的公式運算后賦值 通

45、過調用過程的返回值賦值 BISTU92 RAPTOR數據類型 數值（Number）： 如12，567，-4，3.1415，0.000371 字符串 （String）： 如“Hello， how are you?”， “James Bond”， “The value of x is： ” 字符（Character）： 如A，8，!。 BISTU93 變量報錯的原因 未定義引用 BISTU94 變量報錯的原因 拼寫錯 BISTU95 不同類型的數據不可比較 BISTU96 RAPTOR常量 RAPTOR定義了四個常量（Constant） pi（圓周率） 定義為 3.1416 e （自然對數的底）定

46、義為 2.7183 true /yes(布爾值: 真) 定義為 1 false/no(布爾值：假) 定義為 0 BISTU97 輸入輸入(Input)語句語句 輸入語句的編輯 （Edit）對話框 提示部分 變量部分 BISTU98 輸入輸入(Input)語句語句 輸入語句在流 程圖中顯示的 狀態 運行時對話框 BISTU99 賦值語句（編輯） Set部分為接受賦值的變量或數組元素 To部分為表達式 BISTU100 賦值語句（顯示） 流程圖中的賦值語句 BISTU101 表達式表達式 可以是任何計算單個值的簡單或復雜公式 是值（無論是常量或變量）和運算符的組 合。 例如，考慮下面的兩個例子：

47、（1）x (3+9)/3（2）x 3+(9/3) BISTU102 表達式計算的“優先順序” 1. 計算所有函數的值，然后； 2. 計算括號中表達式，然后； 3. 計算乘冪(，*)，然后； 4. 從左到右，計算乘法和除法，最后 5. 從左到右，計算加法和減法。 BISTU103 內置運算符和函數 數學運算: +，-，*，/，*（加、減、乘、除、乘方） mod， sqrt（求余，開平方） log， abs， （對數，絕對值） ceiling， floor （向下取整，向上取整） BISTU104 內置運算符和函數 三角函數: sin，cos，tan；正弦正弦 ，余弦余弦 ，正切正切 cot，ar

48、csin，arccos；余切余切 ，反正弦反正弦 ，反余弦反余弦 arctan， arccot；反正切反正切 ，反余切反余切 BISTU105 過程調用語句(編輯) 編輯對話框 注意已有過程提示 BISTU106 過程調用語句（顯示） 注意，內置過程，子圖，子程序的調用使 用同樣的語句，但子圖沒有參數；內置過 程或子程序需要參數 BISTU107 輸出語句 執行輸出語句將 在主控（Master Console）窗口顯 示輸出結果 輸出的結果可以 使用或不使用換 行操作 BISTU108 輸出語句的設計技巧 BISTU109 注釋 注釋本身對計算機毫無意義，并不會被執 行。注釋的目的是增強程序的

49、可讀性，幫 助他人理解你所設計的程序或算法 BISTU110 一個帶注釋的算法 注釋的四種類型： 1.編程標題 2.分節描述 3.邏輯描述 4.變量說明 BISTU111 RAPTOR基本程序環境 基本界面 BISTU112 四種基本符號/語句 目的目的符號符號名稱名稱 說明說明 輸入 輸入語句輸 入 數 據 給 一個變量變量 處理 賦值語句使 用 各 類 運 算 來 更 改 的 變量變量的值 處理 過程調用執 行 一 組 在 命 名 過 程 中 定義的指令 輸出 輸出語句顯 示變 量變 量的 值。 BISTU113 變量 變量（variable）表示的是計算機內存中的 位置，用于保存數據值

50、在任何時候，一個變量只能容納一個值 在程序執行過程中，變量的值可以改變 BISTU114 變量賦值過程 說明說明X的值的值程序程序 當程序開始時，沒有 任何變量存在 未定義 第一個賦值語句，X32， 分配數據值32給變量X 32 下一個賦值語句， XX +1，檢索到當前X的 值為32，給它加1，并把 結果33給變量X 33 下一個賦值語句，XX * 2，檢索到X當前值為33， 乘以2，并把結果66給變 量X 66 BISTU115 RAPTOR變量值的設置 基本原則： 任何變量在被引用前必須存在并被賦值 變量的類型由最初的賦值語句所給的數據決定 設置方法 通過輸入語句賦值 通過賦值語句的中的公

51、式運算后賦值 通過調用過程的返回值賦值 BISTU116 RAPTOR數據類型 數值（Number）： 如12，567，-4，3.1415，0.000371 字符串 （String）： 如“Hello， how are you?”， “James Bond”， “The value of x is： ” 字符（Character）： 如A，8，!。 BISTU117 變量報錯的原因 未定義引用 BISTU118 變量報錯的原因 拼寫錯 BISTU119 不同類型的數據不可比較 BISTU120 RAPTOR常量 RAPTOR定義了四個常量（Constant） pi（圓周率） 定義為 3.141

52、6 e （自然對數的底）定義為 2.7183 true /yes(布爾值: 真) 定義為 1 false/no(布爾值：假) 定義為 0 BISTU121 輸入輸入(Input)語句語句 輸入語句的編輯 （Edit）對話框 提示部分 變量部分 BISTU122 輸入輸入(Input)語句語句 輸入語句在流 程圖中顯示的 狀態 運行時對話框 BISTU123 賦值語句（編輯） Set部分為接受賦值的變量或數組元素 To部分為表達式 BISTU124 賦值語句（顯示） 流程圖中的賦值語句 BISTU125 表達式表達式 可以是任何計算單個值的簡單或復雜公式 是值（無論是常量或變量）和運算符的組 合。 例如，考慮下面的兩個例子： （1）x (3+9)/3（2）x 3+(9/3) BISTU126 表達式計算的“優先順序” 1. 計算所有函數的值，然后； 2. 計算括號中表達式，然