1.1.1算法的概念(上課).ppt

1、普通高中課程標準試驗教科書 人教A版數(shù)學必修3 第一章 算法初步,長汀一中 數(shù)學組 賴茂生 2008.2.17,1.1.1算法的概念 1.1.2程序框圖與算法的基本邏輯結構,假設家中生火泡茶有以下幾個步驟： a.洗刷茶壺 b.燒水 c.洗刷茶具 d.沏茶 請設計一個最優(yōu)算法。,算法1：S1：洗刷茶壺 S2：燒水 S3：洗刷茶具 S4：沏茶,算法2： S1：洗刷茶壺 S2：燒水，同時洗刷茶具 S3：沏茶,思考？,第二步：解，得,第一步： - ，得 ,第三步：將 代入，得,1、算法的概念,“算法”通常是指按照一定規(guī)則解決的某一類問題的明確的和有效的步驟，而且能夠在有限步之內完成。算法通?？梢跃幊捎?/p>

2、算機程序，讓計算機執(zhí)行并解決問題。,一般來說，“用算法解決問題” 可以利用 計算機幫助完成。,2、算法的特點,（1）有限性,即一個算法的步驟序列是有限的；,（2）確定性,即算法中的每一步應該是確定的并且能有效地執(zhí)行且得到確定的結果；,（4）邏輯性,即算法從初始步驟開始，分為若干明確的步驟，前一步是后一步的前提，只有執(zhí)行完前一步才能進行下一步，而且每一步都是正確無誤的，從而組成了一個有著很強邏輯性的步驟序列；,（5）不唯一性,即求解一個問題的算法不一定是唯一的；,（6）普遍性,即很多具體的問題，都可以設計合理的算法去解決。,（3）有效性 算法中的每一個步驟都是可以在有限的時 間內完成的基本操作，

3、并能得到確定的結果 。,練習,1、判斷下列關于算法的說法是否確：,1、求解某一類問題的算法是唯一的；,2、算法必須在有限步操作之后停止：,3、算法的每一步必須是明確的，不能有歧義或模糊：,4、算法執(zhí)行后一定產生確定的結果：,一位商人有9枚銀元，其中有1枚略輕的是假銀元。你能用天平（不用砝碼）將假銀元找出來嗎？,例,寫出一個求有限整數(shù)序列中的最大值的算法。,解：算法如下： S1 先假定序列中的第一個整數(shù)為“最大值”。,S2 將序列中的下一個整數(shù)值與“最大值”比較，如果它大于此“最大值”，這時你就假定“最大值”是這個整數(shù)。,S3 如果序列中還有其他整數(shù)，重復S2。,S4 在序列中一直到沒有可比的數(shù)

4、為止，這時假定的“最大值”就是這個序列中的最大值。,例1,任意給定一個大于1的整數(shù)n，試設計一個程序或步驟對n是否為質數(shù)作出判定。,解：算法如下： S1 輸入n。,S2 判斷n是否等于2。若n2，則n是質數(shù)；若n2，則執(zhí)行 S3。,S3 依次從2（n1）檢驗是不是n的因數(shù)，即整除n的數(shù)。若有這樣的數(shù)，則n不是質數(shù)；若沒有這樣的數(shù)，則n是質數(shù)。,例2,寫出一個求有限整數(shù)序列中的最大值的算法。,解：算法如下： S1 先假定序列中的第一個整數(shù)為“最大值”。,S2 將序列中的下一個整數(shù)值與“最大值”比較，如果它大于此“最大值”，這時你就假定“最大值”是這個整數(shù)。,S3 如果序列中還有其他整數(shù)，重復S2

5、。,S4 在序列中一直到沒有可比的數(shù)為止，這時假定的“最大值”就是這個序列中的最大值。,例3,寫出求 的值的算法。,解法1：算法如下： S1 先求 ，得到結果2； S2 將第一步所得結果2再乘以3，得到結果6。 S3 將6再乘以4，得到24； S4 將24再乘以5，得到120； S9 將362880再乘以10，得到3628800，即是最后的結果。,例,用二分法設計一個求方程 的近似正根的算法，精確度0.05。,解,練習 任意給定一個正實數(shù)a，試設計一個算法求 以a為直徑的圓的面積。,第一步：輸入a的值.,第二步：_. 第三步：_. 第四步：輸出圓的面積的值.,解,例,任意給定一個大于1的整數(shù)n

