《程序的靈魂-算法》PPT課件

1、2021/4/2第第2章程序的靈魂算法章程序的靈魂算法2021/4/2程序設(shè)計(jì)概述程序設(shè)計(jì)概述一個(gè)程序應(yīng)包括對數(shù)據(jù)的描述和對數(shù)據(jù)處理的描述。 1對數(shù)據(jù)的描述，即數(shù)據(jù)結(jié)構(gòu)對數(shù)據(jù)的描述，即數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)學(xué)科的核心課程之一，有許多專門著作論述，本課程就不再贅述。 在C語言中，系統(tǒng)提供的數(shù)據(jù)結(jié)構(gòu)，是以數(shù)據(jù)類型的形式出現(xiàn)的。 2對數(shù)據(jù)處理的描述，即計(jì)算機(jī)算法對數(shù)據(jù)處理的描述，即計(jì)算機(jī)算法。算法是為解決一個(gè)問題而采取的方法和步驟，是程序的靈魂。為此，著名計(jì)算機(jī)科學(xué)家沃思（Nikiklaus Wirth）提出一個(gè)公式： 數(shù)據(jù)結(jié)構(gòu) + 算法 = 程序 實(shí)際上，一個(gè)程序除了數(shù)據(jù)結(jié)構(gòu)和算法外，還必須使

2、用一種計(jì)算機(jī)語言，并采用結(jié)構(gòu)化方法來表示。 2021/4/2算法:是指解決一個(gè)具體問題的意義明確的步驟的集合。是有限的 概括地說，算法是指解題方案的準(zhǔn)確而完整的描述。從程序來說，也可以說算法是一個(gè)有限條指令的集合，這些指令確定了解決某一特定類型問題的運(yùn)算序列。 對于同一個(gè)問題可以有不同的解題方法和步驟，也就是有不同的算法。算法有優(yōu)劣，一般而言，應(yīng)當(dāng)選擇簡單的、運(yùn)算步驟少的，既運(yùn)算快、內(nèi)存開銷小的算法（算法的時(shí)空效率）。2021/4/2買電視機(jī)的步驟：選好貨物開票付款拿發(fā)票取貨回家考大學(xué)上大學(xué)的步驟填報(bào)名單交報(bào)名費(fèi)拿準(zhǔn)考證參加考試得到錄取通知書報(bào)到注冊2021/4/2例1 求12345。可先寫出

3、這樣的算法：（1）先求12，得到結(jié)果2；（2）將步驟1得到的結(jié)果再乘以3，得到結(jié)果6；（3）將6再乘以4，得到24；（4）將24再乘以5，得到120。2021/4/2求12345 上述算法太繁瑣，我們找一種通用的表示方法。S1:設(shè)變量p，被乘數(shù)，p=1;s2:設(shè)變量i,代表乘數(shù)，i=2;s3:使pi,乘積放在被乘數(shù)變量p中，可表示為：p i p;s4:使i的值加1，即i+1 i;s5:如果i不大于5，返回重新執(zhí)行步驟s3以及其后的s4、s5;否則，算法結(jié)束。最后得到的p就是5!的值。2021/4/2例2.求13579 11 如果題目改為求13579 11。上述算法稍作改動(dòng)：s1: 1 p;s2

4、: 3 i;s3: p i p;s4: i+2 is5: 若i11,返回s3;否則，結(jié)束。2021/4/2求13579 11 可以看出，用這種方法表示的算法具有通用性、靈活性。S3到s5 組成一個(gè)循環(huán)，在實(shí)現(xiàn)算法時(shí)，要反復(fù)多次執(zhí)行s3、s4、s5等步驟，直到某一時(shí)刻，執(zhí)行s5步驟時(shí)經(jīng)過判斷，乘數(shù)i已超過規(guī)定的數(shù)值而不返回s3步驟為止。 計(jì)算機(jī)實(shí)現(xiàn)循環(huán)是輕而易舉。2021/4/2求13579 11請同學(xué)們仔細(xì)分析循環(huán)結(jié)束的條件，即s5步驟，如果在求13579 11時(shí)，將s5步驟寫成： s5：若I2500,算法停止。2021/4/2（1）使S=0（S作為累加變量）；（2）使N=1（N代表分母）；（

