1、C語言程序設(shè)計教程（第2版）,第3章 簡單算法設(shè)計,第3章 程序的簡單算法制定,本章主要內(nèi)容 1. 結(jié)構(gòu)化程序的算法設(shè)計 2. 結(jié)構(gòu)化算法的性質(zhì)及結(jié)構(gòu) 3. 結(jié)構(gòu)化算法的描述方法 4. 結(jié)構(gòu)化算法流程圖,第3章 程序的簡單算法制定,算法： 解決問題的方法和要遵循的步驟。 算法描述了程序要執(zhí)行的操作及操作的步驟順序。 程序的功能是通過算法來描述的。 C語言程序是一種結(jié)構(gòu)化的程序。 結(jié)構(gòu)化程序： 問題可以分解成相互獨立的幾個部分。 每個獨立部分可以通過簡單的語句或結(jié)構(gòu)來實現(xiàn)。 分問題解的過程就是算法設(shè)計的過程。 重點：掌握分析問題、解決問題的方法。,3.1 結(jié)構(gòu)化程序的算法設(shè)計,【例3-1】 要求

2、從鍵盤輸入3個數(shù)，找出其中最小的那個數(shù)，將其輸出到屏幕。請給出解決這個問題的算法。 分析：程序?qū)τ趶逆I盤輸入的3個數(shù)必須用3個變量來保存，分別為a，b，c代表輸入的3個數(shù)，另外，還需要一個變量min來保存最小的那個數(shù)。 1.先比較a和b的值，把數(shù)值小的放入min中； 2.再將min與c比較，又把數(shù)值小的放入min中。 3.經(jīng)過兩次比較，min中已存放的是a，b，c 3個數(shù)中最小的數(shù)。把min的值輸出就是所需結(jié)果。,3.1 結(jié)構(gòu)化程序的算法設(shè)計,算法步驟： 1輸入3個數(shù)，其值分別賦給3個變量a，b，c； 2把a與b中較小的那個數(shù)放入變量min中； 3把c與min中較小的那個數(shù)放入變量min中；

3、4輸出最后結(jié)果min的值。 改進上面的算法描述，將第2步和第3步的算法具體化。 1輸入三個數(shù)，其值分別賦給三個變量a，b，c； 2比較a與b的值，如果ab，則min=a；否則min=b； 3比較c與min的值，如果cmin，則min=c； 4輸出最后結(jié)果min的值。 通過算法描述的步驟，可以很方便地用程序語言來實現(xiàn)。,3.2 結(jié)構(gòu)化算法的性質(zhì)及結(jié)構(gòu),3.2.1 結(jié)構(gòu)化算法性質(zhì) 1算法名稱 給算法命名，是為了方便算法的描述，在C語言中，算法的名字通常就是函數(shù)名。 2輸入 算法應(yīng)有輸入的數(shù)據(jù)或初始條件。 3輸出 算法通常會有一個或多個輸出，是對輸入數(shù)據(jù)加工后的結(jié)果。 4有效性 算法的每一步都是可執(zhí)

4、行的，可通過人工計算的。 5正確性 算法的結(jié)果必須是正確的，可驗證的。 6有限性 任何算法必須在執(zhí)行有限條指令后結(jié)束。,3.2 結(jié)構(gòu)化算法的性質(zhì)及結(jié)構(gòu),3.2.2 結(jié)構(gòu)化算法的結(jié)構(gòu) 在C語言算法的主要結(jié)構(gòu)有如下3種。 1順序結(jié)構(gòu) 順序結(jié)構(gòu)的特點： 程序在執(zhí)行過程中是按語句的先后順序來執(zhí)行的，每一條語句都代表著一個功能， 2分支結(jié)構(gòu) 分支結(jié)構(gòu)的特點： 程序在執(zhí)行過程中，會根據(jù)條件的不同有選擇的執(zhí)行不同的功能。 3循環(huán)結(jié)構(gòu) 循環(huán)結(jié)構(gòu)的特點： 程序在執(zhí)行過程中，在一定的時間段內(nèi)或一定的條件下，重復(fù)地執(zhí)行某個功能，直到時間已到或條件不再滿足。,3.2 結(jié)構(gòu)化算法的性質(zhì)及結(jié)構(gòu),程序設(shè)計要解決的兩個主要問

