1、C程序設計課件 設計制作：匡珍春 1Chapter 2 Chapter 2 算算 法法C程序設計課件程序設計課件 設計制作：匡珍春設計制作：匡珍春 2算法：算法：為解決一個問題而采取的方法和步驟，為解決一個問題而采取的方法和步驟，或者說是解題步驟的精確描述或者說是解題步驟的精確描述計算機算法：計算機算法：計算機能執(zhí)行的算法計算機能執(zhí)行的算法好的算法：好的算法：方法簡單、運算步驟少、能迅速得方法簡單、運算步驟少、能迅速得出正確結(jié)果的算法出正確結(jié)果的算法設計算法的目的：設計算法的目的：實現(xiàn)該算法實現(xiàn)該算法計算機算法的分類：計算機算法的分類：數(shù)值運算算法和非數(shù)值運數(shù)值運算算法和非數(shù)值運算算法算算法C

2、程序設計課件程序設計課件 設計制作：匡珍春設計制作：匡珍春 31 1 用自然語言表示算法用自然語言表示算法 特點：特點：易表達，但文字冗長，會出現(xiàn)易表達，但文字冗長，會出現(xiàn)“歧義性歧義性”2 2 用流程圖表示算法用流程圖表示算法 流程圖：流程圖：用一些圖框、流程線及文字說明來描述操用一些圖框、流程線及文字說明來描述操作過程的圖形作過程的圖形 特點：特點：明確簡練、形象直觀、流向清楚、易改寫成明確簡練、形象直觀、流向清楚、易改寫成程序程序 用傳統(tǒng)流程圖表示算法用傳統(tǒng)流程圖表示算法 傳統(tǒng)流程圖中的符號：傳統(tǒng)流程圖中的符號：起止框起止框 ( (示算法的開始和結(jié)束示算法的開始和結(jié)束) )C程序設計課件

3、程序設計課件 設計制作：匡珍春設計制作：匡珍春 4判斷框判斷框 ( (一個入口兩個出口，依一個入口兩個出口，依給定的條件是否滿足決定執(zhí)行兩給定的條件是否滿足決定執(zhí)行兩條路徑中的某一路徑條路徑中的某一路徑) )處理框處理框 ( (示示“賦值賦值”等一般處理等一般處理) )輸入輸入/ /輸出框輸出框 ( (示輸入輸出操作示輸入輸出操作) )流程線流程線 ( (示流程的方向示流程的方向) )C程序設計課件程序設計課件 設計制作：匡珍春設計制作：匡珍春 5連接點連接點 ( (小圓圈，將畫在不同地小圓圈，將畫在不同地方的流程線連接起來方的流程線連接起來) )注釋框注釋框 ( (對流程線中某些部分作對流程

4、線中某些部分作必要的說明，不是流程圖中的必要必要的說明，不是流程圖中的必要部分，不反映流程和操作部分，不反映流程和操作) )例例2-1： 求求1 1 2 2 3 3 4 4 5 5，即，即5 5！。用傳統(tǒng)的流程圖表示！。用傳統(tǒng)的流程圖表示算法算法C程序設計課件程序設計課件 設計制作：匡珍春設計制作：匡珍春 6開始開始將結(jié)果將結(jié)果 3 3將結(jié)果將結(jié)果 4 4將結(jié)果將結(jié)果 5 5輸出結(jié)果輸出結(jié)果結(jié)束結(jié)束求求1 1 2 2開始開始t=1t=1t t 2 2t tt t 3 3t tt t 4 4t tt t 5 5t t輸出輸出t t的值的值結(jié)束結(jié)束結(jié)束結(jié)束開始開始t=1t=1i=2i=2t t i

5、 it ti+1i+1i ii5?i5?輸出輸出t t的值的值否否是是C程序設計課件程序設計課件 設計制作：匡珍春設計制作：匡珍春 7例例2-2：有一個有一個大于或等于大于或等于3 3的正整的正整數(shù)數(shù)n n，判斷它是不是，判斷它是不是素數(shù)素數(shù)分析：分析：判斷一個判斷一個數(shù)數(shù)n n是否是素數(shù)，只是否是素數(shù)，只要將要將n n除以除以2 2、3 3、直到直到n-1n-1，如果都不，如果都不能被整除，則能被整除，則n n為素為素數(shù)。由于有相同數(shù)。由于有相同“除除法法”操作，故應用到操作，故應用到“循環(huán)循環(huán)”結(jié)構(gòu)結(jié)構(gòu)開始開始結(jié)束結(jié)束輸入輸入n ni=2i=2i+1i+1i in n能否被能否被i i整除

