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

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

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

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

4、: 3 i;s3: p i p;s4: i+2 is5: 若i11,返回s3;否則，結束。2021/4/2求13579 11 可以看出，用這種方法表示的算法具有通用性、靈活性。S3到s5 組成一個循環(huán)，在實現(xiàn)算法時，要反復多次執(zhí)行s3、s4、s5等步驟，直到某一時刻，執(zhí)行s5步驟時經(jīng)過判斷，乘數(shù)i已超過規(guī)定的數(shù)值而不返回s3步驟為止。 計算機實現(xiàn)循環(huán)是輕而易舉。2021/4/2求13579 11請同學們仔細分析循環(huán)結束的條件，即s5步驟，如果在求13579 11時，將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，轉去執(zhí)行（3）以及其后的各步驟；否則執(zhí)行（6）；（6）打印S的值（即所求之總和）。例例5.求下列級數(shù)的值求下列級數(shù)的值可以寫出下面的算法可以寫出下面的算法2021/4/2 1、有窮性：、有窮性：一個算法應當包含一個算法應當包含有限的步驟，有限的步驟，而不能是無而不能是無限的步驟；同時一個算法應當在執(zhí)行一定數(shù)量的步驟后，限的步驟；同時一個算法應當在執(zhí)行一定數(shù)量的步驟后，算法結束，算法結束，不能死循環(huán)不能死循環(huán)。 事實上事實上“有窮性有窮性”往往指往往指“在合理的范圍之內在合理的范圍之內”的有限的有限步驟。如果讓計

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

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

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

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

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

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

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

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

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

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

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

17、為分別為5、10； a = 5； b = 10；2021/4/2(2)判別選擇結構程序設計 首先判別條件，若條件滿足，程序執(zhí)行a塊，否則，執(zhí)行b塊； 舉例，求a、b兩個 數(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)結構程序設計 循環(huán)又分“當型循環(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)中的指令當條件滿足時當條件滿足時執(zhí)行循環(huán)中指令執(zhí)行循環(huán)中指令i5打印打印t2021/4/2 當型循環(huán)：當型循環(huán)：當條件當條件p成立時，反復執(zhí)行成立時，反復執(zhí)行循環(huán)體中指令，直到循環(huán)體中指令，直到p條件不成立為止。條件不成立為止。當型循環(huán)先判斷，再決定是否執(zhí)行循環(huán)當型循環(huán)先判斷，再決定是否執(zhí)行循環(huán)體，所以在條件體，所以在條件p一次都不滿足時，循一次都不滿足時，循環(huán)體可能一次都不執(zhí)行環(huán)體可能一次都不執(zhí)行當條件當條件p滿足時滿足時執(zhí)行循環(huán)中指令執(zhí)行循環(huán)中指令2021/4/2 直到型循環(huán)：直到型循環(huán)：當條件當條件p不成立時，反復執(zhí)不成立時，反復執(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個學生中成績高于個學生中成績高于80分者的學號和成績。分者的學號和成績。for i=1 to 50 step 1 輸入第輸入第i個同學的學號和成績個同學的學號和成績for i

20、=1 to 50 step 1if gi=80輸出該同學的學號和成績輸出該同學的學號和成績 #includevoid main( ) int num51,score51,i;for(i=1;i51;i+) /輸入輸入50個學生的學號和成績個學生的學號和成績 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 用某種程序設計語言編寫的程序本質上也是問題處理方案的描述，并且是最終的描述。 在一般的程序設計過程中，不提倡一開始就編寫程序，特別是對于大型的程序。 程序是程序設計的最終產品，需要經(jīng)過每一步的細致加工才能得到，如果企圖一開始就編寫出程序，往往會適得其反，達不到預想的結果

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之間的素數(shù)打印出來輸入輸入2到到1000各數(shù)各數(shù)把所有非素數(shù)去掉把所有非素數(shù)去掉打印全部素數(shù)打印全部素數(shù)將將2到到1000各數(shù)存放到數(shù)組各數(shù)存放到數(shù)組a的的a2到到a1000中中for i=2 to 500 將將ai+1到到a1000中能被中能被i整除的數(shù)改為整除的數(shù)改