5、3）S+1/N S （執(zhí)行迭代，S為迭代變量）；（4）N+1 N；（5）若N100，轉(zhuǎn)去執(zhí)行（3）以及其后的各步驟；否則執(zhí)行（6）；（6）打印S的值（即所求之總和）。例例5.求下列級(jí)數(shù)的值求下列級(jí)數(shù)的值可以寫出下面的算法可以寫出下面的算法2021/4/2 1、有窮性：、有窮性：一個(gè)算法應(yīng)當(dāng)包含一個(gè)算法應(yīng)當(dāng)包含有限的步驟，有限的步驟，而不能是無而不能是無限的步驟；同時(shí)一個(gè)算法應(yīng)當(dāng)在執(zhí)行一定數(shù)量的步驟后，限的步驟；同時(shí)一個(gè)算法應(yīng)當(dāng)在執(zhí)行一定數(shù)量的步驟后，算法結(jié)束，算法結(jié)束，不能死循環(huán)不能死循環(huán)。 事實(shí)上事實(shí)上“有窮性有窮性”往往指往往指“在合理的范圍之內(nèi)在合理的范圍之內(nèi)”的有限的有限步驟。如果讓計(jì)

6、算機(jī)執(zhí)行一個(gè)歷時(shí)步驟。如果讓計(jì)算機(jī)執(zhí)行一個(gè)歷時(shí)1000年才結(jié)束的算法，年才結(jié)束的算法，算法盡管有窮，但超過了合理的限度，人們也不認(rèn)為此算法盡管有窮，但超過了合理的限度，人們也不認(rèn)為此算法是有用的。算法是有用的。 2、確定性：、確定性：算法中的算法中的每一個(gè)步驟都應(yīng)當(dāng)是確定的每一個(gè)步驟都應(yīng)當(dāng)是確定的，而不，而不是含糊的、摸棱兩可的。也就是說不應(yīng)當(dāng)產(chǎn)生歧義。特是含糊的、摸棱兩可的。也就是說不應(yīng)當(dāng)產(chǎn)生歧義。特別是算法用自然語言描述時(shí)應(yīng)當(dāng)注意這點(diǎn)。別是算法用自然語言描述時(shí)應(yīng)當(dāng)注意這點(diǎn)。 例如：例如：“將成績優(yōu)秀的同學(xué)名單打印輸出將成績優(yōu)秀的同學(xué)名單打印輸出”就是有歧義就是有歧義的。的?！俺煽儍?yōu)秀成績優(yōu)

7、秀”是要求每門課程都是要求每門課程都90分以上，還是平分以上，還是平均成績在均成績在90分以上？不明確，有歧義，不適合描述算法分以上？不明確，有歧義，不適合描述算法步驟。步驟。2021/4/2 3、有、有0個(gè)或多個(gè)輸入個(gè)或多個(gè)輸入（即：可以沒有輸入，也可以有輸（即：可以沒有輸入，也可以有輸入）入） 所謂輸入是指算法執(zhí)行時(shí)所謂輸入是指算法執(zhí)行時(shí)從外界獲取必要信息從外界獲取必要信息。（外界。（外界是相對算法本身的，輸入可以是人工鍵盤輸入的數(shù)據(jù)，是相對算法本身的，輸入可以是人工鍵盤輸入的數(shù)據(jù)，也可以是程序其它部分傳遞給算法的數(shù)據(jù)）也可以是程序其它部分傳遞給算法的數(shù)據(jù)） 例如：不需要輸入任何信息，就可