6、整除in-1in-1輸出輸出n n是素數(shù)是素數(shù)輸出輸出n n不是素數(shù)不是素數(shù)是是否否否否是是C程序設計課件程序設計課件 設計制作：匡珍春設計制作：匡珍春 8例例2-3：求三個求三個 整數(shù)中整數(shù)中 的最大的最大 數(shù)的系數(shù)的系 統(tǒng)流程統(tǒng)流程 圖。圖。C程序設計課件程序設計課件 設計制作：匡珍春設計制作：匡珍春 9 用用三種基本結(jié)構(gòu)改進流程圖三種基本結(jié)構(gòu)改進流程圖1. 傳統(tǒng)流程圖的弊病傳統(tǒng)流程圖的弊病 流程任意轉(zhuǎn)移，算法難以閱讀和修改，算法的可靠性流程任意轉(zhuǎn)移，算法難以閱讀和修改，算法的可靠性和可維護性難以保證和可維護性難以保證 三種基本結(jié)構(gòu)三種基本結(jié)構(gòu) 為提高算法的質(zhì)量，使算法的設計和閱讀方便，人

7、們制為提高算法的質(zhì)量，使算法的設計和閱讀方便，人們制定出了順序、選擇和循環(huán)三種基本結(jié)構(gòu)。規(guī)定算法定出了順序、選擇和循環(huán)三種基本結(jié)構(gòu)。規(guī)定算法 (程序程序) 只只能由以上三種基本結(jié)構(gòu)組成，即所謂的結(jié)構(gòu)化算法能由以上三種基本結(jié)構(gòu)組成，即所謂的結(jié)構(gòu)化算法 (程序程序)。(1) (1) 順序結(jié)構(gòu)順序結(jié)構(gòu) A A和和B B兩個框兩個框是順序執(zhí)行的是順序執(zhí)行的A AB Ba ab bC程序設計課件程序設計課件 設計制作：匡珍春設計制作：匡珍春 10(2) (2) 選擇結(jié)構(gòu)選擇結(jié)構(gòu)( (分支結(jié)構(gòu)分支結(jié)構(gòu)) ) 依給定的條件選擇執(zhí)行依給定的條件選擇執(zhí)行p pA AB Ba ab b滿足滿足不滿足不滿足C程序設

8、計課件程序設計課件 設計制作：匡珍春設計制作：匡珍春 11(3) (3) 循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)( (重復結(jié)構(gòu)重復結(jié)構(gòu)) ) 作用：作用：反復執(zhí)行某一部分操作反復執(zhí)行某一部分操作 分類：分類：當型循環(huán)和直到型循環(huán)當型循環(huán)和直到型循環(huán) a.a.當型循環(huán)當型循環(huán)(WHILE(WHILE型循環(huán)型循環(huán)) ) 特點：特點：當指定條件滿足當指定條件滿足( (成立成立) )時，就執(zhí)行循環(huán)體，時，就執(zhí)行循環(huán)體，否則就不執(zhí)行否則就不執(zhí)行 分為兩種形式：分為兩種形式： “ “前測試前測試”型：型：先測試條件，后執(zhí)行循環(huán)體先測試條件，后執(zhí)行循環(huán)體 C程序設計課件程序設計課件 設計制作：匡珍春設計制作：匡珍春 12p1p1

9、A A滿足滿足不滿足不滿足a ab b(a)(a)p1p1A A滿足滿足不滿足不滿足a ab b(b)(b)C程序設計課件程序設計課件 設計制作：匡珍春設計制作：匡珍春 13 “ “后測試后測試”型：型：先執(zhí)行循環(huán)體，先執(zhí)行循環(huán)體，然后再測試條件是否然后再測試條件是否成立成立p1p1A A滿足滿足不滿足不滿足a ab bC程序設計課件程序設計課件 設計制作：匡珍春設計制作：匡珍春 14b.b.直到型循環(huán)直到型循環(huán)(UNTIL(UNTIL型循環(huán)型循環(huán)) )特點：特點：執(zhí)行循環(huán)體直到指定的條件滿足執(zhí)行循環(huán)體直到指定的條件滿足( (成立成立) )，此時就不再執(zhí)行循環(huán)此時就不再執(zhí)行循環(huán)形式：形式： “

10、 “前測試前測試”型：型：先測試條件后執(zhí)行循先測試條件后執(zhí)行循環(huán)體，見右圖環(huán)體，見右圖p2p2A A不滿足不滿足滿足滿足a ab bC程序設計課件程序設計課件 設計制作：匡珍春設計制作：匡珍春 15“后測試后測試”型：型：先執(zhí)行循環(huán)體，先執(zhí)行循環(huán)體，然后再測試條件是然后再測試條件是否成立否成立p2p2A A不滿足不滿足滿足滿足a ab bC程序設計課件程序設計課件 設計制作：匡珍春設計制作：匡珍春 16(4) (4) 三種基本結(jié)構(gòu)的特點三種基本結(jié)構(gòu)的特點 a.a. 只有一個入口只有一個入口 b. b. 只有一個出口只有一個出口 c. c. 每個基本結(jié)構(gòu)中每一個部分都有機會被執(zhí)行到每個基本結(jié)構(gòu)中

