1、1.1算法與程序圖框元寶山區第二中學1.1.1 算法的概念學習目標:通過分析具體問題過程與步驟,體會算法的思想,了解算法的含義,能用自然語言描述解決具體問題的算法.學習重點(難點):通過實例體會算法思想,初步理解算法的含義.問題1請你寫出解二元一次方程組的詳細求解過程. 第一步:-2得: 5y=3 第二步: 解得:第三步: 將 代入,解得 .對于一般的二元一次方程組其中 也可以按照上述步驟求解.這些步驟就構成了解二元一次方程組的算法,我們可以根據這一算法編制計算機程序,讓計算機來解二元一次方程組.算法的概念與特征算法(algorithm)這個詞出現于12世紀,指的是用阿拉伯數字進行算術運算的過

2、程.在數學上,現代意義上的“算法”通常是指可以用計算機來解決的某一類問題的程序或步驟,這些程序或步驟必須是明確和有效的,而且能夠在有限步之內完成.說明:(1)事實上算法并沒有精確化的定義.(2)算法雖然沒有一個明確的定義,但其特點是鮮明的,不僅要注意算法的程序性、有限性、構造性、精確性的特點，還應該充分理解算法問題的指向性，即算法往往指向解決某一類問題，泛泛地談算法是沒有意義的。算法學的發展 隨著科學技術的日新月異,算法學也得到了前所未有的發展,現在已經發展到了各個領域.有遺傳算法,排序算法,加密算法,蟻群算法等,與生物學,計算機科學等有著很廣泛的聯系,尤其是在現在的航空航天中,更是有著更廣泛

3、的應用. 很多復雜的運算都是借助計算機和算法來完成的,在高端科學技術中有著很重要的地位.科學家王小云主導破解兩大密碼算法獲百萬大獎楊振寧教授為獲得“求是杰出科學家獎”的山東大學特聘教授王小云頒發了獲獎證書和獎金100萬元人民幣，表彰其密碼學領域的杰出成就。 例1:任意給定一個大于1的整數n,試設計一個程序或步驟對n是否為質數做出判定.分析:請回顧這個問題的解題過程.算法分析:第一步:判斷n是否等于2.若n=2,則n是質數;若n2,則執行第二步. 第二步:依次檢驗2(n-1)這些整數是不是n的因素,即是不是整除n的數.若有這樣的數,則n不是質數;若沒有這樣的數,則n是質數.說明:用語言描述一個算

4、法,最便捷的方式就是按解決問題的步驟進行描述.每一步做一件事情. 若是,則m為所求; 例2:用二分法設計一個求方程x2-2=0的近似根的算法.算法分析:設所求近似根與精確解的差的絕對值不超過=0.005.第一步:令f(x)=x2-2.因為f(1)0,所以設a=1,b=2.第二步:令判斷f(m)是否為0.若否,則繼續判斷f(a) f(m)大于0還是小于0.第三步:若f(a) f (m)0,則令a=m;否則,令b=m. 第四步:判斷|a-b|7時)解:y與x之間的函數關系為:(當0 x7時)(當x7時)求該函數值的算法分析:第一步:輸入每月用水量x;第二步:判斷x是否不超過7.若是,則y=1.2x

5、;若否,則y=1.9x-4.9.第三步:輸出應交納的水費y.作業:課本P6頁T2(只需用自然語言寫出算法步驟) 1.1.2 程序框圖 學習目標:(1)在具體問題的解決過程中,掌握基本的程序框圖的畫法,理解程序框圖的三種基本邏輯結構-順序結構、條件結構、循環結構。(2)通過模仿、操作、探索，經歷通過設計程序框圖表達解決問題的算法的過程。學習重點:通過模仿、操作、探索，經歷通過設計程序框圖表達求解問題的過程，在具體問題解決過程中，理解程序框圖的三種基本邏輯結構.學習難點:用程序框圖清晰表達含有循環結構的算法.例1:任意給定一個大于1的整數n,試設計一個程序或步驟對n是否為質數做出判定.算法分析:第

