四章算法程序與編程ppt課件

1、第四章 算法、程序與編程 問題的提出： 人是如何來處理問題的？ 人是如何處理復(fù)雜問題的？ 計(jì)算機(jī)如何來處理問題的？ 問題的處理計(jì)算機(jī)算法、程序與編程第四章 算法、程序與編程 學(xué)習(xí)目的和要求： 了解算法與程序概念 了解算法的復(fù)雜性與NP問題 熟習(xí)根本算法 知道數(shù)據(jù)和數(shù)據(jù)構(gòu)造 熟習(xí)高級(jí)言語 掌握程序設(shè)計(jì)規(guī)劃 了解程序?qū)嶋H和軟件工程 一種逐漸處理問題或完成義務(wù)的方法一種逐漸處理問題或完成義務(wù)的方法輸入列表輸入列表輸出列表輸出列表算法算法尋覓最大值的一個(gè)算法(1) 輸入5個(gè)數(shù)，輸出其中的最大值 1.輸入：算法接受一組5個(gè)整數(shù)的數(shù)據(jù)。 2.過程 第一步 檢查第一個(gè)整數(shù)，把這個(gè)整數(shù)賦給變量Largest

2、第二步 把第二個(gè)數(shù)與Largest中的數(shù)進(jìn)展比較，如大于Largest中的數(shù)就將該數(shù)賦予它，否那么，Largest中的數(shù)不變 第三步 把第三個(gè)數(shù)與Largest中的數(shù)進(jìn)展比較，如大于Largest中的數(shù)就將該數(shù)賦予它，否那么，Largest中的數(shù)不變。此時(shí)13大于12，所以，變量Largest中變?yōu)?3。 尋覓最大值的一個(gè)算法(2)第四步第四步 把第四個(gè)數(shù)與把第四個(gè)數(shù)與LargestLargest中的數(shù)進(jìn)展比較，中的數(shù)進(jìn)展比較，如大于如大于LargestLargest中的數(shù)就將該數(shù)賦予它，否那中的數(shù)就將該數(shù)賦予它，否那么，么，LargestLargest中的數(shù)不變。此時(shí)第四個(gè)數(shù)是中的數(shù)不變。此

3、時(shí)第四個(gè)數(shù)是9 9，小于小于1313，所以，所以LargestLargest中的數(shù)不變。中的數(shù)不變。第五步第五步 把第四五個(gè)數(shù)與把第四五個(gè)數(shù)與LargestLargest中的數(shù)進(jìn)展比中的數(shù)進(jìn)展比較，如大于較，如大于LargestLargest中的數(shù)就將該數(shù)賦予它，中的數(shù)就將該數(shù)賦予它，否那么，否那么，LargestLargest中的數(shù)不變。此時(shí)第五個(gè)數(shù)中的數(shù)不變。此時(shí)第五個(gè)數(shù)是是1111，小于，小于1313，所以，所以LargestLargest中的數(shù)不變。中的數(shù)不變。3.3.輸出輸出 最大值最大值13 13 終了終了算法的例子表示圖算法的精化算法的泛化三三 種種 結(jié)結(jié) 構(gòu)構(gòu) 算法的根本構(gòu)造算

4、法的根本構(gòu)造 流程圖 偽代碼：是在編寫算法時(shí)，為了更好地表示算法本身，不在一些小的細(xì)節(jié)上糾纏，而采用類似于英語或其他自然言語表示算法的算法表示方法。偽代碼用偽代碼寫出一個(gè)求兩個(gè)數(shù)的平均值的算法AverageOfTwoInput: Two numbersAdd the two numbersDivide the result by 2Return the result by step 2EndPass/NoPassGradeInput: One numberif (the number is greater than or equal to 60)then 1.1 Set the grade t

5、o “passelse 1.2 Set the grade to “nopassEnd ifReturn the gradeEnd 用偽代碼寫出一個(gè)可以把不同數(shù)值成果分成及格或不及格的算法LetterGradeInput: One number1. if (the number is between 90 and 100, inclusive)then 1.1 Set the grade to “AEnd if2. if (the number is between 80 and 89, inclusive)then 2.1 Set the grade to “BEnd if 用偽代碼寫出一個(gè)

6、可以把數(shù)字型成果變成字母等級(jí)成果的算法Continues on the next slide3. if (the number is between 70 and 79, inclusive)then 3.1 Set the grade to “CEnd if4. if (the number is between 60 and 69, inclusive)then 4.1 Set the grade to “DEnd if算法的定義 算法定義1：算法是一組明確步驟的有序集合，它產(chǎn)生結(jié)果，并在有限的時(shí)間內(nèi)終止。 有序集合 明確步驟 產(chǎn)生結(jié)果 在有限的時(shí)間內(nèi)終了 算法定義算法定義2 2： 1 1

