2012高考數(shù)學一輪復習：1.1.1《算法的概念》課件(人教A版必修3).ppt

1、算法與程序框圖,一人帶著一只狼、一只羊和一箱蔬菜要過河,但只有一條小船.乘船時，每次只能帶狼、羊和蔬菜中的一種.當有人在場時，狼、羊、蔬菜都相安無事.一旦人不在,狼會吃羊,羊會吃菜.請設(shè)計一個方案,安全地將狼、羊和蔬菜帶過河.,趣味益智游戲,如何發(fā)電子郵件？,1.1.1 算法的概念,一般地,對于一類問題的機械式地、統(tǒng)一地、按部就班地求解過程稱為算法(algorithm)它是解決某一問題的程序或步驟.,按照這樣的理解,我們可以設(shè)計出很多具體數(shù)學問題的算法.下面看幾個例子:,所謂 “算法”就是解題方法的精確描述.從更廣義的角度來看,并不是只有“計算”的問題才有算法,日常生活中處處都有.如樂譜是樂隊

2、演奏的算法,菜譜是做菜肴的算法,珠算口訣是使用算盤的算法.,第二步, 解得,第三步, - 2得 5y=3; ,第四步, 解得,做一做,你能寫出解一般的二元一次方程組的步 驟嗎？,第一步,第二步,解（3）得,思考,第四步,解（4）得,第三步,第五步,得到方程組的解為,第一步：,第二步：,第三步：,-,事實上，我們可以將一般的二元一次方程組的解法轉(zhuǎn)化成計算機語言，做成一個求解二元一次方程組的程序.,這兒已經(jīng)做好了，試一試吧！,練習1. 給出求1+2+3+4+5+6的一個算法.,解法1.按照逐一相加的程序進行.,第一步:計算1+2,得3;,第二步:將第一步中的運算結(jié)果3與3相加得6;,第三步:將第二

3、步中的運算結(jié)果6與4相加得10;,第四步:將第三步中的運算結(jié)果10與5相加得15;,第五步:將第四步中的運算結(jié)果15與6相加得21.,解法2.可以運用下面公式直接計算.,第一步,取 n =6;,第二步,計算 ;,第三步,輸出計算結(jié)果.,點評:解法1繁瑣,步驟較多; 解法2簡單，步驟較少. 找出好的算法是我們的追求目標.,現(xiàn)在你對算法有了新的認識了嗎？,在數(shù)學中，算法通常是指按照一定規(guī)則解決某一類問題的明確和有限的步驟.現(xiàn)在，算法通?？梢跃幊捎嬎銠C程序，讓計算機執(zhí)行并解決問題.,2.算法的要求,(1)寫出的算法,必須能解決一類問題(例如解任意一個二元一次方程組),并且能重復使用;,(2) 算法過

4、程要能一步一步執(zhí)行,每一步執(zhí)行的操作,必須確切,不能含混不清,而且在有限步之內(nèi)完成后能得出結(jié)果.,1.算法的定義,講授新課,3.算法的基本特征:,明確性:算法對每一個步驟都有確切的、非二義性的規(guī)定,即每一步對于利用算法解決問題的人或計算機來說都是可讀的、可執(zhí)行的,而不需要計算者臨時動腦筋.,有效性:算法的每一個步驟都能夠通過基本運算有效地進行,并得到確定的結(jié)果；對于相同的輸入,無論誰執(zhí)行算法,都能夠得到相同的最終結(jié)果,講授新課,有限性:算法應由有限步組成,至少對某些輸入,算法應在有限多步內(nèi)結(jié)束,并給出計算結(jié)果,信息輸出:一個算法至少要有一個有效的信息輸出,這就是問題求解的結(jié)果.,不唯一性:求解

5、某一個題的解法不一定是唯一的, 對于一個問題可以有不同的算法.,4.算法的描述:,描述算法可以有不同的方式,常用的有自然語言、程序框圖、程序設(shè)計語言、偽代碼等.,數(shù)據(jù)輸入:算法一定要根據(jù)輸入的初始數(shù)據(jù)或給定的初值才能正確執(zhí)行它的每一步驟.,自然語言就是人們?nèi)粘Ｊ褂玫恼Z言,可以是漢語、英語或數(shù)學語言等.用自然語言描述算法的優(yōu)點是通俗易懂,當算法中的操作步驟都是順序執(zhí)行時比較容易理解.缺點是如果算法中包含判斷和轉(zhuǎn)向,并且操作步驟較多時,就不那么直觀清晰了.,(1)自然語言,(2)程序框圖,(3)程序設(shè)計語言,1.1.2程序框圖中講解,1.2基本算法語句中講解,例1.(1)設(shè)計一個算法判斷7是否為質(zhì)

