《算法與程序框圖》演示幻燈片

1、1 2 1.1.1 算法的概念算法的概念 學習目標學習目標: 通過分析具體問題過程與步驟通過分析具體問題過程與步驟,體會算法體會算法 的思想的思想,了解算法的含義了解算法的含義,能用自然語言描述解能用自然語言描述解 決具體問題的算法決具體問題的算法. 學習重點學習重點(難點難點): 通過實例體會算法思想通過實例體會算法思想,初步理解算法的初步理解算法的 含義含義. 3 問題問題1請你寫出解二元一次方程組的詳細求解請你寫出解二元一次方程組的詳細求解 過程過程. 21 21 xy xy 第一步第一步:-2得得: 5y=3 第二步第二步: 解解得得: 3 5 y 第三步第三步: 將將 代入代入,解得

2、解得 . 3 5 y 1 5 x 對于一般的二元一次方程組對于一般的二元一次方程組 其中其中 也可以按照上述步驟求解也可以按照上述步驟求解. 111 222 a xb yc a xb yc 1 22 1 0aba b 4 這些步驟就構成了解二元一次方程組的這些步驟就構成了解二元一次方程組的 算法算法,我們可以根據(jù)這一算法編制計算機程序我們可以根據(jù)這一算法編制計算機程序, 讓計算機來解二元一次方程組讓計算機來解二元一次方程組. 算法的概念與特征算法的概念與特征 算法算法(algorithm)這個詞出現(xiàn)于這個詞出現(xiàn)于12世紀世紀, 指的是用阿拉伯數(shù)字進行算術運算的過程指的是用阿拉伯數(shù)字進行算術運算

3、的過程. 在數(shù)學上在數(shù)學上,現(xiàn)代意義上的現(xiàn)代意義上的“算法算法”通常是指可通常是指可 以用計算機來解決的某一類問題的以用計算機來解決的某一類問題的程序或步程序或步 驟驟, 5 說明說明: (1)事實上算法并沒有精確化的定義事實上算法并沒有精確化的定義. (2)算法雖然沒有一個明確的定義算法雖然沒有一個明確的定義,但其特點但其特點 是鮮明的是鮮明的,不僅要注意不僅要注意算法的程序性、有限算法的程序性、有限 性、構造性、精確性的特點，還應該充分性、構造性、精確性的特點，還應該充分 理解算法問題的指向性，即算法往往指向理解算法問題的指向性，即算法往往指向 解決某一類問題，泛泛地談算法是沒有意解決某一

4、類問題，泛泛地談算法是沒有意 義的。義的。 6 算法學的發(fā)展 隨著科學技術的日新月異,算法學也得 到了前所未有的發(fā)展,現(xiàn)在已經(jīng)發(fā)展到了各 個領域.有遺傳算法遺傳算法,排序算法排序算法,加密算法加密算法,蟻蟻 群算法群算法等,與生物學,計算機科學等有著很廣 泛的聯(lián)系,尤其是在現(xiàn)在的航空航天中,更是 有著更廣泛的應用. 很多復雜的運算都是借助計算機和算 法來完成的,在高端科學技術中有著很重要 的地位. 7 科學家王小云主導破解兩大 密碼算法獲百萬大獎 楊振寧教授為獲得“求是杰出科學家獎” 的山東大學特聘教授王小云頒發(fā)了獲獎證書 和獎金100萬元人民幣，表彰其密碼學領域 的杰出成就。 8 9 例例1

5、:任意給定一個大于任意給定一個大于1的整數(shù)的整數(shù)n,試設計一個程試設計一個程 序或步驟對序或步驟對n是否為質數(shù)做出判定是否為質數(shù)做出判定. 分析分析:請回顧這個問題的解題過程請回顧這個問題的解題過程. 算法分析算法分析: 第一步第一步:判斷判斷n是否等于是否等于2. 若若n=2,則則n是質數(shù)是質數(shù); 若若n2,則執(zhí)行第二步則執(zhí)行第二步. 第二步第二步:依次檢驗依次檢驗2(n-1)這些整數(shù)是不是這些整數(shù)是不是n的的 因素因素,即是不是整除即是不是整除n的數(shù)的數(shù).若有這樣的數(shù)若有這樣的數(shù),則則n不是不是 質數(shù)質數(shù);若沒有這樣的數(shù)若沒有這樣的數(shù),則則n是質數(shù)是質數(shù). 說明說明:用語言描述一個算法用語