7、給定問題和設(shè)備，一個(gè)算法是用該設(shè)備可了給定問題和設(shè)備，一個(gè)算法是用該設(shè)備可了解的言語表示的，處理這個(gè)問題的一種方法是準(zhǔn)確解的言語表示的，處理這個(gè)問題的一種方法是準(zhǔn)確描寫。特別地，算法具有以下特征屬性：描寫。特別地，算法具有以下特征屬性： 算法運(yùn)用于一個(gè)詳細(xì)的輸入集合或問題描畫將在算法運(yùn)用于一個(gè)詳細(xì)的輸入集合或問題描畫將在有窮步動(dòng)作之后得到結(jié)果；有窮步動(dòng)作之后得到結(jié)果； 該序列有一個(gè)獨(dú)一的初始動(dòng)作：該序列有一個(gè)獨(dú)一的初始動(dòng)作： 該序列中的每一個(gè)動(dòng)作有一個(gè)獨(dú)一的后繼動(dòng)作該序列中的每一個(gè)動(dòng)作有一個(gè)獨(dú)一的后繼動(dòng)作 該序列終止時(shí)或者得到這個(gè)問題的解，或者因該該序列終止時(shí)或者得到這個(gè)問題的解，或者因該問題

8、不可解而獲得不可講解明。問題不可解而獲得不可講解明。 算法定義算法定義3 3：一個(gè)算法，就是一個(gè)有窮規(guī)那么的集：一個(gè)算法，就是一個(gè)有窮規(guī)那么的集合，其中之規(guī)那么確定了一個(gè)處理某一特定型問題合，其中之規(guī)那么確定了一個(gè)處理某一特定型問題的運(yùn)算序列。此外，算法的規(guī)那么序列必需滿足以的運(yùn)算序列。此外，算法的規(guī)那么序列必需滿足以下下5 5個(gè)重要條件，即具有以下五個(gè)特性：個(gè)重要條件，即具有以下五個(gè)特性： 1 1有窮性。算法必需總是在執(zhí)行有窮步之后終有窮性。算法必需總是在執(zhí)行有窮步之后終了了 2 2確定性。算法的每一個(gè)步驟必需是確切地定確定性。算法的每一個(gè)步驟必需是確切地定義的；義的； 3 3輸入。算法有零

9、個(gè)或多個(gè)輸入輸入。算法有零個(gè)或多個(gè)輸入 4 4輸出。算法有一個(gè)或多個(gè)輸出，即與輸入有輸出。算法有一個(gè)或多個(gè)輸出，即與輸入有某個(gè)關(guān)系的量。某個(gè)關(guān)系的量。 5 5能行性。算法中有待執(zhí)行的運(yùn)算和操作必需能行性。算法中有待執(zhí)行的運(yùn)算和操作必需是相當(dāng)根本的，即是說，它們原那么上是可以準(zhǔn)確是相當(dāng)根本的，即是說，它們原那么上是可以準(zhǔn)確地進(jìn)展的，而且用筆和紙做有窮次就可以完成。地進(jìn)展的，而且用筆和紙做有窮次就可以完成。 計(jì)算的復(fù)雜性算法的復(fù)雜性的概念計(jì)算的復(fù)雜性算法的復(fù)雜性的概念 計(jì)算空間的復(fù)雜性計(jì)算空間的復(fù)雜性 計(jì)算時(shí)間的復(fù)雜性計(jì)算時(shí)間的復(fù)雜性 類似性與對偶原理：計(jì)算空間與計(jì)算時(shí)間的互換性類似性與對偶原理：

