大學(xué)計(jì)算機(jī)基礎(chǔ)（第六版）課件 10 算法基礎(chǔ)與程序設(shè)計(jì)

第10章算法基礎(chǔ)與程序設(shè)計(jì)01問(wèn)題求解過(guò)程02算法基礎(chǔ)03程序設(shè)計(jì)基礎(chǔ)Contents目錄01問(wèn)題求解過(guò)程介紹用計(jì)算機(jī)求解問(wèn)題的基本過(guò)程問(wèn)題求解過(guò)程分析問(wèn)題建立模型設(shè)計(jì)算法編寫程序調(diào)試測(cè)試程序圖10-1問(wèn)題求解過(guò)程圖即確定計(jì)算機(jī)要做什么,實(shí)現(xiàn)自然語(yǔ)言的邏輯建模。即將原始問(wèn)題轉(zhuǎn)化為數(shù)學(xué)模型。即形式化地描述解決問(wèn)題的途徑和方法。即將算法翻譯成計(jì)算機(jī)程序。即發(fā)現(xiàn)和修改程序運(yùn)行過(guò)程中存在的錯(cuò)誤。問(wèn)題某商場(chǎng)銷售一批襯衫，平均每天可出售30件，每件盈利50元，為擴(kuò)大銷售，增加盈利，盡快減少庫(kù)存，商場(chǎng)決定降價(jià)，如果每件降1元，商場(chǎng)平均每天可多賣2件，若商場(chǎng)平均每天要盈利2100元，問(wèn)襯衫降價(jià)多少元？問(wèn)題求解過(guò)程舉例1．分析問(wèn)題已知：平均每天可出售30件，每件盈利50元，如果每件降1元，商場(chǎng)平均每天可多賣2件，商場(chǎng)平均每天要盈利2100元。目標(biāo)：盡快減少庫(kù)存，計(jì)算每件襯衫降價(jià)多少元。計(jì)算邏輯：盈利=單件盈利*銷售數(shù)量2．建立模型假設(shè)：每件襯衫降價(jià)x元。計(jì)算公式：2100=（50-x)*(30+2*x)整理公式：x2-35x+300=0數(shù)學(xué)模型：求一元二次方程ax2+bx+c=0的根。3．設(shè)計(jì)算法begininputa,b,c//輸入a,b,cx1,x2←0//變量賦初值if(b2-4ac>=0){x1=(-b+sqrt(b2-4ac))/2ax2=(-b-sqrt(b2-4ac))/2a}outputx1,x2//輸出根結(jié)果end4．編寫程序intmain(){floata,b,c,x1=0,x2=0;cin>>a>>b>>c;if(b*b-4*a*c>=0){x1=(-b+sqrt(b*b-4*a*c))/2*a;x2=(-b-sqrt(b*b-4*a*c))/2*a;}cout<<x1<<””<<x2;}5．調(diào)試測(cè)試對(duì)于程序進(jìn)行測(cè)試，看看運(yùn)行結(jié)果是否符合預(yù)先的期望，如果不符合，要進(jìn)行判斷，找出問(wèn)題出現(xiàn)的地方，對(duì)算法或程序進(jìn)行修正，直到得到正確的結(jié)果。由于商場(chǎng)要盡快減少庫(kù)存，所以降價(jià)20元是最佳選擇。02算法基礎(chǔ)介紹有關(guān)算法的基本知識(shí)，并對(duì)常見的算法進(jìn)行舉例01算法的概念02算法的特性和評(píng)價(jià)03算法的三種結(jié)構(gòu)Contents目錄04算法的表示05算法舉例簡(jiǎn)單地說(shuō)，算法就是解決問(wèn)題的一系列步驟。廣義地說(shuō)，為解決問(wèn)題而采用的方法和步驟就是算法。算法是程序設(shè)計(jì)的基礎(chǔ)，算法的質(zhì)量直接影響程序運(yùn)行的效率。算法是求解問(wèn)題步驟的有序集合，它能夠產(chǎn)生結(jié)果并在有限時(shí)間內(nèi)結(jié)束。1

算法的概念舉一個(gè)簡(jiǎn)單的算法例子，假設(shè)求兩個(gè)自然數(shù)m和n的最大公約數(shù)，通常使用輾轉(zhuǎn)相除的歐幾里得算法，算法描述如下:①輸入兩數(shù)m、n。②m除以n得到余數(shù)r。③若r=0，則n即為最大公約數(shù)，算法結(jié)束；否則繼續(xù)進(jìn)行下一步。④令m←n，n←r，轉(zhuǎn)到第②步?！毒耪滤阈g(shù)》是我國(guó)古代最早的算學(xué)著作，以算法為主要內(nèi)容，全書采用問(wèn)題集的形式，收有246個(gè)與生產(chǎn)、生活實(shí)踐有聯(lián)系的應(yīng)用問(wèn)題，其中每道題有問(wèn)(題目)、答(答案)、術(shù)(解題的步驟)，有的是一題一術(shù)，有的是多題一術(shù)或一題多術(shù)。這些問(wèn)題依照性質(zhì)和解法分別隸屬于方田、粟米、衰(cuī)分、少?gòu)V、商功、均輸、盈不足、方程及勾股，共九章。《九章算術(shù)》對(duì)中國(guó)古代數(shù)學(xué)發(fā)展起了承前啟后的作用，是世界古代數(shù)學(xué)名著之一，書中分?jǐn)?shù)解算方法、聯(lián)立一次方程解法、負(fù)數(shù)等，當(dāng)時(shí)在世界上都屬于杰出的研究成果。民族之光-九章算術(shù)民族之光-九章算術(shù)2020年12月4日，中國(guó)科學(xué)技術(shù)大學(xué)宣布該校潘建偉等人成功構(gòu)建76個(gè)光子的量子計(jì)算原型機(jī)，該原型機(jī)的名字"九章"，意為紀(jì)念中國(guó)古代最早的數(shù)學(xué)專著《九章算術(shù)》。民族之光-九章算術(shù)一般地，算法應(yīng)該具有以下特性。1．確定性：一個(gè)算法中的每一個(gè)步驟必須是精確的定義、無(wú)二義性，不會(huì)使編程者對(duì)算法中的描述產(chǎn)生不同的理解。2．有窮性：一個(gè)算法必須在執(zhí)行有窮步后結(jié)束，每一步必須在有窮的時(shí)間內(nèi)完成。3．可行性：算法描述的步驟在計(jì)算機(jī)上是可行的，能在一個(gè)合理的范圍內(nèi)有效地執(zhí)行，并應(yīng)能得到一個(gè)明確的結(jié)果。4．輸入：一般有零個(gè)或多個(gè)輸入值。5．輸出：一個(gè)算法的執(zhí)行過(guò)程中或結(jié)束后要有輸出結(jié)果，或者產(chǎn)生相應(yīng)的動(dòng)作指令。2

