《數(shù)學(xué)（第8版 下冊）》 課件 第5章 算法初步

算法初步第5章204目錄5.1算法的含義5.2流程圖5.3基本算法語句205學(xué)習(xí)目標(biāo)1.通過對解決具體問題過程與步驟的分析（如一元二次方程組求解等問題），體會算法的思想，并能敘述算法的含義.2.在具體問題的解決過程中，能說出程序框圖的三種基本邏輯結(jié)構(gòu)（順序、選擇、循環(huán)）及繪制算法框圖的常用符號和含義.3.能寫出簡單問題的算法及流程，并繪制算法框圖.4.了解偽代碼的基本算法語句，能根據(jù)流程圖用偽代碼寫出簡單問題的算法.2065.1算法的含義207實例考察在你面前的桌面上擺放著A，B兩個大小相同的杯子.A杯子中裝有水，B杯子中裝有飲料，采取怎樣的辦法才能交換A，B兩個杯子中的液體?解決這個問題，我們可以按以下步驟進行.第一步：先找一個容量不小于A，B的空杯子C；第二步：將A杯子中的水倒入到C杯子中；第三步：將B杯子中的飲料倒入到A杯子中；第四步：將C杯子中的水倒入到B杯子中，完成交換.208以上過程實際上是按一種機械的程序進行的一系列操作.一般而言，對一類問題的機械的、統(tǒng)一的求解方法稱為算法.同一項任務(wù)可以用不同的算法完成，花費的時間可能不同.一個算法的好壞可以綜合復(fù)雜程度和執(zhí)行這個算法耗費的時間等因素來衡量.如果一個算法有缺陷或不適合某個問題，執(zhí)行這個算法就不能解決這個問題.209例

寫出求解方程組的一個算法.解

我們用消元法求解這個方程組.第一步：方程①不變，用方程②中x的系數(shù)除以方程①中x的系數(shù)，得到乘數(shù)m=.210第二步：方程②減去

m

倍的方程①，從而消去方程②中的x項，得到第三步：將上面的方程組自下而上回代求解，得到

x=1，y=2.所以，原方程組的解為211上面例子所示的消元回代的算法適用于一般線性方程組的求解.所謂找到了某種算法，是指使用一系列運算規(guī)則能在有限步驟內(nèi)求解某類問題，其中的每條規(guī)則必須是明確定義、可以執(zhí)行的.算法從初始步驟開始，每一個步驟只能有一個確定的后繼步驟，從而組成一個步驟序列，序列的終止表示問題得到解答或指出問題沒有答案.我們所學(xué)過的許多數(shù)學(xué)公式都是算法，加、減、乘、除運算法則以及多項式的運算法則也是算法.2125.2流程圖213實例考察

在快遞派送過程中，因為目的地偏遠(yuǎn)而派送不到的情形被快遞公司稱為快遞超區(qū).一般情況下，快遞公司對此采取以下措施.可以看到，用框圖和線來表示各種操作流程的優(yōu)點是形象直觀、便于理解.2145.2.1流程圖實例考察中，快遞公司把每一步工作流程都按照方框里面的指令操作，各步驟之間用流程線順序連接成一個整體.這種用規(guī)定的圖框、流程線及文字來準(zhǔn)確、直觀地表示算法的圖形，叫做算法的流程圖.它是算法的一種圖形表示形式，其中圖框表示各種操作的類型，圖框中的文字和符號表示操作的內(nèi)容，流程線表示操作的先后次序.構(gòu)成流程圖的圖形符號及其功能見下表.215216

流程圖的圖形符號及其功能5.2.2流程圖的基本機構(gòu)實例考察某企業(yè)根據(jù)崗位需求招募高技能人才，用人部門、人事部門、管理層緊密配合，按照規(guī)定一般遵循以下流程圖.217

從流程圖中可以看出，該算法步驟中，有些是按順序執(zhí)行，有些需選擇執(zhí)行.事實上，算法的流程圖有三種基本的邏輯結(jié)構(gòu)：順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu).這三種結(jié)構(gòu)通過組合和嵌套來表達(dá)算法的流程圖.流程圖可以幫助我們更方便直觀地表現(xiàn)這三種基本的算法結(jié)構(gòu).2181.順序結(jié)構(gòu)順序結(jié)構(gòu)是一種按順序依次進行多個處理的結(jié)構(gòu).如圖所示，虛線框內(nèi)是一個順序結(jié)構(gòu)，其中A

和B