10、計(jì)算空間與計(jì)算時(shí)間的互換性 算法復(fù)雜性的描畫：算法在執(zhí)行過程中總共所需求的算法復(fù)雜性的描畫：算法在執(zhí)行過程中總共所需求的初等運(yùn)算的步數(shù)來表示算法用于求解任一問題的某一初等運(yùn)算的步數(shù)來表示算法用于求解任一問題的某一例子時(shí)所需的時(shí)間。例子時(shí)所需的時(shí)間。計(jì)算的復(fù)雜性與NP問題2 算法復(fù)雜性的表示 多項(xiàng)式時(shí)間算法：是指存在某個(gè)以輸入長度n為變量的多項(xiàng)式函數(shù)中(n)，使其時(shí)間復(fù)雜性函數(shù)為O(p(n)的算法。因此復(fù)雜性為O(n)、O(106n3)、O(5n8)等算法均為多項(xiàng)式時(shí)間算法。 指數(shù)時(shí)間算法：是指任何其時(shí)間復(fù)雜性函數(shù)不能夠如上用多項(xiàng)式函數(shù)去界定的算法，例如O2n、O(n!)、O(nn)、O(2n2

11、)等都在算法上是不可接受的。計(jì)算的復(fù)雜性與NP問題3 時(shí)間復(fù)雜性的表示 O1稱為常數(shù)級(jí)； Ologn稱為對數(shù)級(jí)； On稱為線性級(jí)； O (nc)稱為多項(xiàng)式級(jí)，C為常數(shù)； O Cn稱為指數(shù)級(jí)，C為常數(shù)； O (n!)稱為階乘級(jí)；計(jì)算的復(fù)雜性與NP問題4 P P類與類與NPNP類問題：一個(gè)算法假設(shè)存在圖靈機(jī)可計(jì)算的類問題：一個(gè)算法假設(shè)存在圖靈機(jī)可計(jì)算的多項(xiàng)式時(shí)間計(jì)算復(fù)雜性算法，就將該算法歸入多項(xiàng)式時(shí)間計(jì)算復(fù)雜性算法，就將該算法歸入P P類；類；假設(shè)存在非確定性圖靈機(jī)可計(jì)算的多項(xiàng)式時(shí)間計(jì)算復(fù)假設(shè)存在非確定性圖靈機(jī)可計(jì)算的多項(xiàng)式時(shí)間計(jì)算復(fù)雜性算法，就將其歸入雜性算法，就將其歸入NPNP類。類。 P=N

12、P?P=NP?構(gòu)造圖 構(gòu)造圖：是程序員運(yùn)用的高層設(shè)計(jì)工具。構(gòu)造圖能很好地表示程序設(shè)計(jì)者的邏輯思想的過程；把算法中各個(gè)模塊之間的關(guān)系表示的更加清楚。構(gòu)造圖的常用圖標(biāo)：構(gòu)造圖的常用圖標(biāo)： 遞歸、迭代算法：遞歸算法是算法自我調(diào)用的過程。 迭代的定義：算法中沒有包含算法本身，只是 利用上一步計(jì)算的結(jié)果得出最后答案的算法 遞歸的定義：算法中包含了算法本身的調(diào)用的 算法。 分治算法：就是將一個(gè)難以直接處理的大問題，經(jīng)過分析，分解為一些規(guī)模較小的一樣問題，進(jìn)而對各個(gè)小問題進(jìn)展處理，最后到達(dá)整個(gè)問題的處理。迭代算法的例子遞歸算法的例子遞歸算法中遞歸調(diào)用表示圖FactorialInput: A positive

13、 integer numSet FactN to 0Set i to Iwhile (i is less than or equal to num) 3.1 Set FactN to FactN x I 3.2 Increment iEnd whileReturn FactNEnd迭代算法迭代算法FactorialInput: A positive integer numif (num is equal to 0)then 1.1 return 1else1.2 return num x Factorial (num 1) End ifEnd遞歸算法遞歸算法 簡單數(shù)據(jù)構(gòu)造類型：表41 簡單數(shù)據(jù)

14、類型數(shù)據(jù)與數(shù)據(jù)構(gòu)造簡介2 數(shù)據(jù)構(gòu)造：二元組 Data-structure=(D,R), 稱為數(shù)據(jù)D的數(shù)據(jù)構(gòu)造。其中D為數(shù)據(jù)元素的集合，R是D上關(guān)系的集合。根本數(shù)據(jù)構(gòu)造 數(shù)組(Array) 一維數(shù)組 二維數(shù)組 2.Two-dimensional array(二維數(shù)組二維數(shù)組) 記錄：是一組相關(guān)元素的集合，它們能夠是不同類型的，但整個(gè)記錄是相關(guān)的，有一個(gè)一致的稱號(hào)。 域：具有含義的記錄中命名數(shù)據(jù)的最小元素；它可以有類型且存在于內(nèi)存中；它能被賦值，也可以被選擇和操作。它與變量不同之處在于它是記錄的一個(gè)部分。 數(shù)組與記錄的區(qū)別：數(shù)組中的元素必需是同一類型，而記錄中的元素那么可以一樣或不同類型，只需相關(guān)

15、即可。 在設(shè)計(jì)記錄時(shí)記錄中的數(shù)據(jù)必需都與一個(gè)對象關(guān)聯(lián)。記錄的操作記錄的操作訪問記錄訪問記錄 訪問單個(gè)域訪問單個(gè)域 訪問整個(gè)記錄訪問整個(gè)記錄讀入讀入寫入記錄成員寫入記錄成員Linked lists鏈表鏈表鏈表：是一個(gè)有序的集合，其中每一個(gè)元素都包含鏈表：是一個(gè)有序的集合，其中每一個(gè)元素都包含 下一個(gè)元素的地址；即數(shù)據(jù)和指針地址。下一個(gè)元素的地址；即數(shù)據(jù)和指針地址。幾個(gè)典型的常用的籠統(tǒng)數(shù)據(jù)類型 線性列表Linear list 線性列表的操作 1插入 2刪除 3檢索 4遍歷Insertion in a linear listDeletion from a linear list棧 棧是一種限制性列表

16、，對其的操作添加、刪除只能在一端實(shí)現(xiàn)。(LIFO)Three representations of a stack 棧的操作 入棧 出棧 空Push operation in a stackPop operation in a stack隊(duì)列 隊(duì)列是一種線性列表，對其的操作只能從一端進(jìn)入，另一端刪除。只能按存入的順序進(jìn)展處置。(FIFO)樹節(jié)點(diǎn)：組成樹的有限的元素。節(jié)點(diǎn)：組成樹的有限的元素。分支：銜接各節(jié)點(diǎn)的有向或無向線段。分支：銜接各節(jié)點(diǎn)的有向或無向線段。度：與節(jié)點(diǎn)銜接的分支的數(shù)目。有出度和入度之度：與節(jié)點(diǎn)銜接的分支的數(shù)目。有出度和入度之分，指向節(jié)點(diǎn)的稱入度，分開節(jié)點(diǎn)的稱出度。分，指向節(jié)點(diǎn)的

17、稱入度，分開節(jié)點(diǎn)的稱出度。Subtrees二叉樹二叉樹二叉樹的前序遍歷二叉樹的前序遍歷二叉樹的后序遍歷二叉樹的廣度優(yōu)先遍歷 數(shù)組方式AFCEDB概念性的樹實(shí)踐的存儲(chǔ)構(gòu)造這種存儲(chǔ)方式在二叉樹不是平衡的情況下會(huì)浪費(fèi)存儲(chǔ)空間 二叉樹的運(yùn)用 網(wǎng)絡(luò) 最小生成樹銜接一切節(jié)點(diǎn)的最短途徑圖 圖的運(yùn)用 網(wǎng)絡(luò) 最小生成樹高級(jí)程序設(shè)計(jì)言語程序設(shè)計(jì)言語開展的歷史 機(jī)器言語 匯編言語 高級(jí)言語計(jì)算機(jī)言語過程化言語FORTRANCOBOLPascalCAda闡明性言語PROLOG公用言語HTMLXMLSQL PERL函數(shù)型言語LISPSchenme面向?qū)ο笱哉ZC+JavaVC+程序的構(gòu)建編程與執(zhí)行 程序編寫 編輯程序 鏈

