1、第 2 頁第一章 基于計算機的問題求解 第二章 計算機信息數字化基礎 第三章 計算機的工作原理與硬件體系結構第四章 計算機軟件平臺第五章 計算機網絡平臺第六章 數據處理與數據庫第七章 計算與計算學科第八章 算法與程序設計第九章 實用軟件 第十章 計算機科學前沿技術第 3 頁第八章 算法與程序設計 奧巴馬關于奧巴馬關于“100100萬個萬個3232位整數排序位整數排序”問題的回答。問題的回答。20082008年奧巴馬當選美國總統后訪問谷歌總部，谷歌董事年奧巴馬當選美國總統后訪問谷歌總部，谷歌董事長埃里克長埃里克. .施密特問了他一個問題：施密特問了他一個問題：“獲得總統這份工獲得總統這份工作很難

2、，獲得谷歌的工作也很難。為檢驗奧巴馬的資作很難，獲得谷歌的工作也很難。為檢驗奧巴馬的資格，如果為格，如果為100100萬個萬個3232位整數排序，最有效的辦法是什位整數排序，最有效的辦法是什么？么？”奧巴馬答：奧巴馬答：“總之，冒泡排序是錯的總之，冒泡排序是錯的。”第 4 頁 8.1 算法 8.2 典型問題的算法設計 8.3 數據結構 8.4 程序設計第8章 算法與程序設計第八章 算法與程序設計 第 5 頁 8.1 算法8.1.1 算法的定義“一個算法，就是一個有窮規則的集合，其中之規則規定了一個解決某一特定類型的問題的運算序列。”當代著名計算機科學家D.E.KnuthTHE ART OF C

3、OMPUTER PROGRAMMING 求解問題的分步驟方法 輸入數據輸出結果算法非正式定義示意圖 簡單地說，算法就是解決問題的有限步驟。第 6 頁8.1.1 算法的定義例8-1以黑藍兩色墨水交換為例問題描述：有黑和藍兩個墨水瓶，因錯把黑墨水裝在了藍瓶子里，而藍墨水錯裝在了黑瓶子里，要求將其互換。算法分析：因為兩個瓶子的墨水不能直接交換，所以引入第三個墨水瓶。如果第三個墨水瓶為白色，其交換步驟如下 8.1 算法第 7 頁8.1.1 算法的定義算法分兩大類：數值運算算法非數值運算算法 數值運算是指對問題求數值解如：多項式插值、微分方程求解、函數的定積分求解、上述的隊列算法等，都屬于數值運算范圍。

4、 非數值運算包括非常廣泛的領域如：資料檢索、事務管理、數據處理等，上述的“黑藍兩色墨水交換”也是非數值運算算法。 8.1 算法第 8 頁8.1.2 算法的基本特征算法具有以下基本特征： 有窮性：一個算法必須在執行有限個操作步驟后終止 確定性：算法中每一步的含義必須是確切的，不可出現任何二義性 有效性：算法中的每一步操作都應該能有效執行，一個不可執行的操作是無效的 有零個或多個輸入：這里的輸入是指在算法開始之前所需要的初始數據，輸入的多少取決于特定的問題 有一個或多個輸出：所謂輸出是指與輸入有某種特定關系的量，在一個完整的算法中至少會有一個輸出。 8.1 算法第 9 頁8.1.3 算法的表示方法

5、1.偽代碼表示方法例8-2求解 sum=1+2+3+4+5+（n-1）+n算法用偽代碼表示算法開始； 輸入 n 的值； i 1； sum 0； 循環開始i=n sum sum + i； i i + 1； 循環結束 輸出 sum 的值； 算法結束； 8.1 算法第 10 頁起止框判斷框處理框輸入/輸出框注釋框流向線連接點8.1.3 算法的表示方法2.流程圖表示方法 8.1 算法第 11 頁標準流程圖符號含義符號名稱符 號功 能起止框表示算法的開始和結束輸入/輸出框表示算法的輸入/輸出操作，框內填寫需輸入或輸出的各項處理框表示算法中的各種處理操作，框內填寫處理說明或算式判斷框表示算法中的條件判斷操

6、作，框內填寫判斷條件注釋框表示算法中某操作的說明信息，框內填寫文字說明流程線 和表示算法的執行方向連接點8.1.3 算法的表示方法 8.1 算法第 12 頁 T里保存： 1+2+3+K的連加和。重復進行某種運算，運算對象有規律地變化, 采用循環結構。 例: 給定K值，求1到 K連加和。循環開始輸出 T 的值結束輸入KT+I TI+1 IIKYN1I，0 TT=1+2+3+K。 1 I 0 T T+I T(I=1,2,3,K) 8.1 算法第 13 頁8.1.4 算法設計與優化算法執行效率包括時間效率和空間效率兩方面，稱為時間復雜性（Time Complexity）和空間復雜性（Space Co

