“大學計算機基礎(chǔ)”課程 5

1、Chapter 5算法基礎(chǔ)CS, ZJU9/14/2022Overview算法的概念算法的分類和特性算法的三種結(jié)構(gòu)算法的表示算法的發(fā)現(xiàn)常用算法算法的方法數(shù)據(jù)表達和數(shù)據(jù)結(jié)構(gòu)2022/9/142計算機科學基礎(chǔ)5.1 算法的概念廣義地說，為解決問題而采用的方法和步驟就是算法。在計算機中，算法是程序設(shè)計的基礎(chǔ)，算法的質(zhì)量直接影響程序運行的效率。根據(jù)圖靈理論，只要能夠被分解為有限步驟的問題就可以被計算機執(zhí)行。在計算機領(lǐng)域，算法描述主要就是為了能夠?qū)⑺惴ǖ牟襟E變成計算機能夠用它的語言所實現(xiàn)的表示方式。算法的正式定義：算法是求解問題步驟的有序集合，它能夠產(chǎn)生結(jié)果并在有限時間內(nèi)結(jié)束。2022/9/143計算機

2、科學基礎(chǔ)5.2 算法的分類和特點算法一般可分成兩大類：數(shù)值運算算法非數(shù)值運算算法特性確定性：算法中的每一個步驟都應該是確定的，不應使不同的編程者對算法中的描述產(chǎn)生不同的理解 有窮性：算法中的步驟應該是有限的，否則計算機就會永遠無休止地執(zhí)行程序有效性：算法中的每一個步驟都應該被有效地執(zhí)行，并應能得到一個明確的結(jié)果可有零個或多個輸入有一個或多個輸出2022/9/144計算機科學基礎(chǔ)5.3 算法的三種結(jié)構(gòu)根據(jù)結(jié)構(gòu)化程序設(shè)計，所有的程序都由三種結(jié)構(gòu)構(gòu)成：順序結(jié)構(gòu) 最簡單的一種結(jié)構(gòu)，它使計算機按照命令出現(xiàn)的先后順序依次執(zhí)行循環(huán)結(jié)構(gòu)使計算機按照設(shè)定的條件重復執(zhí)行一組命令分支結(jié)構(gòu) 在程序執(zhí)行過程中 ，根據(jù)設(shè)

3、定的條件來決定程序的執(zhí)行方向2022/9/145計算機科學基礎(chǔ)2022/9/146計算機科學基礎(chǔ)順序結(jié)構(gòu)A B分支結(jié)構(gòu)2022/9/147計算機科學基礎(chǔ)（a）While結(jié)構(gòu) （b） Until結(jié)構(gòu)5.4 算法的表示算法的表示是為了把算法以某種形式加以表達，因此一個算法的表示可以有不同的方法，常用的：自然語言傳統(tǒng)的流程圖結(jié)構(gòu)流程圖偽代碼PAD圖2022/9/148計算機科學基礎(chǔ)2022/9/149計算機科學基礎(chǔ) 例：流程圖求N！的算法2022/9/1410計算機科學基礎(chǔ)求N！的算法例:自然語言2022/9/1411計算機科學基礎(chǔ)求N！的算法例：偽代碼2022/9/1412計算機科學基礎(chǔ)求N！的算

4、法例：偽代碼5.5 算法的發(fā)現(xiàn)發(fā)現(xiàn)算法具有很大的挑戰(zhàn)性“中國郵遞員問題”：不但要選擇路徑，而且要確保這個選擇的路徑是最短的。解決問題的4個步驟：理解問題設(shè)計一個解決問題的方案執(zhí)行這個方案檢驗這個方案 2022/9/1413計算機科學基礎(chǔ)5.6 算法的舉例理解常用的算法進而體會算法的發(fā)現(xiàn)、設(shè)計，是大多數(shù)學習計算機的人所采用的學習方法?；舅惴ㄇ蠛屠鄯e求最大值和最小值求數(shù)的位數(shù)2022/9/1414計算機科學基礎(chǔ)迭代一種建立在循環(huán)基礎(chǔ)上的算法。舉例：“判斷一個整數(shù)是否為素數(shù)”的迭代算法算法思路：素數(shù)是指只能被1和它本身整除的數(shù)。判斷它的方法為：將n（設(shè)n是要被判斷的整數(shù)）作為被除數(shù)，用2（n-1）

5、之間的各個整數(shù)輪流去除，如果都不能整除，則n是素數(shù)。 2022/9/1415計算機科學基礎(chǔ)遞歸遞歸是算法的自我調(diào)用例：求N的階乘。2022/9/1416計算機科學基礎(chǔ)排序迭代的延續(xù)應用。是將一組原始數(shù)據(jù)按照遞增或遞減的規(guī)律進行重新排列的算法。排序不僅用在數(shù)值方面，也用在文本處理中。排序規(guī)則是遞增或遞減，其輸出是原數(shù)據(jù)的一種重新排列。常用的方法有：（如果是從小到大排序的話）選擇法排序把表中最小的數(shù)找到并放入第一個位置，然后比較余下的數(shù)，找到次小的數(shù)放到第二個位置，直到對所有數(shù)據(jù)全部掃描過。冒泡法排序。從列表的最后開始比較相鄰的兩個數(shù)，將較小的向前移動，再和前一個相鄰的數(shù)據(jù)比較，同樣把較小的數(shù)向前