算法的特性和評(píng)價(jià)通?？梢詮囊韵聨讉€(gè)方面來(lái)評(píng)價(jià)算法的優(yōu)劣。1．算法的正確性算法正確性是指算法應(yīng)該滿足具體問(wèn)題的需求。其中“正確”的含義大體上可以分為4個(gè)層次。（1）算法所對(duì)應(yīng)的程序沒(méi)有語(yǔ)法錯(cuò)誤。（2）算法所對(duì)應(yīng)的程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果。（3）算法所對(duì)應(yīng)的程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得到滿足要求的結(jié)果。（4）算法所對(duì)應(yīng)的程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足要求的結(jié)果。達(dá)到第4層含義下的正確性是極為困難的，不少大型軟件在使用多年后，仍然還能發(fā)現(xiàn)其中的錯(cuò)誤。一般情況下，以第3層含義的正確性作為衡量一個(gè)算法是否正確的標(biāo)準(zhǔn)。2

算法的特性和評(píng)價(jià)2．可讀性

一個(gè)好的算法首先應(yīng)該便于人們理解和相互交流，其次才是機(jī)器可執(zhí)行。可讀性好的算法有助于人對(duì)算法的理解，難懂的算法容易隱藏錯(cuò)誤且難于調(diào)試和修改。3．健壯性

作為一個(gè)好的算法，當(dāng)輸入非法數(shù)據(jù)時(shí)，也能適當(dāng)?shù)刈龀稣_反應(yīng)或進(jìn)行相應(yīng)的處理，而不會(huì)產(chǎn)生一些莫名其妙的輸出結(jié)果，或者毫無(wú)反應(yīng)甚至崩潰。2

算法的特性和評(píng)價(jià)4．高效率和低存儲(chǔ)量

算法的效率通常是指算法的執(zhí)行時(shí)間，即根據(jù)算法編寫的程序在運(yùn)行過(guò)程中，從開始到結(jié)束所需要的時(shí)間。對(duì)于一個(gè)具體問(wèn)題的解決通?？梢杂卸鄠€(gè)算法，執(zhí)行時(shí)間短的算法效率比較高。所謂的存儲(chǔ)量是指算法在執(zhí)行過(guò)程中對(duì)存儲(chǔ)空間的需求。一個(gè)算法對(duì)應(yīng)的程序在執(zhí)行時(shí)必須加載到計(jì)算機(jī)的內(nèi)存中，程序本身、程序中用到的變量都要占用內(nèi)存空間，除了這些內(nèi)存消耗外，程序在執(zhí)行過(guò)程中還可能動(dòng)態(tài)地申請(qǐng)額外的內(nèi)存空間。通常情況下，我們根據(jù)算法運(yùn)行時(shí)所需要的時(shí)間和空間，即算法運(yùn)行的時(shí)間復(fù)雜度和空間復(fù)雜度來(lái)評(píng)價(jià)算法的優(yōu)劣。2

算法的特性和評(píng)價(jià)結(jié)構(gòu)化程序設(shè)計(jì)思想包含兩個(gè)方面的內(nèi)容，一是程序由三種基本的邏輯結(jié)構(gòu)組成，二是程序設(shè)計(jì)要自頂向下進(jìn)行。三種結(jié)構(gòu)分別是順序、分支和循環(huán)。其中分支也稱選擇或判斷。事實(shí)證明，使用這三種結(jié)構(gòu)可以使得程序或算法很容易地被理解。結(jié)構(gòu)化程序要求任何程序只有一個(gè)入口或出口，程序中沒(méi)有執(zhí)行不到的語(yǔ)句，且沒(méi)有無(wú)限循環(huán)發(fā)生。算法是程序的基礎(chǔ)，程序是算法的實(shí)現(xiàn)。因此程序的邏輯結(jié)構(gòu)也就是進(jìn)行算法設(shè)計(jì)的三種結(jié)構(gòu)。3

算法的三種結(jié)構(gòu)1．順序結(jié)構(gòu)

順序結(jié)構(gòu)是算法設(shè)計(jì)中最簡(jiǎn)單的一種結(jié)構(gòu)，它使求解問(wèn)題的過(guò)程按照順序由上至下進(jìn)行。如圖10-2所示就是一個(gè)順序結(jié)構(gòu)的表示，其中有兩個(gè)框代表算法的步驟，執(zhí)行了A后接下來(lái)執(zhí)行B指定的操作。

事實(shí)上，無(wú)論哪一類算法，它的主結(jié)構(gòu)都是順序結(jié)構(gòu)的，從一個(gè)入口開始，到一個(gè)出口結(jié)束。3

算法的三種結(jié)構(gòu)3

算法的三種結(jié)構(gòu)AB圖10-2順序結(jié)構(gòu)2．分支結(jié)構(gòu)

