C語言教學算法

1、1第二章第二章算法以及算法的描述方法算法以及算法的描述方法2主要內(nèi)容主要內(nèi)容對數(shù)據(jù)的描述對數(shù)據(jù)的描述對操作的描述對操作的描述數(shù)據(jù)與操作間的關(guān)系數(shù)據(jù)與操作間的關(guān)系數(shù)據(jù)是操作對象，操作的目的是數(shù)據(jù)是操作對象，操作的目的是對數(shù)據(jù)進行加工處理以得到期望對數(shù)據(jù)進行加工處理以得到期望的結(jié)果。的結(jié)果。指定數(shù)據(jù)的類型和組織形式，指定數(shù)據(jù)的類型和組織形式，即：即：數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)。解決問題的操作步驟，解決問題的操作步驟，即：即：算法算法。3l 為解決一個問題而采取的方法和步驟。為解決一個問題而采取的方法和步驟。 （描述解題的操作步驟）（描述解題的操作步驟）l 計算機算法分類計算機算法分類 數(shù)值算法：數(shù)值運算（求

2、方程的根等）數(shù)值算法：數(shù)值運算（求方程的根等） 非數(shù)值算法：常用于事務管理（圖書檢索等）非數(shù)值算法：常用于事務管理（圖書檢索等）算法定義算法定義4算法的特點算法的特點有窮性有窮性確定性確定性輸入數(shù)據(jù)輸入數(shù)據(jù)輸出數(shù)據(jù)輸出數(shù)據(jù)可行性可行性、5l 用自然語言表示用自然語言表示l 用流程圖表示用流程圖表示l 用用N-S流程圖表示流程圖表示l 用偽代碼表示用偽代碼表示l 用計算機語言表示用計算機語言表示算法描述算法描述6示例示例1用用 y = x2-2x+3 計算，當計算，當 x=0,1, 2,3, 4,5 所對應的所對應的y值值1. 置置x的下界為的下界為 0；2. 置置x的上界為的上界為 n=5；3

3、. 當當xn時，重復執(zhí)行如下時，重復執(zhí)行如下3 步，步， 否則算法停止。否則算法停止。F 用公式計算用公式計算y值值F 輸出一組輸出一組x和和y的值的值F x值增加值增加1用自然語言描述用自然語言描述7l 流程圖是通過箭頭相互連接的幾何圖形來表達流程圖是通過箭頭相互連接的幾何圖形來表達 程序運行的方法。程序運行的方法。 流程圖流程圖ANSI規(guī)定的規(guī)定的一些常用流一些常用流程圖符號。程圖符號。起止框起止框輸入輸出框輸入輸出框判斷框判斷框處理框處理框流程線流程線ABBAP1、順序結(jié)構(gòu)、順序結(jié)構(gòu)2、選擇結(jié)構(gòu)、選擇結(jié)構(gòu)PA3、循環(huán)結(jié)構(gòu)、循環(huán)結(jié)構(gòu)PA當型循環(huán)直到型循環(huán)10N-SN-S流程圖流程圖一種流程

4、圖形式一種流程圖形式,在這種流程圖中完全去掉了流程線在這種流程圖中完全去掉了流程線,全部算法寫在一個矩形框內(nèi)全部算法寫在一個矩形框內(nèi). 順序結(jié)構(gòu)順序結(jié)構(gòu) 選擇結(jié)構(gòu)選擇結(jié)構(gòu) 循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)ABNoABPYesWhile P1AUntil P2A111、對于循環(huán)結(jié)構(gòu)，只有兩種畫法，如下：、對于循環(huán)結(jié)構(gòu)，只有兩種畫法，如下：2、對于直到型循環(huán)，條件為真時繼續(xù)執(zhí)行，否則、對于直到型循環(huán)，條件為真時繼續(xù)執(zhí)行，否則退出循環(huán)。退出循環(huán)。N-SN-S流程圖流程圖- - 注意事項注意事項 12偽代碼偽代碼 偽代碼是一種描述語言。偽代碼是一種描述語言。 它只是一種描述程序執(zhí)行過程的工它只是一種描述程序執(zhí)行過程的

5、工 具，是面向具，是面向 讀者的，不能直接用于計算機，實際使用時還需讀者的，不能直接用于計算機，實際使用時還需 轉(zhuǎn)換成某種計算機語言來表示。轉(zhuǎn)換成某種計算機語言來表示。 例：求例：求5！BEGIN（算法開始）（算法開始） 1=t 2=i while i t , i+1= i print tEND（算法結(jié)束）（算法結(jié)束）14用用 y = x2-2x+3 計算，當計算，當 x=0,1, 2,3, 4,5 所對應的所對應的y值值1. 置置x的下界為的下界為 0；2. 置置x的上界為的上界為 n=5；3. 當當xn時，重復執(zhí)行如下時，重復執(zhí)行如下3 步，步， 否則算法停止。否則算法停止。F 用公式計算

