大學(xué)計算機基礎(chǔ)教程課件第8章 算法設(shè)計與實現(xiàn)

18.1算法基礎(chǔ)28.2基本算法設(shè)計方法38.3算法求解問題的過程48.4算法設(shè)計軟件RAPTOR——案例9：學(xué)生成績分析第8章算法設(shè)計與實現(xiàn)本章要點算法的基本概念、特性和設(shè)計要求。1要點算法的表示方法、設(shè)計方法以及使用算法求解現(xiàn)實應(yīng)用問題的一般過程。2要點算法實現(xiàn)軟件RAPTOR的使用方法。3要點算法設(shè)計思想和計算思維能力的訓(xùn)練和培養(yǎng)4要點8.1算法基礎(chǔ)算法基本概念算法求解問題過程RAPTOR軟件環(huán)境算法表示方法RAPTOR軟件使用本章知識點18.1.1算法基本概念28.1.2算法特征和設(shè)計要求38.1.3算法表示方法8.1算法基礎(chǔ)8.1.1算法基本概念（1）2006年，美國卡內(nèi)基梅隆大學(xué)（CarnegieMellonUniversity）計算機科學(xué)系主任周以真教授（JeannetteM.Wing）在美國計算機權(quán)威期刊《Communicatio-nsoftheACM》首次提出“計算思維（ComputationalThinking）”的概念。周教授將計算思維定義為運用計算機科學(xué)的基礎(chǔ)概念進(jìn)行問題求解、系統(tǒng)設(shè)計、以及人類行為理解等涵蓋計算機科學(xué)廣度的一系列思維活動。（2）計算思維代表著一種普遍的認(rèn)識和一類普適的技能，每一個人，而不僅僅是計算機科學(xué)領(lǐng)域的專業(yè)人員，其他各行各業(yè)的人都應(yīng)熱心于它的學(xué)習(xí)和運用。由于計算思維的核心之一便是算法思維，且算法思維也是計算機科學(xué)的精髓。（3）算法（Algorithm）是指在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則。算法是解題方案準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機制和規(guī)則。8.1.1算法基本概念算法和程序的區(qū)別：（1）程序是使用某種計算機編程語言所實現(xiàn)的算法結(jié)果，而算法則不一定需要計算機才能實現(xiàn)，算法的范圍比程序要大。（2）程序不一定滿足算法的有窮性。比如操作系統(tǒng)作為一個很大的程序，只要整個操作系統(tǒng)不被破壞，它將永遠(yuǎn)不會停止，即使沒有任務(wù)需要處理，它仍處于動態(tài)等待中。因此，操作系統(tǒng)不是一個算法。（3）程序中的指令必須是被計算機可執(zhí)行的，而算法中的指令則無此限制。8.1.2算法特征和設(shè)計要求一個設(shè)計良好的算法應(yīng)具有以下五個重要的特征：（1）有窮性：算法的有窮性是指算法必須在執(zhí)行有限個步驟之后停止，而不能無限制的一直執(zhí)行下去。（2）確定性：算法的每一個操作步驟必須要有確切的定義，而不能有含糊不明確性。（3）輸入：算法可以有0個或多個輸入，以描述運算對象的初始環(huán)境，其中的0個輸入是指算法沒有輸入數(shù)據(jù)，算法本身已經(jīng)確定其初始環(huán)境情況。（4）輸出：算法必須有輸出，且其輸出可是一個或多個，用以反映對輸入數(shù)據(jù)處理后的運算結(jié)果。（5）可行性：算法中所有的計算步驟都應(yīng)該能分解為基本的可執(zhí)行操作，即每個計算步驟都可以在有限的時間內(nèi)完成。該特性又稱有效性。8.1.2算法特征和設(shè)計要求算法的設(shè)計要求主要從以下五個方面來考慮：1．算法的時間復(fù)雜度要低算法的時間復(fù)雜度是指執(zhí)行算法全部操作步驟所需要的計算工作總量。O(1)<O(log2n)<O(n)<O(n2)<O(n3)<O(n!)<O(nn)2．算法的空間復(fù)雜度要低算法的空間復(fù)雜度是指算法在執(zhí)行過程中所需要消耗的內(nèi)存空間。3．算法的正確性要高算法的正確性是評價一個算法優(yōu)劣的最重要的標(biāo)準(zhǔn)，也是算法設(shè)計的根本所在。4．算法要有良好的可讀性算法的可讀性是指算法可供除算法設(shè)計者之外的其他人員閱讀和理解的容易程度。5．算法要有極佳的健壯性算法的健壯性是指算法對不合理數(shù)據(jù)輸入或其他異常情況的反應(yīng)能力和處理能力，也稱為容錯性。8.1.3算法表示方法算法可使用自然語言、偽代碼、流程圖等多種不同的方法來描述【例】已知全部學(xué)生成績均已及格，判斷學(xué)生成績是否優(yōu)秀（大于等于90分）。1．自然語言自然語言也就是人們?nèi)粘＝涣魇褂玫恼Z言，可以是漢語或英語或其它人類語言。用自然語言表示的算法通俗易懂，但文字冗長，容易出現(xiàn)歧義。算法描述：如果當(dāng)前需要判斷的學(xué)生成績大于或等于九十分，則該生的成績?yōu)閮?yōu)秀，否則為及格。2.偽代碼偽代碼是用介于自然語言和計算機語言之間的文字和符號來描述算法。8.1.3算法表示方法用英文和符號表示的偽代碼:1 if（score≥90）2 thenexcellent3 else4Pass3．流程圖