8、以計(jì)算出例如：不需要輸入任何信息，就可以計(jì)算出5??；（??；（0個(gè)個(gè)輸入）輸入） 例如：如果要計(jì)算兩個(gè)整數(shù)的最大公約數(shù)，則需要輸入例如：如果要計(jì)算兩個(gè)整數(shù)的最大公約數(shù)，則需要輸入2個(gè)整數(shù)個(gè)整數(shù)m，n。（。（2個(gè)輸入）個(gè)輸入） 4、有、有1個(gè)或多個(gè)輸出個(gè)或多個(gè)輸出（即算法必須得到結(jié)果）（即算法必須得到結(jié)果） 算法的輸出：算法得到的結(jié)果。算法的輸出：算法得到的結(jié)果。算法必須有結(jié)果，沒有算法必須有結(jié)果，沒有結(jié)果的算法沒有意義。結(jié)果的算法沒有意義。（結(jié)果可以是顯示在屏幕上的，（結(jié)果可以是顯示在屏幕上的，也可以是將結(jié)果數(shù)據(jù)傳遞給程序的其它部分）也可以是將結(jié)果數(shù)據(jù)傳遞給程序的其它部分） 5、有效性、有效性

9、算法的每個(gè)步驟都應(yīng)當(dāng)能有效執(zhí)行，并能得到確定的結(jié)算法的每個(gè)步驟都應(yīng)當(dāng)能有效執(zhí)行，并能得到確定的結(jié)果。例如：果。例如：b=0，則執(zhí)行，則執(zhí)行a/b是不能有效執(zhí)行的。是不能有效執(zhí)行的。2021/4/2為了表示一個(gè)算法，可以用不同的方法。常用為了表示一個(gè)算法，可以用不同的方法。常用的算法表示方法：的算法表示方法： 自然語言，傳統(tǒng)流程圖，結(jié)構(gòu)化流程圖自然語言，傳統(tǒng)流程圖，結(jié)構(gòu)化流程圖（N-S流程圖），偽代碼、計(jì)算機(jī)語言等。（重流程圖），偽代碼、計(jì)算機(jī)語言等。（重點(diǎn)：傳統(tǒng)流程圖，點(diǎn)：傳統(tǒng)流程圖，N-S流程圖）流程圖）2021/4/2 自然語言就是人們常用的語言，可以是漢自然語言就是人們常用的語言，可以是

10、漢語、英語或其他語言。語、英語或其他語言。用自然語言表示通俗易懂；用自然語言表示通俗易懂；但文字冗長，容易出現(xiàn)但文字冗長，容易出現(xiàn)“歧義歧義”性；性；而且，用自然語言描述包含分支和循環(huán)的而且，用自然語言描述包含分支和循環(huán)的算法，不很方便。算法，不很方便。一般不使用自然語言描述算法一般不使用自然語言描述算法2021/4/2算法描述語言：是為了說明程序的流程而專門規(guī)是為了說明程序的流程而專門規(guī)定的某種語言。它一般介于自然語言與程序設(shè)計(jì)語定的某種語言。它一般介于自然語言與程序設(shè)計(jì)語言之間，它具有自然語言靈活的特點(diǎn)，同時(shí)又接近言之間，它具有自然語言靈活的特點(diǎn)，同時(shí)又接近于程序設(shè)計(jì)語言的描述。于程序設(shè)計(jì)

11、語言的描述。注意：算法描述語言所描述的流程，一般不能直接算法描述語言所描述的流程，一般不能直接作為程序來使用，最后還需轉(zhuǎn)換成用某種程序設(shè)計(jì)作為程序來使用，最后還需轉(zhuǎn)換成用某種程序設(shè)計(jì)語言所描述的程序。語言所描述的程序。與程序設(shè)計(jì)語言的區(qū)別： 前者比較自由，不象后者那樣受語法的約束，只要前者比較自由，不象后者那樣受語法的約束，只要描述得人們能理解就行，而不必考慮計(jì)算機(jī)處理時(shí)描述得人們能理解就行，而不必考慮計(jì)算機(jī)處理時(shí)所要遵循的規(guī)定或其它一些細(xì)節(jié)。所要遵循的規(guī)定或其它一些細(xì)節(jié)。算法描述語言算法描述語言2021/4/2流程圖：用一些約定的幾何圖形來描述算法。用某種流程圖：用一些約定的幾何圖形來描述算