兩個框是依次執(zhí)行的.順序結(jié)構(gòu)是一種最簡單、最基本的結(jié)構(gòu).2192.選擇結(jié)構(gòu)選擇結(jié)構(gòu)是一種先根據(jù)條件做出判斷，再決定執(zhí)行哪一種操作的結(jié)構(gòu)（或稱為分支結(jié)構(gòu)）.如圖所示，虛線框內(nèi)是一個選擇結(jié)構(gòu)，它包含一個判斷框，當(dāng)條件p成立（或為“真”）時，執(zhí)行A，否則執(zhí)行B.選擇結(jié)構(gòu)是一種有條件的二選一的操作結(jié)構(gòu).2203.循環(huán)結(jié)構(gòu)在算法中，需要重復(fù)執(zhí)行同一操作的結(jié)構(gòu)稱為循環(huán)結(jié)構(gòu).如圖所示，虛線框內(nèi)是一種常見的循環(huán)結(jié)構(gòu)：先判斷所給條件p

是否成立，若p

成立，則執(zhí)行

A；再判斷條件p是否成立，若p仍成立，則又執(zhí)行A，如此反復(fù)，直到某一次條件p不成立時為止.這樣的循環(huán)結(jié)構(gòu)稱為當(dāng)型循環(huán).221下面這種循環(huán)結(jié)構(gòu)稱為直到型循環(huán)：先執(zhí)行A，再判斷條件p是否成立，若p不成立，則再執(zhí)行A，如此反復(fù)，直到p成立，該循環(huán)過程結(jié)束.2225.3基本算法語句223算法是一種數(shù)學(xué)語言，計算機完成任何一項任務(wù)都需要算法，但是計算機無法識別數(shù)學(xué)語言，因此還需要我們把算法表示成計算機能夠“理解”的程序語言.偽代碼（pseudocode）就是介于自然語言與計算機語言之間的文字和符號.程序語言多種多樣，為了表示算法的三種基本邏輯結(jié)構(gòu)，各種程序語言中都包含下列基本的算法語句.2245.3.1賦值語句、輸入和輸出語句在偽代碼中，賦值語句用符號“←”表示，例如

“x←y”

表示將y的值賦給x，其中x是一個變量，y是一個與x同類型的變量或表達(dá)式.2255.3.2條件語句和循環(huán)語句計算機不僅可以進行一些簡單的賦值運算，還可以對給出的條件進行分析、比較、判斷，并按照判斷后的不同情況進行不同的處理.例如，判斷一個數(shù)的正負(fù)、比較兩個數(shù)的大小、對一組數(shù)據(jù)進行排序等.226當(dāng)型循環(huán)可用下面的語句來描述：它表示當(dāng)所給條件p成立時，執(zhí)行循環(huán)體部分，然后再判斷條件p是否成立.如果p

仍成立，那么再次執(zhí)行循環(huán)體，如此反復(fù)，直到某一次條件p不成立時退出循環(huán).227上述算法用當(dāng)型循環(huán)語句

“While...EndWhile”表示如下：228上述的算法也可以改為直到型循環(huán).S1：T←1；S2：I←3；S3：T←T×I；S4：I←I+2；S5：如果I>99，那么轉(zhuǎn)S6，否則轉(zhuǎn)S3；S6：輸出T.229直到型循環(huán)可用下面的語句來描述：它表示先執(zhí)行循環(huán)體部分，然后再判斷條件p

是否成立.如果p不成立，那么再次執(zhí)行循環(huán)體，如此反復(fù)，直到某一次條件p成立時退出循環(huán).230

上述算法用直到型循環(huán)語句“Do...EndDo”表示如下：231如果循環(huán)語句中的循環(huán)次數(shù)已知，那么還可采用“For”

語句來描述.“For”

語句的一般形式是：232上述算法用

“For”

語句可表示如下：在上面的For語句中，如果省略語句“Step2”，那么重復(fù)循環(huán)時，I的值每次增加1.2335.3.3算法應(yīng)用例題解析例

設(shè)計解決“孫子問題”的算法.我國

《算經(jīng)十書》

之一的

《孫子算經(jīng)》

中有這樣的原文：“今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二.問物幾何?答曰：二十三.”“物不知數(shù)”問題提出之后，便引起了人們的很大興趣.南宋數(shù)學(xué)家秦昭九對此加以推廣，并給出新的解法———“大衍求一術(shù)”.這種解法和高斯的解法本質(zhì)上是一致的，但比高斯早了500余年.這種問題的通用解法被稱為

“孫子剩余定理”或“中國剩余定理”，這個定理在近代數(shù)學(xué)和計算機程序設(shè)計中有著廣泛的應(yīng)用.234解

算法設(shè)計思想：“孫子問題”相當(dāng)于求關(guān)于x，y，z的不定方程組的正整數(shù)解.設(shè)所求的數(shù)為m，根據(jù)題意，m

應(yīng)同時滿足下列3個條件：（1）m