分支結(jié)構(gòu)也叫條件結(jié)構(gòu)、選擇結(jié)構(gòu)或判斷結(jié)構(gòu)，在算法設(shè)計(jì)過(guò)程中，可能會(huì)出現(xiàn)判斷，如判斷某門功課的成績(jī)，大于或等于60分為“及格”，否則為“不及格”，這時(shí)就必須采用分支結(jié)構(gòu)實(shí)現(xiàn)。如圖10-3所示為分支結(jié)構(gòu)的一般表示。若條件成立，則執(zhí)行分支A，否則執(zhí)行分支B。

如果在A或B中，又需要根據(jù)判斷設(shè)計(jì)分支結(jié)構(gòu)，就會(huì)出現(xiàn)嵌套的分支結(jié)構(gòu)（多分支結(jié)構(gòu)）。3

算法的三種結(jié)構(gòu)3

算法的三種結(jié)構(gòu)條件AB成立不成立圖10-3分支結(jié)構(gòu)

3．循環(huán)結(jié)構(gòu)

在算法設(shè)計(jì)過(guò)程中可能會(huì)出現(xiàn)重復(fù)執(zhí)行一組工作步驟的情況，我們可以通過(guò)循環(huán)結(jié)構(gòu)來(lái)控制。有兩類循環(huán)結(jié)構(gòu)：當(dāng)型（while）循環(huán)結(jié)構(gòu)和直到型（until）循環(huán)結(jié)構(gòu)。當(dāng)型循環(huán)的原理如圖10-4所示，當(dāng)條件成立時(shí)執(zhí)行A，執(zhí)行完A后再判斷條件是否成立，若成立則繼續(xù)執(zhí)行A，如此反復(fù)，直至條件不成立才結(jié)束循環(huán)。

直到型循環(huán)的原理如圖10-5所示，先執(zhí)行A，再判斷條件是否成立，如果條件不成立則繼續(xù)執(zhí)行A，如此反復(fù)，直至條件成立才結(jié)束循環(huán)。

這兩種循環(huán)結(jié)構(gòu)的區(qū)別在于循環(huán)體A的執(zhí)行順序：對(duì)while結(jié)構(gòu)，如果一開始循環(huán)條件就不成立，則A將不會(huì)被執(zhí)行；而對(duì)until結(jié)構(gòu)，無(wú)論循環(huán)條件成立與否，A至少被執(zhí)行一次。3

算法的三種結(jié)構(gòu)3

算法的三種結(jié)構(gòu)A圖10-5直到型循環(huán)結(jié)構(gòu)條件A成立不成立圖10-4當(dāng)型循環(huán)結(jié)構(gòu)條件成立不成立

算法的表示是為了把算法以某種形式加以描述，同一個(gè)算法可以通過(guò)多種形式來(lái)表達(dá)，常用的有自然語(yǔ)言、傳統(tǒng)流程圖、N-S流程圖、偽代碼、計(jì)算機(jī)語(yǔ)言等。1．自然語(yǔ)言

自然語(yǔ)言是人們?nèi)粘Ｊ褂玫恼Z(yǔ)言，是人類交流信息的工具，因此最常用的表達(dá)問(wèn)題的方法也就是自然語(yǔ)言。10.2.1節(jié)中的算法步驟就是用自然語(yǔ)言方式描述的。用自然語(yǔ)言表示，通俗易懂，但存在以下缺陷：

(1)易產(chǎn)生歧義性，往往根據(jù)上下文才能判別其含義，不太嚴(yán)格。

(2)語(yǔ)句比較煩瑣、文字冗長(zhǎng)，并且很難清楚地表達(dá)算法的邏輯流程，尤其當(dāng)描述有選擇、循環(huán)結(jié)構(gòu)的算法時(shí)，不太方便和直觀。

所以，除了簡(jiǎn)單的問(wèn)題以外，一般不用自然語(yǔ)言描述算法。對(duì)于一些需要有背景知識(shí)進(jìn)行推理的表達(dá)，也許自然語(yǔ)言是最好的選擇。4

算法的表示2．流程圖

流程圖是算法表示的常用的方法，它采用一些圖框、線條以及文字說(shuō)明來(lái)形象、直觀地描述從算法開始到結(jié)束的流程，而不考慮其實(shí)現(xiàn)過(guò)程的細(xì)節(jié)。美國(guó)國(guó)家標(biāo)準(zhǔn)化協(xié)會(huì)規(guī)定了一些常用的流程圖符號(hào)，如表10-1所示。4

算法的表示4

算法的表示符號(hào)名稱圖形功能起止框

表示算法的開始和結(jié)束輸入/輸出框

表示算法的輸入輸出操作處理框

表示算法中的各種處理操作判斷框

表示算法中的條件判斷操作流程線

表示算法的執(zhí)行方向連接點(diǎn)

表示流程圖的延續(xù)4

算法的表示3．N-S流程圖

N-S圖是美國(guó)學(xué)者I.Nassi和B.Shneideman提出的一種新的流程圖形式，并以他們的姓名的第一個(gè)字母命名。N-S圖中去掉了傳統(tǒng)流程圖中帶箭頭的流程線，全部算法以一個(gè)大的矩形框表示，該框內(nèi)還可以嵌套一些從屬于它的小矩形框，適合結(jié)構(gòu)化程序設(shè)計(jì)。圖10-7表示了結(jié)構(gòu)化程序設(shè)計(jì)的三種基本結(jié)構(gòu)的N-S圖。4

算法的表示ABT條件FAB當(dāng)條件成立AA（a）順序結(jié)構(gòu)（b）分支結(jié)構(gòu)（c）當(dāng)型循環(huán)結(jié)構(gòu)（d）直到型循環(huán)結(jié)構(gòu)直到條件成立4．偽代碼