6、移動，直到列表的開始。接著繼續(xù)這個過程，找到的次小的數(shù)排到列表的第二個位置，依次類推，直到結(jié)束。2022/9/1417計算機科學基礎(chǔ)查找問題把一個特定的數(shù)據(jù)從列表中找到并提供它所在的位置（即索引）。對于列表數(shù)據(jù)有兩種基本的方法：順序查找從列表的第一個數(shù)據(jù)（或叫做元素）開始，但給定的數(shù)據(jù)和表中的數(shù)據(jù)匹配時，查找過程結(jié)束，給出這個數(shù)據(jù)所在表中的位置。折半查找也叫二分法，從列表的一半開始，比較列表處于一半（中間）位置的數(shù)據(jù)，判斷是在前半部分還是后半部分（根據(jù)列表的排序確定的）。2022/9/1418計算機科學基礎(chǔ)5.7 算法的方法學貪心法 分治法 動態(tài)規(guī)劃 回溯法 2022/9/1419計算機科學基

7、礎(chǔ)貪心法 貪心算法（Greedy Algorithm）的基本思想是從小的方案推廣到大的解決方法。它分階段工作，在每一個階段選擇最好的方案，而不考慮其后的結(jié)果如何。貪心法主要用于求解最優(yōu)問題，但它已經(jīng)發(fā)展成為一種通用的算法設(shè)計技術(shù)：核心是：可行性每一步選擇必須滿足問題的約束；局部最優(yōu)它是當前可選擇的方案中最優(yōu)的；不可取消性選擇一旦做出，在算法的其后步驟中不能被取消。貪心法不能確定得到的最后解是最優(yōu)的，也不能用于求解最大或最小問題。在算法的效率上，貪心法快速，程序?qū)崿F(xiàn)需要的內(nèi)存開銷也較小。但遺憾的是，它們往往是不正確的。然而一旦被證明是正確的，其執(zhí)行效率和速度有很大的優(yōu)勢。2022/9/1420計

8、算機科學基礎(chǔ)分治法 基本思想就是，將一個較大規(guī)模的問題分解為若干個較小規(guī)模的子問題，找出子問題的解，然后把各個子問題的解合并成整個問題的解。分治法的分（Divide）是指劃分較大問題為若干個較小問題，遞歸求解子問題；分治法的治（Conquer）是指從小問題的解構(gòu)建大問題的解。例： 金塊問題2022/9/1421計算機科學基礎(chǔ)動態(tài)規(guī)劃 動態(tài)規(guī)劃（Dynamic Programming）被描述為：如果一個較大問題可以被分解為若干個子問題，且子問題具有重疊，可以將每個子問題的解存放到一個表中，這樣就可以通過查表解決問題。例：背包問題2022/9/1422計算機科學基礎(chǔ)回溯法 回溯法也叫窮盡搜索法（B

9、rute-Force Search），嘗試分步地去解決一個問題。在分步解決問題的過程中，當它通過嘗試發(fā)現(xiàn)現(xiàn)有的分步答案不能得到有效的、正確的解答的時候，將取消上一步甚至上幾步的計算，再通過其他的可能的分步解答再次嘗試尋找問題的答案。通常使用遞歸實現(xiàn)。例：n皇后問題。2022/9/1423計算機科學基礎(chǔ)5.8數(shù)據(jù)表達和數(shù)據(jù)結(jié)構(gòu)算法最終都需要通過適當?shù)臄?shù)據(jù)表達，以便能夠被計算機所處理。數(shù)據(jù)表達是對數(shù)據(jù)的符號化表示。數(shù)據(jù)結(jié)構(gòu)的定義包括三方面內(nèi)容：邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和對數(shù)據(jù)的操作。按照它的結(jié)構(gòu)形式可以分為鏈、表、堆、隊、樹等。2022/9/1424計算機科學基礎(chǔ)數(shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)元素之間存在某種關(guān)聯(lián)。有三類基本的數(shù)據(jù)之間的結(jié)構(gòu)，如線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系；樹型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系；網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系；2022/9/1425計算機科學基礎(chǔ)數(shù)據(jù)的邏輯關(guān)系反映的是數(shù)據(jù)間的關(guān)系，是靜態(tài)的。靜態(tài)的對象和動態(tài)的作用于對象上的操作就構(gòu)成了數(shù)據(jù)類型。如何用程序設(shè)計語言實現(xiàn)相應的抽象數(shù)據(jù)類型是數(shù)據(jù)結(jié)構(gòu)的一個重要問題：對象如何用程序設(shè)計語言來表示，即對象邏輯結(jié)構(gòu)的物理實現(xiàn)；對象的操作如何實現(xiàn)，即編寫相應的函數(shù)；例：隊