6、言描述一個算法,最便捷的方式就是按最便捷的方式就是按 解決問題的步驟進行描述解決問題的步驟進行描述.每一步做一件事情每一步做一件事情. 10 若是若是,則則m 為所求為所求; 例例2:用二分法設計一個求方程用二分法設計一個求方程x2-2=0的近似根的近似根 的算法的算法. 算法分析算法分析: 設所求近似根與精確解的差的絕對設所求近似根與精確解的差的絕對 值不超過值不超過=0.005. 第一步第一步:令令f(x)=x2-2. 因為因為f(1)0, 所以設所以設a=1,b=2. 第二步第二步:令令, 2 ab m 判斷判斷f(m)是否為是否為0. 若否若否,則繼續(xù)判斷則繼續(xù)判斷f(a) (m)大于

7、大于0還是小于還是小于0. 第三步第三步:若若f(a) (m)0,則令則令a=m;否則否則,令令b=m. 第四步第四步:判斷判斷|a-b|7時時) 16 解解:y與與x之間的函數(shù)關系為之間的函數(shù)關系為: 1.2 , 1.94.9 x y x (當當0 x7時時) (當當x7時時) 求該函數(shù)值的算法分析求該函數(shù)值的算法分析: 第一步第一步:輸入每月用水量輸入每月用水量x; 第二步第二步:判斷判斷x是否不超過是否不超過7.若是若是,則則y=1.2x; 若否若否,則則y=1.9x-4.9. 第三步第三步:輸出應交納的水費輸出應交納的水費y. 17 作業(yè)作業(yè): 課本課本P6頁頁T2 (只需用自然語言寫

8、出算法步驟只需用自然語言寫出算法步驟) 18 1.1.2 程序框圖程序框圖 學習目標學習目標:(1)在具體問題的解決過程中在具體問題的解決過程中,掌握基本掌握基本 的程序框圖的畫法的程序框圖的畫法,理解程序框圖的三種基本邏輯理解程序框圖的三種基本邏輯 結構結構-順序結構、條件結構、循環(huán)結構。順序結構、條件結構、循環(huán)結構。 (2)通過模仿、操作、探索，經(jīng)歷通過設計程序框通過模仿、操作、探索，經(jīng)歷通過設計程序框 圖表達解決問題的算法的過程。圖表達解決問題的算法的過程。 學習重點學習重點:通過模仿、操作、探索，經(jīng)歷通過設計通過模仿、操作、探索，經(jīng)歷通過設計 程序框圖表達求解問題的過程，在具體問題解決

9、程序框圖表達求解問題的過程，在具體問題解決 過程中，理解程序框圖的三種基本邏輯結構過程中，理解程序框圖的三種基本邏輯結構. 學習難點學習難點:用程序框圖清晰表達含有循環(huán)結構的算法用程序框圖清晰表達含有循環(huán)結構的算法. 19 例例1:任意給定一個大于任意給定一個大于1的整數(shù)的整數(shù)n,試設計一個程試設計一個程 序或步驟對序或步驟對n是否為質數(shù)做出判定是否為質數(shù)做出判定. 算法分析算法分析: 第一步第一步:判斷判斷n是否等于是否等于2. 若若n=2,則則n是質數(shù)是質數(shù); 若若n2,則執(zhí)行第二步則執(zhí)行第二步. 第二步第二步:依次檢驗依次檢驗2(n-1)這些整數(shù)是不是這些整數(shù)是不是n的的 因素因素,即是