7、mplexity) 對于具體問題，通常有很多不同的解決方法，即不同的算法。不同算法可能就有不同效率，有時候你選擇了正確的算法，但卻不一定是有效的算法。算法的復雜度包括時間復雜度和空間復雜度，有時降低時間復雜度（或空間復雜度）是以犧牲空間復雜度（或時間復雜度）為代價的對于不同的問題，應具體問題具體分析，找出問題的最佳算法。 8.1 算法第 14 頁練習與思考8-1 冒泡排序法為什么很慢？ 假如要給十個數排序，請畫出表達冒泡排序法的流程圖，并思考這個算法為什么慢？可以通過什么途徑解決？ 8.1 算法第 15 頁 8.1 算法 8.2 典型問題的算法設計 8.3 數據結構 8.4 程序設計第8章 算

8、法與程序設計第八章 算法與程序設計 第 16 頁對4個數0,2,3,9按從大到小的順序排序:冒泡法0,2,3,9 0 22,0,3,9 0 32,3,0,9 0 92,3,9,0 2 33,2,9,0 2 93,9,2,0 3 9第一輪（n-1=3）次比較，（n-1=3）次交換第二輪（n-2=2）次比較，（n-2=2）次交換9,3,2,0 第三輪（n-3=1）次比較，（n-3=1）次交換引入引入 8.2 典型問題的算法設計第 17 頁8.2.1 成績排名問題排序算法問題描述：在一個班級有30名同學，一次考試每個同學有一個考試成績，如何將這30名同學的成績由高至低進行排序？ 問題分析：這是一個排

9、序問題。一般認為，日常的數據處理中有1/4的時間應用在排序上，據不完全統計，到目前為止的排序算法有上千種。算法設計：1、用選擇排序解決方案2、用插入排序解決方案 8.2 典型問題的算法設計第 18 頁8.2.1 成績排名問題排序算法1、用選擇排序解決方案?首先在30名同學中找到最高的分數，使其排在第1位；?然后在剩下的分數中再找最高的分數，使其排在第2位；?依次類推，直至所有的分數都已經排完。這是一種常見的人工實現方式，這種解決方案其實就是計算機排序算法中的選擇排序。 8.2 典型問題的算法設計第 19 頁對5個數5,7,4,2,8按從小到大的順序排序:選擇法5,7,4,2,8 5 22,7,

10、4,5,8 7 42,4,7,5,8 7 52,4,5,7,8 2,4,5,7,8 第一輪（n-1=4）次比較第二輪（n-2=3）次比較完成排序 第三輪（n-3=2）次比較第四輪（n-2=1）次比較引引 8.2 典型問題的算法設計第 20 頁選擇排序的改進： 以冒泡排序法為基礎，在兩兩比較后，不馬上進行交換，而是在找到最大（或最小）的數之后，記錄該數的位置(在數組中的下標)，待一輪比較完畢，再將最大（或最小）的數一次交換到位。 8.2 典型問題的算法設計第 21 頁8.2.1 成績排名問題排序算法2、用插入排序解決方案?首先將第1位同學的分數放在一個隊列中；?然后將第2位同學的分數與隊列中的第

11、1位同學的分數進行比較，如果分數比其高，則放在后面，如果分數比其低，則放在前面；?然后將第3位同學的分數與隊列中的兩位同學的分數進行比較，找到一個插入并仍保持有序的位置，將第3位同學的分數插入到該位置；?依次類推，直至將30位同學的分數都插入到相應位置。這也是一種常見的人工實現方式，該解決方案在計算機排序算法中叫做插入排序。 8.2 典型問題的算法設計第 22 頁插入排序基本思想假設：已經存在一個長度為N的有序(從小到大排列)的數據序列，要將一個新的數插入到該序列中，要求插入后的新序列(長度為N+1)仍然保持有序。 算法關鍵是要確定新數據插入的合適位置。對于一個有序序列，從后向前進行比較，若序

12、列中的數大于要插入的數，則將數列中的數向后移動；否則，完成插入操作。 8.2 典型問題的算法設計第 23 頁8.2.1 成績排名問題排序算法還有哪些經典的排序算法？比較一下這些排序算法的特點，以及在哪種數據下能達到最佳性能？ 8.2 典型問題的算法設計第 24 頁8.2.2 斐波那契數列問題遞歸算法問題描述：著名意大利數學家列昂納多斐波那契（Leonardo Fibonacci）1202年提出一個有趣的數學問題：假定一對雌雄的大兔每一個月能生一對雌雄的小兔，每對小兔過一個月能長成大兔再生小兔，問一對兔子一年能繁殖幾對小兔？于是得到一個數列：1，1，2，3，5，8，13，21，34，55，89，

