“大學(xué)計(jì)算機(jī)基礎(chǔ)”課程 5

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

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

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

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

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

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

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

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

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