偽代碼是一種算法的表達(dá)方法，產(chǎn)生于20世紀(jì)70年代，它是在程序開發(fā)過(guò)程中表達(dá)算法的一種非正式的符號(hào)系統(tǒng)，它不考慮實(shí)現(xiàn)算法的計(jì)算機(jī)語(yǔ)言，是一種與程序設(shè)計(jì)過(guò)程一致的、表達(dá)簡(jiǎn)明扼要的語(yǔ)義結(jié)構(gòu)的方法。4

算法的表示偽代碼使用介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)來(lái)描述算法，有如下簡(jiǎn)單約定：(1)每個(gè)算法用Begin開始、End結(jié)束；若僅表示部分實(shí)現(xiàn)代碼可省略。(2)每一條指令占一行，指令后不跟任何符號(hào)。(3)“//”標(biāo)志表示注釋的開始，一直到行尾。(4)算法的輸入輸出以Input/Output后加參數(shù)表的形式表示。(5)用“←”表示賦值。(6)用縮進(jìn)表示代碼塊結(jié)構(gòu)，包括while和for循環(huán)、if分支判斷等；塊中多條語(yǔ)句用一對(duì){}括起來(lái)。(7)數(shù)組形式：數(shù)組名[下界……上界]；數(shù)組元素：數(shù)組名[序號(hào)]。(8)一些函數(shù)調(diào)用或處理簡(jiǎn)單任務(wù)可以用一句自然語(yǔ)言代替。4

算法的表示10.2.1節(jié)中的關(guān)于求最大公約數(shù)的算法可以采用如下的偽代碼方式進(jìn)行描述，該算法描述采用當(dāng)型循環(huán)結(jié)構(gòu)。4

算法的表示BeginInputm,n//輸入m和n使m>nr←0//變量賦初值r←m/nwhile(r>0){m←nn←rr←m/n}Outputn//輸出最大公約數(shù)End

設(shè)計(jì)一個(gè)問(wèn)題的求解方案需要經(jīng)過(guò)理解問(wèn)題、找出重點(diǎn)、設(shè)計(jì)方案、執(zhí)行方案、在執(zhí)行過(guò)程中修正設(shè)計(jì)方案的過(guò)程，還需要掌握更多的數(shù)學(xué)知識(shí)，包括圖論、組合學(xué)等。

下面舉一個(gè)“求100～1000以內(nèi)的水仙花數(shù)”的例子，來(lái)說(shuō)明如何理解問(wèn)題并設(shè)計(jì)方案。

所謂的水仙花數(shù)是，一個(gè)n位的正整數(shù)的每一位數(shù)的n次冪之和等于這個(gè)數(shù)本身。例如，153=13+53+33，因此153是水仙花數(shù)。100～1000之間的水仙花數(shù)還有370，371和407等。理解這個(gè)問(wèn)題不難，但要設(shè)計(jì)能夠讓計(jì)算機(jī)進(jìn)行計(jì)算的算法就需要解決以下幾個(gè)問(wèn)題：

(1)要遍歷全部的3位正整數(shù)；

(2)分解每一個(gè)3位正整數(shù)，分別得到該正整數(shù)的3個(gè)整數(shù)位；

(3)檢查它們的立方和是否與原數(shù)相等，如果相等，則是水仙花數(shù)。5

算法舉例1．基本算法

算法有很多，同一個(gè)問(wèn)題也有多種算法，例如，最為常見的排序算法，就有選擇法、冒泡法、快速排序、堆排序、希爾排序、桶排序、合并排序、計(jì)數(shù)排序、基數(shù)排序等。其原因是，對(duì)不同的數(shù)據(jù)類型及數(shù)據(jù)表達(dá)，一種方法是有效的，但另一種方法則效果不佳。（1）求和

求和是學(xué)習(xí)計(jì)算機(jī)程序設(shè)計(jì)首先遇到的算法問(wèn)題。適合計(jì)算機(jī)求和的算法是在循環(huán)中使用加法求和。例如，計(jì)算n～m之間的整數(shù)之和。

假設(shè)使用sum存放求和結(jié)果，使用i作為循環(huán)控制變量，則求和算法可以通過(guò)以下偽代碼方式進(jìn)行描述。5

算法舉例5

算法舉例Beginsum←0//定義求和結(jié)果變量，初始值為0i←n//將n賦值給循環(huán)控制變量iwhilei<=mdo{sum←sum+i//將循環(huán)控制變量i的值累加到sum中i←i+1//準(zhǔn)備下一個(gè)數(shù)}End

這個(gè)算法的循環(huán)過(guò)程完成兩個(gè)操作，將一個(gè)整數(shù)加到sum中，并準(zhǔn)備下一次循環(huán)操作。其中，i既是加數(shù)，也是循環(huán)控制變量。（2）累積

累積是將一組數(shù)連續(xù)相乘求其積，類似于求和計(jì)算，把求和計(jì)算的加號(hào)變?yōu)槌颂?hào)即可。典型的例子就是計(jì)算整數(shù)N的階乘。（3）求最大值和最小值

判斷兩個(gè)數(shù)的大小的算法是許多算法的基礎(chǔ)，求最大值和最小值的算法，使用分支結(jié)構(gòu)就可以實(shí)現(xiàn)，這里以求最大值為例。5

算法舉例BeginInputa,bmax←aifmax<bmax←boutputmaxEndBeginInputa,bmax←aifa>bmax←aelsemax←boutputmaxEnd（4）求數(shù)的位數(shù)

給定一個(gè)整數(shù)n，如何計(jì)算得到它的位數(shù)呢？可以考慮的算法是，將該數(shù)循環(huán)除以10直到結(jié)果為0結(jié)束，把循環(huán)次數(shù)記錄下來(lái)就是這個(gè)數(shù)的位數(shù)。5

算法舉例Begincount←1//count為計(jì)數(shù)變量，初值為1inputnn←n/10whilen≠0do{count←count+1n←n/10//將n除以10的結(jié)果重新賦值給n}outputcountEnd2．遞歸