10、不是整除即是不是整除n的數(shù)的數(shù).若有這樣的數(shù)若有這樣的數(shù),則則n不是不是 質數(shù)質數(shù);若沒有這樣的數(shù)若沒有這樣的數(shù),則則n是質數(shù)是質數(shù). 從上節(jié)課我們知道從上節(jié)課我們知道:算法可以用自然語言算法可以用自然語言 來描述來描述.如例如例1 為了使算法的程序或步驟表達得更為直觀為了使算法的程序或步驟表達得更為直觀,我我 們更經(jīng)常地用圖形方式來表示它們更經(jīng)常地用圖形方式來表示它. 20 開始開始 輸入輸入n i=2 求求n除以除以i的余數(shù)的余數(shù)r i的值增加的值增加1仍用仍用i表示表示 in或或r=0? n不是質數(shù)不是質數(shù) 結束結束 是是 否否 是是 n是質數(shù)是質數(shù) 否否 r=0? 設設n是一個大是一個

11、大 于于2的整數(shù)的整數(shù). 一般用一般用i=i+1 表示表示. i=i+1 說明說明:i表示從表示從2(n-1) 的所有正整數(shù)的所有正整數(shù),用以用以 判斷例判斷例1步驟步驟2是否終是否終 止止,i是一個計數(shù)變量是一個計數(shù)變量, 有了這個變量有了這個變量,算法算法 才能依次執(zhí)行才能依次執(zhí)行.逐步逐步 考察從考察從2(n-1)的所的所 有正整數(shù)中是否有有正整數(shù)中是否有n 的因數(shù)存在的因數(shù)存在. 21 思考思考?通過上述算法的兩種不同表達方式的比通過上述算法的兩種不同表達方式的比 較較,你覺得用程序框圖來表達算法有哪些特點你覺得用程序框圖來表達算法有哪些特點? 用程序框圖表示的算法更加簡練用程序框圖表

12、示的算法更加簡練,直觀直觀,流向清流向清 楚楚. 程序框圖程序框圖又稱又稱流程圖流程圖,是一種用規(guī)定的圖形、是一種用規(guī)定的圖形、 指向線及文字說明來準確、直觀地表示算法的指向線及文字說明來準確、直觀地表示算法的 圖形圖形. 通常通常,程序框圖由程序框和流程線組成程序框圖由程序框和流程線組成. 一個或幾個程序框的組合表示算法中的一個步驟一個或幾個程序框的組合表示算法中的一個步驟; 流程線是方向箭頭流程線是方向箭頭,按照算法進行的順序將程序按照算法進行的順序將程序 框連接起來框連接起來. 22 基本的程序框和它們各自表示的功能如下基本的程序框和它們各自表示的功能如下: 圖形符號圖形符號名稱名稱功能

13、功能 終端框終端框 (起止框起止框) 表示一個算法的起始表示一個算法的起始 和結束和結束 輸入、輸輸入、輸 出框出框 表示一個算法輸入和表示一個算法輸入和 輸出的信息輸出的信息 處理框處理框 (執(zhí)行框執(zhí)行框) 判斷某一條件是否成立判斷某一條件是否成立,成立成立 時在出口處標明時在出口處標明“是是”或或 “Y”；不；不”成立時標明成立時標明“否否” 或或“N”. 判斷框判斷框 賦值、計算賦值、計算 流程線流程線連接程序框連接程序框 連接點連接點連接程序框圖的兩部分連接程序框圖的兩部分 23 開始開始 輸入輸入n i=2 求求n除以除以i的余數(shù)的余數(shù)r i=i+1 in或或r=0? n不是質數(shù)不是

14、質數(shù) 結束結束 是是 否否 是是 n是質數(shù)是質數(shù) 否否 r=0? 順序結構順序結構 用程序框圖來表示算法，有用程序框圖來表示算法，有 三種不同的基本邏輯結構：三種不同的基本邏輯結構： 條件結構條件結構 循環(huán)結構循環(huán)結構 24 程序框圖的三種基本的邏輯結構程序框圖的三種基本的邏輯結構 順序結構順序結構 條件結構條件結構 循環(huán)結構循環(huán)結構 25 (1)順序結構順序結構-是由若干個依次執(zhí)行的處理是由若干個依次執(zhí)行的處理 步驟組成的步驟組成的.這是任何一個算法都離不開的這是任何一個算法都離不開的 基本結構基本結構. 例例1:已知一個三角形的三邊邊長分別為已知一個三角形的三邊邊長分別為2,3,4, 利用

