C語(yǔ)言程序ch0 緒論

1、共共 29 29 頁(yè)頁(yè) 第第 2 2 頁(yè)頁(yè) 計(jì)算機(jī)語(yǔ)言：是規(guī)則和符號(hào)的集合，是計(jì)算機(jī)語(yǔ)言：是規(guī)則和符號(hào)的集合，是與計(jì)算機(jī)交流的工具與計(jì)算機(jī)交流的工具 程序：求解問(wèn)題的指令序列程序：求解問(wèn)題的指令序列 軟件：程序的集合軟件：程序的集合學(xué)習(xí)語(yǔ)言學(xué)習(xí)語(yǔ)言 設(shè)計(jì)程序設(shè)計(jì)程序 制作軟件制作軟件學(xué)思想、學(xué)功能、學(xué)操作。熟練工種學(xué)思想、學(xué)功能、學(xué)操作。熟練工種學(xué)規(guī)則、學(xué)方法、學(xué)設(shè)計(jì)、學(xué)應(yīng)用。學(xué)規(guī)則、學(xué)方法、學(xué)設(shè)計(jì)、學(xué)應(yīng)用。 規(guī)范學(xué)習(xí)，靈活應(yīng)用規(guī)范學(xué)習(xí)，靈活應(yīng)用共共 29 29 頁(yè)頁(yè) 第第 3 3 頁(yè)頁(yè)計(jì)算機(jī)語(yǔ)言分類(lèi)計(jì)算機(jī)語(yǔ)言分類(lèi) 面向過(guò)程語(yǔ)言面向過(guò)程語(yǔ)言 面向?qū)ο笳Z(yǔ)言面向?qū)ο笳Z(yǔ)言FORTRANFORTRAN

2、BASICBASICC CPASCALPASCALCOBOLCOBOLLISPLISPC+C+C#C#Visual CVisual CVisual BASICVisual BASICVisual J+Visual J+系統(tǒng)軟件設(shè)計(jì)系統(tǒng)軟件設(shè)計(jì)具有圖形功能具有圖形功能科學(xué)計(jì)算科學(xué)計(jì)算商用商用人工智能人工智能共共 29 29 頁(yè)頁(yè) 第第 4 4 頁(yè)頁(yè)一、一、 程序設(shè)計(jì)的基本概念程序設(shè)計(jì)的基本概念 計(jì)算機(jī)的別名：數(shù)據(jù)處理機(jī)計(jì)算機(jī)的別名：數(shù)據(jù)處理機(jī) 數(shù)據(jù)元素：數(shù)據(jù)的最小單位數(shù)據(jù)元素：數(shù)據(jù)的最小單位 數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)元素的組織形式數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)元素的組織形式程序設(shè)計(jì)程序設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)算法算法方法方法

3、工具工具數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣決定了數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣決定了 軟件或程序的復(fù)雜程度和面貌軟件或程序的復(fù)雜程度和面貌一個(gè)程序應(yīng)包括兩個(gè)方面的內(nèi)容一個(gè)程序應(yīng)包括兩個(gè)方面的內(nèi)容: : 對(duì)數(shù)據(jù)的描述：數(shù)據(jù)結(jié)構(gòu)對(duì)數(shù)據(jù)的描述：數(shù)據(jù)結(jié)構(gòu) 對(duì)操作的描述：算法對(duì)操作的描述：算法完整的程序設(shè)計(jì)應(yīng)該是完整的程序設(shè)計(jì)應(yīng)該是: :共共 29 29 頁(yè)頁(yè) 第第 5 5 頁(yè)頁(yè)程序設(shè)計(jì)步驟程序設(shè)計(jì)步驟 分析問(wèn)題，建立數(shù)學(xué)模型分析問(wèn)題，建立數(shù)學(xué)模型 確定數(shù)據(jù)結(jié)構(gòu)確定數(shù)據(jù)結(jié)構(gòu) 確定算法，描述算法確定算法，描述算法 編制程序，調(diào)試程序編制程序，調(diào)試程序 運(yùn)行結(jié)果運(yùn)行結(jié)果xnns1共共 29 29 頁(yè)頁(yè) 第第 6 6 頁(yè)頁(yè)1. 1. 算法的概念