流程圖主要通過使用一些標(biāo)準(zhǔn)的符號來表示算法的一些執(zhí)行步驟和某些類型的動作，以圖形化的方式描述整個算法。其中的判斷決策用菱形框表示，具體活動用方框表示等。18.2.1蠻力法28.2.2階梯分段法38.2.3遞推法與遞歸法8.2基本算法設(shè)計方法8.2基本算法設(shè)計方法8.2.1蠻力法使用計算機進(jìn)行問題求解的最簡單的方法稱為蠻力法，又稱為窮舉法?；舅悸肥牵菏紫确治瞿繕?biāo)問題的解的特點，確定窮舉對象、窮舉范圍和判定條件，接下來針對整個解空間里面的所有值，一個個依次全部驗證是否是目標(biāo)問題的解。在蠻力法設(shè)計中，窮舉對象和范圍的選擇是非常重要的，它直接影響算法的時間復(fù)雜度。如求出班級所有學(xué)生某門課程的成績總和，就需要將學(xué)生成績一個一個的加起來，所有學(xué)生的成績都參與運算。8.2基本算法設(shè)計方法8.2.2階梯分段法在實際應(yīng)用中并不是所有的問題都是統(tǒng)一的處理方式，基本都需要分門別類的進(jìn)行處理，針對不同的問題應(yīng)用不同的處理方法。

比如判斷學(xué)生成績的好壞情況，除了優(yōu)秀和及格之外，還有良好，中等和不及格的情形.8.2基本算法設(shè)計方法8.2.3遞推法與遞歸法遞推法是一種利用問題本身所具有的遞推關(guān)系求解問題的方法。所謂遞推，就是從已知的初始條件開始，依據(jù)問題本身具有的某種遞推關(guān)系，依次推出問題的各個中間結(jié)果及最終結(jié)果。在實際問題中，內(nèi)涵的遞推關(guān)系需要經(jīng)過分析才能提取出來。如對于數(shù)的階乘從小到大的依次運算就屬于遞推法。由于整數(shù)N的階乘等于N和（N-1）階乘的乘積，即N！=N×（N-1）！。從初始條件0！=1開始，可以得出1！=1×0！=1×1=1，1！的求出之后，就可以得到2！=2×1！=2×1=2，然后3！=3×2！=3×2=6，…就這樣一直計算下去，后面的數(shù)的階乘將會從小到大依次被計算出來。8.2基本算法設(shè)計方法