13、144，233，377， 610， 987， 1597，這就是著名的菲波那契數列。問題分析：題目中數列的規律很容易發現：后面的一個數總是前兩個數的和。如果按照人的思維習慣來計算，該問題看似很容易，但實際做起來就會遇到問題。在數學上，斐波那契數列是以遞歸的方法來定義的。 8.2 典型問題的算法設計第 25 頁8.2.2 斐波那契數列問題遞歸算法1、數學方法求解這是一個典型的遞歸關系。根據以上分析可見，在數學上，斐波納契數列以如下遞歸方法定義：122111nnnFFFFF 8.2 典型問題的算法設計第 26 頁8.2.2 斐波那契數列問題遞歸算法情景問題8-1 如果你看到有這樣一個題目：某人把一個

14、8*8的方格切成四塊，拼成一個5*13的長方形，故作驚訝地問你：為什么6465？你知道這是為什么嗎？提示：斐波那契數列有一項性質，從第二項開始，每個奇數項的平方都比前后兩項之積多1，每個偶數項的平方都比前后兩項之積少1。 8.2 典型問題的算法設計第 27 頁8.2.2 斐波那契數列問題遞歸算法2、算法設計遞歸算法就是把問題轉化為規模縮小了的同類問題的子問題，對這個子問題用函數（或過程）來描述，然后遞歸調用該函數（或過程）以獲得問題的最終解。遞歸算法描述簡潔而且易于理解，所以使用遞歸算法的計算機程序也清晰易讀。 8.2 典型問題的算法設計第 28 頁8.2.2 斐波那契數列問題遞歸算法2、算法

15、設計遞歸算法一般有三個要求（1）每次調用在規模上都有所縮小（2）相鄰兩次重復之間有緊密的聯系，前一次要為后一次做準備（3）在問題的規模最小時，必須直接給出解答而不再進行遞歸調用，因而每次遞歸調用都是有條件的遞歸算法需要關鍵的兩步（1）確定遞歸公式（2）確定邊界（終止）條件 8.2 典型問題的算法設計第 29 頁8.2.2 斐波那契數列問題遞歸算法遞歸算法：遞歸函數用偽代碼描述為：Int Fib(int n) /斐波那契（Fibonacci）數列 if (n = 1或 n = 2) return 1; /邊界條件，無需遞歸if (n=3) return Fib(n-1)+Fib(n-2); /

16、通過遞歸公式求解return 0; /預防錯誤 8.2 典型問題的算法設計第 30 頁8.2.2 斐波那契數列問題遞歸算法練習與思考8-2 對于當前普通的計算機來說，求解斐波那契數列第50項的值所需要的時間不超過1秒。不妨嘗試一下，通過人工計算所需的時間大約是多久？ 總結一下，在這個問題上，人的思維與計算機思維是否有相同之處？計算機解決問題的優勢是什么？ 8.2 典型問題的算法設計第 31 頁8.2.3 最大公約數問題-迭代算法問題描述：公約數，亦稱“公因數”。如果一個整數同時是幾個整數的約數，稱這個整數為它們的“公約數”；公約數中最大的稱為最大公約數。求最大公約數是數學中的經典問題。問題分析

17、：歐幾里德算法（又稱輾轉相除法）是求解最大公約數的傳統方法，其算法的核心基于這樣一個原理： 如果有兩個正整數a和b（a = b），r為a除以b的余數，則有a和b的公約數與b和r的最大公約數是相等的這一結論(證明從略)。基于這個原理，經過反復迭代執行，直到余數r為0時結束迭代，此時的除數便是a和b的最大公約數。 8.2 典型問題的算法設計第 32 頁8.2.3 最大公約數問題-迭代算法利用迭代算法解決問題，需要做好以下三個方面的工作：（1）確定迭代變量。（2）建立迭代關系式。（3）對迭代過程進行控制。 8.2 典型問題的算法設計第 33 頁8.2.3 最大公約數問題-迭代算法圖8-5 歐幾里德算

18、法的迭代計算過程3、用迭代算法求解最大公約數以136和58為例：第1步，13658=2 余20；第2步，5820=2 余18；第3步，2018=1 余2；第4步，182=9 余0算法結束。則最大公約數為2。 8.2 典型問題的算法設計第 34 頁 8.1 算法 8.2 典型問題的算法設計 8.3 數據結構 8.4 程序設計第8章 算法與程序設計第八章 算法與程序設計 第 35 頁 8.3 數據結構8.3.1 計算機語言中的數據組織1.數組的數據組織數組是一種在實際應用中非常重要的數據組織形式，在大量的程序設計中，也是循環控制結構的重要支撐。 舉例來說，當完成10個變量的求和計算，可以通過聲明1

