第三章典型算法介紹浙江省普通本科高校“十四五”重點教材Python程序設(shè)計實踐教程01枚舉算法PARTONE1.算法定義枚舉算法（ExhaustAlgorithm）又叫窮舉法，也稱為暴力破解法，是指針對要解決的問題，列舉出所有可能的情況，逐個判斷哪些符合問題所要求的約束條件，從而得到問題的解。2.算法特點這種算法充分利用計算機(jī)語言的循環(huán)結(jié)構(gòu)，其優(yōu)點是思路簡單，程序編寫和調(diào)試都很方便。如果問題規(guī)模不是很大，要在規(guī)定的時間與空間內(nèi)求出解，那么枚舉算法是最直接、簡單的選擇。這種算法的缺點是運算量比較大、解題效率不高。如果枚舉范圍太大（超過2000000次），會花費大量時間。3.算法思路這種算法的基本思想是根據(jù)問題的條件確定大致范圍，并在該范圍內(nèi)進(jìn)行窮舉并驗證，直到問題得到解決。這種算法一般用于決策最優(yōu)化問題，適合那些很難找到大、小規(guī)模之間的關(guān)系，也不易進(jìn)行分解的問題。第一步確定解題范圍，枚舉出所有可能的解。第三步使可能解的范圍降至最小，以便提高解題效率。第二步判斷是否符合正解的條件。4.算法案例【例】“百雞百錢”問題中國古代數(shù)學(xué)家張丘建在《算經(jīng)》中提出了著名的“百雞百錢”問題：雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一；百錢買百雞，問雞翁、雞母、雞雛各幾何？（已知公雞每只5元，母雞每只3元，小雞1元3只。要求用100元正好買100只雞，問公雞、母雞、小雞各買多少只？）題目分析：設(shè)買x只公雞、y只母雞、z只小雞，則問題轉(zhuǎn)化為三元一次方程組，即x+y+z=100（百雞），5x+3y+z/3=100（百錢），1個方程無法解出3個變量，只能將各種可能的取值代入，求出能使兩個方程成立的解。雞和錢的總數(shù)都是100，因此可以確定x、y、z的取值范圍。x的取值范圍為1～20（100/5=20），y的取值范圍為1～33（100/3≈33），z的取值范圍為1～99，求解流程圖如圖3-1所示。02遞歸算法PARTTWO1.算法定義遞歸算法（RecursionAlgorithm）把問題轉(zhuǎn)化為同類問題的子問題，然后通過遞歸調(diào)用過程（或函數(shù)）表示問題的解。一個程序過程（或函數(shù)）直接或間接調(diào)用自己本身，這種過程（或函數(shù)）稱為遞歸過程（或函數(shù)）。

遞歸調(diào)用分為直接遞歸和間接遞歸。直接遞歸是指在過程中調(diào)用方法本身，間接遞歸是指間接地調(diào)用一個過程。一般來說，遞歸算法需要有邊界條件、遞歸前進(jìn)段、遞歸返回段。不滿足邊界條件時，遞歸前進(jìn)；滿足邊界條件時，遞歸返回。2.算法特點遞歸過程一般通過函數(shù)或子過程來實現(xiàn)，在函數(shù)或子過程的內(nèi)部直接或間接地調(diào)用自身，常用于一些有明顯遞推性質(zhì)的問題。遞歸算法的優(yōu)點

代碼簡潔、清晰、可讀性好。遞歸算法的缺點

遞歸形式比非遞歸形式的運行速度慢。如果遞歸層次太深，會導(dǎo)致堆棧溢出。雖然算法代碼通常顯得很簡潔，但遞歸算法的運行效率較低。所以，如果有別的算法可行，一般不提倡用遞歸算法設(shè)計程序。3.算法思路遞歸