4、算法的概念二、算法和算法的表示二、算法和算法的表示 “一個(gè)算法，就是一個(gè)有窮規(guī)則的一個(gè)算法，就是一個(gè)有窮規(guī)則的集合，其中之規(guī)則規(guī)定了一個(gè)解決某一集合，其中之規(guī)則規(guī)定了一個(gè)解決某一特定類(lèi)型的問(wèn)題的運(yùn)算序列。特定類(lèi)型的問(wèn)題的運(yùn)算序列?！?任何解任何解決問(wèn)題的過(guò)程都是由一定的步驟組成的，決問(wèn)題的過(guò)程都是由一定的步驟組成的，把把解決問(wèn)題確定的方法和有限的步驟稱(chēng)解決問(wèn)題確定的方法和有限的步驟稱(chēng)作為算法作為算法。共共 29 29 頁(yè)頁(yè) 第第 7 7 頁(yè)頁(yè)算法分析：算法分析：這是一個(gè)數(shù)值運(yùn)算問(wèn)題。其中這是一個(gè)數(shù)值運(yùn)算問(wèn)題。其中M M代表要計(jì)算的函數(shù)值，有兩個(gè)不同的表代表要計(jì)算的函數(shù)值，有兩個(gè)不同的表達(dá)式，根

5、據(jù)達(dá)式，根據(jù)x x的取值決定采用哪一個(gè)算式。的取值決定采用哪一個(gè)算式。根據(jù)計(jì)算機(jī)具有邏輯判斷的基本功能，根據(jù)計(jì)算機(jī)具有邏輯判斷的基本功能，用計(jì)算機(jī)解題的算法如下：用計(jì)算機(jī)解題的算法如下：axaxcxcaabxxM22)()(共共 29 29 頁(yè)頁(yè) 第第 8 8 頁(yè)頁(yè) 將將a a、b b、c c和和x x的值輸入到計(jì)算機(jī)；的值輸入到計(jì)算機(jī)； 判斷判斷xa?xa?如果條件成立，執(zhí)行第步，如果條件成立，執(zhí)行第步，否則執(zhí)行第步；否則執(zhí)行第步； 按表達(dá)式按表達(dá)式bx+abx+a2 2計(jì)算出結(jié)果存放到計(jì)算出結(jié)果存放到M M中，中，然后執(zhí)行第步；然后執(zhí)行第步； 按表達(dá)式按表達(dá)式a(c-x)+ca(c-x)+

6、c2 2計(jì)算出結(jié)果存放到計(jì)算出結(jié)果存放到M M中，然后執(zhí)行第步；中，然后執(zhí)行第步； 輸出輸出M M的值；的值； 算法結(jié)束。算法結(jié)束。共共 29 29 頁(yè)頁(yè) 第第 9 9 頁(yè)頁(yè)（1）交換兩個(gè)變量的值）交換兩個(gè)變量的值采用間接交換方法采用間接交換方法 a tb (2)計(jì)數(shù)器和累加器計(jì)數(shù)器和累加器計(jì)數(shù)器：用于統(tǒng)計(jì)循環(huán)的次數(shù)。計(jì)數(shù)器：用于統(tǒng)計(jì)循環(huán)的次數(shù)。如：如： i=i+1累加器：用于實(shí)現(xiàn)數(shù)值求和。累加器：用于實(shí)現(xiàn)數(shù)值求和。如：如： sum=sum+x共共 29 29 頁(yè)頁(yè) 第第 1010 頁(yè)頁(yè)算法分析：這是一個(gè)非數(shù)值運(yùn)算問(wèn)題。因?yàn)閮蓚€(gè)瓶子的墨水不能直接交換，所以，解決這一問(wèn)題的關(guān)鍵是需要引入第三個(gè)墨

7、水瓶。設(shè)第三個(gè)墨水瓶為白色，其交換步驟如下：共共 29 29 頁(yè)頁(yè) 第第 1111 頁(yè)頁(yè)將藍(lán)瓶中的黑墨水裝入白瓶中將藍(lán)瓶中的黑墨水裝入白瓶中將黑瓶中的藍(lán)墨水裝入藍(lán)瓶中將黑瓶中的藍(lán)墨水裝入藍(lán)瓶中將白瓶中的黑墨水裝入黑瓶中將白瓶中的黑墨水裝入黑瓶中交換結(jié)束交換結(jié)束共共 29 29 頁(yè)頁(yè) 第第 1212 頁(yè)頁(yè)（3 3）枚舉法（窮舉法或試湊法）枚舉法（窮舉法或試湊法） 根據(jù)題目的部分條件確定答案的大致范圍，然根據(jù)題目的部分條件確定答案的大致范圍，然后在此范圍內(nèi)對(duì)所有可能的情況逐一驗(yàn)證，直到所后在此范圍內(nèi)對(duì)所有可能的情況逐一驗(yàn)證，直到所有情況驗(yàn)證完。若某個(gè)情況符合題目條件，則為本有情況驗(yàn)證完。若某個(gè)情況

