C語(yǔ)言程序設(shè)計(jì)第3版算法與程序設(shè)計(jì)基礎(chǔ)

1、共 32 頁(yè) 第 1 1 頁(yè)共 32 頁(yè) 第 2 2 頁(yè)共 32 頁(yè) 第 3 3 頁(yè) 計(jì)算機(jī)語(yǔ)言：是規(guī)則和符號(hào)的集合，是與計(jì)算機(jī)語(yǔ)言：是規(guī)則和符號(hào)的集合，是與計(jì)算機(jī)交流的工具。必須具有數(shù)據(jù)表達(dá)和計(jì)算機(jī)交流的工具。必須具有數(shù)據(jù)表達(dá)和數(shù)據(jù)處理（流程控制）的能力。數(shù)據(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)用共 32 頁(yè)

2、 第 4 4 頁(yè)計(jì)算機(jī)語(yǔ)言分類計(jì)算機(jī)語(yǔ)言分類 面向過(guò)程語(yǔ)言面向過(guò)程語(yǔ)言 面向?qū)ο笳Z(yǔ)言面向?qū)ο笳Z(yǔ)言FORTRANFORTRANBASICBASICC CPASCALPASCALCOBOLCOBOLLISPLISPC+C+C#C#Visual CVisual CVisual BASICVisual BASICVisual J+Visual J+系統(tǒng)軟件設(shè)計(jì)系統(tǒng)軟件設(shè)計(jì)具有圖形功能具有圖形功能科學(xué)計(jì)算科學(xué)計(jì)算商用商用人工智能人工智能共 32 頁(yè) 第 5 5 頁(yè)1.1 1.1 程序設(shè)計(jì)的基本概念程序設(shè)計(jì)的基本概念 數(shù)據(jù)元素：數(shù)據(jù)的最小單位數(shù)據(jù)元素：數(shù)據(jù)的最小單位 數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)元素的組織形式數(shù)據(jù)結(jié)構(gòu)：

3、數(shù)據(jù)元素的組織形式程序設(shè)計(jì)程序設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)算法算法方法方法工具工具數(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)該包括四部分: :共 32 頁(yè) 第 6 6 頁(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é)果x

4、nns1 一個(gè)正確的程序通常包含兩方面的含義：一是書(shū)寫(xiě)正一個(gè)正確的程序通常包含兩方面的含義：一是書(shū)寫(xiě)正確，二是結(jié)果正確。書(shū)寫(xiě)正確是指程序語(yǔ)法正確，符合程確，二是結(jié)果正確。書(shū)寫(xiě)正確是指程序語(yǔ)法正確，符合程序語(yǔ)言的規(guī)則；結(jié)果正確是指對(duì)應(yīng)于正確的輸入，程序能序語(yǔ)言的規(guī)則；結(jié)果正確是指對(duì)應(yīng)于正確的輸入，程序能夠得到所期望的輸出。夠得到所期望的輸出。共 32 頁(yè) 第 7 7 頁(yè)程序的三種基本結(jié)構(gòu)1.1.順序結(jié)構(gòu)順序結(jié)構(gòu) 程序按照語(yǔ)句的書(shū)寫(xiě)次序順序執(zhí)行。程序按照語(yǔ)句的書(shū)寫(xiě)次序順序執(zhí)行。 BA 先執(zhí)行先執(zhí)行A A操作，再執(zhí)行操作，再執(zhí)行B B操作，兩者是順序執(zhí)行關(guān)系。操作，兩者是順序執(zhí)行關(guān)系。共 32 頁(yè)

