《計算機科學導(dǎo)論》PPT配套課件

《計算機科學導(dǎo)論》PPT配套課件,計算機科學導(dǎo)論,計算機科學,導(dǎo)論,PPT,配套,課件 第第0808章章 算法算法本章內(nèi)容安排本章內(nèi)容安排&概念概念&三種結(jié)構(gòu)三種結(jié)構(gòu)&算法的表示算法的表示&更正式的定義更正式的定義&基本算法基本算法&子算法子算法&遞歸遞歸21、算法的非正式定義？、算法的非正式定義？&算法是一種逐步解決問題或完成任務(wù)的方法算法是一種逐步解決問題或完成任務(wù)的方法。&算法獨立計算機系統(tǒng)，算法接收一組輸入數(shù)據(jù)并算法獨立計算機系統(tǒng)，算法接收一組輸入數(shù)據(jù)并產(chǎn)生一組輸出數(shù)據(jù)。產(chǎn)生一組輸出數(shù)據(jù)。32、示例、示例&任務(wù)任務(wù)：設(shè)計從一組正整數(shù)中找出最大整數(shù)的算法。：設(shè)計從一組正整數(shù)中找出最大整數(shù)的算法。算法應(yīng)該具有通用性，獨立于整數(shù)的個數(shù)以及整數(shù)算法應(yīng)該具有通用性，獨立于整數(shù)的個數(shù)以及整數(shù)的取值。的取值。&思路思路：先使用少量的數(shù)據(jù)：先使用少量的數(shù)據(jù)(如如5 5個個)，尋找解決問題，尋找解決問題的方法，然后將該方法擴大到任意多個整數(shù)。的方法，然后將該方法擴大到任意多個整數(shù)。&描述描述：1)1)輸入輸入：算法以：算法以5 5個整數(shù)作為輸入個整數(shù)作為輸入2)2)過程過程：逐個數(shù)處理，查找最大值：逐個數(shù)處理，查找最大值3)3)輸出輸出：找到的最大整數(shù)：找到的最大整數(shù)4從從5個整數(shù)中尋找最大值個整數(shù)中尋找最大值53、定義動作、定義動作64、細化、細化&為了使算法具有更好的通用性，需要進行精化。為了使算法具有更好的通用性，需要進行精化。第一步中的動作與其它步不一樣；第一步中的動作與其它步不一樣；第一步中的動作與其它步不一樣；第一步中的動作與其它步不一樣；第二步第五步功能類似，描述不同。第二步第五步功能類似，描述不同。第二步第五步功能類似，描述不同。第二步第五步功能類似，描述不同。&解決方法：解決方法：增加步驟增加步驟增加步驟增加步驟0 0，為，為，為，為LargestLargest賦初值賦初值賦初值賦初值0 0；修改修改修改修改1515步的動作：如果當前數(shù)比最大值大，將最大值步的動作：如果當前數(shù)比最大值大，將最大值步的動作：如果當前數(shù)比最大值大，將最大值步的動作：如果當前數(shù)比最大值大，將最大值置為當前數(shù)。置為當前數(shù)。置為當前數(shù)。置為當前數(shù)。7細化細化85、泛化、泛化&可以對這一算法進行可以對這一算法進行泛化泛化，使其能夠適應(yīng)從，使其能夠適應(yīng)從n n個正個正整數(shù)中找到最大值。整數(shù)中找到最大值。&當當n n非常大時，按照前面算法描述，簡單地將動作非常大時，按照前面算法描述，簡單地將動作重復(fù)編寫重復(fù)編寫n n遍是不可行的！遍是不可行的！&應(yīng)該讓計算機應(yīng)該讓計算機循環(huán)執(zhí)行循環(huán)執(zhí)行一個步驟一個步驟n n次。次。9泛化泛化10本章內(nèi)容安排本章內(nèi)容安排&概念概念&三種結(jié)構(gòu)三種結(jié)構(gòu)&算法的表示算法的表示&更正式的定義更正式的定義&基本算法基本算法&子算法子算法&遞歸遞歸11三種基本結(jié)構(gòu)三種基本結(jié)構(gòu)&計算機科學家們?yōu)榻Y(jié)構(gòu)化程序或算法定義了三種計算機科學家們?yōu)榻Y(jié)構(gòu)化程序或算法定義了三種結(jié)構(gòu)：結(jié)構(gòu)：順序、判斷順序、判斷(選擇選擇)、循環(huán)、循環(huán)。程序只能由這三。程序只能由這三種結(jié)構(gòu)組成，其它結(jié)構(gòu)是不必要的。種結(jié)構(gòu)組成，其它結(jié)構(gòu)是不必要的。&僅僅使用這三種結(jié)構(gòu)，可以使程序僅僅使用這三種結(jié)構(gòu)，可以使程序更容易理解、更容易理解、調(diào)試和修改調(diào)試和修改。12三種基本結(jié)構(gòu)三種基本結(jié)構(gòu)13三種基本結(jié)構(gòu)三種基本結(jié)構(gòu)&順序順序：算法是指令的序列，指令可以是簡單指令，：算法是指令的序列，指令可以是簡單指令，也可以是其它兩種結(jié)構(gòu)之一，依次執(zhí)行。也可以是其它兩種結(jié)構(gòu)之一，依次執(zhí)行。&判斷判斷：有時候需要：有時候需要檢測條件是否滿足檢測條件是否滿足，若測試結(jié)，若測試結(jié)果為真，即條件滿足，執(zhí)行一個分支的順序結(jié)構(gòu)；果為真，即條件滿足，執(zhí)行一個分支的順序結(jié)構(gòu)；假如結(jié)果為假，即條件不滿足，執(zhí)行另一個分支的假如結(jié)果為假，即條件不滿足，執(zhí)行另一個分支的順序結(jié)構(gòu)。順序結(jié)構(gòu)。&循環(huán)循環(huán)：當一系列順序指令需要重復(fù)執(zhí)行時，可以：當一系列順序指令需要重復(fù)執(zhí)行時，可以使用循環(huán)結(jié)構(gòu)。使用循環(huán)結(jié)構(gòu)。14本章內(nèi)容安排本章內(nèi)容安排&概念概念&三種結(jié)構(gòu)三種結(jié)構(gòu)&算法的表示算法的表示&更正式的定義更正式的定義&基本算法基本算法&子算法子算法&遞歸遞歸151、UML統(tǒng)一建模語言統(tǒng)一建模語言&UMLUML是算法的圖形化表示，顯示算法從開始到結(jié)是算法的圖形化表示，顯示算法從開始到結(jié)束的整個流程。束的整個流程。162、偽代碼、偽代碼&偽代碼是算法的一種類似英語的表示法。偽代碼是算法的一種類似英語的表示法。17偽代碼示例偽代碼示例&問題問題 用偽代碼寫出一個求兩個整數(shù)之和的算法用偽代碼寫出一個求兩個整數(shù)之和的算法用偽代碼寫出一個求兩個整數(shù)之和的算法用偽代碼寫出一個求兩個整數(shù)之和的算法&解答解答18偽代碼示例偽代碼示例&問題問題 將數(shù)值成績劃分為及格或不及格的算法將數(shù)值成績劃分為及格或不及格的算法將數(shù)值成績劃分為及格或不及格的算法將數(shù)值成績劃分為及格或不及格的算法&解答解答19偽代碼示例偽代碼示例&問題問題 將數(shù)字型成績（整數(shù)）轉(zhuǎn)為為字母成績的算法將數(shù)字型成績（整數(shù)）轉(zhuǎn)為為字母成績的算法將數(shù)字型成績（整數(shù)）轉(zhuǎn)為為字母成績的算法將數(shù)字型成績（整數(shù)）轉(zhuǎn)為為字母成績的算法&解答解答20偽代碼示例偽代碼示例&問題問題 從一組整數(shù)中找最大數(shù)的算法從一組整數(shù)中找最大數(shù)的算法從一組整數(shù)中找最大數(shù)的算法從一組整數(shù)中找最大數(shù)的算法&解答解答21偽代碼示例偽代碼示例&問題問題 從一組整數(shù)的前從一組整數(shù)的前從一組整數(shù)的前從一組整數(shù)的前10001000個數(shù)中找最大值的算法個數(shù)中找最大值的算法個數(shù)中找最大值的算法個數(shù)中找最大值的算法&解答解答22本章內(nèi)容安排本章內(nèi)容安排&概念概念&三種結(jié)構(gòu)三種結(jié)構(gòu)&算法的表示算法的表示&更正式的定義更正式的定義&基本算法基本算法&子算法子算法&遞歸遞歸23算法更正式的定義算法更正式的定義&算法：是一組明確步驟的有序集合，它產(chǎn)生結(jié)果算法：是一組明確步驟的有序集合，它產(chǎn)生結(jié)果并在有限的時間內(nèi)終止。并在有限的時間內(nèi)終止。有序集合有序集合有序集合有序集合：必須是一組定義完好并排列有序的指令集合。：必須是一組定義完好并排列有序的指令集合。：必須是一組定義完好并排列有序的指令集合。：必須是一組定義完好并排列有序的指令集合。明確步驟明確步驟明確步驟明確步驟：每一步都必須清晰明確定義：每一步都必須清晰明確定義：每一步都必須清晰明確定義：每一步都必須清晰明確定義 產(chǎn)生結(jié)果產(chǎn)生結(jié)果產(chǎn)生結(jié)果產(chǎn)生結(jié)果 在有限的時間內(nèi)終止在有限的時間內(nèi)終止在有限的時間內(nèi)終止在有限的時間內(nèi)終止24本章內(nèi)容安排本章內(nèi)容安排&概念概念&三種結(jié)構(gòu)三種結(jié)構(gòu)&算法的表示算法的表示&更正式的定義更正式的定義&基本算法基本算法&子算法子算法&遞歸遞歸251、求和、求和&如何對不定數(shù)量的一系列數(shù)求和？如何對不定數(shù)量的一系列數(shù)求和？&基本思路：在循環(huán)中使用加法運算?；舅悸罚涸谘h(huán)中使用加法運算。先將和先將和先將和先將和sumsum初始化為初始化為初始化為初始化為0 0；執(zhí)行循環(huán)，在每次迭代中將一個新數(shù)加到和執(zhí)行循環(huán)，在每次迭代中將一個新數(shù)加到和執(zhí)行循環(huán)，在每次迭代中將一個新數(shù)加到和執(zhí)行循環(huán)，在每次迭代中將一個新數(shù)加到和(sum)(sum)之上；之上；之上；之上；結(jié)束循環(huán)，返回結(jié)果。結(jié)束循環(huán)，返回結(jié)果。結(jié)束循環(huán)，返回結(jié)果。結(jié)束循環(huán)，返回結(jié)果。26求和求和272、乘積、乘積283、排序、排序&排序排序是計算機科學中一個最基本的應(yīng)用。如果數(shù)是計算機科學中一個最基本的應(yīng)用。如果數(shù)據(jù)是無序的，從一堆數(shù)據(jù)中查找一條信息是非常困據(jù)是無序的，從一堆數(shù)據(jù)中查找一條信息是非常困難的。排序之后，使得查找數(shù)據(jù)變得非常容易快捷。難的。排序之后，使得查找數(shù)據(jù)變得非常容易快捷。&簡單的排序算法簡單的排序算法 選擇排序選擇排序選擇排序選擇排序 冒泡排序冒泡排序冒泡排序冒泡排序 插入排序插入排序插入排序插入排序29選擇排序選擇排序&列表被分成兩個子列表：列表被分成兩個子列表：已排序已排序和和未排序未排序的；初的；初始時已排序部分為空。始時已排序部分為空。&排序時，排序時，從未排序列表中找到最小元素，與第一從未排序列表中找到最小元素，與第一個元素交換個元素交換。&經(jīng)過選擇和交換后，將未排序列表中的第一個元經(jīng)過選擇和交換后，將未排序列表中的第一個元素劃入排序列表中，這一過程稱為一次素劃入排序列表中，這一過程稱為一次掃描掃描。每次。每次掃描后，未排序列表減少一個元素，已排序列表增掃描后，未排序列表減少一個元素，已排序列表增加一個元素。加一個元素。&對于對于n n個數(shù)據(jù)，需要進行個數(shù)據(jù)，需要進行n-1n-1次掃描。次掃描。30選擇排序選擇排序31選擇排序示例選擇排序示例32選擇排序的選擇排序的UML圖圖33冒泡排序冒泡排序&列表也被分成兩個子列表：已列表也被分成兩個子列表：已排序和未排序的排序和未排序的；初始時已排序部分為空。初始時已排序部分為空。&在未排序的子列表中，最小的元素通過在未排序的子列表中，最小的元素通過冒泡冒泡的方的方法選出來并移動到已排序子列表中，這一過程稱為法選出來并移動到已排序子列表中，這一過程稱為一次掃描。每次掃描，未排序元素增加一次掃描。每次掃描，未排序元素增加1 1個，已排個，已排序元素減少序元素減少1 1個。個。&冒泡時，進行冒泡時，進行兩兩比較兩兩比較，如果前者較大，則，如果前者較大，則交換交換數(shù)據(jù)。數(shù)據(jù)。&對于對于n n個數(shù)據(jù)，需要進行個數(shù)據(jù)，需要進行n-1n-1次掃描。次掃描。34冒泡排序冒泡排序35冒泡排序示例冒泡排序示例36插入排序插入排序&列表也被分成兩個子列表：列表也被分成兩個子列表：已排序和未排序已排序和未排序的；的；初始時已排序部分為空。初始時已排序部分為空。&在每次掃描過程中，取出未排序列表中的第一個在每次掃描過程中，取出未排序列表中的第一個元素，然后轉(zhuǎn)到已排序列表中，將其元素，然后轉(zhuǎn)到已排序列表中，將其插入到合適的插入到合適的位置上位置上。每次掃描，未排序列表增加。每次掃描，未排序列表增加1 1個，已排序個，已排序列表減少列表減少1 1個。個。&對于對于n n個數(shù)據(jù)，需要進行個數(shù)據(jù)，需要進行n-1n-1次掃描。次掃描。37插入排序插入排序38插入排序示例插入排序示例39其它排序方法其它排序方法&選擇、插入、冒泡排序是基本的排序算法，都需選擇、插入、冒泡排序是基本的排序算法，都需要兩重循環(huán)，要兩重循環(huán)，算法的效率不高算法的效率不高。&其它的一些高效排序算法有：其它的一些高效排序算法有：快速排序、堆排序、快速排序、堆排序、希爾排序、桶式排序、合并排序希爾排序、桶式排序、合并排序等，不同的排序算等，不同的排序算法對不同類型的數(shù)據(jù)列表更有效。在數(shù)據(jù)結(jié)構(gòu)課程法對不同類型的數(shù)據(jù)列表更有效。在數(shù)據(jù)結(jié)構(gòu)課程中介紹。中介紹。404、查找、查找&查找也是一種基本算法，實現(xiàn)在列表中確定目標查找也是一種基本算法，實現(xiàn)在列表中確定目標所在位置。查找通常返回具有要查找目標值的所在位置。查找通常返回具有要查找目標值的第一第一個元素的位置個元素的位置(索引索引)&兩種查找兩種查找 順序查找順序查找順序查找順序查找：適用無序列表：適用無序列表：適用無序列表：適用無序列表 折半查找折半查找折半查找折半查找：適用有序列表：適用有序列表：適用有序列表：適用有序列表41順序查找順序查找&用于查找用于查找無序列表無序列表，一般用這種方法查找規(guī)模較，一般用這種方法查找規(guī)模較小的列表。小的列表。&順序查找從表頭開始順序查找從表頭開始逐個元素查找逐個元素查找，當找到目標，當找到目標元素或查找完整個列表時，查找過程結(jié)束。元素或查找完整個列表時，查找過程結(jié)束。42順序查找示例順序查找示例43折半查找折半查找&順序查找很慢順序查找很慢，尤其當列表中數(shù)據(jù)非常多時，逐，尤其當列表中數(shù)據(jù)非常多時，逐個元素比較非常費時。當列表有序時，可采用效率個元素比較非常費時。當列表有序時，可采用效率非常高的非常高的折半查找算法折半查找算法。&折半查找時，折半查找時，先測試中間元素先測試中間元素，可以判斷出目標，可以判斷出目標在列表的前半部分還是后半部分。如果在前半部分，在列表的前半部分還是后半部分。如果在前半部分，則不用比較后半部分數(shù)據(jù)，排除掉一半數(shù)據(jù)。則不用比較后半部分數(shù)據(jù)，排除掉一半數(shù)據(jù)。&重復(fù)折半過程，直到找到目標或確定目標不在列重復(fù)折半過程，直到找到目標或確定目標不在列表中。表中。44折半查找示例折半查找示例45本章內(nèi)容安排本章內(nèi)容安排&概念概念&三種結(jié)構(gòu)三種結(jié)構(gòu)&算法的表示算法的表示&更正式的定義更正式的定義&基本算法基本算法&子算法子算法&遞歸遞歸46子算法子算法&結(jié)構(gòu)化編程的結(jié)構(gòu)化編程的原則原則要求把算法分成幾個單元，稱要求把算法分成幾個單元，稱之為之為子算法子算法。&子算法又可以劃分為更小的子算法，一直到子算子算法又可以劃分為更小的子算法，一直到子算法變?yōu)樽畋举|(zhì)的（獨立的任務(wù)）。法變?yōu)樽畋举|(zhì)的（獨立的任務(wù)）。&劃分子算法的好處：劃分子算法的好處：程序容易理解，易于解決問題；程序容易理解，易于解決問題；程序容易理解，易于解決問題；程序容易理解，易于解決問題；可在其它地方調(diào)用，可重用、可維護?？稍谄渌胤秸{(diào)用，可重用、可維護?？稍谄渌胤秸{(diào)用，可重用、可維護?？稍谄渌胤秸{(diào)用，可重用、可維護。47子算法子算法48結(jié)構(gòu)圖結(jié)構(gòu)圖&程序員使用的另一個編程工具就是程序員使用的另一個編程工具就是結(jié)構(gòu)圖結(jié)構(gòu)圖。&結(jié)構(gòu)圖是一種高層結(jié)構(gòu)圖是一種高層設(shè)計工具設(shè)計工具，顯示算法中不同模，顯示算法中不同模塊之間的關(guān)系。塊之間的關(guān)系。49本章內(nèi)容安排本章內(nèi)容安排&概念概念&三種結(jié)構(gòu)三種結(jié)構(gòu)&算法的表示算法的表示&更正式的定義更正式的定義&基本算法基本算法&子算法子算法&遞歸遞歸501、迭代的定義、迭代的定義&編寫算法有兩種途徑，一種是編寫算法有兩種途徑，一種是迭代迭代，一種是，一種是遞歸遞歸。遞歸是算法自我調(diào)用的過程遞歸是算法自我調(diào)用的過程&階乘計算的迭代定義階乘計算的迭代定義512、遞歸的定義、遞歸的定義&遞歸算法定義中包含對其自身的調(diào)用。遞歸算法定義中包含對其自身的調(diào)用。&階乘的遞歸調(diào)用階乘的遞歸調(diào)用523的階乘計算過程的階乘計算過程53迭代算法迭代算法54遞歸算法遞歸算法55