算法的基本思想(北師大版)

1、第二章第二章 算法初步算法初步1 1 算法的基本思想算法的基本思想1.1.了解算法的含義，形成算法的初步印象，體會算法是解了解算法的含義，形成算法的初步印象，體會算法是解決問題的決問題的“機(jī)械機(jī)械”程序，并能在有限步內(nèi)解決問題；程序，并能在有限步內(nèi)解決問題；2.2.能夠用自然語言敘述算法；能夠用自然語言敘述算法；3.3.掌握正確的算法應(yīng)滿足的條件；掌握正確的算法應(yīng)滿足的條件；4.4.會寫出簡單問題的算法會寫出簡單問題的算法. . 作為家里的一員，在平時分擔(dān)一些力所能及的事是我們作為家里的一員，在平時分擔(dān)一些力所能及的事是我們應(yīng)盡的義務(wù)，你每天都幫家里做家務(wù)嗎？你會燒開水嗎？請應(yīng)盡的義務(wù)，你每天

2、都幫家里做家務(wù)嗎？你會燒開水嗎？請寫出你在家中燒開水的過程寫出你在家中燒開水的過程. .1 1、往壺內(nèi)注水；、往壺內(nèi)注水；2 2、點火加熱；、點火加熱；3 3、觀察：如果水開，則停止燒火，否則繼續(xù)燒火；、觀察：如果水開，則停止燒火，否則繼續(xù)燒火；4 4、如果水未開，重復(fù)過程、如果水未開，重復(fù)過程 “ “3”3”，直至水開，直至水開. .2 2、判斷水是否燒開與是否繼續(xù)燒火的過程是一個反饋、判斷水是否燒開與是否繼續(xù)燒火的過程是一個反饋與判斷的過程，因此有必要不斷重復(fù)過程與判斷的過程，因此有必要不斷重復(fù)過程“3”. 3”. 小結(jié)：小結(jié)：1 1、其實大部分事情都是按照一定的程序執(zhí)行的，因此、其實大部

3、分事情都是按照一定的程序執(zhí)行的，因此要理清事情的每一步要理清事情的每一步. . 事實上，我們完成任何事，都要有步驟，合理安排步事實上，我們完成任何事，都要有步驟，合理安排步驟，會達(dá)到事半功倍的效果驟，會達(dá)到事半功倍的效果. .從我們數(shù)學(xué)的意義來講，在解從我們數(shù)學(xué)的意義來講，在解決某些問題時，需要設(shè)計出一系列可操作或可計算的步驟，決某些問題時，需要設(shè)計出一系列可操作或可計算的步驟，通過實施這些步驟來解決問題，我們通常把這些步驟稱為通過實施這些步驟來解決問題，我們通常把這些步驟稱為解決問題的一種算法解決問題的一種算法. .這種描述不是算法的定義，但反映了這種描述不是算法的定義，但反映了算法的基本思

4、想算法的基本思想. . 隨著計算科學(xué)和信息技術(shù)的飛速發(fā)展，算法的思想隨著計算科學(xué)和信息技術(shù)的飛速發(fā)展，算法的思想已經(jīng)滲透到社會的方方面面已經(jīng)滲透到社會的方方面面. .在以前的學(xué)習(xí)中，雖然沒有在以前的學(xué)習(xí)中，雖然沒有出現(xiàn)算法這個名詞，但實際上在數(shù)學(xué)教學(xué)中已經(jīng)滲透了出現(xiàn)算法這個名詞，但實際上在數(shù)學(xué)教學(xué)中已經(jīng)滲透了大量的算法思想，如四則運算的過程、求解方程的步驟大量的算法思想，如四則運算的過程、求解方程的步驟等等等等. .完成這些工作都需要一系列程序化的步驟，這就是完成這些工作都需要一系列程序化的步驟，這就是算法的思想算法的思想. . 例例1 1 在電視臺的某個娛樂節(jié)目中，要求參與者快速猜出物品的價

5、格在電視臺的某個娛樂節(jié)目中，要求參與者快速猜出物品的價格. .主持人出示某件物品，參與者每次估算出一個價格，主持人只能回答主持人出示某件物品，參與者每次估算出一個價格，主持人只能回答高了、低了或者正確高了、低了或者正確. .在某次節(jié)目中，主持人出示了一臺價值在在某次節(jié)目中，主持人出示了一臺價值在10001000元元以內(nèi)的隨身聽，并開始了競猜以內(nèi)的隨身聽，并開始了競猜. .下面是主持人和參與者的一段對話：下面是主持人和參與者的一段對話：如果你是參與者，你接下來會怎么猜？如果你是參與者，你接下來會怎么猜？800元！高了!400元！600元！低了!低了!參與者主持人主持人實際上，可以把過程概括如下：