11、每一個部分都有機會被執(zhí)行到 d. d. 結(jié)構(gòu)內(nèi)不存在結(jié)構(gòu)內(nèi)不存在“死循環(huán)死循環(huán)”例題：例題：求求1+2+3+1+2+3+直到其和等于或大于直到其和等于或大于100100為止。為止。用含用含基本結(jié)構(gòu)基本結(jié)構(gòu)的流程圖表示其算法的流程圖表示其算法分析：分析：和數(shù)和數(shù)用用變量變量 t t 存放，存放，加數(shù)加數(shù)用用變量變量 i i 存放存放C程序設計課件程序設計課件 設計制作：匡珍春設計制作：匡珍春 17結(jié)束開始0 t,1 it+iti+1it100輸出t的值不成立成立順序結(jié)構(gòu)順序結(jié)構(gòu)順序結(jié)構(gòu)順序結(jié)構(gòu)循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)C程序設計課件程序設計課件 設計制作：匡珍春設計制作：匡珍春 18 用用N NS S流程

12、圖表示算法流程圖表示算法 N-S流程圖是目前用得比較普遍的具有三種基本結(jié)構(gòu)流程圖是目前用得比較普遍的具有三種基本結(jié)構(gòu)的結(jié)構(gòu)化流程圖，其流程圖的符號如下：的結(jié)構(gòu)化流程圖，其流程圖的符號如下：a.a.順序結(jié)構(gòu)順序結(jié)構(gòu)塊塊A A、B B是按是按順序執(zhí)行的順序執(zhí)行的b. b. 選擇結(jié)構(gòu)選擇結(jié)構(gòu) p p條件成立執(zhí)條件成立執(zhí)行行A A操作，操作，p p條件不條件不成立執(zhí)行成立執(zhí)行B B操作操作ABABp成立成立 不不成立成立C程序設計課件程序設計課件 設計制作：匡珍春設計制作：匡珍春 19c.c.循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)前測試當型循環(huán)前測試當型循環(huán)當當p1p1滿足滿足A A前測試直到型循環(huán)前測試直到型循環(huán)直到直到

13、p2p2滿足滿足A A后測試當型循環(huán)后測試當型循環(huán)當當p1p1滿足滿足A A后測試直到型循環(huán)后測試直到型循環(huán)直到直到p2p2滿足滿足A AC程序設計課件程序設計課件 設計制作：匡珍春設計制作：匡珍春 20例例2-4: 求求1+2+31+2+3直到其和等于或大于直到其和等于或大于100100為止，用為止，用N NS S圖表示其算法圖表示其算法直到直到t t 100100輸出輸出t t0 0 t, 1 t, 1 i it+i t+i t ti+1 i+1 i i思考：思考： 怎樣改成前測試怎樣改成前測試直到型循環(huán)直到型循環(huán) 怎樣改成當型循怎樣改成當型循環(huán)環(huán)C程序設計課件程序設計課件 設計制作：匡珍

14、春設計制作：匡珍春 213 3 用偽代碼（算法描述語言）表示算法用偽代碼（算法描述語言）表示算法 偽代碼：偽代碼：用介于自然語言和計算機語言之間的文字用介于自然語言和計算機語言之間的文字和符號來描述算法和符號來描述算法 特點：特點：書寫方便，格式緊湊，便于向計算機語言算書寫方便，格式緊湊，便于向計算機語言算法（即程序）過渡，適用于軟件專業(yè)人員使用。法（即程序）過渡，適用于軟件專業(yè)人員使用。4 4 用計算機語言表示算法用計算機語言表示算法 用計算機語言表示算法即編寫計算機能夠執(zhí)行的程序用計算機語言表示算法即編寫計算機能夠執(zhí)行的程序( (用非計算機語言如自然語言、偽代碼或流程圖等表示的用非計算機語

15、言如自然語言、偽代碼或流程圖等表示的算法計算機是不能執(zhí)行的，必須轉(zhuǎn)換成計算機語言程序算法計算機是不能執(zhí)行的，必須轉(zhuǎn)換成計算機語言程序才能被計算機執(zhí)行才能被計算機執(zhí)行) ) 用用C C語言表示算法就是用語言表示算法就是用C C語言編程。要實現(xiàn)該算法語言編程。要實現(xiàn)該算法必須運行該程序。必須運行該程序。C程序設計課件程序設計課件 設計制作：匡珍春設計制作：匡珍春 22 有窮性：有窮性： 一個算法應包含有限個操作步驟一個算法應包含有限個操作步驟 確定性：確定性： 算法中的每一個步驟應當是確定的算法中的每一個步驟應當是確定的, ,而而不應是含糊的、模棱兩可的不應是含糊的、模棱兩可的 有零個或多個輸入：有零個或多個輸入：從外界取得必要的信息從外界取得必要的信息 有一個或多個輸出：有一個或多個輸出：算法得到的結(jié)果即算法的輸算法得到的結(jié)果即算法的輸出，沒有輸出的算法是沒有意義的出，沒有輸出的算法是沒有意義的 有效性：有效性：算法中的每一個步驟都應當能有效地執(zhí)算法中的每一個步驟都應當能有效地執(zhí)行，并得到確定的結(jié)果行，并得到確定的結(jié)果C程序設計課件程序設計課件 設計制作：匡珍春設計制作：匡珍春