5、題： （1）按什么順序或步驟來執(zhí)行； （2）用什么語句來實現(xiàn)。 算法設(shè)計是核心問題。,提示,3.3 結(jié)構(gòu)化算法的描述方法,常用的描述方法有自然語言、流程圖、偽代碼等。 3.3.1 自然語言 用類自然語言表示算法。 如：漢語、英語或其他語言。 特點：通俗易懂，簡單明了。,3.3 結(jié)構(gòu)化算法的描述方法,【例3-2】 從鍵盤輸入兩個變量的值a、b，請按輸入值從小到大的順序?qū)⑦@兩個變量的值輸出到屏幕。請寫出這個問題的算法描述。 算法描述： 第1步：輸入變量a和b的值； 第2步：比較a和b的值； 如果a大于等于b，則先輸出a，再輸出b； 否則，先輸出b，再輸出a； 第3步：算法結(jié)束。,3.3 結(jié)構(gòu)化算法

6、的描述方法,【例3-3】 幾何級數(shù)求和：sum=1+2+3+4+5+(n1)+n。請寫出該問題的算法。 算法描述： 第1步：給定一個大于0的正整數(shù)n的值； 第2步：定義一個整型變量i，設(shè)其初始值1； 第3步：定義整型變量sum，其初始值設(shè)置為0； 第4步：如果i小于等于n，則轉(zhuǎn)第5步，否則執(zhí)行第8步； 第5步：將sum的值加上i的值后，重新賦值給sum； 第6步：將i的值加1，重新賦值給i； 第7步：執(zhí)行第4步； 第8步：輸出sum 的值； 第9步：算法結(jié)束。,3.3 結(jié)構(gòu)化算法的描述方法,3.3.2 流程圖 流程圖是一種算法的形象表示。 流程圖是由流程線和幾何圖形框連接而成的。 算法流程圖的

7、符號采用美國國家標(biāo)準(zhǔn)化協(xié)會(ANSI)規(guī)定的一些常用符號：,流程線,算法流程圖的3種基本結(jié)構(gòu)： 順序結(jié)構(gòu)、分支結(jié)構(gòu)、循環(huán)結(jié)構(gòu) 1.順序結(jié)構(gòu) 順序結(jié)構(gòu)是一種簡單的線性結(jié)構(gòu)，根據(jù)流程線所示的方向，按順序執(zhí)行各矩形框的指令。 基本流程圖：,注： 指令A(yù)、指令B、指令C可以是一條或多條指令。 執(zhí)行順序：ABC。,3.3 結(jié)構(gòu)化算法的描述方法,3.3 結(jié)構(gòu)化算法的描述方法,2.分支結(jié)構(gòu) 分支結(jié)構(gòu)要對給定的條件進行判斷，看是否滿足給定的條件，根據(jù)條件結(jié)果的真假而分別執(zhí)行不同的執(zhí)行框。 基本流程圖有兩種：,注： (1) 虛線框表示可將分支結(jié)構(gòu)看成一個矩形框。 (2)指令A(yù)、指令B可以是一條或多條指令，也可以

8、是分支結(jié)構(gòu)。,3.3 結(jié)構(gòu)化算法的描述方法,3.循環(huán)結(jié)構(gòu) 分支結(jié)構(gòu)是在條件為真的情況下，重復(fù)執(zhí)行某個執(zhí)行框中的內(nèi)容。 基本流程圖有兩種：,注：(1) 虛線框表示可將循環(huán)結(jié)構(gòu)看成一個矩形框。 (2) 指令A(yù)稱為循環(huán)體，可以是一條或多條指令，也可以是其 他分支或循環(huán)結(jié)構(gòu)。 (3) do_while結(jié)構(gòu)可以轉(zhuǎn)化成while結(jié)構(gòu)。,(1) while 循環(huán)：,(2) do_ while 循環(huán)：,3.3 結(jié)構(gòu)化算法的描述方法,循環(huán)結(jié)構(gòu)的特點： 在循環(huán)體指令A(yù)中必須要有對條件的值進行修改的語句，使得經(jīng)過有限次循環(huán)后，循環(huán)一定能結(jié)束。 while型循環(huán)中循環(huán)體可能一次都不執(zhí)行，而do_while型循環(huán)則至少

