C語言程序設(shè)計(jì)課件 第11章

第11章計(jì)算機(jī)算法基礎(chǔ)11.1常用算法11.2查找算法11.3排序算法本章小結(jié)

11.1常用算法

11.1.1迭代法迭代法也稱輾轉(zhuǎn)法，是一種不斷用變量的舊值遞推新值的方法，通常用于解決無法直接求解或者求解較為復(fù)雜的問題。迭代法的基本思想是將一個(gè)復(fù)雜問題的求解過程轉(zhuǎn)化為相對(duì)簡(jiǎn)單的迭代算式，然后從一個(gè)初始值開始，通過不斷迭代運(yùn)算，逐步逼近問題的解，直到滿足預(yù)設(shè)的精度要求或者收斂條件為止。

迭代分為精確迭代和近似迭代。精確迭代是指迭代算法本身提供了問題的精確解。如最大公約數(shù)、進(jìn)制轉(zhuǎn)換、質(zhì)因數(shù)的分解等問題都適合使用精確迭代來解決。而近似迭代是指迭代算法不能得到精確解，只能通過控制迭代次數(shù)或精度使解無限逼近精確解，可用于解決優(yōu)化問題、數(shù)值積分等問題。比如，在機(jī)器學(xué)習(xí)中，梯度下降法就是一種典型的近似迭代算法，它通過不斷地調(diào)整模型參數(shù)來最小化損失函數(shù)，從而得到最優(yōu)的模型。求解方程根常用的“二分法”和“牛頓迭代法”也屬于近似迭代。

例11-1任意給出兩個(gè)正整數(shù)m和n，求它們的最大公約數(shù)和最小公倍數(shù)。

解題思路利用輾轉(zhuǎn)法求最大公約數(shù)，然后根據(jù)最大公約數(shù)得到最小公倍數(shù)，迭代方法如下：

(1)用m對(duì)n求余，余數(shù)記作r，即有語句r=m%n；

(2)將除數(shù)作為被除數(shù)，余數(shù)作為除數(shù)求新的余數(shù)，即m=n，n=r；

(3)重復(fù)執(zhí)行步驟(2)，直到余數(shù)為0為止，此時(shí)n即為最小公倍數(shù)。

迭代法更主要的應(yīng)用是進(jìn)行數(shù)值的近似求解，它既可以用來求解代數(shù)方程，又可以用來求解微分方程。在科學(xué)計(jì)算領(lǐng)域，人們常會(huì)遇到求微分方程的數(shù)值解或解方程f(x)=0等計(jì)算問題。這些問題無法用類似求和或求均值那樣的精確求解方法進(jìn)行求解。例如，一般的一元五次或更高階方程、幾乎所有的超越方程以及描述電磁波運(yùn)動(dòng)規(guī)律的麥克斯韋方程等，它們的解都無法用解析方法求解，為此，人們只能用數(shù)值計(jì)算的方法求出問題的近似解，而解的誤差是人們可以估計(jì)和控制的。

例11-2用迭代法求方程x3?-?4x?-?6?=?0在x?=?2附近的一個(gè)根。

重復(fù)以上步驟，可以逐次求得更精確的值。顯然，迭代過程就是通過重復(fù)執(zhí)行一系列計(jì)算來獲得問題近似答案，且每一次重復(fù)計(jì)算將產(chǎn)生一個(gè)更精確的解。

用計(jì)算機(jī)算法實(shí)現(xiàn)這一計(jì)算過程，不可能讓迭代無限制循環(huán)進(jìn)行，因此只能通過控制迭代次數(shù)或精度使解無限接近精確解。

下面介紹計(jì)算機(jī)算法的設(shè)計(jì)。

設(shè)方程為f(x)=0，用某種數(shù)學(xué)方法導(dǎo)出等價(jià)的形式x=g(x)，然后按以下步驟執(zhí)行。

(1)選一個(gè)方程的近似根，賦給變量x0；

(2)將x0的值保存于變量x1，然后計(jì)算g(x1)，并將結(jié)果存于變量x0；

(3)當(dāng)x0與x1的差的絕對(duì)值還不滿足指定的精度要求時(shí)，重復(fù)步驟(2)的計(jì)算。

若方程有根，并且用上述方法計(jì)算出來的近似根序列收斂，則按上述方法求得的x0就認(rèn)為是方程的根。上述算法用C程序的形式表示如下：

例11-3編寫求解例11-2問題的C語言程序。

程序運(yùn)行結(jié)果為