18、接程序文本編寫編譯程序鏈接程序程序系統(tǒng)庫程序的執(zhí)行預(yù)處置程序編譯翻譯程序程序規(guī)劃與設(shè)計(jì)程序規(guī)劃與設(shè)計(jì)(1)(1) 程序規(guī)劃程序規(guī)劃 步驟步驟1:1:分析問題并制定概要設(shè)計(jì)方案。編程人員必分析問題并制定概要設(shè)計(jì)方案。編程人員必需對問題有完全、準(zhǔn)確的了解，用準(zhǔn)確的言語對問需對問題有完全、準(zhǔn)確的了解，用準(zhǔn)確的言語對問題進(jìn)展描畫，主要思索以下幾個(gè)方面；題進(jìn)展描畫，主要思索以下幾個(gè)方面； 問題的輸入是什么？知的是什么？還要給什么，問題的輸入是什么？知的是什么？還要給什么，運(yùn)用什么格式。運(yùn)用什么格式。 期望的輸出是什么？需求什么類型的報(bào)告、圖期望的輸出是什么？需求什么類型的報(bào)告、圖表或信息。表或信息。 從

19、給定的輸入到期望的輸出，必要的處置步驟從給定的輸入到期望的輸出，必要的處置步驟是什么？是什么？ 步驟步驟2:2:制定詳細(xì)設(shè)計(jì)：算法設(shè)計(jì)必需制定一組制定詳細(xì)設(shè)計(jì)：算法設(shè)計(jì)必需制定一組準(zhǔn)確的步驟，即編寫提綱。這些步驟應(yīng)該是明確、準(zhǔn)確的步驟，即編寫提綱。這些步驟應(yīng)該是明確、詳細(xì)和有限的，并能在合理的時(shí)間內(nèi)完成；同時(shí)選詳細(xì)和有限的，并能在合理的時(shí)間內(nèi)完成；同時(shí)選定實(shí)現(xiàn)各步驟的言語。定實(shí)現(xiàn)各步驟的言語。程序規(guī)劃與設(shè)計(jì)程序規(guī)劃與設(shè)計(jì)(2)(2) 步驟步驟3:3:用編程言語編寫程序代碼及其文檔。用編程言語編寫程序代碼及其文檔。在步驟在步驟2 2中越詳細(xì)清楚用程序代碼就越容易。中越詳細(xì)清楚用程序代碼就越容易。