遞歸法是直接或者間接地調(diào)用自身的算法。使用遞歸法求解的問題具有這樣的一些類似特征：首先求解的問題可以被分解成規(guī)模較小的問題，從這些小規(guī)模問題的解可方便地構(gòu)造出原來大問題的解，且原來的大問題和分解后的小問題都可以使用同一種策略來求解。特別地，當(dāng)求解問題的規(guī)模為1時，可直接求解。在此仍然以數(shù)的階乘為例，令函數(shù)f(n)表述變量n的階乘如下所示f(n)=n！=n×(n-1)！=n×f(n-1),n≥1.在式中有階乘函數(shù)f(x)在計算的過程中調(diào)用自身的情形。比如要計算6的階乘f(6)，依式（8-1）可得f(6)=6×f(5)，此時發(fā)現(xiàn)f(6)的計算過程用到了f(5)…18.3.1明確問題對象28.3.2分析問題本質(zhì)38.3.3確定實現(xiàn)步驟48.3.4算法流程求解8.3算法求解問題的過程8.3算法求解問題的過程8.3.1明確問題對象在分析問題對象之前，首先應(yīng)該制定一個使用算法求解問題的計劃方案，其中列出的內(nèi)容盡量詳實。接下來要熟悉所求解問題的應(yīng)用背景，最好向行業(yè)內(nèi)部人員或者最終用戶了解一些所求解的問題的特殊要求，與其他行業(yè)或應(yīng)用背景所不同的特征方面。然后將所求解的問題的應(yīng)用范圍限定在一定區(qū)域之內(nèi)，并以行業(yè)內(nèi)部人員或最終用戶的特殊要求加以約束，進(jìn)一步的限制應(yīng)用領(lǐng)域。8.3.2

分析問題本質(zhì)該階段的主要任務(wù)是把上一階段得到的所求解問題的主要功能，業(yè)務(wù)處理流程，初始需要輸入的數(shù)據(jù)，數(shù)據(jù)的中間處理結(jié)果以及最終的輸出結(jié)構(gòu)等內(nèi)容進(jìn)一步的深入的分析，明確其本質(zhì)內(nèi)容，將其從現(xiàn)實的應(yīng)用抽象到可用計算機處理的問題模型。在抽象成問題模型的基礎(chǔ)上，對初始的兩套算法實施方案進(jìn)行完善和細(xì)化。分析問題本質(zhì)階段最重要的兩項內(nèi)容分別是抽象和模型化。8.3算法求解問題的過程8.3.3確定實現(xiàn)步驟在對問題對象模型化的基礎(chǔ)上對問題模型進(jìn)行細(xì)化處理，分析其各功能模塊之間的邏輯關(guān)系和調(diào)用關(guān)系，并給出明確、清晰地表述，為后續(xù)算法的實現(xiàn)打下堅實的基礎(chǔ)。如模塊的功能說明,業(yè)務(wù)處理邏輯,限制條件,輸入輸出數(shù)據(jù)等。

8.3.4算法流程求解

使用算法流程求解問題對象的過程中，也主要是從宏觀和微觀兩方面進(jìn)行，給整個問題對象和細(xì)分的各個功能模塊都選擇相應(yīng)的比較適合的算法。當(dāng)然，在某個功能模塊規(guī)模較大或者業(yè)務(wù)流程復(fù)雜的情形下可對其進(jìn)一步細(xì)分成更小的模塊，對這些小的模塊也應(yīng)設(shè)計相應(yīng)的算法。

