高中數(shù)學(xué)《算法的概念》課件(新人教B版必修)

1、 算法算法作為一個名詞，在中學(xué)教科書中作為一個名詞，在中學(xué)教科書中并沒有出現(xiàn)過，我們在基礎(chǔ)教育階段還并沒有出現(xiàn)過，我們在基礎(chǔ)教育階段還沒有接觸算法概念。但是我們卻從小學(xué)沒有接觸算法概念。但是我們卻從小學(xué)就開始接觸算法，熟悉許多問題的算法。就開始接觸算法，熟悉許多問題的算法。如，做四則運算要如，做四則運算要先乘除后加減先乘除后加減，從里，從里往外脫括弧，豎式筆算等都是算法，至往外脫括弧，豎式筆算等都是算法，至于于乘法口訣乘法口訣、珠算口訣珠算口訣更是算法的具體更是算法的具體體現(xiàn)。體現(xiàn)。 我們知道我們知道解一元二次方程解一元二次方程的算法，求的算法，求解一元一次不等式、一元二次函數(shù)圖象解一元一次不

2、等式、一元二次函數(shù)圖象的畫法，解線性方程組的算法，求兩個的畫法，解線性方程組的算法，求兩個數(shù)的最大公因數(shù)的算法等。因此，數(shù)的最大公因數(shù)的算法等。因此，算法其實是重要的數(shù)學(xué)對象算法其實是重要的數(shù)學(xué)對象。一、算法的概念一、算法的概念 算法算法(algorithm)一詞源于算術(shù)一詞源于算術(shù)(algorism),即算術(shù)方法，是指一個即算術(shù)方法，是指一個由已知推求未知由已知推求未知的的運算過程。后來，人們把它推廣到一般，運算過程。后來，人們把它推廣到一般，把把進(jìn)行某一工作的方法和步驟進(jìn)行某一工作的方法和步驟稱為算法。稱為算法。 廣義地說，廣義地說，算法就是做某一件事的步算法就是做某一件事的步驟或程序驟或

3、程序。菜譜是做菜肴的算法，洗衣。菜譜是做菜肴的算法，洗衣機的使用說明書是操作洗衣機的算法，機的使用說明書是操作洗衣機的算法，歌譜是一首歌曲的算法。歌譜是一首歌曲的算法。 在數(shù)學(xué)中，在數(shù)學(xué)中，主要研究計算機能實現(xiàn)的主要研究計算機能實現(xiàn)的算法算法，即按照某種機械程序步驟一定可，即按照某種機械程序步驟一定可以得到結(jié)果的解決問題的程序。比如解以得到結(jié)果的解決問題的程序。比如解方程的算法、函數(shù)求值的算法、作圖的方程的算法、函數(shù)求值的算法、作圖的算法，等等。算法，等等。例例1 “一群小兔一群雞，兩群合到一群里，一群小兔一群雞，兩群合到一群里，要數(shù)腿共要數(shù)腿共48，要數(shù)腦袋整，要數(shù)腦袋整17，多少小兔，多少

4、小兔多少雞？多少雞？”解：算術(shù)方法：如果沒有小兔，那么小雞解：算術(shù)方法：如果沒有小兔，那么小雞應(yīng)為應(yīng)為17只，總的腿數(shù)應(yīng)為只，總的腿數(shù)應(yīng)為217=34條，條，但現(xiàn)在有但現(xiàn)在有48條腿，造成腿的數(shù)目不夠是由條腿，造成腿的數(shù)目不夠是由于小兔的數(shù)目為于小兔的數(shù)目為0，每有一只小兔便會增，每有一只小兔便會增加兩條腿，故應(yīng)有加兩條腿，故應(yīng)有(48172) 2=7只小只小兔。相應(yīng)的，小雞有兔。相應(yīng)的，小雞有10只。只。代數(shù)方法：設(shè)有代數(shù)方法：設(shè)有x只小雞，只小雞，y只小兔只小兔. 則則172448xyxy將第一個方程的兩邊同乘以將第一個方程的兩邊同乘以2加到第二加到第二個方程中去，得到個方程中去，得到17

5、(42)48 17 2xyy解第二個方程得解第二個方程得y=7.把把y代入到第一個方程得代入到第一個方程得x=10.思考思考1 教材中例教材中例1是著名的是著名的“雞兔同籠雞兔同籠”問題，其中第一種解法是算術(shù)方法，教問題，其中第一種解法是算術(shù)方法，教材中對它的評價是材中對它的評價是“簡單直觀，卻包含簡單直觀，卻包含著深刻的算法思想著深刻的算法思想”，那么它是如何體，那么它是如何體現(xiàn)算法的思想呢？現(xiàn)算法的思想呢？S1 假設(shè)沒有小兔，則小雞應(yīng)為假設(shè)沒有小兔，則小雞應(yīng)為n只；只；S2 計算總腿數(shù)為計算總腿數(shù)為2n只；只； S3 計算實際總腿數(shù)與假設(shè)總腿數(shù)的差值計算實際總腿數(shù)與假設(shè)總腿數(shù)的差值為為m2