20、在用程序代碼在用程序代碼“翻譯的過程一定要準(zhǔn)確、翻譯的過程一定要準(zhǔn)確、完好。特別是對文檔的編寫，對各條語句功完好。特別是對文檔的編寫，對各條語句功能的注釋，往往會(huì)被忽視，現(xiàn)代編程是一種能的注釋，往往會(huì)被忽視，現(xiàn)代編程是一種團(tuán)體的協(xié)作行為，讓他人能容易地看懂他的團(tuán)體的協(xié)作行為，讓他人能容易地看懂他的程序，對整個(gè)系統(tǒng)的編寫是絕對必要的。同程序，對整個(gè)系統(tǒng)的編寫是絕對必要的。同時(shí)對程序的修正維護(hù)都有很大的協(xié)助。時(shí)對程序的修正維護(hù)都有很大的協(xié)助。程序規(guī)劃與設(shè)計(jì)程序規(guī)劃與設(shè)計(jì)(3)(3) 步驟步驟4:4:測試程序：這是一個(gè)在前幾個(gè)步驟進(jìn)測試程序：這是一個(gè)在前幾個(gè)步驟進(jìn)展過程中一個(gè)不斷反復(fù)的過程。對于編寫

21、出展過程中一個(gè)不斷反復(fù)的過程。對于編寫出來的每一部分代碼，都應(yīng)該進(jìn)展測試，以確來的每一部分代碼，都應(yīng)該進(jìn)展測試，以確保程序運(yùn)轉(zhuǎn)的正確性。保程序運(yùn)轉(zhuǎn)的正確性。 步驟步驟5:5:驗(yàn)證程序：一旦程序編寫完并進(jìn)展一驗(yàn)證程序：一旦程序編寫完并進(jìn)展一定的測試后，就應(yīng)該經(jīng)過大范圍的測試來驗(yàn)定的測試后，就應(yīng)該經(jīng)過大范圍的測試來驗(yàn)證。驗(yàn)證時(shí)必需根據(jù)用戶的要求，不斷進(jìn)展證。驗(yàn)證時(shí)必需根據(jù)用戶的要求，不斷進(jìn)展修正調(diào)整到用戶稱心為止。修正調(diào)整到用戶稱心為止。程序規(guī)劃與設(shè)計(jì)程序規(guī)劃與設(shè)計(jì)(4)(4) 程序設(shè)計(jì)和調(diào)試程序設(shè)計(jì)和調(diào)試 養(yǎng)成良好的編程風(fēng)格養(yǎng)成良好的編程風(fēng)格錯(cuò)誤定位設(shè)計(jì)錯(cuò)誤修復(fù)程序錯(cuò)誤修復(fù)程序重測軟件工程 軟件工程：在大型的軟件開發(fā)中，引入軟件工程：在大型的軟件開發(fā)中，引入工程管理的一整套的管理方法，對軟件工程管理的一整套的管理方法，對軟件開發(fā)過程進(jìn)展規(guī)劃、設(shè)計(jì)、監(jiān)控和檢測，開發(fā)過程進(jìn)展規(guī)劃、設(shè)計(jì)、監(jiān)控和檢測，以確保開發(fā)的過程、開發(fā)時(shí)間和軟件質(zhì)以確保開發(fā)的過程、開發(fā)時(shí)間和軟件質(zhì)量都在人的控制管理之下，從而使軟件量都在人的控制管理之下，從而使軟件開發(fā)的順利進(jìn)展。所以，對軟件