5、第 8 8 頁(yè) 2. 2.選擇結(jié)構(gòu)選擇結(jié)構(gòu) 通過(guò)判斷特定條件，選擇一個(gè)分支執(zhí)行。通過(guò)判斷特定條件，選擇一個(gè)分支執(zhí)行。當(dāng)當(dāng)P P條件成立時(shí)，執(zhí)行條件成立時(shí)，執(zhí)行A A操作，否則執(zhí)行操作，否則執(zhí)行B B操作操作APB 成立成立不成立不成立 語(yǔ)句語(yǔ)句不成立不成立 P成立成立當(dāng)當(dāng)P P條件成立時(shí)，執(zhí)行語(yǔ)句操作，否則跳過(guò)語(yǔ)句操作條件成立時(shí)，執(zhí)行語(yǔ)句操作，否則跳過(guò)語(yǔ)句操作共 32 頁(yè) 第 9 9 頁(yè) 3. 循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu) 在給定條件下，反復(fù)執(zhí)行循環(huán)體，直到條件不滿足為止在給定條件下，反復(fù)執(zhí)行循環(huán)體，直到條件不滿足為止. .(1)形式形式a （當(dāng)型循環(huán)結(jié)構(gòu)）（當(dāng)型循環(huán)結(jié)構(gòu)）不成立不成立 PA成立成立 當(dāng)當(dāng)

6、P P條件成立時(shí)，反復(fù)執(zhí)行條件成立時(shí)，反復(fù)執(zhí)行A,A,直到直到P P為零為止。為零為止。共 32 頁(yè) 第 1010 頁(yè)(2)(2)形式形式b b （直到型循環(huán)結(jié)構(gòu)）（直到型循環(huán)結(jié)構(gòu)）先執(zhí)行先執(zhí)行A A操作，再判斷操作，再判斷P P是否成立，若是否成立，若P P成立，再執(zhí)成立，再執(zhí)行行A A，直到，直到P P不成立為止。不成立為止。AP成立成立不成立不成立 共 32 頁(yè) 第 1111 頁(yè)1. 1. 算法的概念算法的概念1.2 1.2 算法概述算法概述 “ “一個(gè)算法，就是一個(gè)有窮規(guī)則的一個(gè)算法，就是一個(gè)有窮規(guī)則的集合，其中之規(guī)則規(guī)定了一個(gè)解決某一集合，其中之規(guī)則規(guī)定了一個(gè)解決某一特定類型的問(wèn)題的

7、運(yùn)算序列。特定類型的問(wèn)題的運(yùn)算序列?！?” 任何解任何解決問(wèn)題的過(guò)程都是由一定的步驟組成的，決問(wèn)題的過(guò)程都是由一定的步驟組成的，把把解決問(wèn)題確定的方法和有限的步驟稱解決問(wèn)題確定的方法和有限的步驟稱作為算法作為算法。共 32 頁(yè) 第 1212 頁(yè)算法分析：算法分析：這是一個(gè)數(shù)值運(yùn)算問(wèn)題。其中這是一個(gè)數(shù)值運(yùn)算問(wèn)題。其中M M代表要計(jì)算的函數(shù)值，有兩個(gè)不同的表代表要計(jì)算的函數(shù)值，有兩個(gè)不同的表達(dá)式，根據(jù)達(dá)式，根據(jù)x x的取值決定采用哪一個(gè)算式。的取值決定采用哪一個(gè)算式。根據(jù)計(jì)算機(jī)具有邏輯判斷的基本功能，根據(jù)計(jì)算機(jī)具有邏輯判斷的基本功能，用計(jì)算機(jī)解題的算法如下：用計(jì)算機(jī)解題的算法如下：axaxcxca