6、實際上，可以把過程概括如下：例例2 2 在給定素數(shù)表的條件下，設(shè)計算法，將在給定素數(shù)表的條件下，設(shè)計算法，將936936分解分解成素因數(shù)的乘積成素因數(shù)的乘積.(4000.(4000以內(nèi)的素數(shù)表見課本附錄以內(nèi)的素數(shù)表見課本附錄1)1)解解: :算法步驟如下：算法步驟如下：1.1.判斷判斷936936是否為素數(shù)：否是否為素數(shù)：否. .2.2.確定確定936936的最小素因數(shù)：的最小素因數(shù)：2. 936=22. 936=24684683.3.判斷判斷468468是否為素數(shù)：否是否為素數(shù)：否. .4.4.確定確定468468的最小素因數(shù)：的最小素因數(shù)：2. 936=22. 936=22 2234234

7、5.5.判斷判斷234234是否為素數(shù)：否是否為素數(shù)：否. .6.6.確定確定234234的最小素因數(shù)：的最小素因數(shù)：2. 936=22. 936=22 22 21171177.7.判斷判斷117117是否為素數(shù)：否是否為素數(shù)：否. .8.8.確定確定117117的最小素因數(shù)：的最小素因數(shù)：3. 936=23. 936=22 22 23 339399.9.判斷判斷3939是否為素數(shù)：否是否為素數(shù)：否. .10.10.確定確定3939的最小素因數(shù)：的最小素因數(shù)：3. 936=23. 936=22 22 23 33 31313判斷判斷1313是否為素數(shù)：是否為素數(shù)：1313是素數(shù)，所以分解結(jié)束是素

8、數(shù)，所以分解結(jié)束. .分解結(jié)果是：分解結(jié)果是： 936=2936=22 22 23 33 31313 例例3 3 設(shè)計一個算法，求設(shè)計一個算法，求840840與與17641764的最大公因數(shù)的最大公因數(shù). .1.1.先將先將840840進(jìn)行素因數(shù)分解：進(jìn)行素因數(shù)分解： ；2.2.然后將然后將17641764進(jìn)行素因數(shù)分解：進(jìn)行素因數(shù)分解： ；3.3.確定他們的公共素因數(shù)確定他們的公共素因數(shù)2,3,72,3,7；4.4.確定公共素因數(shù)的指數(shù)：公共素因數(shù)確定公共素因數(shù)的指數(shù)：公共素因數(shù)2,3,72,3,7的指數(shù)分別為的指數(shù)分別為2,1,1;2,1,1;5.5.最大公約數(shù)為最大公約數(shù)為: .: .解

9、：解：算法步驟如下：算法步驟如下：384023 5 7 222176423721123784例例4 “4 “韓信點兵韓信點兵”問題問題. .韓信是漢高祖劉邦手下的大將，他英勇善戰(zhàn)，韓信是漢高祖劉邦手下的大將，他英勇善戰(zhàn)，智謀超群，為建立漢朝立下了汗馬功勞智謀超群，為建立漢朝立下了汗馬功勞. .據(jù)說他在點兵的時候，為了據(jù)說他在點兵的時候，為了保住軍事機(jī)密，不讓敵人知道自己部隊的實力，采用下述點兵的方保住軍事機(jī)密，不讓敵人知道自己部隊的實力，采用下述點兵的方法：先令士兵從法：先令士兵從1 13 3報數(shù)，結(jié)果最后一個士兵報報數(shù)，結(jié)果最后一個士兵報2 2；再令士兵從；再令士兵從1 15 5報數(shù)，結(jié)果最

10、后一個士兵報報數(shù)，結(jié)果最后一個士兵報3 3；又令士兵從；又令士兵從1 17 7報數(shù)，結(jié)果最后一個報數(shù)，結(jié)果最后一個士兵報士兵報4.4.這樣，韓信很快就算出了自己部隊的總?cè)藬?shù)這樣，韓信很快就算出了自己部隊的總?cè)藬?shù). .請設(shè)計一個算請設(shè)計一個算法，求出士兵至少有多少人法，求出士兵至少有多少人? ?分析：分析：從報數(shù)情況分析，總?cè)藬?shù)除以從報數(shù)情況分析，總?cè)藬?shù)除以3 3余余2 2；總?cè)藬?shù)除以；總?cè)藬?shù)除以5 5余余3 3；總?cè)藬?shù)；總?cè)藬?shù)除以除以7 7余余4.4.算法的第一步是將所有的除以算法的第一步是將所有的除以3 3余余2 2的正整數(shù)找出來，按從小的正整數(shù)找出來，按從小到大排成一列到大排成一列. .第