12、法。用某種圖框表示某種操作，用箭頭表示算法流程圖框表示某種操作，用箭頭表示算法流程流程圖（的符號(hào)及意義）美國標(biāo)準(zhǔn)化協(xié)會(huì)流程圖（的符號(hào)及意義）美國標(biāo)準(zhǔn)化協(xié)會(huì)ANSI規(guī)定了一規(guī)定了一些常用的流程圖符號(hào)，已為世界各國程序工作者普遍采用：些常用的流程圖符號(hào)，已為世界各國程序工作者普遍采用：啟止框輸入輸出框判斷選擇框處理框流程線連接點(diǎn)注釋框2021/4/2 l起止框：起止框：表示算法的開始和結(jié)束。一般內(nèi)部只寫表示算法的開始和結(jié)束。一般內(nèi)部只寫“開始開始”或或“結(jié)束結(jié)束”。 l l 處理框：處理框：表示算法的某個(gè)處理步驟，一般內(nèi)部常常填寫表示算法的某個(gè)處理步驟，一般內(nèi)部常常填寫賦值操作。賦值操作。 l l

13、輸入輸出框：輸入輸出框：表示算法請求輸入輸入需要的數(shù)據(jù)或算法表示算法請求輸入輸入需要的數(shù)據(jù)或算法將某些結(jié)果輸出。一般內(nèi)部常常填寫將某些結(jié)果輸出。一般內(nèi)部常常填寫“輸入輸入”,“打印打印/顯顯示示” l l菱形框（判斷框）菱形框（判斷框）：作用主要是對一個(gè)給定條件進(jìn)行判作用主要是對一個(gè)給定條件進(jìn)行判斷，根據(jù)給定的條件是否成立來決定如何執(zhí)行其后的操作。斷，根據(jù)給定的條件是否成立來決定如何執(zhí)行其后的操作。它有一個(gè)入口，兩個(gè)出口。它有一個(gè)入口，兩個(gè)出口。 l l連接點(diǎn)連接點(diǎn)：用于將畫在不同地方的流程線連接起來。同一用于將畫在不同地方的流程線連接起來。同一個(gè)編號(hào)的點(diǎn)是相互連接在一起的，實(shí)際上同一編號(hào)的點(diǎn)

14、是個(gè)編號(hào)的點(diǎn)是相互連接在一起的，實(shí)際上同一編號(hào)的點(diǎn)是同一個(gè)點(diǎn)，只是畫不下才分開畫。使用連接點(diǎn)，還可以避同一個(gè)點(diǎn)，只是畫不下才分開畫。使用連接點(diǎn)，還可以避免流程線的交叉或過長，使流程圖更加清晰。免流程線的交叉或過長，使流程圖更加清晰。 l l注釋框注釋框：注釋框不是流程圖中必須的部分，不反映流程注釋框不是流程圖中必須的部分，不反映流程和操作，它只是對流程圖中某些框的操作做必要的補(bǔ)充說和操作，它只是對流程圖中某些框的操作做必要的補(bǔ)充說明，以幫助閱讀流程圖的人更好地理解流程圖的作用。明，以幫助閱讀流程圖的人更好地理解流程圖的作用。2021/4/2 例例2.6： 求求5 5！t=1i=2t=t*ii=

15、i+1i5結(jié)束 NY 開始2021/4/2例例2.7輸出輸出50名學(xué)生中成績在名學(xué)生中成績在80分以上者的學(xué)生和成績分以上者的學(xué)生和成績1=igi80打印打印gi,fii+1=ii50結(jié)束結(jié)束YYNN開始開始1=i輸入輸入gi,fii+1=ii50NY2021/4/2 傳統(tǒng)流程圖采用流程線指出各框的執(zhí)行順序，傳統(tǒng)流程圖采用流程線指出各框的執(zhí)行順序，對對流程線的使用沒有嚴(yán)格限制流程線的使用沒有嚴(yán)格限制。因此，使用者可以。因此，使用者可以不受限制地使流程轉(zhuǎn)來轉(zhuǎn)去，使流程圖變得毫無不受限制地使流程轉(zhuǎn)來轉(zhuǎn)去，使流程圖變得毫無規(guī)律規(guī)律。人們對這種流程圖進(jìn)行改進(jìn)，。人們對這種流程圖進(jìn)行改進(jìn)，規(guī)定幾種基規(guī)定