6、，試設計 一個程序或步驟對n是否為質數(shù)作出判斷。,第一步：判斷n是否等于2。若n2，則n是質數(shù)； 若n2，則執(zhí)行第二步；,第二步：依次從2到（n-1）檢驗是不是n的因數(shù)， 即是否能整除n的數(shù)。若有這樣的數(shù)，則n不是 質數(shù)；否則，n是質數(shù)。,解：,練習 任意給定3個正實數(shù)，試設計一個算法，判斷 分別以這三個數(shù)為三邊邊長的三角形是否存在。,第一步: 輸入三個正實數(shù)a , b , c.,解,第二步：？,小結：,算法的特征是什么？,算法的概念：算法通常指可以用來解決的某 一類問題的步驟或程序，這些步驟或程序必須是明 確的和有效的，而且能夠在有限步之內完成的。,2、算法的特點,（1）有限性,即一個算法的

7、步驟序列是有限的；,（2）確定性,即算法中的每一步應該是確定的并且能有效地執(zhí)行且得到確定的結果；,（4）邏輯性,即算法從初始步驟開始，分為若干明確的步驟，前一步是后一步的前提，只有執(zhí)行完前一步才能進行下一步，而且每一步都是正確無誤的，從而組成了一個有著很強邏輯性的步驟序列；,（5）不唯一性,即求解一個問題的算法不一定是唯一的；,（6）普遍性,即很多具體的問題，都可以設計合理的算法去解決。,（3）有效性 算法中的每一個步驟都是可以在有限的時 間內完成的基本操作，并能得到確定的結果 。,二、 算法的表示,1. 用自然語言表示,2. 用程序框圖表示,終端框（起止框）,處理框,輸入輸出框,判斷框,流程

8、線,常用流程圖符號（程序框）,表示一個算法的起始和結束,表示一個算法輸入和輸出的信息,判斷某一條件是否成立，成立時在 出口處標明“是”或“Y”；不成立時 標明“否”或“N”.,賦值、計算,表示流程的路徑和方向,二、 算法的表示,1. 用自然語言表示,2. 用程序框圖表示,第一步：判斷n是否等于2. 若n=2,則n是質數(shù);若n2, 則執(zhí)行第二步. 第二步:依次從2到(n-1)檢驗是不是n的因數(shù), 即整數(shù)n 的數(shù), 若有這樣的數(shù), 則n 不是質數(shù); 若沒有這樣的 數(shù), 則n 是質數(shù).,例1 任意給定一個大于1的整數(shù)n ，試設計一個程序 或步驟對n是否為質數(shù)做出判定。,二、 算法的表示,1. 用自然

9、語言表示 優(yōu)點是使用日常用語, 通俗易懂 缺點是文字冗長, 容易出現(xiàn)歧義,2. 用程序框圖表示: 用圖框表示各種操作 優(yōu)點是直觀形象, 易于理解,比較自然語言與程序框圖表示方法的各自特點,順序結構,條件結構,循環(huán)結構,P,A,三種基本結構（表示一個良好算法的基本單元）,順序結構,條件結構（選擇結構）,循環(huán)結構,While（當型）循環(huán),Until（直到型）循環(huán),成立,不成立,順序結構,由若干個依次執(zhí)行的處理步驟組成的。,例1 已知一個三角形的三邊邊長分別為2、3、4，利用 海倫-秦九韶公式設計一個算法，求出它的面積，畫出 它的程序框圖.,條件結構（選擇結構）,算法的流程根據條件是否成立有不同的流

10、向,例2 任意給定3個正實數(shù)，設計一個算法， 判斷分別以這3個數(shù)為三邊邊長的三角形是 否存在.畫出這個算法的程序框圖.,例3 設計房租收費的算法,其要求是:住房面積80平方米以內,每平方米收費3元,住房面積超過80平方米時,超過部分,每平方米收費5元.輸入住房面積數(shù),輸出應付的房租.,算法分析：,第一步：輸入住房面積S,第二步：根據面積選擇計費方式：如果S小于或等于80，則租金為M=s3，否則為M=240+(S-80)5,第三步：輸出房租M的值。,小結：,算法的特征是什么？,算法的概念：算法通常指可以用來解決的某 一類問題的步驟或程序，這些步驟或程序必須是明 確的和有效的，而且能夠在有限步之內完成的。,2、算法的特點,（1）有限性,即一個算法的步驟序列是有限的；,（2）確定性,即算法中的每一步應該是確定的并且能有效地執(zhí)行且得到確定的結果；,（4）邏輯性,即算法從初始步驟開始，分為若干明確的步驟，前一步是后一步的前提，只有執(zhí)行完前一步才能進行下一步，而且每一步都是正確無誤的，從而組成了一個有著很強邏輯性的步驟序列；,（5）不唯一性,即求解一個問題的算法不一定是唯一的；,（6）普遍性,即很多具體的問題，都可以設計合理的算法去