6、n；S4 計算小兔只數(shù)為計算小兔只數(shù)為 ; 22mnS5 小雞的只數(shù)為小雞的只數(shù)為n . 22mn思考思考2 教材中例教材中例1的第二種解法是列方程的第二種解法是列方程組的方法，它是否也是一種算法呢？組的方法，它是否也是一種算法呢？探究：是的，其算法步驟為：探究：是的，其算法步驟為： S1 設(shè)未知數(shù)；設(shè)未知數(shù)；S2 根據(jù)題意列方程組；根據(jù)題意列方程組；S3 解方程組；解方程組；S4 還原實際問題，得到實際問題的答案。還原實際問題，得到實際問題的答案。 在實際中，很多問題可以歸結(jié)為求解在實際中，很多問題可以歸結(jié)為求解二元一次方程組，下面我們用消元法來二元一次方程組，下面我們用消元法來解一般的二元

7、一次方程組解一般的二元一次方程組11 1122121 12222 a xa xba xa xbS1 假定假定a110，a11a21得得 11 11221112221 12211 221 1 ()a xa xba aa axa ba bS2 如果如果a11a22a12a210，則執(zhí)行下步；，則執(zhí)行下步； 否則執(zhí)行否則執(zhí)行S6S3 兩邊同除以兩邊同除以a11a22a12a210得得 11 1122111 221 12112221 12 a xa xba ba bxa aa aS4 代入代入.得得 22 11221112221 1211 221 12112221 12 a ba bxa aa aa

8、ba bxa aa aS5 輸出結(jié)果輸出結(jié)果x1，x2， S6 若若a11b2a21b10. 則執(zhí)行下一步；否則執(zhí)行下一步；否則執(zhí)行則執(zhí)行S8S7 輸出輸出“方程組無解方程組無解”.S8 輸出輸出“方程組有無窮多個解方程組有無窮多個解” 以上解二元一次方程組的方法，叫做以上解二元一次方程組的方法，叫做高斯消去法高斯消去法二、算法的特點二、算法的特點 不論在哪一種算法中，它們都是經(jīng)有限不論在哪一種算法中，它們都是經(jīng)有限次步驟完成的，因而它們體現(xiàn)了次步驟完成的，因而它們體現(xiàn)了算法的有算法的有窮性窮性。 在算法中，每一步都能明確地執(zhí)行，在算法中，每一步都能明確地執(zhí)行，且有確定的結(jié)果，因此具有且有確定

9、的結(jié)果，因此具有確定性確定性。 在所有算法中，每一步操作都是可以在所有算法中，每一步操作都是可以執(zhí)行的，也就是具有執(zhí)行的，也就是具有可行性可行性。 為了便于計算機運算，它們必須先輸入為了便于計算機運算，它們必須先輸入已知數(shù)據(jù)，而計算的目的分別是解方程組已知數(shù)據(jù)，而計算的目的分別是解方程組和求最大值等，因此必須輸出結(jié)果，也就和求最大值等，因此必須輸出結(jié)果，也就是必須有輸入和輸出。是必須有輸入和輸出。 算法解決的都是一類問題（分別是解決算法解決的都是一類問題（分別是解決求方程組的解和確定一個有理整數(shù)序列中求方程組的解和確定一個有理整數(shù)序列中的最大值問題），因此具有的最大值問題），因此具有普適性普適

10、性。體驗體驗 ：寫出解方程：寫出解方程x22x3=0的一個算法的一個算法. 配方法：配方法：S1 移項，得移項，得x22x=3 S2 式兩邊同加式兩邊同加1并配方得并配方得 (x1)2=4 S3 式兩邊開方，得式兩邊開方，得x1=2 S4 解解式得式得x=3或或x=1因式分解法：因式分解法：S1 將方程左邊因式分解得將方程左邊因式分解得(x3)(x+1)=0 S2 由由得得x3=0或或x+1=0 S3 解解得得x=3或或x1公式法：公式法：S1 計算方程的判別式，判斷其符號計算方程的判別式，判斷其符號 =(2)24(3)0；S2 將將a=1，b=2，c=3代入求根公式，代入求根公式， 得得x=

11、3或或x=1例例2 寫出一個求有限整數(shù)列中的最大值寫出一個求有限整數(shù)列中的最大值的算法。的算法。解：算法如下：解：算法如下： S1 先假定序列中的第一個整數(shù)為先假定序列中的第一個整數(shù)為“最大值最大值”; S2 將序列中的下一個整數(shù)值與將序列中的下一個整數(shù)值與“最大值最大值”比比較，如果它大于此較，如果它大于此“最大值最大值”，這時你就假定，這時你就假定“最大值最大值”是這個整數(shù)；是這個整數(shù)； S3 如果序列中還有其他整數(shù)，重復(fù)如果序列中還有其他整數(shù)，重復(fù)S2; S4 在序列中一直到?jīng)]有可比的數(shù)為止，這時在序列中一直到?jīng)]有可比的數(shù)為止，這時假定的假定的“最大值最大值”就是這個序列中的最大值。就是