16、幾種基本的結(jié)構(gòu)，然后由這些基本結(jié)構(gòu)按一定規(guī)律組成本的結(jié)構(gòu)，然后由這些基本結(jié)構(gòu)按一定規(guī)律組成算法結(jié)構(gòu)，整個(gè)算法結(jié)構(gòu)是由上而下地將各個(gè)基算法結(jié)構(gòu)，整個(gè)算法結(jié)構(gòu)是由上而下地將各個(gè)基本結(jié)構(gòu)順序排列起來本結(jié)構(gòu)順序排列起來。這樣可以在一定程度上，。這樣可以在一定程度上，提高算法的質(zhì)量。提高算法的質(zhì)量。2021/4/2三種基本結(jié)構(gòu)是：（1）順序結(jié)構(gòu) 按指令的順序依次執(zhí)行（2）判斷選擇結(jié)構(gòu)： 根據(jù)判別條件有選擇地改變 執(zhí)行流程（3）循環(huán)結(jié)構(gòu)： 有條件的重復(fù)地執(zhí)行某個(gè)程序塊2021/4/2(1)順序結(jié)構(gòu)程序設(shè)計(jì) 依次順序執(zhí)行程序語句 執(zhí)行執(zhí)行a塊塊執(zhí)行執(zhí)行b塊塊a塊塊b塊塊AB例如，令例如，令a、b的值的值分別

17、為分別為5、10； a = 5； b = 10；2021/4/2(2)判別選擇結(jié)構(gòu)程序設(shè)計(jì) 首先判別條件，若條件滿足，程序執(zhí)行a塊，否則，執(zhí)行b塊； 舉例，求a、b兩個(gè) 數(shù)中的最大值；滿足條件否滿足條件否滿足滿足不滿足不滿足執(zhí)行執(zhí)行a塊塊執(zhí)行執(zhí)行b塊塊條件成立？條件成立？執(zhí)行執(zhí)行a塊塊執(zhí)行執(zhí)行b塊塊成立成立不成立不成立b max？Max = a；max = b；YN2021/4/2(3)循環(huán)結(jié)構(gòu)程序設(shè)計(jì) 循環(huán)又分“當(dāng)型循環(huán)”和“直到型循環(huán)” 舉例，求1100的累加和。 int i，sum=0； while（i =100) sum=sum+i; i=i+1; 直到條件滿足為止直到條件滿足為止執(zhí)行

18、循環(huán)中的指令執(zhí)行循環(huán)中的指令當(dāng)條件滿足時(shí)當(dāng)條件滿足時(shí)執(zhí)行循環(huán)中指令執(zhí)行循環(huán)中指令i5打印打印t2021/4/2 當(dāng)型循環(huán)：當(dāng)型循環(huán)：當(dāng)條件當(dāng)條件p成立時(shí)，反復(fù)執(zhí)行成立時(shí)，反復(fù)執(zhí)行循環(huán)體中指令，直到循環(huán)體中指令，直到p條件不成立為止。條件不成立為止。當(dāng)型循環(huán)先判斷，再?zèng)Q定是否執(zhí)行循環(huán)當(dāng)型循環(huán)先判斷，再?zèng)Q定是否執(zhí)行循環(huán)體，所以在條件體，所以在條件p一次都不滿足時(shí)，循一次都不滿足時(shí)，循環(huán)體可能一次都不執(zhí)行環(huán)體可能一次都不執(zhí)行當(dāng)條件當(dāng)條件p滿足時(shí)滿足時(shí)執(zhí)行循環(huán)中指令執(zhí)行循環(huán)中指令2021/4/2 直到型循環(huán)：直到型循環(huán)：當(dāng)條件當(dāng)條件p不成立時(shí)，反復(fù)執(zhí)不成立時(shí)，反復(fù)執(zhí)行循環(huán)體中的指令，直到行循環(huán)體中的指