由以上介紹可知，近似迭代的基本構(gòu)建方法是：首先確定一個(gè)適當(dāng)?shù)牡闶剑⑦x擇一個(gè)初始近似值以及解的誤差，然后通過循環(huán)處理來執(zhí)行迭代過程。終止循環(huán)的條件是前后兩次得到的近似值之差的絕對(duì)值小于或等于預(yù)先設(shè)定的誤差，此時(shí)將最后一次迭代得到的近似值視為問題的解。

11.1.2窮舉法

窮舉法又稱為枚舉法或者蠻力法，是一種在問題域的解空間中對(duì)所有可能的解進(jìn)行窮舉搜索，并根據(jù)條件選擇最優(yōu)解的方法。窮舉法的基本思想是根據(jù)題目的部分條件確定解的大致范圍，并在此范圍內(nèi)對(duì)所有可能的情況逐一驗(yàn)證，直到全部情況驗(yàn)證完畢。若某個(gè)情況驗(yàn)證符合題目的全部條件，則為題目的一個(gè)解；若全部情況驗(yàn)證后都不符合題目的全部條件，則題目無解。

窮舉法由于會(huì)進(jìn)行大量的重復(fù)計(jì)算，自然會(huì)用到程序的循環(huán)結(jié)構(gòu)，因此靈活運(yùn)用循環(huán)結(jié)構(gòu)進(jìn)行程序設(shè)計(jì)是窮舉法程序設(shè)計(jì)的關(guān)鍵。

例11-4100塊磚由100個(gè)人來搬，成年男人一人搬4塊，成年女人一人搬3塊，小孩(不限男女)3人抬一塊，問成年男人、成年女人、小孩各幾人？請(qǐng)列出所有可能的取值結(jié)果。

解題思路這是一個(gè)典型的窮舉問題。如果用x、y、z分別代表成年男人、成年女人、小孩的人數(shù)，根據(jù)題意可列出方程：4x?+?3y?+?z/3?=?100。先確定每種類型人員的數(shù)量的取值范圍，由題意可知，成年男人x的取值范圍是0～100/4?=?25，成年女人y的取值范圍是0～100/3?=?33，小孩的取值范圍是0～99(必須不大于100且為3的倍數(shù))。使用窮舉法遍歷所有可能的取值結(jié)果，逐一判斷篩選出正確的結(jié)果。

例11-5抓賊問題。警察審問四名竊賊嫌疑犯。已知，這四人當(dāng)中僅有一名是竊賊，還知道這四人中每人要么是誠(chéng)實(shí)的，要么總是說謊。他們給警察的回答是：

甲說：“乙沒有偷，是丁偷的?！?/p>

乙說：“我沒有偷，是丙偷的?！?/p>

丙說：“甲沒有偷，是乙偷的?！?/p>

丁說：“我沒有偷?！?/p>

請(qǐng)根據(jù)這四人的回答判斷誰是竊賊。

解題思路本題用窮舉法求解。假設(shè)甲乙丙丁四人是否為竊賊用數(shù)組a表示，第i個(gè)元素的值等于“1”表示第i個(gè)人是竊賊；等于“0”表示該人不是。根據(jù)題意可列出求解的條件。

①甲說：“乙沒有偷，是丁偷的?！睂?duì)應(yīng)于(a[1]+a[3]==1)竊賊要么是乙，要么是丁。

②乙說：“我沒有偷，是丙偷的?！睂?duì)應(yīng)于(a[1]+a[2]==1)竊賊要么是乙，要么是丙。

③丙說：“甲沒有偷，是乙偷的。”對(duì)應(yīng)于(a[0]+a[1]==1)竊賊要么是甲，要么是乙。

④丁說：“我沒有偷?！睂?duì)應(yīng)于(a[0]+a[1]+a[2]==1||a[3]==1)竊賊只有一個(gè)。

上述4個(gè)條件之間是“與”的關(guān)系。整理表達(dá)式后，就可以得到完整的問題求解條件：

(a[3]+a[1]==1&&a[1]+a[2]==1&&a[0]+a[1]==1)

窮舉法的特點(diǎn)是算法簡(jiǎn)單，容易理解，但運(yùn)算量較大。通常適用于可確定取值范圍，但沒有更好的算法可用的情況。窮舉法常用于解決“有幾種組合”“是否存在”“求解不定方程”等問題類型。這種算法的設(shè)計(jì)通常依賴于循環(huán)控制結(jié)構(gòu)來實(shí)現(xiàn)。