19、0個變量a1、a2、a3、a4、a5、a6、a7、a8、a9、a10，將變量賦值后，通過計算a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9 + a10 即可獲得最終的答案。而假如需要完成1000個變量甚至10000個變量的求和計算，則聲明1000個變量甚至10000個變量，顯然是一種不合適的行為。 如在C語言中，聲明100個整數變量的數組形式如下：int arr100;第 36 頁8.3.1 計算機語言中的數據組織1.數組的數據組織圖8-6 數組的存儲與存取形式 8.3 數據結構第 37 頁8.3.1 計算機語言中的數據組織1.數組的數據組織100個變量的

20、求和操作可以使用如下的算法形式來完成，形式非常簡潔。int sum = 0;for(i=0; i100; i+)sum += arri; 8.3 數據結構第 38 頁2. 結構體的數據組織表8-4 學生成績表學號學號姓名姓名性別性別英語英語線性代數線性代數物理物理離散數學離散數學1104030308趙男806481851104030309錢男715483601104030301孫女756083501104030317李男816784601104030324周女827260678.3.1 計算機語言中的數據組織 8.3 數據結構第 39 頁2.結構體的數據組織如: 針對上述的數據表格，可以針對每

21、一名同學的數據組裝成一個結構體類型，以C語言為例，其定義如下：struct studentint no;char name20;char sex5;float score4;通過這種“結構體”，可以將“列式存儲方式”改變為“行式存儲方式”，從而更利于算法的實現。8.3.1 計算機語言中的數據組織 8.3 數據結構第 40 頁1.數據結構的概念通常，一些常用的、成熟的方法整理成為若干固定的數據組織形式，這就是數據結構。數據結構中的典型形式有數組、棧、隊列、鏈表、樹、圖、堆、散列表等類型。8.3.2 數據結構 8.3 數據結構第 41 頁2. 數據的邏輯結構數據可以根據其是否具有底層結構劃分成基本

22、類型和構造類型兩類，而常見的基本類型有：8.3.2 數據結構 8.3 數據結構第 42 頁3. 數據的存儲結構常見的存儲映像方式如下： 順序方式 鏈接方式 索引方式 散列方式上面4種方式可以混合使用，同一種數據在不同的算法和應用中也可以采用不同的存儲映像方式，從而形成不同的數據結構。8.3.2 數據結構 8.3 數據結構第 43 頁4. 數據的運算數據以一定的方式組織在一起的目的是為了對其進行加工處理，常見的運算有：插入在已有數據結構中添加新的數據元素或結點。刪除 刪除數據結構中的某個數據元素或結點。查找 在數據結構中查找某特定數據元素。排序 按某種特定規律改變數據結構中的數據元素或結點的排列

23、順序。更新 改變數據結構中數據元素的值。8.3.2 數據結構 8.3 數據結構第 44 頁練習與思考8-3 如果你要編寫給100個數排序的程序，你會考慮用什么形式存放數據？為什么？ 8.3 數據結構第 45 頁 8.1 算法 8.2 典型問題的算法設計 8.3 數據結構 8.4 程序設計第8章 算法與程序設計第八章 算法與程序設計 第 46 頁 8.4 程序設計8.4.1 計算機語言與語言處理系統1.計算機語言的分類從發展角度 機器語言、匯編語言和高級語言第一代：機器語言 （2進制機器指令，機器能直接執行）第二代：匯編語言 （符號代替機器語言，需要翻譯）第三代：高級語言 （英語和數學語言代替機

24、器語言，需要翻譯）第 47 頁1.計算機語言的分類從高級語言自身特點 過程式語言，如：Cobol、Forturn、Algol、Pascal、Ada、C； 函數式語言，如：Lisp； 數據流語言，如S：ISAL、VAL； 面向對象語言，如：Smalltalk、CLU、C+； 邏輯語言，如：Prolog； 字符串語言，如：SNOBOL； 并發程序設計語言，如：Concurrent、 Pascal、Modula 2等類型的語言。 8.4 程序設計8.4.1 計算機語言與語言處理系統第 48 頁2.計算機語言處理系統 解釋源程序解釋程序邊解釋邊執行結果用戶編輯 編輯器出錯目標程序可執行程序庫文件連接程序編譯程序編輯器出錯編譯編譯連接編輯 用戶源程序結果 8.4 程序設計8.4.1 計算機語言與語言處理系統第 49 頁1.數據結構與算法程序=數據結構+算法程序設計過程的四個步驟（1）分析問題，建立數學模型。（2）確定數據結構和算法。（3）編制程序。（4）調試程序。 8.4 程序設計8.4.2 面向過程程序設計第 50 頁2.結構化程序設計