常用的算法思想

常用的算法思想第1頁，課件共20頁，創(chuàng)作于2023年2月3.1什么是算法一個(gè)程序往往要包含兩個(gè)方面的描述，一是對(duì)數(shù)據(jù)組織的描述；一是對(duì)程序操作流程的描述。對(duì)數(shù)據(jù)組織的描述主要是指定數(shù)據(jù)的類型和數(shù)據(jù)的組織形式（例如數(shù)組），稱作數(shù)據(jù)結(jié)構(gòu)（datastructure），在下一節(jié)將會(huì)講到。對(duì)程序操作流程的描述就是程序的操作步驟，也本節(jié)所要介紹的所謂算法（algorithm）。正如NikiklausWirth提出的公式：數(shù)據(jù)結(jié)構(gòu)+算法=程序一樣，算法是一個(gè)程序中不可缺少的一部分。如果把一個(gè)可運(yùn)行的程序比喻成一個(gè)具有生命的人，那么數(shù)據(jù)結(jié)構(gòu)就是這個(gè)人的軀體，而算法則是這個(gè)人的靈魂或者說精神。所謂算法，廣義地講就是解決問題的方法和過程。第2頁，課件共20頁，創(chuàng)作于2023年2月3.2算法的分類表示及測(cè)評(píng)1、算法的分類。2、算法的表示。3、算法性能的測(cè)評(píng)第3頁，課件共20頁，創(chuàng)作于2023年2月3.3窮舉法思想窮舉法(ExhaustiveAttackmethod)，又稱為強(qiáng)力法(Brute-forcemethod)，它是一種最為直接，實(shí)現(xiàn)最為簡單，同時(shí)又最為耗時(shí)的一種解決實(shí)際問題的算法思想。本節(jié)將詳細(xì)介紹窮舉法的算法思想。第4頁，課件共20頁，創(chuàng)作于2023年2月3.3.1基本概念窮舉法算法的基本思想是：在可能的解空間中窮舉出每一種可能的解，并對(duì)每一個(gè)可能解進(jìn)行判斷，從中得到問題的答案。使用窮舉法思想解決實(shí)際問題，最關(guān)鍵的步驟是劃定問題的解空間，并在該解空間中一一枚舉每一個(gè)可能的解。這里有兩點(diǎn)需要注意。一是解空間的劃定必須保證覆蓋問題的全部解。如果解空間集合用H表示，問題的解集用h表示，那么只有當(dāng)時(shí)，才能使用窮舉法求解。二是解空間集合及問題的解集一定是離散的集合，也就是說集合中的元素是可列的、有限的。第5頁，課件共20頁，創(chuàng)作于2023年2月3.3.2尋找給定區(qū)間的素?cái)?shù)【實(shí)例3-3】尋找[1，100]之間的素?cái)?shù)。分析：解決這個(gè)問題最簡便的方法就是使用窮舉法。在[1，100]中對(duì)每一個(gè)整數(shù)進(jìn)行判斷，看它是不是素?cái)?shù)。在這里，問題的解空間自然就是[1，100]中的全部整數(shù)，因?yàn)椴粫?huì)有任何一個(gè)解超出這個(gè)范圍，同時(shí)該解空間構(gòu)成的集合元素是可列有限的。算法描述如下：for(i=1;i<=100;i++)if(i是素?cái)?shù))輸出i;判斷一個(gè)數(shù)是否是素?cái)?shù)的算法描述在3.2節(jié)中已詳細(xì)介紹，這里不再贅述。第6頁，課件共20頁，創(chuàng)作于2023年2月3.3.3TOM的借書方案【實(shí)例3-4】TOM共有5本新書，要借給A,B,C三位同學(xué)，每人只能借1本書，則TOM可以有多少種不同的借書方法。分析：這個(gè)問題仍然可以用窮舉法輕松地解決。假設(shè)TOM的5本書編號(hào)為{1，2，3，4，5}，每個(gè)同學(xué)可能借到的書的范圍就限定在{1，2，3，4，5}之中。因此TOM借書給3位同學(xué)的組合方案不可能超過53=125種。由這125種借書方案構(gòu)成的解空間可描述為{(x1,x2,x3)|1≤xi≤5,且xi∈R}，該解空間是由3個(gè)各包含5個(gè)元素（圖書編號(hào)）的集合排列組合而成。應(yīng)用窮舉法在該空間中搜索答案。第7頁，課件共20頁，創(chuàng)作于2023年2月3.4遞歸與分治思想遞歸與分治的算法思想往往是相伴而生的，它們?cè)诟黝愃惴ㄖ惺褂梅浅ｎl繁，應(yīng)用遞歸和分治的算法思想有時(shí)可以設(shè)計(jì)出代碼簡潔且比較高效的算法來。本章將詳細(xì)介紹遞歸與分治的算法思想。第8頁，課件共20頁，創(chuàng)作于2023年2月3.4.1基本概念在解決一些比較復(fù)雜的問題，特別是解決一些規(guī)模較大的問題時(shí)，我們常常將問題進(jìn)行分解。具體來說，就是將一個(gè)規(guī)模較大的問題分割成規(guī)模較小的同類問題，然后將這些小的子問題逐個(gè)加以解決，最終也就將整個(gè)大的問題解決了。這種分而治之的思想稱作分治的思想。在解決一些問題比較復(fù)雜、計(jì)算量龐大的問題時(shí)經(jīng)常被用到。一個(gè)最為經(jīng)典的使用分治思想設(shè)計(jì)的算法就是第二章中介紹過的“折半查找算法”。折半查找算法利用了元素之間的順序關(guān)系（有序序列），采用分而治之的策略，不斷縮小問題的規(guī)模，每次都將問題的規(guī)模減小至上一次的1/2。采用順序查找的方法對(duì)關(guān)鍵字進(jìn)行搜索的時(shí)間復(fù)雜度為O(n)，而采用折半查找方法的時(shí)間復(fù)雜度僅為O(log2n)。第9頁，課件共20頁，創(chuàng)作于2023年2月3.4.2計(jì)算整數(shù)的劃分?jǐn)?shù)【實(shí)例3-6】將一個(gè)正整數(shù)n表示成一系列的正整數(shù)之和：被稱作正整數(shù)n的一個(gè)劃分。一個(gè)正整數(shù)n可能存在著不同的劃分，例如正整數(shù)6的全部的劃分為：6=66=5+16=4+26=4+1+16=3+36=3+2+16=3+1+1+16=2+2+26=2+2+1+16=2+1+1+1+16=1+1+1+1+1+1第10頁，課件共20頁，創(chuàng)作于2023年2月3.4.3遞歸的折半查找算法【實(shí)例3-7】有一個(gè)數(shù)組A[10]，里面存放了10個(gè)整數(shù)，順序遞增。A[10]={2,3,5,7,8,10,12,15,19,21}任意輸入一個(gè)用數(shù)字n，用折半查找法找到n位于數(shù)組中的位置。如果n不屬于數(shù)組A，顯示錯(cuò)誤提示。要求用遞歸的方法實(shí)現(xiàn)折半查找。分析：在第二章中曾詳細(xì)地介紹過折半查找的算法，它是一種針對(duì)有序序列（或文件記錄）的高效的查找算法。折半查找的基本思想是：減小查找序列的長度。它的查找過程是：先確定待查找記錄的所在的范圍，然后逐漸縮小查找的范圍，直至找到該記錄為止（也可能查找失?。?。因此它也是一種基于分治的算法思想設(shè)計(jì)出來的查找算法。第11頁，課件共20頁，創(chuàng)作于2023年2月3.5貪心算法思想貪心算法的思想非常簡單而且算法效率很高，在一些問題的解決上有著明顯的優(yōu)勢(shì)。本章將詳細(xì)介紹貪心算法的基本思想。第12頁，課件共20頁，創(chuàng)作于2023年2月3.5.1基本概念所謂貪心算法，就是總是做出在當(dāng)前看來是最好的選擇的一種方法。以上述的找零錢為例，為了找給顧客的硬幣數(shù)量最少，在選擇硬幣的面值時(shí)，當(dāng)然是盡可能地選擇面值大的硬幣。因此嚴(yán)格意義上講，要使用貪心算法求解問題，該問題應(yīng)當(dāng)具備以下性質(zhì)。（1）貪心選擇性質(zhì)：（2）最優(yōu)子結(jié)構(gòu)性質(zhì)：第13頁，課件共20頁，創(chuàng)作于2023年2月3.5.2最優(yōu)裝船問題【實(shí)例3-8】有一批集裝箱要裝入一個(gè)載重量為C的貨船中，每個(gè)集裝箱的重量由用戶自己輸入指定，在貨船的裝載體積不限的前提下，如何裝載集裝箱才能盡可能多地將集裝箱裝入貨船中。分析：這個(gè)問題可以用貪心算法求得最優(yōu)解。只要每次裝船時(shí)，采取重量最輕的集裝箱先裝船的策略，就可以得到最優(yōu)裝船問題的一個(gè)最優(yōu)解。第14頁，課件共20頁，創(chuàng)作于2023年2月3.6回溯法回溯法是一種非常有效，適用范圍相當(dāng)廣泛的算法設(shè)計(jì)思想。許多復(fù)雜的問題，規(guī)模較大的問題都可以使用回溯法求解。因此回溯法又有“通用解題方法”的美稱。本章將詳細(xì)介紹回溯法的算法思想。第15頁，課件共20頁，創(chuàng)作于2023年2月3.6.1基本概念回溯法的基本思想是：在包含問題的所有解的解空間樹中，按照深度優(yōu)先搜索的策略，從根結(jié)點(diǎn)出發(fā)深度探索解空間樹。當(dāng)探索到某一結(jié)點(diǎn)時(shí)，要先判斷該結(jié)點(diǎn)是否包含問題的解，如果包含，就從該結(jié)點(diǎn)出發(fā)繼續(xù)探索下去；如果該結(jié)點(diǎn)不包含問題的解，那就說明以該結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹一定不包含問題的最終解，因此要跳過對(duì)以該結(jié)點(diǎn)為根的子樹的系統(tǒng)探索，逐層向其祖先結(jié)點(diǎn)回溯。這個(gè)過程叫做解空間樹的“剪枝”操作。如果應(yīng)用回溯法求解問題的所有解，要回溯到解空間樹的樹根，這樣根結(jié)點(diǎn)的所有子樹都被探索到才結(jié)束。如果只要求解問題的一個(gè)解，那么在探索解空間樹時(shí)，只要搜索到問題的一個(gè)解就可以結(jié)束了。第16頁，課件共20頁，創(chuàng)作于2023年2月3.6.2四皇后問題求解【實(shí)例3-9】應(yīng)用回溯法的思想求解四皇后問題。分析：上面一節(jié)中已經(jīng)詳細(xì)介紹了回溯法解決四皇后問題的基本過程。在這里將給出具體的算法描述和程序清單。其實(shí)在解決四皇后問題時(shí)，并不一定要真的構(gòu)建出這樣一棵解空間樹，它完全可以通過一個(gè)遞歸回溯來模擬。所謂解空間樹只是一個(gè)邏輯上的抽象。當(dāng)然也可以用樹結(jié)構(gòu)來真實(shí)地創(chuàng)建出一棵解空間樹，不過那樣會(huì)比較浪費(fèi)空間資源。第17頁，課件共20頁，創(chuàng)作于2023年2月3.7數(shù)值概率算法在解決實(shí)際問題時(shí)，有時(shí)會(huì)用到所謂的概率算法。概率算法允許在執(zhí)行過程中隨機(jī)地選擇下一步的計(jì)算步驟，因此使用概率算法有時(shí)會(huì)大大地提高算法的效率，但有時(shí)也可能得不到問題的全部答案。第18頁，課件共20頁，創(chuàng)作于2023年2月3.7.1基本概念概率算法大致分為四類：數(shù)值概率算法，蒙特卡洛(MonteCarlo)算法，拉斯維加斯(LasVegas)算法，和舍伍德(Sherwood)算法。這里只介紹最為基礎(chǔ)的數(shù)值概率算法。數(shù)值概率算法常應(yīng)用于解決數(shù)值計(jì)算的問題。應(yīng)用數(shù)值概率算法往往只能得到問題的近似解，并且該近似解的精度一般隨著計(jì)算時(shí)間的增加而不斷提高。因?yàn)樵谝恍?shù)值問題中，不可能也沒有必要計(jì)算出問題的精確解（例如：計(jì)算無理數(shù)π的取值等），因此，在解決一些數(shù)值計(jì)算的問題時(shí)，數(shù)值概率算法常能派上用場(chǎng)。第19頁，課件共20頁，創(chuàng)作于2023年2月3.7.2計(jì)算定積分【實(shí)例3-10】設(shè)f(x)=1-x2，計(jì)算定積分：的值。分析：函數(shù)f(