把一個問題歸結(jié)為一個或多個規(guī)模更小的子問題，然后用同樣的方法求解規(guī)模更小的子問題，要求子問題與原問題是同一類型，以保證可用同樣的方法求解。如此下去，直到子問題的規(guī)模小到可以直接求解。遞歸算法有以下三個基本要求。①每次循環(huán)都必須使問題規(guī)模變小。②遞歸操作中相鄰的兩步是緊密關(guān)聯(lián)的，在返回到上一層的操作中，前一次的輸出信息是后一次的輸入信息。③當(dāng)子問題的規(guī)模足夠小時，能直接求出該子問題的解，也就是說必須具備結(jié)束遞歸的初始條件。4.算法案例【例】階乘問題階乘（Factorial）是指1到n之間的所有自然數(shù)相乘的結(jié)果。在進(jìn)行問題求解前，首先分析下面的分段函數(shù)。f(n)=1，n=1f(n)=nf(n-1)，n>1編寫程序時，以fact()函數(shù)的調(diào)用過程為例，遞歸調(diào)用分為遞推和回歸兩個階段，如圖3-2所示。遞歸調(diào)用4.算法案例【例】漢諾塔（Hanoi）問題漢諾塔問題是一個古典數(shù)學(xué)問題，只能用遞歸算法來解決。有一個漢諾塔，塔內(nèi)有A、B、C三個座。開始時A上有64個盤子，盤子的大小不同，大的在下面，小的在上面，如圖3-3所示。現(xiàn)有一個和尚想將這64個盤子從A移動到C上，但他每次只能移動一個盤子。在移動過程中，必須保持A、B、C上的盤子是大盤在下、小盤在上的狀態(tài)。在移動過程中可以利用B，請分析移動過程。漢諾塔4.算法案例首先考慮A上最下面的盤子，如果能將它上面的63個盤子移動到C上，則完成任務(wù)，具體步驟如下。①將A最上面的63個盤子移動到B上。②將A上剩下的一個盤子移動到C上。③將B上的63個盤子移動到C上。如果能完成上述三步，則完成任務(wù)，這種方法就是遞歸的思考方法。為了將A最上面的63個盤子移動到B上，還需要做以下工作。①將A最上面的62個盤子移動到C上。②將A上剩下的一個盤子移動到B上。③將C上的62個盤子移動到B上。03分治算法PARTTHREE1.算法定義分治算法

