計算機科學導論-基于計算思維的思想與方法（第4版） 課件【ch07】問題求解的算法基礎

計算機科學導論基于計算思維的思想與方法問題求解的算法基礎第七章新工科建設之路·計算機類系列教材01算法——問題求解的核心算法——問題求解的核心01一、算法的基本概念算法研究史上最著名的古老算法是用于求兩個整數(shù)的最大公約數(shù)的歐幾里得(Euclid)算法。這個算法最早出現(xiàn)在大約公元前350——300年由古希臘數(shù)學家歐幾里得寫成的《Elements》(《幾何原本》)中，它被人們公認為是算法史上的第一個算法，歐幾里得算法的原理是重復應用等式1.算法的起源算法——問題求解的核心01一、算法的基本概念算法是求解問題的方法和步驟，并具有完整的規(guī)則。把算法歸納為以下5個顯著特征。(1)確定性；(2)有效性；(3)有窮性；(4)有零個或多個輸入；(5)有一個或多個輸出。2.算法的特征算法——問題求解的核心01二、算法的設計要求1.正確性(Correctness)正確性是指對一切合法的輸入，都能在有限次的計算后產生正確的結果。算法的正確是評價一個算法優(yōu)劣的重要指標，一旦完成對算法的描述，必須證明它是正確的。2.可讀性(Readality)可讀性是指算法可供人們閱讀的容易程度。一個好的算法應便于閱讀、理解、編碼、修改等。從書寫角度來說，結構上要直觀、清晰、美觀，并在必要的地方加上注釋說明。算法——問題求解的核心01二、算法的設計要求3.健壯性(Robustness)健壯性是指一個算法對不合理輸入數(shù)據的反應能力和處理能力。程序設計時要充分考慮異常情況。健壯性體現(xiàn)了思維的縝密性，如果沒有對算法進行仔細認真的考察，特別是極端數(shù)據、特殊數(shù)據的處理，就很可能使算法失去準確性。4.算法的運行效率算法的運行效率是指在程序執(zhí)行時，所需耗用的時間和所占用的內存空間。耗用的時間和占用的空間越少，則算法的運行效率越高。算法的運行效率是評價算法好壞的重要指標。算法——問題求解的核心01三、算法的復雜性1.時間復雜度(TimeComplexity)算法的時間復雜度是指度量時間的復雜性，即算法的時間效率的指標。換言之，時間復雜度是與求解問題的規(guī)模、算法輸入數(shù)據相關的函數(shù)，該函數(shù)表示算法運行所花費的時間。為了簡化問題，通常用算法運行某段代碼的次數(shù)來代替準確的執(zhí)行時間，記為T(n)。T即Time的首字母，T(n)中的n表示問題規(guī)模的大小，一般指待處理的數(shù)據量的大小。算法——問題求解的核心01三、算法的復雜性2.空間復雜度(SpaceComplexity)算法的空間復雜度是指算法運行的存儲空間，是實現(xiàn)算法所需的內存空間的大小?？臻g復雜度也是與求解問題規(guī)模、算法輸入數(shù)據相關的函數(shù)，記為S(n)。空間復雜度的分析方法與時間復雜度的分析是類似的，往往希望算法有常數(shù)數(shù)量級或多項式數(shù)量級的空間復雜度。算法——問題求解的核心01四、算法的描述方法1.用自然語言描述算法自然語言是人們日常所使用的語言，如漢語、英語、日語等。用自然語言描述算法是最原始方法，也是最直觀、通俗易懂、為人們所熟悉的方法。算法——問題求解的核心01四、算法的描述方法2.用圖形描述算法由于用自然語言描述算法的邏輯結構不是太好，對于稍復雜的算法問題很容易出錯，因此常用圖形描述算法。目前，用來描述算法的圖形有3種：流程圖(FlowChart)、N-S圖和PAD圖，

它們各有其優(yōu)點，人們更多地習慣用流程圖描述算法，并特別適合初學者。算法——問題求解的核心01四、算法的描述方法3.用偽代碼描述算法偽代碼是一種介于自然語言與高級語言之間描述方法，常用偽代碼符號如表7-1所示。算法——問題求解的核心01四、算法的描述方法4.用程序設計語言描述算法無論是用自然語言或偽代碼，還是用流程圖所描述的算法，都不能被機器識別，最后必須將它們轉換成程序設計語言。因此，用程序設計語言來描述算法是最直接有效的方法。存在以下不足：(1)要求設計者必須熟練掌握程序設計語言和編程技巧；(2)要求描述計算步驟的細節(jié)，從而忽視了算法的本質；