注意以下幾個方面：系統(tǒng)的角度；功能模塊；接口；測試用例；注釋；折衷方案18.4.1RAPTOR軟件環(huán)境28.4.2案例說明和分析38.4.3RAPTOR控制結(jié)構(gòu)48.4.4RAPTOR數(shù)組應(yīng)用58.4.5RAPTOR算法設(shè)計8.4算法設(shè)計軟件RAPTOR——案例9：學(xué)生成績分析8.4.1RAPTOR軟件環(huán)境8.4.1RAPTOR軟件環(huán)境RAPTOR（theRapidAlgorithmicPrototypingToolforOrderedReasoning），是一種可視化的程序設(shè)計軟件。字符輸出界面子圖或子程序卡調(diào)速滑塊初始圖樣圖形符號和指令變量顯示區(qū)8.4.1RAPTOR軟件環(huán)境8.4.1RAPTOR軟件環(huán)境RAPTOR常用數(shù)據(jù)類型①數(shù)值型：數(shù)值型數(shù)據(jù)是代表數(shù)量且能夠進(jìn)行數(shù)值運算的數(shù)據(jù)類型。這種類型的數(shù)據(jù)主要由數(shù)字、小數(shù)點、正負(fù)號組成，如-1.732，0，-9，80，3.1416和0.00168等。②字符串：字符串是由數(shù)字、字母、下劃線等組成的一串字符。通常以字符串的整體作為運算和操作對象，如“Hello，ComputerWorld！”和“065000”等。③字符型：字符型數(shù)據(jù)是不具計算能力的文字?jǐn)?shù)據(jù)類型。其中包括中文字符、英文字符、數(shù)字字符和其他ASCⅡ字符，如’V’，’6’和’@’等。8.4.1RAPTOR軟件環(huán)境使用RAPTOR進(jìn)行算法設(shè)計時對于變量的處理需要注意以下兩點：①所有變量在被引用前必須存在并被正確賦值。8.4.1RAPTOR軟件環(huán)境②變量類型由最初的賦值語句所賦予的數(shù)據(jù)類型來確定，在整個算法設(shè)計中所有的操作和賦值都應(yīng)該使用同一數(shù)據(jù)類型。8.4.1RAPTOR軟件環(huán)境常量名稱含義常量值pi圓周率3.1416e自然對數(shù)的底2.7183true/yes布爾值：真1false/no布爾值：假08.4.1RAPTOR軟件環(huán)境運算符功能描述舉例說明+加法運算he=80+90=170-減法運算cha=90-80=10*乘法運算ji=90*3=270/除法運算shang=170/2=85^乘方運算chengfang1=2^3=8**乘方運算chengfang2=2**3=8rem求余運算yushu1=9rem3=0mod求余運算yushu2=16mod7=28.4.1RAPTOR軟件環(huán)境運算符功能描述舉例說明sqrt求平方根gen=sqrt(9)=3log求e的對數(shù)duishu=log(10)=2.3026abs求絕對值jueduizhi=abs(-9.2)=9.2ceiling向上取整shangquzheng=ceiling(9.2)=10floor向下取整xiaquzheng=floor(9.2)=9sin正弦函數(shù)zhengxian=sin(pi/2)=1cos余弦函數(shù)yuxian=cos(pi/2)=0tan正切函數(shù)zhengqie=tan(pi/4)=1cot余切函數(shù)yuqie=cot(pi/4)=1arcsin反正弦函數(shù)fanzhengxian=arcsin(1)=1.5708arccos反余弦函數(shù)fanyuxian=arcos(0)=1.5708arctan反正切函數(shù)fanzhengqie=arctan(1，1)=0.7584arccot反余切函數(shù)fanyuqie=arccot(1，1)=0.7584random偽隨機數(shù)suijishu=random=0.67118.4.2案例說明和分析1、案例說明已知某個班級共52名學(xué)生的綜合測評成績，且該班所有學(xué)生的綜合測評成績均及格，分別求出該班綜合測評成績的最高分、最低分以及平均分，并統(tǒng)計該班的優(yōu)秀人數(shù)。其他：（1）所有學(xué)生的綜合測評成績均為整數(shù)。（2）綜合測評成績達(dá)到或超過九十分記為優(yōu)秀。8.4.2案例說明和分析2、案例分析運用8.3節(jié)使用算法求解問題的一般流程來加以分析，其中包括明確問題對象，分析問題本質(zhì)，確定實現(xiàn)步驟和算法流程求解四個階段（1）明確問題對象; （2）分析問題本質(zhì);（3）確定實現(xiàn)步驟; （4）算法流程求解：8.4.2案例說明和分析（1）明確問題對象首先明確問題對象是某班52名學(xué)生的綜合測評成績，要對這些成績進(jìn)行處理，最后得到其最高成績，最低成績和平均成績，并計算優(yōu)秀人數(shù)。注意：第一點，所有學(xué)生的綜合測評成績均及格，即都在六十分以上且包括六十分；第二點，綜合測評成績超過九十分的為優(yōu)秀；第三點，由于所有學(xué)生的綜合測評成績?yōu)檎麛?shù)，則最高成績和最低成績也為整數(shù)，平均成績不一定是整數(shù)，優(yōu)秀人數(shù)本身就隱含著整數(shù)的限制。初步方案:首先要獲得52名學(xué)生的綜合測評成績，范圍在六十分和一百分之間且包括六十分和一百分。然后依次比較所有成績得到最高和最低成績，將所有成績求和得平均成績，最后對所有的成績判斷其是否大于或等于九十分，統(tǒng)計大于或等于九十分的成績數(shù)目。8.4.2案例說明和分析（2）分析問題本質(zhì)制定初步方案后，對其進(jìn)行進(jìn)一步的深入分析，抽象成數(shù)學(xué)模型。首先將整個問題看成一個整體，對于問題整體而言，輸入數(shù)據(jù)是52個整數(shù)，且必須在60到100之間，經(jīng)過問題過程的處理，最后問題整體的輸出是52個整數(shù)的最大值、最小值和平均值以及超過或等于90的整數(shù)的個數(shù)。經(jīng)過上述分析，整個問題對象的輸入就是一組整數(shù)，可用score[52]表示，輸出的最大值、最小值、平均值和大于或等于90的整數(shù)個數(shù)分別用maxscore，minscore，average和num90表示，并且依據(jù)處理結(jié)果的不同可將整個問題功能劃分成五個模塊，模塊1獲得52個介于60和100之間的整數(shù)，模塊2要求出其最大值，模塊3要求出其最小值，模塊4要求出其平均值，模塊5要統(tǒng)計超過或等于90的整數(shù)個數(shù)。8.4.2案例說明和分析（3）確定實現(xiàn)步驟對于第一個功能模塊，需要給數(shù)組score[52]賦值，由于一共需要賦值52次，且都是相同的賦值操作，因而這里需要用到循環(huán)結(jié)構(gòu)，每次賦值的來源可以用RAPTOR的隨機函數(shù)random，但注意random只能產(chǎn)生0到1之間的小數(shù)，另由于數(shù)組元素中的值需要限制在60到100之間，此時可用“60+random*40”來實現(xiàn)，還需注意的一點是所有的數(shù)組元素都是整數(shù)，因而需要進(jìn)行下取整操作，最后可用floor（60+random*40）給一個數(shù)組元素賦值。8.4.2案例說明和分析對于第二個功能模塊，要求出數(shù)組score[52]中所有數(shù)組元素的最大值，其中可用的一個策略是，首先將數(shù)組的第一個元素score[1]賦值給maxscore，然后用maxscore依次和后面的score[2]、score[3]、…等相比較，如果當(dāng)前比較的數(shù)組元素score[i]的值比maxscore中的值要大，就把maxscore的值變成當(dāng)前數(shù)組元素score[i]的值，就這樣一直比較下去，一直比較到score[52]結(jié)束后，maxscore里面的值將是所有數(shù)組里面的最大值。（3）確定實現(xiàn)步驟8.4.2案例說明和分析對于第三個功能模塊，其思路和求最大值的思路一樣，也是首先將數(shù)組的第一個元素score[1]賦值給minscore，然后用minscore依次與后面的score[2]、score[3]、…等相比較，如果當(dāng)前比較的數(shù)組元素score[i]的值比minscore中的值要小，就把minscore的值變成當(dāng)前數(shù)組元素score[i]的值，就這樣一直比較下去，一直比較到score[52]結(jié)束后，minscore里面的值將是所有數(shù)組里面的最小值。（3）確定實現(xiàn)步驟8.4.2案例說明和分析對于第四個功能模塊，要求其平均值，就應(yīng)該將所有的數(shù)組元素全部加起來求和，然后除以52，就會得到，在此可用引入一個表示和的變量he，將0先賦值給he，接著依次計算he=he+score[i]，結(jié)合循環(huán)結(jié)構(gòu)令i逐步從1增加到52，則全部的數(shù)組元素都加入變量he中，最后可得平均成績average=he/52。（3）確定實現(xiàn)步驟8.4.2案例說明和分析