9、執(zhí)行一次循環(huán)。 do_while型循環(huán)可以轉(zhuǎn)化成為while型循環(huán)結(jié)構(gòu)，但while型循環(huán)不一定能轉(zhuǎn)化為do_while型循環(huán)。,3.3 結(jié)構(gòu)化算法的描述方法,關(guān)于結(jié)構(gòu)化流程圖的規(guī)則： 1. 可分別將順序結(jié)構(gòu)、分支結(jié)構(gòu)、循環(huán)結(jié)構(gòu)的基本流程圖看成是一個執(zhí)行框。 2. 任何兩個按順序的執(zhí)行框可以合并為一個執(zhí)行框。 反復(fù)運用規(guī)則1和規(guī)則2可得到結(jié)構(gòu)化流程圖的最簡形式：,特別提示,3.3 結(jié)構(gòu)化算法的描述方法,【例3-4】分析下面的流程圖，是否符合結(jié)構(gòu)化算法標(biāo)準(zhǔn)。,3.3 結(jié)構(gòu)化算法的描述方法,【例3- 5 】將例3-1的算法用流程圖表示，分析其是否符合結(jié) 構(gòu)化的標(biāo)準(zhǔn)。 從鍵盤輸入3個數(shù)，找出其中最小

10、的那個數(shù)，將其輸出到屏幕。,3.3 結(jié)構(gòu)化算法的描述方法,【例3-6】 將例3-2所描述的問題用算法流程圖來表示。 從鍵盤輸入兩個整型變量a，b的值，按輸入值從小到大的順序輸出到屏幕。 算法流程圖為：,3.3 結(jié)構(gòu)化算法的描述方法,【例3-7】將例3-3所描述的問題用算法流程圖來表示。 計算幾何級數(shù)的和：sum=1+2+3+4+5+(n1)+n。 算法流程圖為：,3.3 結(jié)構(gòu)化算法的描述方法,3.3.3 偽代碼 偽代碼是一種接近于程序語言的算法描述方法。 特點： 采用有限的英文單詞作為偽代碼的符號系統(tǒng)，按照特定的格式來表達算法，可讀性好，方便將算法改寫成計算機的程序源代碼。 偽代碼的7個主要部

11、分： (1) 算法名稱 (2)指令序列 (3)輸出/輸出 (4)分支選擇 (5)賦值 (6)循環(huán) (7)算法結(jié)束,3.3 結(jié)構(gòu)化算法的描述方法,1算法名稱 兩種表示算法的偽代碼： 過程（Procedure）函數(shù)（Function） 過程和函數(shù)的區(qū)別是： 過程是執(zhí)行一系列的操作，不需要返回操作的結(jié)果，無返回數(shù)據(jù)； 函數(shù)是執(zhí)行一系列的操作后，要將操作的結(jié)果返回，有返回數(shù)據(jù)。 算法偽代碼的書寫規(guī)則： Procedure () Function () 如： Procedure Hanoi_Tower() 表示名為Hanoi_Tower的一個過程。 Function Fac(x) 表示名為Fac的一個函數(shù)。 Function Prog (n) 表示名為Prog的一個函數(shù)。,3.4 算法設(shè)計范例,【例3-11】 把從鍵盤輸入的大寫字母轉(zhuǎn)換成小寫字母輸出，若為小寫字母或其他字符，則不作任何轉(zhuǎn)換直接輸出。 分析：用字符變量ch來接收從鍵盤輸入的字符。大、小寫字母的ASCII碼值相差32，大寫字母A的值為65，而小寫字母a的值為97。 流程圖描述的算法：,3.4 算法設(shè)計范例,【例3-12】 已知實數(shù)a，b，計算u的值：u=(r+s)2，