將一個規(guī)模為n的問題分解為k個規(guī)模較小的子問題（這些子問題相互獨立且與原問題的性質(zhì)相同），再把子問題分成更小的子問題，直到子問題可以直接進(jìn)行求解，原問題的解即為子問題解的合并。任何一個可以用計算機(jī)求解的問題所需的計算時間都與其規(guī)模有關(guān)。問題的規(guī)模越小，越容易求解，所需的計算時間也越少。“分而治之”技巧是很多高效算法的基礎(chǔ)，如排序算法（快速排序、歸并排序等）、傅里葉變換（快速傅里葉變換）等。由分治算法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技術(shù)提供了方便。2.算法特點當(dāng)問題的規(guī)模縮小到一定程度時，就可以容易地解決。如果問題可以分解為若干個規(guī)模較小的相同問題，則該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。利用子問題的解可以合并出問題的最終解。所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。010203043.算法思路（1）分解將要解決的問題劃分成若干規(guī)模較小的同類問題。（2）求解當(dāng)子問題劃分得足夠小時，用較簡單的方法解決。（3）合并按原問題的要求，將子問題的解逐層合并，構(gòu)成原問題的解。4.算法案例【例】在有序數(shù)據(jù)數(shù)列中查找給定的數(shù)設(shè)n個有序數(shù)（從小到大排序）存放在數(shù)組a[0]～a[n-1]中，要查找的數(shù)為x。用變量bot、top、mid分別表示所查找的數(shù)據(jù)范圍的底部（序列的下界）、頂部（序列的上界）、中間（mid=(bot+top)/2），算法如下。（1）如果x=a[mid]，則已找到給定的數(shù)，退出循環(huán)，否則進(jìn)行下面的判斷。（2）如果x<a[mid]，則x必定在bot～mid-1范圍內(nèi)，即top=mid-1。（3）如果x>a[mid]，則x必定在mid+1～top范圍內(nèi)，即bot=mid+1。（4）確定了新的查找范圍后，重復(fù)進(jìn)行以上比較，直到找到給定的數(shù)或top≤bot。04遞推算法PARTFOUR1.算法定義遞推算法一種簡單的算法，即通過已知條件，利用特定關(guān)系得出中間推論，直至得到結(jié)果。順推法從已知條件出發(fā)，逐步推算出要解決的問題。逆推法從已知問題的結(jié)果出發(fā)，用迭代表達(dá)式逐步推算出問題的開始條件，即順推法的逆過程。3.算法思路遞推算法的本質(zhì)按規(guī)律逐次推出（計算）下一步的結(jié)果，所以更多用于計算。遞推算法是計算序列的一種常用算法，其思想是把一個復(fù)雜的、龐大的計算過程轉(zhuǎn)化為簡單過程的多次重復(fù)，利用了計算機(jī)速度快和“不知疲倦”的特點。第一步確定問題的數(shù)據(jù)信息之間存在著特定的遞推關(guān)系，并用數(shù)學(xué)公式描述出來。第三步盡量使用簡單變量，使計算的過程值暫用的空間量少，以便提高解題效率。第二步確定由已知的基礎(chǔ)數(shù)據(jù)可以遞推出后面的數(shù)據(jù)。4.算法案例【例】斐波那契數(shù)列（FibonacciSequence）問題斐波那契數(shù)列是：1，1，2，3，5，8，13，21，34，55，89，144…，求第n項的值。設(shè)它的函數(shù)為F(n)，已知F(1)=1、F(2)=1，那么F(n)=F(n-1)+F(n-2)(n≥3)，則通過順推可以知道，F(xiàn)(3)=F(1)+F(2)=2、F(4)=F(2)+F(3)=3……只要配合循環(huán)控制序列項編號，就很容易得到想要的項值。05貪心算法PARTFIVE1.算法定義貪心算法將問題的求解過程看作一系列選擇，它所作的每一個選擇都是當(dāng)前狀態(tài)下某種意義上的最優(yōu)解（即貪心選擇），并期望通過每次所作的貪心選擇（局部最優(yōu)解）導(dǎo)致最終結(jié)果是問題的一個最優(yōu)解或近似最優(yōu)解。2.算法特點有一個以最優(yōu)方式解決的問題。為了構(gòu)造問題的解決方案，有一個候選的對象的集合。隨著算法的進(jìn)行，將積累起其他兩個集合，一個包含已經(jīng)被考慮過并被選出的候選對象，另一個包含已經(jīng)被考慮過但被丟棄的候選對象。有一個函數(shù)來檢查一個候選對象的集合是否提供了問題的解答，該函數(shù)不考慮此時的解決方法是否最優(yōu)。還有一個函數(shù)檢查是否一個候選對象的集合是可行的，即是否可能往該集合上添加更多的候選對象以獲得一個解。和上一個函數(shù)一樣，此時不考慮解決方法的最優(yōu)性。選擇函數(shù)可以指出哪個剩余的候選對象最有希望構(gòu)成問題的解。01020304053.算法思路貪心算法的主要思路如下。①建立數(shù)學(xué)模型來描述問題。②把求解的問題分成若干個子問題。③對每一子問題求解，得到子問題的局部最優(yōu)解。④把子問題的局部最優(yōu)解合成原來問題的一個解。一般情況下，要選出最優(yōu)量度標(biāo)準(zhǔn)并不是一件容易的事，但對某問題選擇出最優(yōu)量度標(biāo)準(zhǔn)后，用貪心算法求解特別有效。4.算法案例【例】背包問題（KnapsackProblem）假設(shè)有n個物品和一個背包，物品i的重量是Wi，價值為Pi，背包的載荷能力為M。對于任一物品，該物品只能裝入一次，并且不能只裝入物品的一部分（要么整體裝入背包，要么不裝入）。請問：如何選擇物品，才能使裝入背包中的物品的總價值最大？將該問題轉(zhuǎn)化成數(shù)學(xué)語言。給定M>0、Wi>0、Pi>0（1≤i≤n），要求找出一個n元向量（X1，X2，…，Xn），使得∑WiXi≤M，而且∑PiXi最大。4.算法案例【例】旅游路徑的選擇貪心算法也很適合用于旅游路徑的選擇，如圖所示，假如要從節(jié)點5走到節(jié)點3，最短的路徑是什么呢？以貪心算法來說，當(dāng)然是先走到節(jié)點1，接著走到節(jié)點2，最后走到節(jié)點3，這樣的距離是28。可是從圖中我們發(fā)現(xiàn)直接從節(jié)點5走到節(jié)點3才是最短的距離，也就是說，在這種情況下無法用貪心算法找到最佳的解決方案。旅游路徑的選擇06回溯算法PARTSIX1.算法定義回溯算法（Back-TrackingAlgorithm）一種“選優(yōu)”的搜索方法，按照“選優(yōu)”的條件向前搜索，以達(dá)到目標(biāo)；如果搜索到某一步時，發(fā)現(xiàn)原先的選擇并不“優(yōu)”或達(dá)不到目標(biāo)，就退一步重新選擇，這種走不通就退回再走的技術(shù)就是回溯算法。2.算法特點回溯算法