為了獲得大型問(wèn)題的解決方案，常用的方法就是把該大型問(wèn)題化解為一個(gè)或幾個(gè)相似的、規(guī)模更小的子問(wèn)題。對(duì)子問(wèn)題可以采用同樣的方法。這樣，一直遞歸下去，直到子問(wèn)題足夠小，成為一個(gè)基本情況，這時(shí)可以直接給出子問(wèn)題的解答。

遞歸是算法的自我調(diào)用。有關(guān)求N的階乘的計(jì)算就是最典型的遞歸結(jié)構(gòu)。為了說(shuō)明遞歸算法的結(jié)構(gòu)，把這個(gè)問(wèn)題從定義的角度進(jìn)行展開。

假設(shè)階乘函數(shù)的定義為：5

算法舉例遞歸算法f(5)=5×f(4)f(4)=4×f(3)f(3)=3×f(2)f(2)=2×f(1)f(1)=1×f(0)f(0)=1f(1)=1×1f(2)=2×1f(3)=3×2f(4)=4×6f(5)=5×24圖10-8計(jì)算階乘的遞歸步驟

遞歸是一個(gè)重復(fù)調(diào)用的過(guò)程，我們把它對(duì)自身的調(diào)用看作是產(chǎn)生了一個(gè)副本，每次調(diào)用都有一個(gè)副本產(chǎn)生并等待處理，當(dāng)結(jié)束條件滿足時(shí)將停止產(chǎn)生副本。如圖10-8所示的遞歸過(guò)程的結(jié)束條件是f(0)=1，當(dāng)遞歸進(jìn)入這個(gè)步驟后，副本將停止產(chǎn)生，算法將處于等待狀態(tài)的副本按照后進(jìn)先出（FILO）的原則依次處理（返回），最后得到運(yùn)算結(jié)果。

每個(gè)遞歸過(guò)程都包含如下兩個(gè)步驟：

(1)定義一個(gè)能夠不使用遞歸方法就可以直接處理的基本情況作為出口，即定義一個(gè)終止遞歸的條件；

(2)不斷調(diào)用遞歸方法本身，將一種特殊的情況化解為規(guī)模較小的情況，持續(xù)下去，最終到達(dá)對(duì)基本情況的求解。5

算法舉例上面的計(jì)算階乘的示例，可以寫成下面的f()函數(shù)：intf(intn){if(n==0)return1;elsereturnn*f(n-1);}5

算法舉例4．排序

排序是是將一組原始數(shù)據(jù)按照遞增或遞減的規(guī)律進(jìn)行重新排列的算法。常用排序算法分類參見10.2.5節(jié)，這里介紹選擇排序。選擇排序算法的主要思想是，掃描數(shù)據(jù)序列，找到最小的數(shù)據(jù)，將該數(shù)據(jù)交換到序列最前面的位置，然后對(duì)其余數(shù)據(jù)序列重復(fù)前面的步驟直到數(shù)據(jù)全部排序?yàn)橹梗J(rèn)從小到大排序）。

對(duì)一組數(shù)的排序的算法涉及數(shù)據(jù)形式和組織結(jié)構(gòu)，為簡(jiǎn)單起見，我們舉例說(shuō)明。假設(shè)有一組6個(gè)數(shù)：12，6，1，15，3，19，現(xiàn)在希望將該數(shù)組中的數(shù)據(jù)采用選擇排序方法從小到大排列，圖10-9演示了6個(gè)數(shù)的排序過(guò)程，圖中的陰影方框表示未排序數(shù)據(jù)。5