12、這個序列中的最大值。 如果讓你去找，你可能不會這樣做，可如果讓你去找，你可能不會這樣做，可能認(rèn)為，這樣太機械、太枯燥。不要忘了，能認(rèn)為，這樣太機械、太枯燥。不要忘了，我們寫的是算法。算法要求我們寫的是算法。算法要求按部就班按部就班地做，地做，每一步都有每一步都有唯一的結(jié)果唯一的結(jié)果，又要求寫出的算，又要求寫出的算法對法對任意整數(shù)序列都適用任意整數(shù)序列都適用，總能得到結(jié)果。，總能得到結(jié)果。所以上面寫的，符合算法的要求。所以上面寫的，符合算法的要求。 下面我們用數(shù)學(xué)語言，寫出對任意下面我們用數(shù)學(xué)語言，寫出對任意3個個整數(shù)整數(shù)a，b，c求出最大值的算法。求出最大值的算法。S1 max=aS2 如果如

13、果bmax, 則則max=b.S3 如果如果Cmax, 則則max=c.S4 max就是就是a, b, c中的最大值。中的最大值。例例3 寫出求寫出求1+2+3+4+5+6的一個算法。的一個算法。解：算法解：算法1：S1 計算計算1+2得到得到3；S2 將第一步中的運算結(jié)果將第一步中的運算結(jié)果3與與3相加得到相加得到6S3 將第二步中的運算結(jié)果將第二步中的運算結(jié)果6與與4相加得到相加得到10S4 將第三步中的運算結(jié)果將第三步中的運算結(jié)果10與與5相加得到相加得到15S5 將第四步中的運算結(jié)果將第四步中的運算結(jié)果15與與6相加得到相加得到21算法算法2：S1：取：取n=6；S2：計算：計算S3：

14、輸出運算結(jié)果。：輸出運算結(jié)果。2) 1( nn算法算法3：S1 將原式變形為將原式變形為(1+6)+(2+5)+(3+4)=37；S2 計算計算37；S3 輸出運算結(jié)果。輸出運算結(jié)果。例例4. 求求1357911的值，寫出其的值，寫出其算法。算法。算法算法1；第一步，先求第一步，先求13，得到結(jié)果，得到結(jié)果3；第二步，將第一步所得結(jié)果第二步，將第一步所得結(jié)果3再乘以再乘以5，得，得到結(jié)果到結(jié)果15；第三步，再將第三步，再將15乘以乘以7，得到結(jié)果，得到結(jié)果105；第四步，再將第四步，再將105乘以乘以9，得到，得到945；第五步，再將第五步，再將945乘以乘以11，得到，得到10395，即，即

15、是最后結(jié)果。是最后結(jié)果。算法算法2：用：用P表示被乘數(shù)，表示被乘數(shù)，i表示乘數(shù)。表示乘數(shù)。S1 使使P=1;S2 使使i=3;S3 使使P=Pi；S4 使使i=i+2；S5 若若i11，則返回到，則返回到S3繼續(xù)執(zhí)行；否則繼續(xù)執(zhí)行；否則算法結(jié)束。算法結(jié)束。 由于計算機動是高速計算的自動機器，由于計算機動是高速計算的自動機器，實現(xiàn)實現(xiàn)循環(huán)循環(huán)的語句可以在很短的時間內(nèi)完成。的語句可以在很短的時間內(nèi)完成。對于對于循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)的詳細(xì)情況，我們將在以后的詳細(xì)情況，我們將在以后的學(xué)習(xí)中介紹。的學(xué)習(xí)中介紹。 例例6. 利用二分法求函數(shù)利用二分法求函數(shù)y=f(x) (x在定義區(qū)在定義區(qū)間間D) 上的一個變

16、號零點上的一個變號零點x0的近似值的近似值x，使，使它與零點的誤差不超過正數(shù)它與零點的誤差不超過正數(shù) ，即使，即使|xx0| ，寫出它的一個算法，寫出它的一個算法.S1 在在D內(nèi)取一個閉區(qū)間內(nèi)取一個閉區(qū)間a，b，使，使f(a)與與f(b)異號，即異號，即f(a)f(b)0；S2 令令x0= ，計算，計算f(x0)； 2abS3 若若f(x0)=0，則，則x0就是就是y=f(x)的零點；的零點；若若f(x0)與與f(a)異號，則異號，則a=a，b=x0，否則，否則a=x0，b=b；S4 判斷判斷|ab|是否成立，若成立，則是否成立，若成立，則區(qū)間區(qū)間a，b內(nèi)任意實數(shù)都是內(nèi)任意實數(shù)都是x0的近似值；的近似值；否則，返回否則，返回S2，直到不等式，直到不等式 |ab|2x +4；求求M(1，2)與與N(3，5)兩點連線的方程可兩點連線的方程可先求先求MN的斜率再利用點斜式方程求得的斜率再利用點斜式方程求得A. 1 個個 B. 2 個個 C. 3 個個 D. 4 個個21C6寫出求寫出求123100的一個算法的