8、符合題目條件，則為本題的一個(gè)答案；若全部情況驗(yàn)證完后均不符合題目題的一個(gè)答案；若全部情況驗(yàn)證完后均不符合題目的條件，則問(wèn)題無(wú)解。的條件，則問(wèn)題無(wú)解。 如：百元買(mǎi)百雞問(wèn)題。如：百元買(mǎi)百雞問(wèn)題。 (4)(4)遞推法（迭代法）遞推法（迭代法） 利用問(wèn)題本身所具有的某種遞推關(guān)系求解問(wèn)題。利用問(wèn)題本身所具有的某種遞推關(guān)系求解問(wèn)題。 從初值出發(fā)，歸納出新值與舊值間直到最后值為從初值出發(fā)，歸納出新值與舊值間直到最后值為止存在的關(guān)系，從而把一個(gè)復(fù)雜的計(jì)算過(guò)程轉(zhuǎn)換為簡(jiǎn)止存在的關(guān)系，從而把一個(gè)復(fù)雜的計(jì)算過(guò)程轉(zhuǎn)換為簡(jiǎn)單過(guò)程的多次重復(fù)，每次重復(fù)都從舊值的基礎(chǔ)上遞推單過(guò)程的多次重復(fù)，每次重復(fù)都從舊值的基礎(chǔ)上遞推出新值，

9、并由新值代替舊值。出新值，并由新值代替舊值。 如：求高次方程的近似解問(wèn)題。如：求高次方程的近似解問(wèn)題。共共 29 29 頁(yè)頁(yè) 第第 1313 頁(yè)頁(yè)（5 5）求最大值、最小值問(wèn)題）求最大值、最小值問(wèn)題 采用如同打擂臺(tái)的方法。采用如同打擂臺(tái)的方法。 在在n n個(gè)數(shù)中，先假設(shè)第一個(gè)數(shù)為最大值，個(gè)數(shù)中，先假設(shè)第一個(gè)數(shù)為最大值，成為擂主，依次同第成為擂主，依次同第2 2，3 3，n n個(gè)數(shù)據(jù)逐一個(gè)數(shù)據(jù)逐一比較，一旦某個(gè)數(shù)大，馬上替換擂主；所有比較，一旦某個(gè)數(shù)大，馬上替換擂主；所有值比較完，最大值也就獲得。值比較完，最大值也就獲得。 求最小值問(wèn)題則先假設(shè)第一個(gè)數(shù)為最小值求最小值問(wèn)題則先假設(shè)第一個(gè)數(shù)為最小值

10、。 共共 29 29 頁(yè)頁(yè) 第第 1414 頁(yè)頁(yè) 算法是一個(gè)有窮規(guī)則的集合，這些規(guī)則確定了算法是一個(gè)有窮規(guī)則的集合，這些規(guī)則確定了解決某類(lèi)問(wèn)題的一個(gè)運(yùn)算序列。解決某類(lèi)問(wèn)題的一個(gè)運(yùn)算序列。 算法的基本特征：算法的基本特征：l有窮性：有窮性：算法必須在執(zhí)行有限個(gè)操作后終止；算法必須在執(zhí)行有限個(gè)操作后終止； l確定性：確定性：算法中每一步的含義必須是確切的，算法中每一步的含義必須是確切的，不可出現(xiàn)任何二義性；不可出現(xiàn)任何二義性；l有效性：有效性：算法中的每一步操作都應(yīng)該能有效執(zhí)算法中的每一步操作都應(yīng)該能有效執(zhí)行，一個(gè)不可執(zhí)行的操作是無(wú)效的；行，一個(gè)不可執(zhí)行的操作是無(wú)效的；l有零個(gè)或多個(gè)輸入有零個(gè)或多

11、個(gè)輸入 ；l有一個(gè)或多個(gè)輸出有一個(gè)或多個(gè)輸出。共共 29 29 頁(yè)頁(yè) 第第 1515 頁(yè)頁(yè)可以用不同的方法表示算法，常用方法有：可以用不同的方法表示算法，常用方法有：自然語(yǔ)言自然語(yǔ)言傳統(tǒng)流程圖傳統(tǒng)流程圖結(jié)構(gòu)化流程圖結(jié)構(gòu)化流程圖偽代碼偽代碼 介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的用文字和介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的用文字和符號(hào)來(lái)描述算法的工具。一種假的代碼，不符號(hào)來(lái)描述算法的工具。一種假的代碼，不能被計(jì)算機(jī)所理解，便于轉(zhuǎn)換成編程語(yǔ)言。能被計(jì)算機(jī)所理解，便于轉(zhuǎn)換成編程語(yǔ)言。共共 29 29 頁(yè)頁(yè) 第第 1616 頁(yè)頁(yè)(1)(1)用用流程圖流程圖表示表示算法算法 美國(guó)國(guó)家標(biāo)準(zhǔn)化協(xié)會(huì)美國(guó)國(guó)家標(biāo)準(zhǔn)化協(xié)會(huì)ANS