算法舉例圖10-9選擇排序算法排序過(guò)程選擇排序算法的偽代碼如下：selectionSort(arrayA){for(inti=0;i<A.length-1;i++){

//外循環(huán)變量i，控制循環(huán)次數(shù)，掃描n-1次找最小數(shù)并交換到數(shù)組前方intmin=ifor(intj=i+1;j<A.length;j++){

//內(nèi)循環(huán)找最小數(shù)的位置if(A[j]<A[min]){min=j}}5

算法舉例if(i!=min){

//最小數(shù)與序列最前面位置i的元素A[i]交換intswap=A[i]A[i]=A[min]A[min]=swap}}}

那么對(duì)n個(gè)數(shù)的排序需要n-1次掃描過(guò)程：第一次掃描過(guò)程將比較n個(gè)數(shù)，得到最小的那個(gè)數(shù)的位置，和第一個(gè)數(shù)的位置互換，比較次數(shù)為n-1次；第二次掃描將從第二個(gè)數(shù)開始，得到次小的數(shù)與第二個(gè)數(shù)的位置互換，比較次數(shù)為n-2次；最后一次比較最后的兩個(gè)數(shù)，比較次數(shù)為1次?？梢缘玫?，對(duì)n個(gè)數(shù)選擇法排序的比較次數(shù)為：（n-1）+（n-2）+……+2+1，即n（n-1）/2次，如圖10-9所示6個(gè)數(shù)的排序的比較次數(shù)為15次。

以算法的概念，掃描過(guò)程為外循環(huán)，掃描次數(shù)為n-1次，每次掃描的過(guò)程為內(nèi)循環(huán)，每次掃描中進(jìn)行比較的次數(shù)為n-i次，i為外循環(huán)的次數(shù)。每次比較得到的結(jié)果是記錄較小的那個(gè)數(shù)的位置，內(nèi)循環(huán)結(jié)束，再進(jìn)行位置的互換。5

算法舉例5．查找

在計(jì)算機(jī)科學(xué)中，另外一種常用的算法是查找，即把一個(gè)特定的數(shù)據(jù)從數(shù)組或序列中找到并提供它所在的位置，即索引（下標(biāo)），如圖10-10所示。

對(duì)于數(shù)組或序列數(shù)據(jù)的查找有兩種基本方法：順序查找和折半查找。數(shù)組或序列無(wú)序或有序，順序查找都可實(shí)現(xiàn)，而折半查找必須使用在已經(jīng)排序的數(shù)組或序列中。

順序查找從列表的第一個(gè)數(shù)據(jù)開始，當(dāng)給定的數(shù)據(jù)與表中的數(shù)據(jù)匹配時(shí)，查找過(guò)程結(jié)束，給出這個(gè)數(shù)據(jù)所在數(shù)組或序列的位置。

5

算法舉例12611531917

對(duì)數(shù)據(jù)量較小的數(shù)組或序列，順序查找是沒(méi)有什么問(wèn)題的。對(duì)大量數(shù)據(jù)的數(shù)組或序列，這個(gè)算法的查找速度就變得非常慢了。如果數(shù)組或序列是無(wú)序的，則順序查找是唯一的算法。對(duì)已經(jīng)排序了的數(shù)組或序列可以使用折半查找。當(dāng)然，無(wú)序的數(shù)組或序列也可以先進(jìn)行排序再使用折半查找。

折半查找算法是指在在一個(gè)有序數(shù)據(jù)集中（假設(shè)數(shù)據(jù)元素遞增排列），將搜索項(xiàng)與數(shù)據(jù)集的中間位置的數(shù)據(jù)元素進(jìn)行比較，如果搜索項(xiàng)小于中間位置的數(shù)據(jù)元素，則只搜索數(shù)據(jù)集的前半部分；否則，搜索數(shù)據(jù)集的后半部分。

如果搜索項(xiàng)等于中間位置的數(shù)據(jù)元素，則返回該中間位置的數(shù)據(jù)元素的地址，搜索成功結(jié)束。折半查找算法的偽代碼如下：5

算法舉例FuncbinarySearch(list[0..N-1]，DataElementsearchItem)//參數(shù)為需要查找的數(shù)據(jù)，返回?cái)?shù)據(jù)位置{

intleft=0;//定義查找范圍的左邊界

intright=length-1;//定義查找范圍的右邊界

intmid=-1;//定義查找范圍的中間位置

booleanfound=false;//定義查找結(jié)果標(biāo)志

while(left<=rightand!found)//如果左邊界小于等于右邊界且未找到，就繼續(xù)折半

{

mid=(left+right)/2;//以折半方式計(jì)算新的查找范圍中間位置

if(list[mid]=searchItem)//如果中間位置的值等于要查找的值，就設(shè)置為已找到

found=true;5

算法舉例5

算法舉例else

if(list[mid]>searchItem)//如果中間位置的值大于要查找的數(shù)據(jù)，則重新設(shè)置查找范圍的右邊界

right=mid+1;

else//如果中間位置的值小于要查找的數(shù)據(jù)，則重新設(shè)置查找范圍的左邊界

left=mid+1;}if(found)//如果查找結(jié)果標(biāo)志為已找到，則返回中間位置，否則返回-1returnmid;elsereturn-1;}如果采用遞歸方式，折半查找算法的偽代碼如下：binarySearch(list[0..N-1],searchValue,left,right){//參數(shù)為數(shù)據(jù)序列、要查找的值、左邊界、右邊界

if(right<left)//如果右邊界小于左邊界，說(shuō)明未找到

return-1;

mid=left+((right-left)/2);//計(jì)算查找范圍的中間位置

if(list[mid]>searchValue)

//如果中間位置的值大于要查找的值，則遞歸查找左半部分

binarySearch(list,searchValue,left,mid-1);5

算法舉例elseif(list[mid]<searchValue)

//如果中間位置的值小于要查找的值，則遞歸查找右半部分

binarySearch(list,searchValue,mid+1,right);

else

returnmid;

}5

算法舉例5

算法舉例假設(shè)要從一個(gè)有序數(shù)組或序列中查找值為75的數(shù)據(jù)位置，折半查找的計(jì)算過(guò)程如圖10-10所示。03程序設(shè)計(jì)基礎(chǔ)講解程序設(shè)計(jì)的基礎(chǔ)知識(shí)以及面向過(guò)程與面向?qū)ο蟪绦蛟O(shè)計(jì)思想01計(jì)算機(jī)語(yǔ)言概述02程序設(shè)計(jì)基本元素03面向過(guò)程的程序設(shè)計(jì)思想Contents目錄04面向?qū)ο蟮某绦蛟O(shè)計(jì)思想1計(jì)算機(jī)語(yǔ)言概述程序設(shè)計(jì)語(yǔ)言泛指一切用于書寫計(jì)算機(jī)程序的語(yǔ)言，包括匯編語(yǔ)言、機(jī)器語(yǔ)言以及高級(jí)語(yǔ)言?？梢钥闯龀绦蛟O(shè)計(jì)語(yǔ)言是計(jì)算機(jī)語(yǔ)言的一個(gè)子集。程序設(shè)計(jì)語(yǔ)言可分為低級(jí)語(yǔ)言與高級(jí)語(yǔ)言兩大類。低級(jí)語(yǔ)言是與機(jī)器有關(guān)的語(yǔ)言，包括機(jī)器語(yǔ)言和匯編語(yǔ)言。高級(jí)語(yǔ)言是與機(jī)器無(wú)關(guān)的語(yǔ)言。1計(jì)算機(jī)語(yǔ)言概述1．機(jī)器語(yǔ)言機(jī)器語(yǔ)言是以“0”、“1”二進(jìn)制代碼形式表示的機(jī)器基本指令的集合，是計(jì)算機(jī)硬件唯一可以直接識(shí)別的語(yǔ)言。機(jī)器語(yǔ)言是最早出現(xiàn)的計(jì)算機(jī)語(yǔ)言，屬于第一代程序設(shè)計(jì)語(yǔ)言。使用機(jī)器語(yǔ)言編寫程序是十分痛苦的，因?yàn)檫@種語(yǔ)言直觀性較差、難閱讀、難修改。而且，由于每臺(tái)計(jì)算機(jī)的指令系統(tǒng)往往各不相同，所以，在一臺(tái)計(jì)算機(jī)上執(zhí)行的程序，要想在中一臺(tái)不同的計(jì)算機(jī)上執(zhí)行，必須重新編寫程序，造成了重復(fù)工作。但是，由于使用的是針對(duì)特定型號(hào)計(jì)算機(jī)的語(yǔ)言，故而運(yùn)算效率是所有語(yǔ)言中最高的。1計(jì)算機(jī)語(yǔ)言概述2．匯編語(yǔ)言匯編語(yǔ)言是為了解決機(jī)器語(yǔ)言難于理解和記憶的缺點(diǎn)，用易于理解和記憶的名稱和符號(hào)表示機(jī)器指令。例如，用“ADD”代表加法，“MOV”代表數(shù)據(jù)移動(dòng)等。匯編語(yǔ)言比機(jī)器語(yǔ)言直觀，使得程序的編寫、糾錯(cuò)和維護(hù)變得相對(duì)簡(jiǎn)單了。匯編語(yǔ)言源程序需要由匯編程序翻譯成機(jī)器語(yǔ)言程序才能執(zhí)行。由于匯編語(yǔ)言還是針對(duì)特定硬件的一種程序設(shè)計(jì)語(yǔ)言，因此效率仍十分高，能準(zhǔn)確發(fā)揮計(jì)算機(jī)硬件的功能和特長(zhǎng)，程序精煉而質(zhì)量高，所以至今仍是一種常用而強(qiáng)有力的軟件開發(fā)工具。但匯編語(yǔ)言基本上還是一條指令對(duì)應(yīng)一種基本操作，對(duì)機(jī)器硬件十分依賴，移植性不好。不論是機(jī)器語(yǔ)言還是匯編語(yǔ)言都是面向硬件具體操作的，要求使用者必須對(duì)硬件結(jié)構(gòu)及其工作原理都十分熟悉，這對(duì)非計(jì)算機(jī)專業(yè)人員是難以做到的，對(duì)于計(jì)算機(jī)的推廣應(yīng)用是不利的。1計(jì)算機(jī)語(yǔ)言概述3．高級(jí)語(yǔ)言高級(jí)語(yǔ)言是人們?yōu)榱私鉀Q低級(jí)語(yǔ)言的不足而設(shè)計(jì)的程序設(shè)計(jì)語(yǔ)言。它是一些接近于自然語(yǔ)言和數(shù)學(xué)語(yǔ)言的語(yǔ)句組成。因此，更接近于要解決問(wèn)題的表示方法，并在一定程度上與機(jī)器無(wú)關(guān)。用高級(jí)語(yǔ)言編寫的程序易學(xué)、易用、易維護(hù)。高級(jí)語(yǔ)言是有語(yǔ)法結(jié)構(gòu)的，有著接近自然語(yǔ)意的指令集，高級(jí)語(yǔ)言編寫出的程序稱為源程序，該程序需要通過(guò)翻譯系統(tǒng)編譯或解釋后才能被計(jì)算機(jī)執(zhí)行。高級(jí)語(yǔ)言不依賴于計(jì)算機(jī)系統(tǒng)，不同的翻譯程序可以把相同的高級(jí)語(yǔ)言程序翻譯成不同計(jì)算機(jī)可執(zhí)行的機(jī)器語(yǔ)言。這些機(jī)器語(yǔ)言是不同的，但它們的意義是一樣的，執(zhí)行效果是一樣的。常見的高級(jí)語(yǔ)言有FORTRAN、Basic、Pascal、C、C++、Java、C#、Python等。2程序設(shè)計(jì)基本元素程序設(shè)計(jì)語(yǔ)言的基本元素是指大多數(shù)高級(jí)程序設(shè)計(jì)語(yǔ)言的必不可少的組成元素。一般包括語(yǔ)句、表達(dá)式、注釋、數(shù)據(jù)類型、程序控制結(jié)構(gòu)、子例程等。語(yǔ)句是組成語(yǔ)言的最小的獨(dú)立元素。程序是計(jì)算機(jī)指令的序列，因此可以說(shuō)程序是一個(gè)或多個(gè)計(jì)算機(jī)語(yǔ)句組成的序列。語(yǔ)句本身是由許多語(yǔ)言元素組成的。在語(yǔ)句中，常用的語(yǔ)言元素包括變量、常量、運(yùn)算符、表達(dá)式、函數(shù)、賦值等。變量的名稱應(yīng)該遵循程序設(shè)計(jì)語(yǔ)言的標(biāo)識(shí)符命名規(guī)則。不同的程序設(shè)計(jì)語(yǔ)言，標(biāo)識(shí)符命名規(guī)則也不盡相同。為了增強(qiáng)程序源代碼的可讀性，變量的名稱建議采用大小寫字母結(jié)合的描述性名稱。例如，用來(lái)存儲(chǔ)學(xué)生姓名的studentName變量名稱比x變量名稱的可讀性要高。程序設(shè)計(jì)基本元素程序設(shè)計(jì)語(yǔ)言元素語(yǔ)句：表達(dá)式、賦值表達(dá)式：變量、常量、運(yùn)算符數(shù)據(jù)類型：數(shù)值、字符、布爾控制語(yǔ)句：順序、分支、循環(huán)注釋子例程程序設(shè)計(jì)基本元素程序是計(jì)算機(jī)指令的序列，因此可以說(shuō)程序是一個(gè)或多個(gè)計(jì)算機(jī)語(yǔ)句組成的序列。語(yǔ)句本身是由許多語(yǔ)言元素組成的。常用的語(yǔ)言元素包括變量、常量、運(yùn)算符、表達(dá)式、函數(shù)、賦值等。