8、abxxM22)()(共 32 頁(yè) 第 1313 頁(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)+c2 2計(jì)算出結(jié)果存放到計(jì)算出結(jié)果存放到M M中，然后執(zhí)行第中，然后執(zhí)行第步；步； 輸出輸出M M的值；的值； 算法結(jié)束。算法結(jié)束。axaxcxcaabxxM22)()(共 32 頁(yè) 第 1414 頁(yè)算法分析：算法

9、分析：這是一個(gè)非數(shù)值運(yùn)算問(wèn)題。因這是一個(gè)非數(shù)值運(yùn)算問(wèn)題。因?yàn)閮蓚€(gè)瓶子的墨水不能直接交換，所以，為兩個(gè)瓶子的墨水不能直接交換，所以，解決這一問(wèn)題的關(guān)鍵是需要解決這一問(wèn)題的關(guān)鍵是需要引入第三個(gè)引入第三個(gè)墨水瓶墨水瓶。設(shè)第三個(gè)墨水瓶為白色，其交。設(shè)第三個(gè)墨水瓶為白色，其交換步驟如下：換步驟如下：共 32 頁(yè) 第 1515 頁(yè)將藍(lán)瓶中的黑墨水裝入白瓶中將藍(lán)瓶中的黑墨水裝入白瓶中將黑瓶中的藍(lán)墨水裝入藍(lán)瓶中將黑瓶中的藍(lán)墨水裝入藍(lán)瓶中將白瓶中的黑墨水裝入黑瓶中將白瓶中的黑墨水裝入黑瓶中交換結(jié)束交換結(jié)束共 32 頁(yè) 第 1616 頁(yè)2.2.算法的基本特征算法的基本特征 算法是一個(gè)有窮規(guī)則的集合，這些規(guī)則確定了

10、算法是一個(gè)有窮規(guī)則的集合，這些規(guī)則確定了解決某類問(wèn)題的一個(gè)運(yùn)算序列。解決某類問(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è)或多個(gè)輸入：執(zhí)行算法時(shí)，從外界獲得必執(zhí)行算法時(shí)，從外界獲得必要的信息要的信息 ；l有一個(gè)或多

11、個(gè)輸出：有一個(gè)或多個(gè)輸出：算法的解就是輸出算法的解就是輸出。共 32 頁(yè) 第 1717 頁(yè)3.3.算法的常用表示方法算法的常用表示方法可以用不同的方法表示算法，常用方法有：可以用不同的方法表示算法，常用方法有：自然語(yǔ)言自然語(yǔ)言傳統(tǒng)流程圖傳統(tǒng)流程圖結(jié)構(gòu)化流程圖結(jié)構(gòu)化流程圖 共 32 頁(yè) 第 1818 頁(yè)（1 1）自然語(yǔ)言）自然語(yǔ)言自然語(yǔ)言即是使用漢語(yǔ)、英語(yǔ)或其他語(yǔ)言去描述算法。自然語(yǔ)言即是使用漢語(yǔ)、英語(yǔ)或其他語(yǔ)言去描述算法。 例例 有有5050名學(xué)生的成績(jī)，要求將他們之中名學(xué)生的成績(jī)，要求將他們之中8080分以上的成績(jī)分以上的成績(jī)打印出來(lái)。設(shè)用打印出來(lái)。設(shè)用g g代表學(xué)生成績(jī)，代表學(xué)生成績(jī)，gi

12、 gi 代表第代表第i i個(gè)學(xué)生成績(jī)。個(gè)學(xué)生成績(jī)。算法可表示如下：算法可表示如下：1 1）使使i=1i=1 ；2 2）如果如果gi gi 80 80 ，則打印，則打印 gi gi ，否則不打印；，否則不打??；3 3）使使i i的值加的值加1 1 ；4 4）如果如果 i i 50, 50, 返回返回S2S2， 繼續(xù)執(zhí)行；繼續(xù)執(zhí)行； 否則，算法結(jié)束否則，算法結(jié)束。特點(diǎn)特點(diǎn)：描述算法通俗易懂，容易產(chǎn)生歧義。對(duì)復(fù)雜問(wèn)題，：描述算法通俗易懂，容易產(chǎn)生歧義。對(duì)復(fù)雜問(wèn)題，語(yǔ)句繁瑣、冗長(zhǎng)，并且很難清楚地表達(dá)算法的邏輯流程，語(yǔ)句繁瑣、冗長(zhǎng)，并且很難清楚地表達(dá)算法的邏輯流程，往往需要根據(jù)上下文判別其含義，尤其對(duì)描