11.1.3遞推法

遞推是一種數(shù)學(xué)方法和算法技術(shù)，主要用于解決問題和計(jì)算數(shù)值。它基于初始信息(如數(shù)列的初始項(xiàng))和遞推關(guān)系(如數(shù)列的規(guī)則)來逐步推導(dǎo)問題的答案或計(jì)算未知項(xiàng)的值。遞推法通常以循環(huán)的形式進(jìn)行，每一步都依賴于前一步的結(jié)果，從而避免求通項(xiàng)公式的復(fù)雜過程。

遞推法適用于具有明顯規(guī)律和線性關(guān)系的問題，具有高效和簡(jiǎn)潔的優(yōu)勢(shì)。例如，斐波那契數(shù)列的計(jì)算就是一個(gè)典型的遞推法的應(yīng)用，通過遞推公式F(n)=F(n-1)+F(n-2)(其中F(0)=0，F(xiàn)(1)=1)來計(jì)算數(shù)列的每一項(xiàng)。

例11-6采用遞推法求4的階乘值。

例11-7斐波那契數(shù)列為：1，1，2，3，5，8，13，21，34，55…即滿足

請(qǐng)編寫求斐波那契(Fibonacci)數(shù)列的第n項(xiàng)的函數(shù)。

用遞推法編寫的fib(n)函數(shù)如下：

11.1.4遞歸法

遞歸法是設(shè)計(jì)和描述算法的一種有力的工具，它通過將一個(gè)大問題拆分成一個(gè)或多個(gè)相似的子問題，并逐步解決這些子問題來解決整個(gè)問題。遞歸法的兩個(gè)關(guān)鍵組成部分是基本情況和遞歸調(diào)用?；厩闆r是指可以直接求解或返回結(jié)果的簡(jiǎn)單情況，而遞歸調(diào)用是指函數(shù)在執(zhí)行過程中調(diào)用自身來解決更小規(guī)模的子問題。

遞歸法常常應(yīng)用于解決具有自相似性的問題，如樹和圖的遍歷、分治算法等。盡管遞歸法能提供簡(jiǎn)潔、直觀的解決方案，但也可能帶來額外的開銷和運(yùn)行效率低的問題，特別是在處理大規(guī)模數(shù)據(jù)時(shí)需要注意堆棧溢出等情況。

例11-8用遞歸法編寫例11-7所需的函數(shù)fib(n)。

遞歸法的執(zhí)行過程分遞推和回歸兩個(gè)階段。在遞推階段，復(fù)雜問題的求解被推導(dǎo)為規(guī)模較小的子問題的求解，例如，對(duì)于fib(n)，它被推導(dǎo)為求解fib(n-1)和fib(n-2)。換言之，計(jì)算fib(n)需要先計(jì)算fib(n-1)和fib(n-2)，而這兩者又依賴于更小規(guī)模的問題，如fib(n-3)和fib(n-4)，以此類推，直至得到fib(2)和fib(1)的結(jié)果為1。在遞推階段，必須定義終止遞推的情況，如在fib()函數(shù)中，當(dāng)n為2或1時(shí)終止遞推。

在回歸階段，當(dāng)獲得最簡(jiǎn)單情況的解后，逐級(jí)返回，逐步獲得較為復(fù)雜問題的解。例如，得到fib(2)和fib(1)的解后，返回得到fib(3)的結(jié)果，直至得到fib(n-1)和fib(n-2)的結(jié)果后，返回得到fib(n)的結(jié)果。

在編寫遞歸函數(shù)時(shí)要注意，函數(shù)中的局部變量和參數(shù)只是局限于當(dāng)前調(diào)用層，當(dāng)遞推進(jìn)入“簡(jiǎn)單問題”層時(shí)，原來層次上的參數(shù)和局部變量便被隱蔽起來。在一系列“簡(jiǎn)單問題”層，它們各自有自己的參數(shù)和局部變量。

遞歸法必須確保在每次遞歸調(diào)用時(shí)問題規(guī)模都能夠縮小，否則可能導(dǎo)致無限遞歸和堆棧溢出等問題。此外，遞歸法的運(yùn)行效率可能較低，因?yàn)樗婕岸啻魏瘮?shù)調(diào)用和重復(fù)計(jì)算。當(dāng)某個(gè)遞歸法能較方便地轉(zhuǎn)換為遞推法時(shí)，通常按遞推法編寫程序。例如上例計(jì)算斐波那契數(shù)列的第n項(xiàng)的函數(shù)fib(n)應(yīng)采用例11-7所示的遞推法，即從斐波那契數(shù)列的前兩項(xiàng)出發(fā)，逐次由前兩項(xiàng)計(jì)算出下一項(xiàng)，直至計(jì)算出第n項(xiàng)。