19、令，直到p條件成立為止。條件成立為止。直到型循環(huán)先執(zhí)行循環(huán)體，然后再判斷直到型循環(huán)先執(zhí)行循環(huán)體，然后再判斷條件條件p，所以循環(huán)體至少執(zhí)行一次。，所以循環(huán)體至少執(zhí)行一次。直到條件直到條件p滿足為止?jié)M足為止執(zhí)行循環(huán)中的指令執(zhí)行循環(huán)中的指令2021/4/2例例2.16求求5！的偽代碼表示的算法。！的偽代碼表示的算法。1=tfor i=1 to 5 step 1 i*t=tprint t2021/4/2例例2.17打印出打印出50個(gè)學(xué)生中成績高于個(gè)學(xué)生中成績高于80分者的學(xué)號(hào)和成績。分者的學(xué)號(hào)和成績。for i=1 to 50 step 1 輸入第輸入第i個(gè)同學(xué)的學(xué)號(hào)和成績個(gè)同學(xué)的學(xué)號(hào)和成績for i

20、=1 to 50 step 1if gi=80輸出該同學(xué)的學(xué)號(hào)和成績輸出該同學(xué)的學(xué)號(hào)和成績 #includevoid main( ) int num51,score51,i;for(i=1;i51;i+) /輸入輸入50個(gè)學(xué)生的學(xué)號(hào)和成績個(gè)學(xué)生的學(xué)號(hào)和成績 scanf(%d%d,&numi,&scorei);/循環(huán)體語句循環(huán)體語句for(i=1;i=80) printf(n%d%d,numi,scorei);2021/4/2例例2.18：打?。捍蛴?0002500年的每一年是否閏年年的每一年是否閏年for y=2000 to 2500 step 1 if y能被能被4整除且不能被整除且不能被1

21、00整除或能被整除或能被400整除整除輸出第輸出第y年是閏年年是閏年 else 輸出第輸出第y年不是閏年年不是閏年2021/4/2例例2.19：求：求10019914131211sum=0sign=1for i=1 to 100 step 1 sum=sum+sign/i sign=-signprint sum2021/4/2 用某種程序設(shè)計(jì)語言編寫的程序本質(zhì)上也是問題處理方案的描述，并且是最終的描述。 在一般的程序設(shè)計(jì)過程中，不提倡一開始就編寫程序，特別是對于大型的程序。 程序是程序設(shè)計(jì)的最終產(chǎn)品，需要經(jīng)過每一步的細(xì)致加工才能得到，如果企圖一開始就編寫出程序，往往會(huì)適得其反，達(dá)不到預(yù)想的結(jié)果

22、。2021/4/2例題例題例例2.20 求求5！，用！，用C語言表示語言表示main ( )int i,t;t=1;i=2;while(i=5)t=t*i;i=i+1;printf(“%d”,t);2021/4/2例例 求求1-1/2+1/3+.+1/99-1/100的值的值main( )int sign=1;float deno=2.0,sun=1.0,term;while (deno=100)sign=-sign;term=sign/deno;sum=sum+term;deno=deno+1;printf(“%f”,sum);2021/4/2例2.22將1到1000之間的素?cái)?shù)打印出來輸入輸入2到到1000各數(shù)各數(shù)把所有非素?cái)?shù)去掉把所有非素?cái)?shù)去掉打印全部素?cái)?shù)打印全部素?cái)?shù)將將2到到1000各數(shù)存放到數(shù)組各數(shù)存放到數(shù)組a的的a2到到a1000中中for i=2 to 500 將將ai+1到到a1000中能被中能被i整除的數(shù)改為整除的數(shù)改