15、海倫利用海倫-秦九韶公式設計一個算法秦九韶公式設計一個算法,求出它的求出它的 面積面積,畫出算法的程序框圖畫出算法的程序框圖. 算法分析算法分析: 第一步第一步:計算計算p的值的值. 第二步第二步:由海倫由海倫-秦九韶公式求出三角形的面積秦九韶公式求出三角形的面積S. 第三步第三步:輸出輸出S的值的值. 26 (1)順序結構順序結構-是由若干個依次執(zhí)行的處理是由若干個依次執(zhí)行的處理 步驟組成的步驟組成的.這是任何一個算法都離不開的這是任何一個算法都離不開的 基本結構基本結構. 例例1:已知一個三角形的三邊邊長分別為已知一個三角形的三邊邊長分別為2,3,4, 利用海倫利用海倫-秦九韶公式設計一個

16、算法秦九韶公式設計一個算法,求出它的求出它的 面積面積,畫出算法的程序框圖畫出算法的程序框圖. 算法分析算法分析: 第一步第一步:計算計算p的值的值. 第二步第二步:由海倫由海倫-秦九韶公式求出三角形的面積秦九韶公式求出三角形的面積S. 第三步第三步:輸出輸出S的值的值. 27 程序框圖程序框圖: 開始開始 234 2 p (2)(3)(4)Sp ppp 輸出輸出S 結束結束 28 畫出畫出:已知三角形的三已知三角形的三 邊長邊長a,b,c,求它的面積求它的面積 的程序框圖的程序框圖. 開始開始 2 abc p ()()()Sp papbpc 輸出輸出S 結束結束 輸入輸入a,b,c 返回返回

17、 29 已知三角形三邊長分別為已知三角形三邊長分別為a,b,c,則三角則三角 形的面積為形的面積為 其中其中 這個公式被稱為海倫這個公式被稱為海倫秦九韶公式秦九韶公式. ()()()Sp papbpc 2 abc p 返回返回 30 (2)條件結構條件結構-在一個算法中在一個算法中,經(jīng)常會遇到一經(jīng)常會遇到一 些條件的判斷些條件的判斷,算法的流向根據(jù)條件是否成算法的流向根據(jù)條件是否成 立有不同的流向立有不同的流向.條件結構就是處理這種過條件結構就是處理這種過 程的結構程的結構. 例例2:任意給定任意給定3個正實數(shù)個正實數(shù),設計一個算法設計一個算法,判斷分判斷分 別以這別以這3個數(shù)為三邊邊長的三角

18、形是否存在個數(shù)為三邊邊長的三角形是否存在.畫畫 出這個算法的程序框圖出這個算法的程序框圖. 算法分析算法分析: 第一步第一步:輸入輸入3個正實數(shù)個正實數(shù)a,b,c; 第二步第二步:判斷判斷a+bc,a+cb,b+ca是否同時成立是否同時成立, 若是若是,則能組成三角形則能組成三角形;若否若否,則組不成三角形則組不成三角形. 31 程序框圖程序框圖:開始開始 輸入輸入a,b,c a+bc,a+cb,b+ca是否是否 同時成立同時成立? 是是 存在這樣的存在這樣的 三角形三角形 不存在這樣的不存在這樣的 三角形三角形 否否 結束結束 32 例例3:為了加強居民的節(jié)水意識為了加強居民的節(jié)水意識,某市

19、制訂了以某市制訂了以 下生活用水收費標準下生活用水收費標準:每戶每月用水未超過每戶每月用水未超過 7m3時時,每立方米收費每立方米收費1.0元元,并加收并加收0.2元的城元的城 市污水處理費市污水處理費;超過超過7m3的部分的部分,每立方米收費每立方米收費 1.5元元,并加收并加收0.4元的城市污水處理費元的城市污水處理費,請你寫請你寫 出某戶居民每月應交納的水費出某戶居民每月應交納的水費y(元元)與用水量與用水量 x(m3)之間的函數(shù)關系之間的函數(shù)關系,然后設計一個求該函然后設計一個求該函 數(shù)值的算法數(shù)值的算法,并畫出程序框圖并畫出程序框圖. 解解:y與與x之間的函數(shù)關系為之間的函數(shù)關系為:

20、 1.2 , 1.94.9 x y x (當當0 x7時時) (當當x7時時) 33 解解:y與與x之間的函數(shù)關系為之間的函數(shù)關系為: 1.2 , 1.94.9 x y x (當當0 x7時時) (當當x7時時) 算法分析算法分析: 第一步第一步:輸入每月用水量輸入每月用水量 x; 第二步第二步:判斷判斷x是否不超是否不超 過過7.若是若是,則則y=1.2x;若若 否否,則則y=1.9x-4.9. 第三步第三步:輸出應交納的水輸出應交納的水 費費y. 開始開始 輸入輸入x 0 x7? 是是 y=1.2x 否否 y=1.9x-4.9 輸出輸出y 結束結束 程序框圖程序框圖 34 例例4.畫程序框

21、圖畫程序框圖, 對于輸入的對于輸入的x值值, 輸出相應的輸出相應的y值值. 0(0) 1(01) (1) x yx x x 開始開始 程序框圖程序框圖 x0? 是是 y=0 否否 0 x1? 是是 y=1 否否 y=x 輸出輸出y 結束結束 輸入輸入x 35 是是 例例5.設計一個求任意數(shù)的絕對值的算法設計一個求任意數(shù)的絕對值的算法,并畫出并畫出 程序框圖程序框圖. (0) | ( xx x xx 當時 當 100? 是是 輸出輸出S 結束結束 否否 直到直到 型循型循 環(huán)結環(huán)結 構構 開始開始 i=1 S=0 i100? 是是 S=S+i i=i+1 否否 輸出輸出S 結束結束 當型循環(huán)當型

22、循環(huán) 結構結構 40 說明說明:(1)一般地一般地,循環(huán)結構中都有一個計數(shù)變量循環(huán)結構中都有一個計數(shù)變量 和累加變量和累加變量.計數(shù)變量用于記錄循環(huán)次數(shù)計數(shù)變量用于記錄循環(huán)次數(shù),同時它同時它 的取值還用于判斷循環(huán)是否終止的取值還用于判斷循環(huán)是否終止,累加變量用于累加變量用于 輸出結果輸出結果.累加變量和計數(shù)變量一般是同步執(zhí)行累加變量和計數(shù)變量一般是同步執(zhí)行 的的,累加一次累加一次,記數(shù)一次記數(shù)一次. (2)循環(huán)結構分為兩種循環(huán)結構分為兩種-當型和直到型當型和直到型. 當型循環(huán)當型循環(huán)在每次執(zhí)行循環(huán)體前對循環(huán)條在每次執(zhí)行循環(huán)體前對循環(huán)條 件進行判斷件進行判斷,當條件滿足時執(zhí)行循環(huán)體當條件滿足時執(zhí)

23、行循環(huán)體,不滿足不滿足 則停止則停止;(當條件滿足時反復執(zhí)行循環(huán)體當條件滿足時反復執(zhí)行循環(huán)體) 直到型循環(huán)直到型循環(huán)在執(zhí)行了一次循環(huán)體之后在執(zhí)行了一次循環(huán)體之后,對對 控制循環(huán)條件進行判斷控制循環(huán)條件進行判斷,當條件不滿足時執(zhí)行當條件不滿足時執(zhí)行 循環(huán)體循環(huán)體,滿足則停止?jié)M足則停止.(反復執(zhí)行循環(huán)體反復執(zhí)行循環(huán)體,直到條件直到條件 滿足滿足) 41 程序框圖程序框圖: 開始開始 i=1 S=0 S=S+i i=i+1 i100? 是是 輸出輸出S 結束結束 否否 直到直到 型循型循 環(huán)結環(huán)結 構構 開始開始 i=1 S=0 i100? 是是 S=S+i i=i+1 否否 輸出輸出S 結束結束