12、I(American ANSI(American National Standard Institute)National Standard Institute)規(guī)定了規(guī)定了一些常用的流程圖符號(hào)：一些常用的流程圖符號(hào)：起止框起止框判斷框判斷框處理框處理框輸入輸入/輸出框輸出框注釋框注釋框流向線流向線連接點(diǎn)連接點(diǎn)共共 29 29 頁(yè)頁(yè) 第第 1717 頁(yè)頁(yè)例：例： 有有50個(gè)學(xué)生個(gè)學(xué)生 ，要求將他們之中成績(jī)?cè)?，要求將他們之中成?jī)?cè)?0分以上分以上者打印出來(lái)。用者打印出來(lái)。用g代表學(xué)生成績(jī)，代表學(xué)生成績(jī)， gi 代表第代表第i個(gè)學(xué)生成個(gè)學(xué)生成績(jī)?？?jī)。算法可表示如下：算法可表示如下：S1：1i S2

13、：如果：如果gi 80 ，則打印，則打印 gi ，否則不打印，否則不打印S3： i+1 i S4: 如果如果 i 50, 返回返回S2， 繼續(xù)執(zhí)行；繼續(xù)執(zhí)行； 否則，算法結(jié)束。否則，算法結(jié)束。共共 29 29 頁(yè)頁(yè) 第第 1818 頁(yè)頁(yè)開(kāi)始開(kāi)始1 igi=80輸出輸出gii+1 ii50結(jié)束結(jié)束YNN程序流程圖示例程序流程圖示例共共 29 29 頁(yè)頁(yè) 第第 1919 頁(yè)頁(yè) 傳統(tǒng)流程圖的弊端傳統(tǒng)流程圖的弊端 傳統(tǒng)流程圖用流程線指出各框的執(zhí)行順序，傳統(tǒng)流程圖用流程線指出各框的執(zhí)行順序，對(duì)流程線的使用沒(méi)有嚴(yán)格限制。因此，使用者對(duì)流程線的使用沒(méi)有嚴(yán)格限制。因此，使用者可以毫不受限制地使流程隨意地轉(zhuǎn)向，

14、使流程可以毫不受限制地使流程隨意地轉(zhuǎn)向，使流程圖變得毫無(wú)規(guī)律，閱讀者要花很大精力去追蹤圖變得毫無(wú)規(guī)律，閱讀者要花很大精力去追蹤流程，使人難以理解算法的邏輯。如圖：流程，使人難以理解算法的邏輯。如圖：共共 29 29 頁(yè)頁(yè) 第第 2020 頁(yè)頁(yè)傳統(tǒng)流程圖的流程可以是：缺點(diǎn)：缺點(diǎn)：難以閱讀、修改，使算法的可靠性和可維難以閱讀、修改，使算法的可靠性和可維護(hù)性難以保證。護(hù)性難以保證。解決辦法：解決辦法：必須限制箭頭的濫用，即不允許無(wú)規(guī)必須限制箭頭的濫用，即不允許無(wú)規(guī)律地使流程隨意轉(zhuǎn)向，只能順序的進(jìn)行下去。律地使流程隨意轉(zhuǎn)向，只能順序的進(jìn)行下去。 共共 29 29 頁(yè)頁(yè) 第第 2121 頁(yè)頁(yè)（2 2）N

15、 NS S流程圖流程圖 N NS S流程圖流程圖 由美國(guó)學(xué)者由美國(guó)學(xué)者I.I.N Nassiassi和和B.B.S Shneidermanhneiderman提出表提出表示算法的圖形工具。基本單元是矩形框示算法的圖形工具。基本單元是矩形框, ,用不同用不同的形狀線分割的形狀線分割, ,表示三種結(jié)構(gòu)表示三種結(jié)構(gòu). .只有一個(gè)入口只有一個(gè)入口, ,一一個(gè)出口個(gè)出口, ,沒(méi)有流程線。沒(méi)有流程線。 N-SN-S圖的優(yōu)點(diǎn)圖的優(yōu)點(diǎn) 比文字描述直觀、形象、比文字描述直觀、形象、 易于理解；比傳易于理解；比傳統(tǒng)流程圖緊湊易畫(huà)。尤其是它廢除了流程線，整統(tǒng)流程圖緊湊易畫(huà)。尤其是它廢除了流程線，整個(gè)算法結(jié)構(gòu)是由各個(gè)