printf("%-5d",i*100+j*10+k);

k=a*b*c+100+sum(a,2);表達(dá)式是構(gòu)成語(yǔ)句的重要元素。表達(dá)式是常量、變量、運(yùn)算符、函數(shù)調(diào)用等按照優(yōu)先級(jí)規(guī)則組成的序列。

if(i*100+j*10+k==i*i*i+j*j*j+k*k*k)程序設(shè)計(jì)基本元素基本數(shù)據(jù)類型通過(guò)組合可以構(gòu)成復(fù)雜的復(fù)合數(shù)據(jù)類型。一般地，基本數(shù)據(jù)類型包括：整數(shù)類型、浮點(diǎn)數(shù)據(jù)類型、字符類型和字符串類型、布爾類型、枚舉類型等。程序設(shè)計(jì)基本元素變量的名稱應(yīng)該遵循程序設(shè)計(jì)語(yǔ)言的標(biāo)識(shí)符命名規(guī)則。為了增強(qiáng)程序源代碼的可讀性，變量的名稱建議采用大小寫字母結(jié)合的描述性名稱。例如，用來(lái)存儲(chǔ)學(xué)生姓名的studentName變量名稱比x變量名稱的可讀性要高。

intcount1,count2;

booleanisman;

char

studentname;程序設(shè)計(jì)基本元素注釋是程序中的有助于理解代碼的提示和說(shuō)明。在處理注釋時(shí)，任何編譯程序或解釋程序都會(huì)忽略注釋。intcount1,count2;//count1代表1班人數(shù)，count2代表2班人數(shù)程序有三種基本結(jié)構(gòu)類型，即順序結(jié)構(gòu)、條件分支結(jié)構(gòu)和循環(huán)結(jié)構(gòu)。除此以外，還有其他一些程序控制結(jié)構(gòu)，例如異常處理等。程序設(shè)計(jì)基本元素程序三種基本控制結(jié)構(gòu)類型switch(表達(dá)式)｛case1:…break;case2:…break;｝for(inti=0;i<=100;i++)｛…｝while(i<=100)｛…｝do｛…｝while(i<=100)try{…}catch(e){…}finally｛…｝if(表達(dá)式)｛…｝else{…}條件分支結(jié)構(gòu)循環(huán)結(jié)構(gòu)異常處理AA；BB；CC；順序結(jié)構(gòu)程序設(shè)計(jì)基本元素子例程是某個(gè)主程序的一部分代碼，該代碼執(zhí)行特定的任務(wù)并且與主程序中的其他代碼相對(duì)獨(dú)立。子例程又被稱為子程序、過(guò)程、方法、函數(shù)等。在主程序中可以調(diào)用子例程來(lái)執(zhí)行。main()