6、用公式計算y值值F 輸出一組輸出一組x和和y的值的值F x值增加值增加1用自然語言描述用自然語言描述開 始0 x5 nx n ?y = x2-2x+3輸出：x與y值增值：x=x+1結(jié) 束YN用流程圖描述用流程圖描述用用N-S圖描述圖描述 0 x 5 n 是 x n 否計算： y = x2-2x+3打印： x與y值增值：x=x+1 直到 x n17用計算機語言表示用計算機語言表示-用用C C語言描述語言描述main() int x, y, n; x=0; n=5; while( x = n) y=x*x-2*x+3; printf(“%d %d”, x, y); x=x+1; 18 例：判斷一個

7、數(shù)能否同時被例：判斷一個數(shù)能否同時被3 3和和5 5整除。整除。分別用流程圖、分別用流程圖、N-SN-S流程圖、偽代碼來描流程圖、偽代碼來描述這個問題的解決方法。述這個問題的解決方法。19自然語言：自然語言：1 1、設(shè)置變量、設(shè)置變量a a，讀入輸入數(shù)據(jù)；，讀入輸入數(shù)據(jù)；2 2、計算、計算a a是否能被是否能被3 3整除：是，進行步驟整除：是，進行步驟3 3，否則，否則進行步驟進行步驟4 4；3 3、計算、計算a a是否能被是否能被5 5整除：是，進行步驟整除：是，進行步驟5 5，否則，否則進行步驟進行步驟4 4；4 4、輸出結(jié)果，、輸出結(jié)果，a a不能同時被不能同時被3 3和和5 5整除；整

8、除；5 5、輸出結(jié)果，、輸出結(jié)果，a a能同時被能同時被3 3和和5 5整除。整除。a a能被能被5 5整除？整除？是是 否否輸出能輸出能同時整除同時整除輸出不能輸出不能同時整除同時整除 a a能被能被3 3整除？整除？是是 否否輸出不能輸出不能同時整除同時整除輸入輸入a a的值的值開始開始輸入輸入a a的值的值a a能被能被3 3整除？整除？否否是是a a能被能被5 5整除？整除？否否是是輸出輸出a a能同時被能同時被3 3和和5 5整除。整除。結(jié)束結(jié)束輸出輸出a a不能同時被不能同時被3 3和和5 5整除。整除。偽代碼：偽代碼：BEGINBEGIN（算法開始）（算法開始）讀入讀入a a的值

9、的值if(aif(a能被能被3 3整除整除) ) ifif（a a能被能被5 5整除）輸出整除）輸出 能同時整除；能同時整除；else else 輸出輸出 不能同時整除；不能同時整除；else else 輸出輸出 不能同時整除；不能同時整除；END(END(算法結(jié)束算法結(jié)束) )外層外層內(nèi)層內(nèi)層思考題：思考題：分別用分別用流程圖流程圖、N-S流程圖流程圖、偽代碼偽代碼來描來描述如下問題：述如下問題： 輸入一個年份（四位數(shù)，如輸入一個年份（四位數(shù)，如2009），判），判斷是否為閏年。斷是否為閏年。閏年的一年有閏年的一年有366366天，其中天，其中2 2月份為月份為2929天。天。公歷閏年的精確

10、計算方法公歷閏年的精確計算方法: :、普通年能被、普通年能被4 4整除的為閏年。（如整除的為閏年。（如20042004年就年就是閏年是閏年,1901,1901年不是閏年）年不是閏年）、世紀年能被、世紀年能被400400整除而不能被整除而不能被32003200整除的為整除的為閏年。閏年。( (如如20002000年是閏年，年是閏年，33203320年不是閏年年不是閏年) ) 、對于數(shù)值很大的年份能整除、對于數(shù)值很大的年份能整除3200,3200,但同時又但同時又能整除能整除172800172800則又是閏年則又是閏年.(.(如如172800172800年是閏年，年是閏年，864000864000年不是閏年）年不是閏年）25這里把條件簡單化，閏年的條件為：這里把條件簡單化，閏年的條件為：能夠被能夠被400整除的年份；整除的年份；能夠被能夠被4整除且不能被整除且不能被100整除的年份；整除的年份；輸入四位年份賦值給輸入四位年份賦值給year,year,設(shè)置狀態(tài)變量設(shè)置狀態(tài)變量state=0state=0 year year是否能被是否能被400400整除？整除？否否 是是State=1State=1 year ye