16、基本結(jié)構(gòu)按順序組成的，個(gè)算法結(jié)構(gòu)是由各個(gè)基本結(jié)構(gòu)按順序組成的，N-N-S-S流程圖中的上下順序就是執(zhí)行時(shí)的順序。流程圖中的上下順序就是執(zhí)行時(shí)的順序。共共 29 29 頁(yè)頁(yè) 第第 2222 頁(yè)頁(yè)0t,0ii+1i t+it直到直到 i 100輸出輸出 t 的值的值傳統(tǒng)流程圖與傳統(tǒng)流程圖與N-SN-S流程圖的比較流程圖的比較i 100不成立不成立成立成立開(kāi)始開(kāi)始 0t,0ii+1i t+it輸出輸出 t 的值的值結(jié)束結(jié)束例例1 1：1+2+3+1+2+3+ + 加到加到100100為止為止共共 29 29 頁(yè)頁(yè) 第第 2323 頁(yè)頁(yè)三、程序的三種基本結(jié)構(gòu)三、程序的三種基本結(jié)構(gòu)(1) 順序結(jié)構(gòu)順序結(jié)

17、構(gòu) 程序按照語(yǔ)句的書(shū)寫(xiě)次序順序執(zhí)行。程序按照語(yǔ)句的書(shū)寫(xiě)次序順序執(zhí)行。 BA 先執(zhí)行先執(zhí)行A操作，再執(zhí)行操作，再執(zhí)行B操作，兩者是順序執(zhí)行關(guān)系。操作，兩者是順序執(zhí)行關(guān)系。共共 29 29 頁(yè)頁(yè) 第第 2424 頁(yè)頁(yè) (2) 選擇結(jié)構(gòu)選擇結(jié)構(gòu) 通過(guò)判斷特定條件，選擇一個(gè)分支執(zhí)行。通過(guò)判斷特定條件，選擇一個(gè)分支執(zhí)行。當(dāng)當(dāng)P條件成立時(shí)，執(zhí)行條件成立時(shí)，執(zhí)行A操作，否則執(zhí)行操作，否則執(zhí)行B操作操作APB 成立成立不成立不成立 語(yǔ)句語(yǔ)句不成立不成立 P成立成立當(dāng)當(dāng)P條件成立時(shí)，執(zhí)行語(yǔ)句操作，否則跳過(guò)語(yǔ)句操作條件成立時(shí)，執(zhí)行語(yǔ)句操作，否則跳過(guò)語(yǔ)句操作共共 29 29 頁(yè)頁(yè) 第第 2525 頁(yè)頁(yè) ( 3)循環(huán)

18、結(jié)構(gòu)循環(huán)結(jié)構(gòu) 在給定條件下，反復(fù)執(zhí)行循環(huán)體，直到條件不滿(mǎn)足為止在給定條件下，反復(fù)執(zhí)行循環(huán)體，直到條件不滿(mǎn)足為止.1)形式a不成立不成立 PA成立成立 當(dāng)當(dāng)P條件成立時(shí)，反復(fù)執(zhí)行條件成立時(shí)，反復(fù)執(zhí)行A,直到直到P為零為止。為零為止。共共 29 29 頁(yè)頁(yè) 第第 2626 頁(yè)頁(yè)2)2)形式形式b b先執(zhí)行先執(zhí)行A操作，再判斷操作，再判斷P是否成立，若是否成立，若P成立，再執(zhí)成立，再執(zhí)行行A，直到，直到P不成立為止。不成立為止。AP成立成立不成立不成立 共共 29 29 頁(yè)頁(yè) 第第 2727 頁(yè)頁(yè) 三種基本程序結(jié)構(gòu)的三種基本程序結(jié)構(gòu)的NSNS流程圖流程圖條件條件YNS1 S22.2.選擇結(jié)構(gòu)選擇結(jié)構(gòu)S1S21.1.順序結(jié)構(gòu)順序結(jié)構(gòu)3.3.循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu) 循環(huán)體循環(huán)體循環(huán)體循環(huán)體當(dāng)滿(mǎn)足條件時(shí)當(dāng)滿(mǎn)足條件時(shí)直到條件滿(mǎn)足時(shí)直到條件滿(mǎn)足時(shí)當(dāng)型循環(huán)當(dāng)型循環(huán)直到型循環(huán)直到型循環(huán)共共 29 29 頁(yè)頁(yè) 第第 2828 頁(yè)頁(yè)四、結(jié)構(gòu)化程序設(shè)計(jì)方法四、結(jié)構(gòu)化程序設(shè)計(jì)方法