6、一步:判斷n是否等于2.若n=2,則n是質數;若n2,則執行第二步. 第二步:依次檢驗2(n-1)這些整數是不是n的因素,即是不是整除n的數.若有這樣的數,則n不是質數;若沒有這樣的數,則n是質數.從上節課我們知道:算法可以用自然語言來描述.如例1 為了使算法的程序或步驟表達得更為直觀,我們更經常地用圖形方式來表示它.開始輸入ni=2求n除以i的余數ri的值增加1仍用i表示in或r=0?n不是質數結束是否是n是質數否r=0?設n是一個大于2的整數.一般用i=i+1表示. i=i+1說明:i表示從2(n-1)的所有正整數,用以判斷例1步驟2是否終止,i是一個計數變量,有了這個變量,算法才能依次執

7、行.逐步考察從2(n-1)的所有正整數中是否有n的因數存在.思考?通過上述算法的兩種不同表達方式的比較,你覺得用程序框圖來表達算法有哪些特點?用程序框圖表示的算法更加簡練,直觀,流向清楚.程序框圖又稱流程圖,是一種用規定的圖形、指向線及文字說明來準確、直觀地表示算法的圖形.通常,程序框圖由程序框和流程線組成.一個或幾個程序框的組合表示算法中的一個步驟;流程線是方向箭頭,按照算法進行的順序將程序框連接起來.基本的程序框和它們各自表示的功能如下:圖形符號名稱功能終端框(起止框)表示一個算法的起始和結束輸入、輸出框表示一個算法輸入和輸出的信息處理框(執行框)判斷某一條件是否成立,成立時在出口處標明“

8、是”或“Y”；不”成立時標明“否”或“N”.判斷框賦值、計算流程線連接程序框連接點連接程序框圖的兩部分開始輸入ni=2求n除以i的余數ri=i+1in或r=0?n不是質數結束是否是n是質數否r=0?順序結構用程序框圖來表示算法，有三種不同的基本邏輯結構：條件結構循環結構程序框圖的三種基本的邏輯結構順序結構條件結構循環結構(1)順序結構-是由若干個依次執行的處理步驟組成的.這是任何一個算法都離不開的基本結構.例1:已知一個三角形的三邊邊長分別為2,3,4,利用海倫-秦九韶公式設計一個算法,求出它的面積,畫出算法的程序框圖.算法分析:第一步:計算p的值.第二步:由海倫-秦九韶公式求出三角形的面積S

9、.第三步:輸出S的值.(1)順序結構-是由若干個依次執行的處理步驟組成的.這是任何一個算法都離不開的基本結構.例1:已知一個三角形的三邊邊長分別為2,3,4,利用海倫-秦九韶公式設計一個算法,求出它的面積,畫出算法的程序框圖.算法分析:第一步:計算p的值.第二步:由海倫-秦九韶公式求出三角形的面積S.第三步:輸出S的值.程序框圖:開始輸出S結束畫出:已知三角形的三邊長a,b,c,求它的面積的程序框圖.開始輸出S結束輸入a,b,c返回已知三角形三邊長分別為a,b,c,則三角形的面積為其中 這個公式被稱為海倫秦九韶公式.返回(2)條件結構-在一個算法中,經常會遇到一些條件的判斷,算法的流向根據條件

10、是否成立有不同的流向.條件結構就是處理這種過程的結構.例2:任意給定3個正實數,設計一個算法,判斷分別以這3個數為三邊邊長的三角形是否存在.畫出這個算法的程序框圖.算法分析:第一步:輸入3個正實數a,b,c;第二步:判斷a+bc,a+cb,b+ca是否同時成立,若是,則能組成三角形;若否,則組不成三角形.程序框圖:開始輸入a,b,ca+bc,a+cb,b+ca是否同時成立?是存在這樣的三角形不存在這樣的三角形否結束例3:為了加強居民的節水意識,某市制訂了以下生活用水收費標準:每戶每月用水未超過7m3時,每立方米收費1.0元,并加收0.2元的城市污水處理費;超過7m3的部分,每立方米收費1.5元