11、二步是從第一步的數(shù)列中找出除以第二步是從第一步的數(shù)列中找出除以5 5余余3 3的一列數(shù)，按的一列數(shù)，按從小到大排成一列從小到大排成一列. .最后在滿足前兩個條件的第二步數(shù)列中再找出除以最后在滿足前兩個條件的第二步數(shù)列中再找出除以7 7余余4 4的一列數(shù)，這列數(shù)中最小的數(shù)，即為我們所求的數(shù)的一列數(shù)，這列數(shù)中最小的數(shù)，即為我們所求的數(shù). .（1 1）首先確定最小的滿足除以）首先確定最小的滿足除以3 3余余2 2的正整數(shù)：的正整數(shù)：2.2.解：解：具體算法步驟如下：具體算法步驟如下：（5 5）在第）在第4 4步得到的一列數(shù)中，找出滿足除以步得到的一列數(shù)中，找出滿足除以7 7余余4 4的最小的最小數(shù)：

12、數(shù)：53.53.這就是我們要求的數(shù)這就是我們要求的數(shù). .（4 4）然后依次加上）然后依次加上1515，得到，得到8 8，2323，3838，5353，顯然這，顯然這些數(shù)既滿足除以些數(shù)既滿足除以3 3余余2 2，又滿足除以，又滿足除以5 5余余3.3.（3 3）在上列數(shù)中確定最小的滿足除以）在上列數(shù)中確定最小的滿足除以5 5余余3 3的正整數(shù)：的正整數(shù)：8.8.（2 2）依次加）依次加3 3就得到所有除以就得到所有除以3 3余余2 2的正整數(shù)：的正整數(shù)：2 2，5 5，8 8，1111，1414，1717，2020，2323，2626，2929，3232，3535，3838，4141，4444

13、，4747，5050，5353，56563 3、算法要簡潔，要清晰可讀，不能繁雜，易程序化、算法要簡潔，要清晰可讀，不能繁雜，易程序化. .算法不同于求解一個具體問題的方法，是這種方法算法不同于求解一個具體問題的方法，是這種方法的高度概括的高度概括. .一個好的算法有如下要求：一個好的算法有如下要求：1 1、寫出的算法，必須能解決一類問題（如一元二次方、寫出的算法，必須能解決一類問題（如一元二次方程求根公式），并且能重復(fù)使用程求根公式），并且能重復(fù)使用. .2 2、算法過程要能一步一步執(zhí)行，每步執(zhí)行的操作，必、算法過程要能一步一步執(zhí)行，每步執(zhí)行的操作，必須確切，不能含混不清，而且在有限步能得出

14、結(jié)果須確切，不能含混不清，而且在有限步能得出結(jié)果. .例例5 5、寫出以下問題的算法：、寫出以下問題的算法：一位商人有一位商人有9 9枚銀元，其中有枚銀元，其中有1 1枚略輕的是假銀元枚略輕的是假銀元. .你能你能用天平（不用砝碼）將假銀元找出來嗎？用天平（不用砝碼）將假銀元找出來嗎？解解: : 1. 1.把銀元分成把銀元分成3 3組，每組組，每組3 3枚枚. . 2 2先將兩組分別放在天平的兩邊先將兩組分別放在天平的兩邊. .如果天平不平衡，那如果天平不平衡，那邊假銀元就放在輕的那一組；如果天平左右平衡，則假邊假銀元就放在輕的那一組；如果天平左右平衡，則假銀元就在末稱的第銀元就在末稱的第3

15、3組里組里. .3 3取出含假銀元的那一組，從中任取兩枚銀元放在天平取出含假銀元的那一組，從中任取兩枚銀元放在天平的兩邊的兩邊. .如果左右不平衡，則輕的那一邊就是假銀元；如如果左右不平衡，則輕的那一邊就是假銀元；如果天平兩邊平衡，則末稱的那一枚就是假銀元果天平兩邊平衡，則末稱的那一枚就是假銀元. .算法是什么？算法是什么？算法可以理解為由基本運算及規(guī)定的運算順序構(gòu)成的算法可以理解為由基本運算及規(guī)定的運算順序構(gòu)成的完整的解題步驟，或看成按要求設(shè)計好的、有限的、確完整的解題步驟，或看成按要求設(shè)計好的、有限的、確切的計算序列，并且這樣的步驟或序列能解決一類問題切的計算序列，并且這樣的步驟或序列能解