13、述含有選擇、往往需要根據(jù)上下文判別其含義，尤其對(duì)描述含有選擇、循環(huán)結(jié)構(gòu)的算法，不太方便和直觀，一般不常使用。循環(huán)結(jié)構(gòu)的算法，不太方便和直觀，一般不常使用。共 32 頁(yè) 第 1919 頁(yè)(2)(2)傳統(tǒng)流程圖傳統(tǒng)流程圖 美國(guó)國(guó)家標(biāo)準(zhǔn)化協(xié)會(huì)美國(guó)國(guó)家標(biāo)準(zhǔn)化協(xié)會(huì)ANSI(American ANSI(American National Standard Institute)National Standard Institute)規(guī)定了規(guī)定了一些常用的流程圖符號(hào)：一些常用的流程圖符號(hào)：起止框起止框判斷框判斷框處理框處理框輸入輸入/輸出框輸出框注釋框注釋框流向線流向線連接點(diǎn)連接點(diǎn)共 32 頁(yè) 第 2020

14、頁(yè)程序流程圖表示程序流程圖表示開(kāi)始開(kāi)始1 igi=80輸出輸出gii+1 ii50結(jié)束結(jié)束成立成立不成立不成立不成立不成立成立成立傳統(tǒng)流程圖用流傳統(tǒng)流程圖用流程線指出各框的程線指出各框的執(zhí)行順序，對(duì)流執(zhí)行順序，對(duì)流程線的使用沒(méi)有程線的使用沒(méi)有嚴(yán)格限制。嚴(yán)格限制。共 32 頁(yè) 第 2121 頁(yè)傳統(tǒng)流程圖的流程可以是：缺點(diǎn)：缺點(diǎn)：使用者可以毫不受限制地使流程隨意地轉(zhuǎn)向，使用者可以毫不受限制地使流程隨意地轉(zhuǎn)向，使流程圖變得毫無(wú)規(guī)律，難以閱讀、修改，使算法的使流程圖變得毫無(wú)規(guī)律，難以閱讀、修改，使算法的可靠性和可維護(hù)性難以保證?？煽啃院涂删S護(hù)性難以保證。解決辦法：解決辦法：必須限制箭頭的濫用，即不允許

15、無(wú)規(guī)律地必須限制箭頭的濫用，即不允許無(wú)規(guī)律地使流程隨意轉(zhuǎn)向，只能順序的進(jìn)行下去。使流程隨意轉(zhuǎn)向，只能順序的進(jìn)行下去。 共 32 頁(yè) 第 2222 頁(yè)（3 3）NSNS流程圖流程圖 NSNS流程圖流程圖 由美國(guó)學(xué)者由美國(guó)學(xué)者I.I.N Nassiassi和和B.B.S Shneidermanhneiderman提出表提出表示算法的圖形工具?；締卧蔷匦慰蚴舅惴ǖ膱D形工具?；締卧蔷匦慰? ,用不同用不同的形狀線分割的形狀線分割, ,表示三種結(jié)構(gòu)。只有一個(gè)入口表示三種結(jié)構(gòu)。只有一個(gè)入口, ,一一個(gè)出口個(gè)出口, ,沒(méi)有流程線。沒(méi)有流程線。N-SN-S圖的優(yōu)點(diǎn)圖的優(yōu)點(diǎn) 比文字描述直觀、形象、比文字

16、描述直觀、形象、 易于理解；比傳易于理解；比傳統(tǒng)流程圖緊湊易畫(huà)。尤其是它廢除了流程線，整統(tǒng)流程圖緊湊易畫(huà)。尤其是它廢除了流程線，整個(gè)算法結(jié)構(gòu)是由各個(gè)基本結(jié)構(gòu)按順序組成的，個(gè)算法結(jié)構(gòu)是由各個(gè)基本結(jié)構(gòu)按順序組成的，N-N-S-S流程圖中的上下順序就是執(zhí)行時(shí)的順序。流程圖中的上下順序就是執(zhí)行時(shí)的順序。共 32 頁(yè) 第 2323 頁(yè) 三種基本程序結(jié)構(gòu)的三種基本程序結(jié)構(gòu)的NSNS流程圖流程圖條件條件TF語(yǔ)句1 語(yǔ)句22.2.選擇結(jié)構(gòu)選擇結(jié)構(gòu)語(yǔ)句1語(yǔ)句21.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)滿足條件時(shí)當(dāng)滿足條件時(shí) 直到條件成立直到條件成立循環(huán)結(jié)構(gòu)一循環(huán)結(jié)構(gòu)一循環(huán)結(jié)構(gòu)二