24、當型循環(huán)當型循環(huán) 結構結構 42 開始開始 輸入輸入n i=2 求求n除以除以i的余數(shù)的余數(shù)r i=i+1 in或或r=0? n不是質數(shù)不是質數(shù) 結束結束 是是 否否 是是 n是質數(shù)是質數(shù) 否否 r=0? 順序結構順序結構 用程序框圖來表示算法，有用程序框圖來表示算法，有 三種不同的基本邏輯結構：三種不同的基本邏輯結構： 條件結構條件結構 循環(huán)結構循環(huán)結構直到型循直到型循 環(huán)結構環(huán)結構 43 若是若是,則則m 為所求為所求; 探究探究:畫出用二分法求方程畫出用二分法求方程x2-2=0的近似根的近似根(精確精確 度為度為0.005)的程序框圖的程序框圖. 算法分析算法分析: 第一步第一步:令令f

25、(x)=x2-2. 因為因為f(1)0, 所以設所以設a=1,b=2. 第二步第二步:令令, 2 ab m 判斷判斷f(m)是否為是否為0. 若否若否,則繼續(xù)判斷則繼續(xù)判斷f(a) (m)大于大于0還是小于還是小于0. 第三步第三步:若若f(a) (m)0,則令則令a=m;否則否則,令令b=m. 第四步第四步:判斷判斷|a-b|0? 程序框圖程序框圖 開始開始 f(x)=x2-2 輸入誤差輸入誤差 和初值和初值a,b 2 ab m f(m)=0? a=m 否否 b=m |a-b|0? 程序框圖程序框圖 開始開始 f(x)=x2-2 輸入誤差輸入誤差 和初值和初值a,b 2 ab m a=m 否

26、否 b=m |a-b|3? 否否 結束結束 輸入輸入y y=5y=1.2x+1.4 50 是是 2.(P40頁頁A組組T3) 0.3(3) 0.1 (3 t y t 當0時 當t時) 程序框圖程序框圖: 開始開始 輸入輸入t 0t3? 否否 結束結束 輸入輸入y y=0.3y=0.1t 51 3.(P40頁頁A組組T1(1) 0(0) 1(01) (1) x yx x x 開始開始 程序框圖程序框圖 x0? 是是 y=0 否否 0 x1? 是是 y=1 否否 y=x 輸出輸出y 結束結束 輸入輸入x 52 4.(P40頁頁A組組T1(2) 2 2 (2) (0) 4(0) (2) (0) xx

27、 yx xx 開始開始 程序框圖程序框圖 x100? 是是 輸出輸出S 結束結束 否否 直到直到 型循型循 環(huán)結環(huán)結 構構 開始開始 i=1 S=0 i100? 是是 S=S+i2 i=i+1 否否 輸出輸出S 結束結束 當型循環(huán)當型循環(huán) 結構結構 5.P12頁頁A 組組T2. 54 開始開始 i=1 S=0 S=S+ i=i+1 in? 是是 輸出輸出S 結束結束 否否 直到直到 型循型循 環(huán)結環(huán)結 構構 開始開始 i=1 S=0 in? 是是 S=S+ i=i+1 否否 輸出輸出S 結束結束 當型循環(huán)當型循環(huán) 結構結構 6.P40頁頁A 組組T4. 輸入輸入n 1 i 1 i 輸入輸入n

28、55 7(P12BT1).某高中男子體育小組的某高中男子體育小組的50m跑成績跑成績(單位單位:s) 為為: 6.4, 6.5, 7.0, 6.8, 7.1, 7.3, 6.9, 7.4, 7.5. 設計一個算法設計一個算法,從這些成績中搜出小于從這些成績中搜出小于6.8s的成績的成績. 算法分析算法分析: 第一步第一步:把計數(shù)變量把計數(shù)變量n的初值設為的初值設為1. 第二步第二步:輸入一個成績輸入一個成績r,判斷判斷r與與6.8的大小的大小.若若 r6.8,則執(zhí)行下一步則執(zhí)行下一步;若若r9,則結束則結束. 56 開始開始 n=1 程序框圖程序框圖 輸入輸入r r6.8? 是是 n=n+1 n9? 是是 否否 輸出輸出r 否否 結束結束 直到型循直到型循 環(huán)結構環(huán)結構 57 8(P12BT2)設計一個求解二元一次方程組設