16、決一類問題. .現(xiàn)代意義上的現(xiàn)代意義上的“算法算法”通常是指可以用計算機(jī)來解決通常是指可以用計算機(jī)來解決的某一類問題的程序或步驟的某一類問題的程序或步驟. .說明：說明：1 1、算法實際上就是解決某一類問題的步驟和方法，在解、算法實際上就是解決某一類問題的步驟和方法，在解決問題時形成的規(guī)律性的東西，按照算法描述的規(guī)則與決問題時形成的規(guī)律性的東西，按照算法描述的規(guī)則與步驟，一步一步地去做，最終便能解決問題步驟，一步一步地去做，最終便能解決問題. .2 2、算法的基本思想就是我們分析問題時的想法、算法的基本思想就是我們分析問題時的想法. .由于想法由于想法不同、思考的角度不同，著手點不一樣，同一問

17、題存在不不同、思考的角度不同，著手點不一樣，同一問題存在不同的算法，算法有優(yōu)劣之分同的算法，算法有優(yōu)劣之分. .3 3、從熟悉的問題出發(fā)，體會算法的程序化思想，學(xué)會用、從熟悉的問題出發(fā)，體會算法的程序化思想，學(xué)會用自然語言來描述算法自然語言來描述算法. .例例6 6在函數(shù)的應(yīng)用部分在函數(shù)的應(yīng)用部分, ,我們學(xué)習(xí)了用二分法求方程我們學(xué)習(xí)了用二分法求方程f(x)=0f(x)=0的近似解的近似解. .如圖所示如圖所示分析：分析：y yx xO Oa ab bx x* *二分法的基本思想是二分法的基本思想是: :將方程的有將方程的有解區(qū)間分為兩個小區(qū)間解區(qū)間分為兩個小區(qū)間, ,然后判斷然后判斷解在哪個

18、小區(qū)間解在哪個小區(qū)間; ;繼續(xù)把有解的區(qū)繼續(xù)把有解的區(qū)間一分為二進(jìn)行判斷間一分為二進(jìn)行判斷, ,如此周而復(fù)如此周而復(fù)始始, ,直到求出滿足精度要求的近似直到求出滿足精度要求的近似解解. .其算法步驟如下其算法步驟如下5.5.判斷新的有解區(qū)間長度是否大于精確度判斷新的有解區(qū)間長度是否大于精確度: :(1)(1)如果新的有解區(qū)間長度大于精確度如果新的有解區(qū)間長度大于精確度, ,則在新的有解區(qū)間則在新的有解區(qū)間的基礎(chǔ)上重復(fù)上述步驟的基礎(chǔ)上重復(fù)上述步驟; ;(2)(2)如果新的有解區(qū)間長度小于或等于精確度如果新的有解區(qū)間長度小于或等于精確度, ,則這個有解則這個有解區(qū)間中的任意一個數(shù)均為方程的滿足精度

19、的近似解區(qū)間中的任意一個數(shù)均為方程的滿足精度的近似解. .3.3.計算計算f(0.5)=-0.625;f(0.5)=-0.625;6.6.計算計算f(0.75)=-0.015625;f(0.75)=-0.015625;9.9.計算計算f(0.875)=0.435 546 875;f(0.875)=0.435 546 875;10.10.由于由于f(0.75)f(0.875)0,f(0.75)f(0.875)0.1;0.75,0.875,0.875-0.75=0.1250.1;12.12.計算計算f(0.8125)=0.196533203125;f(0.8125)=0.196533203125;

20、所以，區(qū)間所以，區(qū)間0.75,0.81250.75,0.8125中的任一數(shù)值，都可以中的任一數(shù)值，都可以作為方程的近似解作為方程的近似解. .13.13.第一步第一步: :令令f(x)=xf(x)=x3 3+x+x2 2-1,-1,因為因為f(0)f(1)0,f(0)f(1)0,)f(m)0,則令則令x x1 1= m;= m;否則否則, ,令令x x2 2= m.= m.簡化寫法簡化寫法: :第四步第四步: :判斷判斷|x|x1 1-x-x2 2|0.1|0.1是否成立是否成立? ?若是若是, ,則則x x1 1,x,x2 2之間的中之間的中間值為滿足條件的近似解間值為滿足條件的近似解; ;若否若否, ,則返回第二步則返回第二步. .算法的特征算法的特征 有窮性：有窮性：一個算法應(yīng)包含有限的操作步驟而不應(yīng)是無限的一個算法應(yīng)包含有限的操作步驟而不應(yīng)是無限的; ; 確定性：確定性：算法中每一個步驟應(yīng)當(dāng)是