{

int

i=1,j=1,k;

sum(i,j,10);

}intsum(inta,intb,intc)//子例程{intsum=0;sum=a+b+c;returnsum;}

3面向過(guò)程的程序設(shè)計(jì)思想高級(jí)語(yǔ)言分為面向過(guò)程的語(yǔ)言和面向?qū)ο蟮恼Z(yǔ)言。其中，面向過(guò)程是一種以過(guò)程為中心的編程思想。面向過(guò)程也可稱之為面向記錄編程思想，就是分析出解決問(wèn)題所需要的步驟，然后定義函數(shù)來(lái)實(shí)現(xiàn)每一個(gè)步驟，工作時(shí)只需要依次調(diào)用各個(gè)函數(shù)就可以了。假設(shè)需要編程控制一部智能手機(jī)，面向過(guò)程的編程思想是先定義開機(jī)、打電話、上網(wǎng)、關(guān)機(jī)等過(guò)程，接下來(lái)只需要在主程序中調(diào)用每個(gè)過(guò)程即可。以下偽代碼表達(dá)了面向過(guò)程的程序設(shè)計(jì)思想。3面向過(guò)程的程序設(shè)計(jì)思想voidmain(){charnumber=;

start()；//調(diào)用開機(jī)方法（過(guò)程函數(shù)）

call(number)；//調(diào)用打電話方法（過(guò)程函數(shù)）

internet()；//調(diào)用上網(wǎng)方法（過(guò)程函數(shù)）

close()；//調(diào)用關(guān)機(jī)方法（過(guò)程函數(shù)）

……}start(){...}//開機(jī)方法（過(guò)程函數(shù)）具體實(shí)現(xiàn)call(char[]number){...}//打電話方法（過(guò)程函數(shù)）具體實(shí)現(xiàn)internet(){...}//上網(wǎng)方法（過(guò)程函數(shù)）具體實(shí)現(xiàn)close(){...}//關(guān)機(jī)方法（過(guò)程函數(shù)）具體實(shí)現(xiàn)……4面向?qū)ο蟮某绦蛟O(shè)計(jì)思想

面向?qū)ο笫且环N以事物為中心的編程思想，將抽象出的數(shù)據(jù)和方法（函數(shù)）封裝到一個(gè)類（class）中，供程序設(shè)計(jì)者使用。

假設(shè)需要編程控制一部智能手機(jī)，面向?qū)ο蟮木幊谭椒ㄊ紫刃枰獙⑹謾C(jī)實(shí)體抽象成類,需要定義類的靜態(tài)屬性，例如品牌、顏色、手機(jī)號(hào)碼等,還要定義類的動(dòng)態(tài)方法，例如設(shè)置手機(jī)屬性、獲取手機(jī)屬性、開機(jī)、打電話等。以下偽代碼表達(dá)了對(duì)手機(jī)實(shí)體類的定義。4面向?qū)ο蟮某绦蛟O(shè)計(jì)思想publicclassTelePhone{

Stringbrand=””;

Stringcolor=””;

Stringnumber=””;

voidsetBrand(Stringbrand){……}