11.1.5回溯法

回溯法也稱為試探法，該方法首先暫時(shí)放棄關(guān)于問題規(guī)模大小的限制，并將問題的候選解按某種順序逐一枚舉和檢驗(yàn)。當(dāng)發(fā)現(xiàn)當(dāng)前候選解不可能是解時(shí)，就選擇下一個(gè)候選解；若當(dāng)前候選解除了不滿足問題規(guī)模要求外，滿足所有其他要求時(shí)，繼續(xù)擴(kuò)大當(dāng)前候選解的規(guī)模，并繼續(xù)試探。如果當(dāng)前候選解滿足包括問題規(guī)模在內(nèi)的所有要求時(shí)，該候選解就是問題的一個(gè)解。在回溯法中，擴(kuò)大當(dāng)前候選解的規(guī)模，并繼續(xù)試探的過程稱為向前試探(前探)。放棄當(dāng)前候選解，尋找下一個(gè)候選解的過程稱為回溯。

回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達(dá)到目標(biāo)。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)稱為回溯，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為“回溯點(diǎn)”。例11-9就是一個(gè)典型的利用回溯法求解的例子。

例11-9迷宮問題。在指定的迷宮中找一條從入口到出口的可通路徑。

解題思路圖11-1所示的方塊圖表示迷宮，其中空白方塊表示通道，灰色方塊表示墻，在迷宮數(shù)組中分別用0和1表示?，F(xiàn)要在迷宮中找一條從入口到出口的可通路徑，基本的算法思想是：從入口處開始向前探路(探的方向有右、下、左和上)，當(dāng)沿著某個(gè)方向往前探一步時(shí)，若可通則繼續(xù)往前探，若不通則換個(gè)方向后再探，若4個(gè)方向上均不通(四個(gè)方向上的相鄰方塊要么是墻塊，要么是已探過的通道塊)，則按原路回退一步后換個(gè)方向再探。在探路的過程中，用一個(gè)二維數(shù)組記錄迷宮的可通路徑。

圖11-1迷宮問題示意圖

下面對(duì)程序進(jìn)行一些說明。

(1)程序中使用的函數(shù)如下：

①輸出迷宮數(shù)組的函數(shù)printMaze()。

②在迷宮中探尋可通路徑的函數(shù)findOnePath()。

(2)函數(shù)findOnePath()中使用的數(shù)組如下：

①迷宮數(shù)組maze[N1][N2]。數(shù)組元素值為0代表通(通道)，為1代表不通(墻)。

②可通路徑數(shù)組stack[N1*N2][2]。

程序中，所設(shè)置的條件編譯語句可以將每一步前探或回退后的可通路徑顯示出來，用以對(duì)回溯過程進(jìn)行跟蹤。整個(gè)過程可以通過圖11-2形象地描繪出來。圖11-2(a)演示從入口連續(xù)向前探尋12步后到達(dá)b位置。圖11-2(b)演示從b位置開始，連續(xù)回退8步后到達(dá)a位置。圖11-2(c)演示從a位置開始，連續(xù)前探14步后到達(dá)迷宮出口。最終，根據(jù)本程序探尋到的從入口到出口的一條迷宮可通路徑如圖11-2(c)中的實(shí)線箭頭所示。

圖11-2例11-9程序?qū)崿F(xiàn)的前探與回退過程

11.1.6貪婪法

貪婪法又稱為貪心法，是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因?yàn)樗∪チ藶檎易顑?yōu)解要窮舉所有可能而必須耗費(fèi)的大量時(shí)間。貪婪法常以當(dāng)前情況為基礎(chǔ)進(jìn)行最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不需要回溯。因?yàn)椴贿M(jìn)行回溯處理，貪婪法只在很少的情況下可以得到真正的最優(yōu)解，比如最短路徑、圖的最小生成樹等。

例11-10找零錢問題。當(dāng)前使用的貨幣面額分別是100、50、20、10、5、2、1元。在購(gòu)物找錢時(shí)，怎樣找錢才能使找零的張數(shù)最少?請(qǐng)根據(jù)找零的金額輸出找零的方案。

