C語言程序設計課件 第11章

第11章計算機算法基礎11.1常用算法11.2查找算法11.3排序算法本章小結

11.1常用算法

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

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

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

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

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

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

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

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

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

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

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

下面介紹計算機算法的設計。

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

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

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

(3)當x0與x1的差的絕對值還不滿足指定的精度要求時，重復步驟(2)的計算。

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

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

程序運行結果為

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

11.1.2窮舉法

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

窮舉法由于會進行大量的重復計算，自然會用到程序的循環(huán)結構，因此靈活運用循環(huán)結構進行程序設計是窮舉法程序設計的關鍵。

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

解題思路這是一個典型的窮舉問題。如果用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ù))。使用窮舉法遍歷所有可能的取值結果，逐一判斷篩選出正確的結果。

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

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

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

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

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

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

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

①甲說：“乙沒有偷，是丁偷的?！睂?a[1]+a[3]==1)竊賊要么是乙，要么是丁。

②乙說：“我沒有偷，是丙偷的?！睂?a[1]+a[2]==1)竊賊要么是乙，要么是丙。

③丙說：“甲沒有偷，是乙偷的?！睂?a[0]+a[1]==1)竊賊要么是甲，要么是乙。

④丁說：“我沒有偷?！睂?a[0]+a[1]+a[2]==1||a[3]==1)竊賊只有一個。

上述4個條件之間是“與”的關系。整理表達式后，就可以得到完整的問題求解條件：

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

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

11.1.3遞推法

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

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

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

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

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

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

11.1.4遞歸法

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

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

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

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

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

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

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

11.1.5回溯法

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

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

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

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

圖11-1迷宮問題示意圖

下面對程序進行一些說明。

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

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

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

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

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

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

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

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

11.1.6貪婪法

貪婪法又稱為貪心法，是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因為它省去了為找最優(yōu)解要窮舉所有可能而必須耗費的大量時間。貪婪法常以當前情況為基礎進行最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不需要回溯。因為不進行回溯處理，貪婪法只在很少的情況下可以得到真正的最優(yōu)解，比如最短路徑、圖的最小生成樹等。

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

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

11.2查找算法

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

11.2.2二分查找

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

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

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

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

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

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

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

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

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

11.3排序算法

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

11.3.1冒泡排序

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

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

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

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

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