對于最后一個功能模塊，要求統(tǒng)計超過或等于90的數(shù)組元素的個數(shù)num90，首先令num90的值為0，接下來要結(jié)合循環(huán)結(jié)構(gòu)，令循環(huán)變量i依次從1逐步增加到52，將每一個數(shù)組元素提出來判斷score[i]≥90是否成立，如果成立則將num90的數(shù)值加1，即num90=num90+1,則循環(huán)結(jié)構(gòu)內(nèi)部還應(yīng)有一個選擇結(jié)構(gòu)，等全部的數(shù)組元素判斷完成，則num90的數(shù)值將是數(shù)組中超過或者等于90的數(shù)組元素個數(shù)。（3）確定實現(xiàn)步驟8.4.2案例說明和分析對于五個不同的功能模塊，分別使用偽代碼實現(xiàn)的算法流程如下所示。（4）算法流程求解①獲得數(shù)據(jù)1數(shù)組元素賦值score[52]=02循環(huán)變量i賦值i=13while（i≤52）4score[i]=floor（60+random*40）;5循環(huán)變量i=i+16endwhile8.4.2案例說明和分析②求最大值③求最小值1maxscore賦值為score[1]2循環(huán)變量i賦值i=13while（i≤52）4if（score[i]>maxscore）

maxscore=score[i]5endif6循環(huán)變量i=i+17endwhile8輸出maxscore1minscore賦值為score[1]2循環(huán)變量i賦值i=13while（i≤52）4if（score[i]<minscore）

minscore=score[i]5endif6循環(huán)變量i=i+17endwhile8輸出minscore8.4.2案例說明和分析④求平均值⑤統(tǒng)計優(yōu)秀個數(shù)1變量he賦值he=02循環(huán)變量i賦值i=13while（i≤52）4he=he+score[i]5循環(huán)變量i=i+16endwhile7平均值average=he/528輸出average1變量num90賦值num90=02循環(huán)變量i賦值i=13while（i≤52）4if（score[i]≥90）num90=num90+15endif6循環(huán)變量i=i+17endwhile8輸出num908.4.3RAPTOR控制結(jié)構(gòu)1．順序結(jié)構(gòu)順序結(jié)構(gòu)是最簡單的控制結(jié)構(gòu)，其中按照語句的先后順序來逐個執(zhí)行，如右圖所示。程序執(zhí)行時將從最初的Start開始，逐個依據(jù)箭頭的方向，一直執(zhí)行到結(jié)束End語句。8.4.3RAPTOR控制結(jié)構(gòu)2．選擇結(jié)構(gòu)選擇結(jié)構(gòu)是依據(jù)一定的判斷條件，有選擇的執(zhí)行算法程序中的語句。其并不像順序結(jié)構(gòu)那樣將算法程序中的