解題思路用貪婪法解決這個(gè)問題，在找錢時(shí)，為使找回的零錢的張數(shù)最少，不考慮找零錢的所有可能方案，而是從最大面值的幣種開始，按遞減的順序考慮各幣種，先盡量用大面值的幣種，當(dāng)不足大面值幣種的金額時(shí)才去考慮下一種較小面值的幣種。

11.2查找算法

11.2.1順序查找順序查找又稱線性查找，適用于順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表的查找。要查找的數(shù)一般稱為關(guān)鍵字，順序查找就是將給定的關(guān)鍵字與數(shù)組元素(或鏈表結(jié)點(diǎn))逐個(gè)進(jìn)行比較，一旦查找到與關(guān)鍵字相等的數(shù)組元素(或鏈表結(jié)點(diǎn))，則表示查找成功并輸出有關(guān)信息，否則查找失敗并提示沒有匹配值。例11-11是一個(gè)簡(jiǎn)單的順序查找算法示例。

11.2.2二分查找

二分查找要求數(shù)組是有序數(shù)組，如果不是有序數(shù)組，必須先排序，然后才能使用二分查找。二分查找的算法思想如下：

(1)把查找范圍平分為兩部分，首先判斷中點(diǎn)元素是否為要查找的關(guān)鍵字。

(2)如果要查找的關(guān)鍵字不位于中點(diǎn)，則將該關(guān)鍵字與中點(diǎn)元素比較大小，判斷它位于中點(diǎn)左邊還是右邊，縮小查找范圍。

(3)鎖定查找范圍后，在該部分排除上一步中比較的中點(diǎn)，并在此范圍內(nèi)重復(fù)步驟(1)(2)。

(4)逐步縮小查找范圍，如果查找到要找的關(guān)鍵字，則輸出相關(guān)信息，否則輸出查找失敗信息。

例11-12在一個(gè)有序的數(shù)列中查找指定的數(shù)。

解題思路數(shù)列有序則可以使用二分查找：假設(shè)有序數(shù)列遞增且存放在一個(gè)數(shù)組中。查找時(shí)，先查找中點(diǎn)值，若待查找的數(shù)等于中點(diǎn)值，則查找成功；若待查找的數(shù)小于中點(diǎn)值，則到數(shù)組的前半部分查找；若待查找的數(shù)大于中點(diǎn)值，則到數(shù)組的后半部分查找。這樣一直查找下去，如果找到了要查找的數(shù)，則查找成功，否則查找失敗，表明有序數(shù)列中不存在要查找的數(shù)。

此例要用到3變量：low、high和mid，分別指示被查找的那一部分有序數(shù)列的低下標(biāo)值、高下標(biāo)值和中間位置。如在有序數(shù)列(13,25,34,48,57,62,71,88,96)中查找88，則二分查找過程如圖11-3所示。

二分查找的算法流程如圖11-4所示。圖11-3二分查找88的過程圖11-4二分查找的算法流程

11.3排序算法

排序算法有直接插入排序、折半插入排序、簡(jiǎn)單選擇排序、希爾排序、冒泡排序、快速排序、堆排序、歸并排序等，這些排序算法在數(shù)據(jù)結(jié)構(gòu)課程中將會(huì)詳細(xì)闡述。本節(jié)主要介紹最簡(jiǎn)單的兩種排序算法：冒泡排序和快速排序。

11.3.1冒泡排序

若對(duì)N個(gè)數(shù)進(jìn)行升序排列，則冒泡排序的算法思想如下：

(1)從第1個(gè)數(shù)開始，將第1個(gè)數(shù)與第2個(gè)數(shù)進(jìn)行比較，若為逆序，則交換。然后比較第2個(gè)數(shù)與第3個(gè)數(shù)，若為逆序，則交換。依次類推，直至第N?-?1個(gè)數(shù)與第N個(gè)數(shù)比較并處理完為止。此時(shí)完成第一趟冒泡排序，最大的數(shù)已經(jīng)排在第N個(gè)位置上。

(2)對(duì)前N?-?1個(gè)數(shù)按上述同樣的方法進(jìn)行第二趟冒泡排序。這樣，次大的數(shù)將排在第N?-?1個(gè)位置上，以此類推，再對(duì)前N?-?2個(gè)數(shù)進(jìn)行第三趟冒泡排序。

(3)重復(fù)上述過程，總共進(jìn)行N?-?1趟排序。

例11-13輸入5個(gè)數(shù)，用冒泡排序?qū)?個(gè)數(shù)按升序排列