沿著一條路往前走，能進(jìn)則進(jìn)，不能進(jìn)則退回來，換一條路再試。回溯算法在迷宮搜索中很常見，如果某條路走不通，就返回前一個路口，繼續(xù)探尋下一條路。回溯算法其實就是一種枚舉算法。不過回溯算法使用剪枝函數(shù)，剪去一些不可能到達(dá)最終狀態(tài)（即答案）的節(jié)點，從而減少狀態(tài)空間樹的節(jié)點。3.算法思路通過對問題的分析，找出一個解決問題的線索，然后沿著這個線索向前試探，若試探成功，就得到解；若試探失敗，就逐步往回退，換別的路線再向前試探。回溯算法實際上是廣度與深度結(jié)合的搜索方法，深度搜索過程中碰到條件不滿足的情況，則退回上一層，進(jìn)行全面的搜索。4.算法案例【例】老鼠走迷宮一只老鼠在一個n×n迷宮的入口處，它想吃迷宮出口處放著的奶酪，這只老鼠能否吃到奶酪？如果可以吃到，請給出一條從入口到奶酪的路徑。老鼠在迷宮的入口處，迷宮中有許多墻，使大部分路徑都被擋住而無法前進(jìn)。老鼠可以采用嘗試錯誤的方法找到出口。不過，這只老鼠必須能在走錯路時重來一次并把走過的路記下來，避免下次走同樣的路，直到找到出口。老鼠行進(jìn)時，必須遵守以下三個原則。①一次只能走一格。②遇到墻無法往前走時，退回一步找找看是否有其他路可以走。③走過的路不會再走第二次。4.算法案例在編寫走迷宮程序之前，我們先來了解如何在計算機(jī)中表現(xiàn)一個仿真迷宮。這時可以使用二維數(shù)組，并符合以下規(guī)則。maze[i][j]=1表示[i][j]處有墻，無法通行。maze[i][j]=0表示[i][j]處無墻，可通行。一個10×10的迷宮如圖所示，灰色部分是墻，白色部分是可以走的路。迷宮的入口在上面，出口在右側(cè)。4.算法案例這個迷宮其實是由10×10=100個格子組成的，灰色格子代表墻，白色格子代表路，如圖(a)所示。“灰色格子代表墻，白色格子代表路”是用語言形式描述的，需要轉(zhuǎn)換成數(shù)學(xué)形式，用1和0分別定義灰色格子和白色格子，如圖(b)所示。4.算法案例從數(shù)學(xué)的角度分析老鼠走迷宮的過程。假設(shè)老鼠從左上角的maz