(3)程序設計語言基于串行，算法的邏輯流程難以遵循，邏輯較復雜時問題越顯嚴重。02數(shù)值數(shù)據求解——算法策略數(shù)值數(shù)據求解——算法策略02窮舉算法(ExhaustiveAttackAlgorithm)，也稱為枚舉算法(EnumerateAlgorithm)或稱為強力算法(Brute-forceAlgorithm)，是針對要解決的問題，列舉所有可能的情況，逐個判斷哪些條件符合問題所要求的約束條件，從而得到問題的解。一、窮舉算法數(shù)值數(shù)據求解——算法策略021.算法思想(1)確定范圍：按照問題要求確定問題解的大致范圍一一列舉，遍歷所有可能的組合值。(2)條件約束：判斷題解是否符合正解條件，避免解題結果錯誤。(3)循環(huán)運算：使可能解的范圍降至最小，以便提高解題效益。一、窮舉算法數(shù)值數(shù)據求解——算法策略022.算法特點(1)算法優(yōu)點：思路簡單，問題的答案是一個有窮的集合，可以一一列舉出來。(2)算法缺點：運算量比較大，解題效率不高。(3)算法應用：適用于決策類最優(yōu)化問題。一、窮舉算法數(shù)值數(shù)據求解——算法策略02回溯算法(Back-TrackingAlgorithm)是窮舉法和試探法的結合，它將要解決的問題的所有解空間(SolutionSpace)分為若干節(jié)點，每個節(jié)點有若干可供選擇的后續(xù)節(jié)點，然后按某種順序逐一窮舉和試驗。若不滿足條件，返回到上一層節(jié)點，恢復剛才的參數(shù)，再試探其他分支。二、回溯算法數(shù)值數(shù)據求解——算法策略02二、回溯算法1.算法思想回溯法是一種解決問題的方法，而不是一種特殊算法?；厮菟惴ㄒ话惆凑找韵虏襟E求解：(1)定義：針對所給問題，定義問題的解空間，至少包含問題的一個最優(yōu)解；(2)確定：根據定義，確定易于搜索的解空間結構，使得能用回溯方法搜索整個解空間；(3)搜索：以深度優(yōu)先的方式搜索解空間，并且在搜索過程中用剪枝函數(shù)避免無效搜索。數(shù)值數(shù)據求解——算法策略02二、回溯算法2.算法特點回溯算法本質上是一種窮舉法，但它是比窮舉“聰明”的搜索技術，有“通用解題法”之稱。當一個問題沒有顯而易見的解法時，可以嘗試使用回溯法求解。不過，該算法耗時多，效率低。由于回溯算法是對解空間的深度優(yōu)先探索，所以在一般情況下可用遞歸函數(shù)來實現(xiàn)回溯算法。數(shù)值數(shù)據求解——算法策略02三、遞推算法遞推算法(RecurrenceAlgorithm)是根據問題本身的已知條件，利用特定關系得出中間推論，直至得到結果的算法。遞推算法本質上屬于歸納法，即根據簡單、特殊實例，總結一般性結論。遞推算法分為順推和反推(逆推)兩種。順推是指從已知條件出發(fā)，逐步推算出求解結果；反推是指從已知結果出發(fā)，用迭代表達式逐步推出問題的開始條件(初始值)，它是順推的逆過程。數(shù)值數(shù)據求解——算法策略02三、遞推算法1.算法思想遞推方法是假設問題在某一步某個條件下成立，下一步可根據這一步所得到的關系進行推導，把一個復雜、龐大的計算過程轉化為簡單過程的多次重復運算。遞推算法一般按以下步驟進行。(1)確定問題數(shù)據之間的特定關系，并將這種關系規(guī)律歸納成簡捷的遞推關系式