17、循環(huán)結(jié)構(gòu)二共 32 頁(yè) 第 2424 頁(yè)0t,0ii+1i t+it直到直到 i 100輸出輸出 t 的值的值傳統(tǒng)流程圖與傳統(tǒng)流程圖與N-SN-S流程圖的比較流程圖的比較i 100 NY開(kāi)始開(kāi)始 0t,0ii+1i t+it輸出輸出 t 的值的值結(jié)束結(jié)束例例1 1：1+2+3+ 1+2+3+ 加到加到100100為止為止共 32 頁(yè) 第 2525 頁(yè)例：例：打印打印5050名名學(xué)生中成績(jī)學(xué)生中成績(jī)高于高于8080分的分的學(xué)號(hào)和成績(jī)學(xué)號(hào)和成績(jī)用用N-SN-S圖表圖表示。示。 共 32 頁(yè) 第 2626 頁(yè)1. 1. 枚舉法（窮舉法）枚舉法（窮舉法）特點(diǎn)特點(diǎn): :算法簡(jiǎn)單，容易理解，運(yùn)算算法簡(jiǎn)單，

18、容易理解，運(yùn)算量大。量大?；舅枷耄夯舅枷耄?根據(jù)題目的部分條件確定答案的大致范圍，然后在根據(jù)題目的部分條件確定答案的大致范圍，然后在此范圍內(nèi)對(duì)所有可能的情況逐一驗(yàn)證，直到所有情況均此范圍內(nèi)對(duì)所有可能的情況逐一驗(yàn)證，直到所有情況均通過(guò)驗(yàn)證。若某個(gè)情況符合題目條件，則為本題的一個(gè)通過(guò)驗(yàn)證。若某個(gè)情況符合題目條件，則為本題的一個(gè)答案；若全部情況驗(yàn)證完后均不符合題目的條件，則問(wèn)答案；若全部情況驗(yàn)證完后均不符合題目的條件，則問(wèn)題無(wú)解。題無(wú)解。 如：百元買百雞問(wèn)題。假定小雞每只如：百元買百雞問(wèn)題。假定小雞每只0.50.5元，公雞每元，公雞每只只2 2元，母雞每只元，母雞每只3 3元?，F(xiàn)在有元?，F(xiàn)在有1

19、00100元錢要求買元錢要求買100100只雞，只雞，問(wèn)共有幾種購(gòu)雞方案？問(wèn)共有幾種購(gòu)雞方案？ 根據(jù)題目，設(shè)母雞、公雞、小雞各為根據(jù)題目，設(shè)母雞、公雞、小雞各為x,y,zx,y,z只，列出只，列出方程為：方程為：x+y+z=100 x+y+z=100，3x+2y+0.5z=1003x+2y+0.5z=100 利用窮舉法，將各種可能的組合一一測(cè)試，輸出符合利用窮舉法，將各種可能的組合一一測(cè)試，輸出符合條件的組合。即在各個(gè)變量的取值范圍內(nèi)不斷變化條件的組合。即在各個(gè)變量的取值范圍內(nèi)不斷變化x,y,zx,y,z的值，窮舉的值，窮舉x,y,zx,y,z全部可能的組合，若滿足方程組則是一全部可能的組合，若滿足方程組則是一組解。組解。 1.3 1.3 幾種常用算法介紹幾種常用算法介紹共 32 頁(yè) 第 2727 頁(yè)#include stdio.hmain() int x,y,z; printf(母雞母雞 公雞公雞 小雞