11、,并加收0.4元的城市污水處理費,請你寫出某戶居民每月應交納的水費y(元)與用水量x(m3)之間的函數關系,然后設計一個求該函數值的算法,并畫出程序框圖.解:y與x之間的函數關系為:(當0 x7時)(當x7時)解:y與x之間的函數關系為:(當0 x7時)(當x7時)算法分析:第一步:輸入每月用水量x;第二步:判斷x是否不超過7.若是,則y=1.2x;若否,則y=1.9x-4.9.第三步:輸出應交納的水費y.開始輸入x0 x7?是y=1.2x否y=1.9x-4.9輸出y結束程序框圖例4.畫程序框圖,對于輸入的x值,輸出相應的y值.開始程序框圖x0?是y=0否0 x100?是輸出S結束否直到型循環

12、結構開始i=1S=0i100?是S=S+ii=i+1否輸出S結束當型循環結構說明:(1)一般地,循環結構中都有一個計數變量和累加變量.計數變量用于記錄循環次數,同時它的取值還用于判斷循環是否終止,累加變量用于輸出結果.累加變量和計數變量一般是同步執行的,累加一次,記數一次.(2)循環結構分為兩種-當型和直到型.當型循環在每次執行循環體前對循環條件進行判斷,當條件滿足時執行循環體,不滿足則停止;(當條件滿足時反復執行循環體)直到型循環在執行了一次循環體之后,對控制循環條件進行判斷,當條件不滿足時執行循環體,滿足則停止.(反復執行循環體,直到條件滿足)程序框圖:開始i=1S=0S=S+ii=i+1

13、i100?是輸出S結束否直到型循環結構開始i=1S=0i100?是S=S+ii=i+1否輸出S結束當型循環結構開始輸入ni=2求n除以i的余數ri=i+1in或r=0?n不是質數結束是否是n是質數否r=0?順序結構用程序框圖來表示算法，有三種不同的基本邏輯結構：條件結構循環結構直到型循環結構 若是,則m為所求; 探究:畫出用二分法求方程x2-2=0的近似根(精確度為0.005)的程序框圖.算法分析:第一步:令f(x)=x2-2.因為f(1)0,所以設a=1,b=2.第二步:令判斷f(m)是否為0.若否,則繼續判斷f(a) (m)大于0還是小于0.第三步:若f(a) (m)0,則令a=m;否則,

14、令b=m. 第四步:判斷|a-b|0?程序框圖開始f(x)=x2-2輸入誤差和初值a,bf(m)=0?a=m否b=m|a-b|0?程序框圖開始f(x)=x2-2輸入誤差和初值a,ba=m否b=m|a-b|3?否結束輸入yy=5y=1.2x+1.4是2.(P40頁A組T3)程序框圖:開始輸入t0t3?否結束輸入yy=0.3y=0.1t3.(P40頁A組T1(1)開始程序框圖x0?是y=0否0 x1?是y=1否y=x輸出y結束輸入x4.(P40頁A組T1(2)開始程序框圖x100?是輸出S結束否直到型循環結構開始i=1S=0i100?是S=S+i2i=i+1否輸出S結束當型循環結構5.P12頁A組

15、T2.開始i=1S=0S=S+i=i+1in?是輸出S結束否直到型循環結構開始i=1S=0in?是S=S+i=i+1否輸出S結束當型循環結構6.P40頁A組T4.輸入n輸入n7(P12BT1).某高中男子體育小組的50m跑成績(單位:s)為: 6.4, 6.5, 7.0, 6.8, 7.1, 7.3, 6.9, 7.4, 7.5.設計一個算法,從這些成績中搜出小于6.8s的成績.算法分析:第一步:把計數變量n的初值設為1.第二步:輸入一個成績r,判斷r與6.8的大小.若r6.8,則執行下一步;若r9,則結束.開始n=1程序框圖輸入rr6.8?是n=n+1n9?是否輸出r否結束直到型循環結構8(P12BT2)設計一個求解二元一次方程組其中 的算法,并畫出程序框圖.算法分析:第一步:判斷a1是否等于0.如果a10,由+u,得 (b2+b1u)y=c2+c1u;如果a1=0,執行第三步.第二步:解,得輸出y.第三步:將y值代入,得輸出x.開始程序框圖輸入a1,b1,c1,a2,b2,c2a10?是u=-a2/a1b=b2+b1uc=c2+c1uy=c/bx=(c2-b2y)/a2否y=c1/b1輸出x,y結束9(P41頁B組T3)設計一個算法,判斷一個正的n(n2)位數是不是回文數,用自然語言描述算法步驟.算法步驟:第一步:輸入一個正