6、數(shù).,第一步, 用2除7,得到余數(shù)1.因為余數(shù)不為0， 所以2不能整除7.,第二步, 用3除7,得到余數(shù)1.因為余數(shù)不為0， 所以3不能整除7.,第三步, 用4除7,得到余數(shù)3.因為余數(shù)不為0， 所以4不能整除7.,第四步, 用5除7,得到余數(shù)2.因為余數(shù)不為0， 所以5不能整除7.,第五步, 用6除7,得到余數(shù)1.因為余數(shù)不為0， 所以6不能整除7.因此，7是質(zhì)數(shù).,例1.(2)設(shè)計一個算法判斷35是否為質(zhì)數(shù).,第一步, 用2除35,得到余數(shù)1.因為余數(shù)不為0， 所以2不能整除35.,第二步, 用3除35,得到余數(shù)2.因為余數(shù)不為0， 所以3不能整除35.,第三步, 用4除35,得到余數(shù)3.

7、因為余數(shù)不為0， 所以4不能整除35.,第四步, 用5除35,得到余數(shù)0.因為余數(shù)為0， 所以5能整除35.因此，35不是質(zhì)數(shù).,變式1: “判斷53是否質(zhì)數(shù)”的算法如下： 第1步,用2除53得余數(shù)為1,余數(shù)不為0,所以2不能整除53; 第2步,用3除53得余數(shù)為2,余數(shù)不為0,所以3不能整除53; 第52步,用52除53得余數(shù)為1,余數(shù)不為0,故52不能整除53; 所以53是質(zhì)數(shù).,上述算法正確嗎？請說明理由.,算法要“面面俱到”,不能省略任何一個細小的步驟,只有這樣,才能在人設(shè)計出算法后,把具體的執(zhí)行過程交給計算機完成.,設(shè)計一個具體問題的算法時,與過去熟悉地解數(shù)學題的過程 有直接的聯(lián)系,

8、但這個過程必須被分解成若干個明確的步驟, 而且這些步驟必須是有效的.,變式2:任意給定一個大于1的整數(shù)n,試設(shè)計一個程序或步驟對n是否為質(zhì)數(shù)做出判定.,分析:回顧這個問題的解題過程.,算法步驟:,第一步:判斷n是否等于2.,若n=2,則n是質(zhì)數(shù);,若n2,則執(zhí)行第二步.,第二步:依次檢驗2(n-1)這些整數(shù)是不是n的約數(shù),即是不是整除n的數(shù).若有這樣的數(shù),則n不是質(zhì)數(shù);若沒有這樣的數(shù),則n是質(zhì)數(shù).,二分法,對于區(qū)間a,b 上連續(xù)不斷、且 f(a)f(b)0的函數(shù)y=f(x),通過不斷地 把函數(shù)f(x)的零點所在的區(qū)間一分 為二，使區(qū)間的兩個端點逐步逼近 零點，進而得到零點或其近似值的 方法叫做

9、二分法.,第四步, 若f(a) f(m) 0,則含零點的區(qū)間為a,m；,第二步, 給定區(qū)間a,b,滿足f(a) f(b)0,第三步, 取中間點,第五步,判斷f(m)是否等于或者a,b的長度是否小于d，若是，則m是方程的近似解;否則，返回第三步,將新得到的含零點的仍然記為a,b.,否則，含零點的區(qū)間為m, b.,算法步驟： 第一步, 令 ,給定精確度d.,當d=0.005時，按照以上算法，可得下面表和圖.,于是，開區(qū)間（1.4140625,1.41796875）中的實數(shù)都是當精確度為0.005時的原方程的近似解.,練習2. 任意給定一個正實數(shù),設(shè)計一個算法求以這個數(shù)為半徑的圓的面積.,算法步驟:,第一步:給定一個正實數(shù)r; 第二步:計算以r為半徑的圓的面積S=r2; 第三步:得到圓的面積S.,練習3. 任意給定一個大于 1 的正整數(shù) n ，設(shè)計一個算法求出 n 的所有因數(shù).,算法步驟：,第一步, 依次以2 （n 1）為除數(shù)除 n ，檢查余數(shù)是否為0；若是，則是 n 的因數(shù)；若不是，則不是 n 的因數(shù)；,第二步, 在 n 的因數(shù)中加入 1 和 n；,第三步, 輸出n的所有因數(shù).,練習4. 寫出求一元二次方程 ax2+bx+c=0 的根的算法.,第一步,計算=b2-4ac.,第二步,如果0,則原方程無實數(shù)解 ;否則(0)時，,第三步:輸出x1, x2或無實數(shù)解.,小結(jié)：,算法的特征