；(2)確定由已知的基礎數(shù)據可以遞推出后面的數(shù)據，而且盡量簡化變量，以減少變量暫用空間。數(shù)值數(shù)據求解——算法策略02三、遞推算法2.算法特點每相鄰兩項之間的變化有一定規(guī)律性，通過后項與前項之間的關系，從初始條件入手，一步步地按遞推關系進行遞推，直到求出最終結果。(1)算法優(yōu)點：思路簡單，無論是程序編寫還是程序調試，都很方便，而且程序運行效率高。(2)算法缺點：運算的過程值較多，耗用空間大。適合大、小規(guī)模之間的關系。(3)算法應用：適用于已知本身條件，利用特定關系得出中間推論，直至得到最終結果。數(shù)值數(shù)據求解——算法策略02四、迭代算法迭代算法(IterativeAlgorithm)就是在數(shù)的序列中建立起后項與前項之間的關系，通過從一個初始值出發(fā)，不斷用變量的舊值遞推新值的過程。迭代算法包括求精確解和近似解的算法。1.迭代算法思想所謂迭代，就是為了逼近所需目標或結果而重復反饋，每次迭代的結果作為下次迭代的初始值。迭代與遞推的區(qū)別源于問題的性質，在實際問題中可能遇到以下兩種情況。(1)可以表示成數(shù)學上明確的遞推公式。(2)無法直接寫出顯式遞推公式：只能通過“迭代”，并且可分為精確迭代和近似迭代。數(shù)值數(shù)據求解——算法策略02四、迭代算法2.算法特點(1)算法優(yōu)點：對一組指令進行重復執(zhí)行，每次執(zhí)行時都從變量的原值中推出它的一個新值。(2)算法缺點：如果方程無解，算法的近似根序列不會收斂，迭代過程失??；如果方程雖然有解但迭代公式選擇不當，或迭代的初始近似根選擇不合理，也會導致迭代失敗。(3)算法應用：是遞推算法的反推形式，適用于方程求根，方程組求解，矩陣求特征值等。數(shù)值數(shù)據求解——算法策略02五、遞歸算法遞歸算法(RecursiveAlgorithm)是指在定義算法的過程中，用自身的簡單情況來定義自身，直接或間接地調用自身的一種算法。一個直接或間接地調用自身的過程稱為遞歸過程(RecursiveProcedure)，一個使用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)(RecursiveFunction)。1.算法思想遞歸是一種強有力的數(shù)學工具，它可使問題的描述和求解變得簡潔和清晰，它有兩種形式。(1)直接遞歸(2)間接遞歸數(shù)值數(shù)據求解——算法策略02五、遞歸算法2.算法特點本質上，遞歸和遞推都是同一種解決問題的思路，都是把問題進行分解，但遞推是由小到大的推導，而遞歸則是由大到小的推導。(1)算法優(yōu)點：程序代碼簡潔、清晰，可讀性好。(2)算法缺點：如果遞歸層次太深(太多)，會導致堆棧溢出，而且遞歸算法運行效率較低。(3)算法應用：適用于當問題本身或所涉及的數(shù)據結構是遞歸定義的情況，可與分治法結合。數(shù)值數(shù)據求解——算法策略02六、分治算法分治算法(DivideandConquerAlgorithm)是將一個難以直接解決的大問題，劃分成一些規(guī)模較小子問題，以便各個擊破。因此，分治算法是一種“分而治之”的算法思想策略。1.算法思想由分治算法產生的子問題往往是原問題的較小模式，最終使子問題縮小到容易直接求解，自然導致遞歸過程的產生，也為使用遞歸技術提供了方便。分治算法一般按照以下步驟求解：(1)分解(2)求解(3)合并數(shù)值數(shù)據求解——算法策略02六、分治算法2.算法特點“分而治之”策略是很多高效算法的思想基礎，由分治法產生的子問題往往是原問題的較小或最小模式，這既導致了遞歸過程的產生，也為使用遞歸技術提供了方便，最終使子問題縮小到很容易直接求出其解。分治算法與遞歸算法像一對孿生兄弟經常同時應用在算法設計中，并由此產生許多高效算法，如漢諾塔問題、折半查找、快速排序等，都是分治策略運用的典型實例。數(shù)值數(shù)據求解——算法策略02七、貪心算法貪心算法(GreedyAlgorithm)是把一一個復雜問題分解為一系列較為簡單的局部最優(yōu)選擇，每一步選擇都是對當前解的一個擴展，直到獲得問題的完整解。貪心算法的典型應用是求解最優(yōu)問題(OptimizationProblem)，即在滿足一定約束條件下，使得目標函數(shù)的值達到最大或最小。數(shù)值數(shù)據求解——算法策略02七、貪心算法1.算法思想貪心算法的指導思想是將待求的問題分解成若干子問題進行分步求解，并且每一步總是做出當前最好的選擇，即得到局部最優(yōu)解，然后將各個子問題的局部最優(yōu)解組合成原問題的一個解。由此可見，貪心算法體現(xiàn)了“快刀斬亂麻”的思想，以當前和局部利益最大化為導向的求解策略。2.算法特點貪心算法是最接近人類日常思維的一種問題求解方法，例如“背包問題”“田忌賽馬”等都是典型實例。數(shù)值數(shù)據求解——算法策略02八、動態(tài)規(guī)劃1.算法思想為了解決某一多階段決策過程的優(yōu)化問題，而依次做出n個決策D1，D2，.，Dn；如果這個決策序列是最優(yōu)的，不論前面決策是怎樣的，以后的最優(yōu)決策取決于由前面決策所確定的當前狀態(tài)。動態(tài)規(guī)劃一般按照以下步驟求解。(1)劃分(2)推導(3)記錄數(shù)值數(shù)據求解——算法策略02八、動態(tài)規(guī)劃2.算法特點(1)算法優(yōu)點：能夠得到全局最優(yōu)解，可以得到一族最優(yōu)解，由于動態(tài)規(guī)劃方法反映了動態(tài)過程演變的聯(lián)系和特征，在計算時可以利用實際知識和經驗提高求解效率。(2)算法缺點：一是沒有統(tǒng)一的標準模型；二是數(shù)值方法求解時需要額外的內存空間。(3)算法應用：動態(tài)規(guī)劃方法是解決復雜問題的思維方法，在經濟管理、生產調度、工程技術和最優(yōu)控制值等方面得到廣泛應用，用動態(tài)規(guī)劃方法求解比用其它方法求解更為方便、有效。03非數(shù)值數(shù)據處理——數(shù)據結構非數(shù)值數(shù)據處理——數(shù)據結構03一、線性表結構線性表(LinearTable)是由有限個相同的數(shù)據元素所構成的序列，通常記為a1，a2，...an。除了第一個元素只有直接后繼、最后一個元素只有直接前驅，其余數(shù)據元素都有一個直接前驅和一個直接后繼。學生檔案表是一個典型的線性表。1.線性表的定義非數(shù)值數(shù)據處理——數(shù)據結構03一、線性表結構將一個線性表存儲到計算機中可以采用多種不同的方法來實現(xiàn)，通常采用的方法有順序存儲結構(也稱為靜態(tài)存儲結構)和鏈式存儲結構(也稱為動態(tài)存儲結構)。2.線性表的實現(xiàn)非數(shù)值數(shù)據處理——數(shù)據結構03一、線性表結構線性表是最簡單、最常用的一種數(shù)據結構，通常用于對大量數(shù)據元素進行隨機存取的情況，例如，程序設計中使用的數(shù)組和字符串，由學生學籍信息構成的檔案表項，用計算機進行學籍管理時對數(shù)據表項實現(xiàn)添加、刪除、修改、查找、存儲等操作，都是線性表的典型應用。若對線性表的這些基本操作加以一定的限制，則形成特殊結構的線性表，即棧結構和隊列結構。3.線性表的應用非數(shù)值數(shù)據處理——數(shù)據結構03二、棧結構1.棧結構的定義棧(Stack)或堆棧是限制線性表中元素的插入和刪除只能在線性表的同一端進行的一種特殊線性表，是一種“先進后出”的數(shù)據結構，首先存入棧中的元素在棧底(Bottom)，最后存入棧中的元素在棧項(Top)，，它是允許插入或刪除的端口，沒有元素的堆棧稱為空棧。棧結構形如子彈夾，其數(shù)據動態(tài)如圖7-12所示。非數(shù)值數(shù)據處理——數(shù)據結構03二、棧結構2.棧結構的實現(xiàn)棧結構的具體實現(xiàn)取決于棧的存儲結構，存儲結構不同，其相應的算法描述方法也不同。存儲結構通常分為順序存儲和鏈接存儲兩種形式。3.棧結構的應用在程序設計中通常用于數(shù)據逆序處理的各種場合，如對數(shù)據進行首尾元素互換的排序操作、函數(shù)嵌套調用時返回地址的存放、編譯過程中的語法分析等。在程序設計中，函數(shù)嵌套調用和遞歸調用的實現(xiàn)都包含棧的應用。非數(shù)值數(shù)據處理——數(shù)據結構03三、隊列結構隊列結構也是一種運算受限的線性表，其限制是僅允許在表的一端進行插入，而在表的另一端進行刪除。這種邏輯結構被稱為隊列(Queue)，只允許插入的一端被稱為隊尾(Rear)，只允許刪除的一端被稱為隊首(Front)。1.隊列結構的定義非數(shù)值數(shù)據處理——數(shù)據結構03三、隊列結構隊列結構可以采用順序存儲結構來實現(xiàn)，也可以采用鏈表存儲結構來實現(xiàn)。順序存儲結構：一般情況下，使用一維數(shù)組作為隊列的順序存儲空間；再設兩個指示器：一個指向隊頭元素位置的指示器front，另一個指向隊尾元素位置的指示器rear。鏈表存儲結構：在一個鏈表隊列中需要設定兩個指針(頭指針和尾指針)，分別指向隊列的頭部和尾部。2.隊列結構的實現(xiàn)非數(shù)值數(shù)據處理——數(shù)據結構03三、隊列結構隊列結構可用于應用系統(tǒng)中的事件規(guī)劃，典型的實例是CPU資源的競爭問題，如在操作系統(tǒng)中用來解決主機與外部設備之間速度不匹配或多個用戶引起的資源競爭問題。3.隊列結構的應用非數(shù)值數(shù)據處理——數(shù)據結構03四、樹結構1.樹結構的定義樹結構(TreeStructure)是一種非常重要的非線性數(shù)據結構，該結構因節(jié)點之間存在的分支、層次關系非常類似一顆倒立的樹而得名。(Subtree)。樹的定義是遞歸的，深刻地反映了樹的固有特性，即一棵非空樹是由若干子樹構成的，而子樹又可由若干更小的子樹構成。非數(shù)值數(shù)據處理——數(shù)據結構03四、樹結構2.二叉樹和哈夫曼樹二叉樹是指每個節(jié)點的度至多為2的有序樹，如圖7-15所示。哈夫曼樹又稱為最優(yōu)二叉樹，是指對于一組帶有確定權值的葉節(jié)點構造出具有最小帶權路徑長度(最精簡、最高效描述)的二叉樹。非數(shù)值數(shù)據處理——數(shù)據結構03四、樹結構3.二叉樹的實現(xiàn)二叉樹的實現(xiàn)可以采用順序存儲結構，也可以采用鏈表存儲結構，但主要采用鏈表存儲結構。順序存儲結構：完全二叉樹采用自上而下，每層自左向右的順序存儲；非完全二叉樹也按完全二叉樹的形式來存儲，不過需要增加空節(jié)點。鏈表存儲結構：用順序存儲結構存放一般的二叉樹比較浪費存儲空間，所以通常采用鏈表的方式存儲。非數(shù)值數(shù)據處理——數(shù)據結構03四、樹結構4.二叉樹的遍歷遍歷(Traversal)是指沿著某條搜索路線依次對樹中每個節(jié)點僅做一次訪問。二叉樹遍歷的實質是將非線性結構的數(shù)據線性化的過程，并先遍歷左子樹，再遍歷右子樹。5.樹結構的應用樹結構在計算機領域中具有廣泛應用。例如，在編譯系統(tǒng)中，用樹來表示源程序的語法結構；在人工智能系統(tǒng)中，用樹來描述數(shù)據模型；在文件系統(tǒng)中，用樹來描述目錄結構；在數(shù)據庫中，用樹結構來組織信息和大型列表的搜索。04數(shù)據元素操作——查找和排序數(shù)據元素操作——查找和排序04一、查找算法1.順序查找(SequentialSearch)順序查找，又稱為線性查找，是一種最簡單的查找算法，既適用于線性表的順序存儲結構，也適用于線性表的鏈式存儲結構。(1)順序查找算法思想：順序查找是從線性表的一段開始，順序掃描該線性表。(2)順序查找算法分析：對n個元素進行順序查找，若查找成功，則所需比較關鍵字的次數(shù)最少為1，即R[n]