1.算法案的基本思想課件

2.1.1算法案例分析（1）1.算法案的基本思想算法的基本思想例1

在電視臺(tái)的某個(gè)娛樂節(jié)目中,要求參與者快速猜出物品價(jià)格.主持人出某件物品,參與者每次估算出一個(gè)價(jià)格,主持人只能回答高了、低了或者正確.在某次節(jié)目中，主持人出示了一臺(tái)價(jià)值在1000元以內(nèi)的隨身聽，并開始了競(jìng)猜.下面是主持人和參與者之間的一段對(duì)話：參與者：800元！主持人：高了！參與者：400元！主持人：低了！參與者：600元！主持人：低了！

……

如果你是參與者，你接下來會(huì)怎么猜？1.算法案的基本思想分析理解如果用P表示商品的價(jià)格，則參與者的猜測(cè)結(jié)果為：由主持人的第一次回答，P在0~800元之間；由主持人的第二次回答，P在400~800元之間；由主持人的第三次回答，P在600~800之間.1.算法案的基本思想根據(jù)參與者的猜測(cè)，我們知道，參與者首先需要確定的是商品價(jià)格的范圍，數(shù)學(xué)上一般可以用區(qū)間來表示，然后再根據(jù)主持人的回答，報(bào)出區(qū)間中點(diǎn)，將價(jià)格區(qū)間縮小一半.因此，下一步參與者要猜的數(shù)應(yīng)是700元，然后根據(jù)主持人的回答繼續(xù)猜，直至猜出正確價(jià)格.分析理解1.算法案的基本思想抽象概括實(shí)際上，可以把上述過程概括如下：1.報(bào)出首次價(jià)格T1；2.根據(jù)主持人的回答確定價(jià)格區(qū)間：（1）若報(bào)價(jià)小于商品價(jià)格，則商品的價(jià)格區(qū)間為（T1，1000）；（2）若報(bào)價(jià)大于商品價(jià)格，則商品的價(jià)格區(qū)間為（0，T1）；（3）若報(bào)價(jià)等于商品價(jià)格，則游戲結(jié)束.3.如果游沒有結(jié)束，則報(bào)出上面確定的價(jià)格區(qū)間的中點(diǎn)T2.按照上述方法，繼續(xù)判斷，直到游戲結(jié)束.

像這樣的一系列步驟通常稱為這個(gè)問題的一個(gè)算法.1.算法案的基本思想分析理解1.查表判斷936是否是素?cái)?shù)：（1）如果936是素?cái)?shù)，則分解結(jié)束；（2）如果不是素?cái)?shù)，則進(jìn)行第2步.2.確定936的最小素因數(shù):2.936=2×4683.查表判斷468是否則是素?cái)?shù):(1)如果468是素?cái)?shù),則分解結(jié)束;(2)如果468不是素?cái)?shù),則重復(fù)上述步驟,確定468的最小素因數(shù).重復(fù)進(jìn)行上述步驟,直到找出936的所有素因數(shù).例2

在給定素?cái)?shù)表的條件下，設(shè)計(jì)算法，將936分解成素因數(shù)的乘積（4000以內(nèi)的素?cái)?shù)見附錄1）1.算法案的基本思想解算法步驟如下:1.判斷936是否為素?cái)?shù):否.2.確定936的最小素因數(shù):2.936=2×468.3.判斷468是否為素?cái)?shù):否.4.確定468最小素因數(shù):2.936=2×2×234.5.判斷234是否為素?cái)?shù)：否.6.確定234最小素因數(shù)：2.936=2×2×2×1177.判斷117是否為素?cái)?shù)：否.分析理解短除法1.算法案的基本思想8.確定117最小素因數(shù)：3.936=2×2×2×3×39.9.判斷39是否為素?cái)?shù)：否.10.確定39的最小素因數(shù)：3.936=2×2×2×3×3×1311.判斷13是否為素?cái)?shù)：13是素?cái)?shù).所以分解結(jié)束.

分解結(jié)果是：936=2×2×2×3×3×13分析理解1.算法案的基本思想分析理解

按照以上程序，完成了對(duì)936的素因數(shù)分解.實(shí)際上，在給定素?cái)?shù)表的基礎(chǔ)上，對(duì)任意自然數(shù)n，都可以按照上述辦法進(jìn)行分解.

以上步驟是解決素因數(shù)分解問題的一個(gè)過程，只要依照這一系列步驟，都能解決這個(gè)問題.我們把這一系列步驟成為解決這個(gè)問題的一個(gè)算法.1.算法案的基本思想

我們已經(jīng)學(xué)習(xí)了對(duì)自然數(shù)進(jìn)行素因數(shù)分解的方法，下面的算法就是在此基礎(chǔ)上設(shè)計(jì)的.解答這個(gè)問題需要按以下思路進(jìn)行.首先，對(duì)兩個(gè)數(shù)分別進(jìn)行素因數(shù)分解：840=23×3×5×7，1764=22×32×72

其次，確定兩數(shù)的公共素因數(shù)：2，3，7.接著，確定公共素因數(shù)的指數(shù)：對(duì)于公共素因數(shù)2，22是1764的因數(shù)，23是840的因數(shù)，因此22是這兩個(gè)數(shù)的公因數(shù)，這樣就確定了公共素因數(shù)2的指數(shù)為2.

同樣，可以確定出公因數(shù)3和7的指數(shù)均為1.

這樣，就確定了840與1746的最大公因數(shù)為：

22×31×71=84.例3

設(shè)計(jì)一個(gè)算法，求840與1764的最大公因數(shù).例題講解1.算法案的基本思想解算法步驟如下：1.先將840進(jìn)行素因數(shù)分解：840=23×3×5×7；2.然后將1764進(jìn)行素因數(shù)分解：1746=22×32×72；3.確定它們的公共素因數(shù)：2，3，7；4.確定公共素因數(shù)的指數(shù)：公共素因數(shù)2，3，7的指數(shù)分別為2，1，1；5.最大公因數(shù)為：22×31×71=84.例題講解1.算法案的基本思想分析理解

以上步驟就是求兩個(gè)正整數(shù)的最大公因數(shù)的一個(gè)算法.這個(gè)算法的思想具有一般性，它可以幫助設(shè)計(jì)求三個(gè)或者三個(gè)以上正整數(shù)的最大公因數(shù)的算法.在這個(gè)算法的設(shè)計(jì)中，我們首先分別對(duì)840和1764進(jìn)行素因數(shù)分解，那么，如何將840或1764的所有素因數(shù)都找出來呢？例2給出了具體的算法.我們通常會(huì)把“對(duì)自然數(shù)進(jìn)行素因數(shù)分解”的算法，做成一個(gè)“程序包”，又稱為一個(gè)“平臺(tái)”，在需要“對(duì)自然數(shù)進(jìn)行素因數(shù)分解”時(shí)，把做好的“程序包”拿來使用即可.同樣的，我們也可以把“求兩個(gè)自然數(shù)的最大公因數(shù)”1.算法案的基本思想做成一個(gè)“程序包”或“平臺(tái)”，在解決其他問題時(shí)，如果需要“求兩個(gè)自然數(shù)的最大公因數(shù)”，我們就可以把做好的程序包直接拿來使用，通常把這種思想稱為“平臺(tái)思想”，“平臺(tái)”的思想在算法設(shè)計(jì)中是一個(gè)最基本的思想，也是數(shù)學(xué)中思考問題的一個(gè)重要思想.

通過以上的例子可以看出，算法是解決某類問題的一系列步驟或程序，只要按照這些步驟執(zhí)行，都能使問題得到解決.一般來說，“用算法解決問題”都是可以利用計(jì)算機(jī)幫助完成的.分析理解1.算法案的基本思想課堂練習(xí)1.模仿例3，設(shè)計(jì)一個(gè)算法，求324，440，556的最大公因數(shù).1.解（1）分別將324，440，556進(jìn)行素因數(shù)分解：

324=22×34，440=23×5×11，556=22×139.

（2）確定三個(gè)數(shù)的公共素因數(shù)：2

（3）確定公共素因數(shù)的指數(shù)：2

（4）最大公因數(shù)為：22=4.1.算法案的基本思想2.解（1）首先將1356和2400進(jìn)行素因數(shù)分解：

1356=22×3×113，2400=25×3×52.（2）確定最小公倍數(shù)的素因數(shù)：2，3，5，113.

（3）確定素因數(shù)的指數(shù)分別為：5，1，2，1.

（4）最小公倍數(shù)為：25×3×52×113=271200.課堂練習(xí)2.設(shè)計(jì)算法，求1356和2400的最小公倍數(shù).1.算法案的基本思想2.1.1算法案例分析(2)1.算法案的基本思想例題解析

例1“韓信點(diǎn)兵”問題韓信是漢高祖劉邦手上的大將，他英勇善戰(zhàn)，智謀超群，為建立漢朝立下了汗馬功勞.據(jù)說他在點(diǎn)兵的時(shí)候，為了保住軍事機(jī)密，不讓敵人知道自己部隊(duì)的實(shí)力，采用下述點(diǎn)兵方式：先令士兵從1~3報(bào)數(shù)，結(jié)果最后一個(gè)士兵報(bào)2；再令士兵從1~5報(bào)數(shù)，結(jié)果最后一個(gè)士兵報(bào)3；又令士兵從1~7報(bào)數(shù)，結(jié)果最后一個(gè)士兵報(bào)4.1.算法案的基本思想分析理解

士兵從1~3報(bào)數(shù)，最后一個(gè)士兵報(bào)2.這句話說明士兵的總?cè)藬?shù)除以3余2.算法的第一步是將所有除以3余2的正整數(shù)找出來，按照從小到大的順序排成一列數(shù).士兵從1~5報(bào)數(shù)，最后一個(gè)士兵報(bào)3.這句話說明士兵的總?cè)藬?shù)除以5余3.算法的第二步是從上列數(shù)中找出除以5余3的一列數(shù).

最后，在滿足前兩個(gè)條件的上列數(shù)中再找出除以7余4的一列數(shù)，這列數(shù)中最小的數(shù)，即為我們所求的數(shù)可.這樣，韓信很快計(jì)算出了自己部隊(duì)士兵的總?cè)藬?shù).請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，求出士兵至少有多少人.1.算法案的基本思想解算法步驟如下：1.首先確定最小的滿足除以3余2的正整數(shù)：2；2.依次加3就得到所有除以3余2的正整數(shù)：

2，5，8，11，14，17，20，23，26，29，32，35，38，41，44，47，50，53，56，…3.在上列數(shù)中確定最小的滿足除以5余3的正整數(shù)：8；分析理解1.算法案的基本思想4.然后依次加上15，得到8，23，38，53，…不難看出，這些數(shù)既滿足除以3余2，又滿足除以5余3；5.在第4步得到得以列數(shù)中找出滿足除以7余4的最小數(shù)53，這就是我們要求的數(shù).

在完成上述步驟后就找到了所求的數(shù)53，這5個(gè)步驟稱為解決“韓信點(diǎn)兵”問題的一個(gè)算法.1.算法案的基本思想想一想

大家可以想一想，能否在這個(gè)算法的基礎(chǔ)會(huì)上作一些改進(jìn)，以更快地獲得結(jié)果？實(shí)際上，我們顛倒一下3，5，7的順序，就可以得到另一個(gè)算法；

1.首先確定最小的除以7余4的正整數(shù)：4；

2.依次加7就得到所有除以7余4的正整數(shù)；

4，11，18，25，32，39，46，53，60，…1.算法案的基本思想3.在第2步得到的一列數(shù)中確定最小的除以5余3的正整數(shù)：18；4.然后依次加上35，得到

18，53，88，…5.在第4步得到的一列數(shù)中找出最小的滿足除以3余2的正整數(shù)：53.1.算法案的基本思想例題解析例2

一位商人有9枚銀元，其中有一枚略輕的是假銀元.你能用天平（不用砝碼）將假銀元找出來嗎？

最容易想到的解決這個(gè)問題的一種方法是：把9枚銀元按順序排成一列，先稱前2枚，若不平衡，則可找出假銀元；若平衡，則2枚銀元都是真的，再依次與剩下的銀元比較，就能找出假銀元.1.算法案的基本思想分析理解

解按照下列步驟，就能將假銀元找出來：

1.任取2枚銀元分別放在天平的兩邊.如果天平左右不平衡，則輕的一邊就是假銀元；如果天平平衡，則進(jìn)行第二步.2.取下右邊的銀元，放在一邊，然后把剩余的7枚銀元依次放在右邊進(jìn)行稱量，直到天平不平衡，偏輕的那一枚就是假銀元.

這種算法最少要稱1次，最多要稱7次，是不是還有更好的辦法，使得稱量次數(shù)少一些？我們可以采用下面的方法：1.算法案的基本思想1.把銀元分成3組，每組3枚.2.先將兩組分別放在天平的兩邊.如果天平不平衡，那么假銀元就在輕的那一組；如果天平左右平衡，則假銀元就在未稱的第3組里.3.取出含假銀元的那一組，從中任取兩枚銀元放在天平的兩邊.如果左右不平衡，則輕的那一邊就是假銀元；如果天平兩邊平衡，則未稱的那一枚就是假銀元.分析理解1.算法案的基本思想分析理解

進(jìn)分析發(fā)現(xiàn)，這種算法只需稱量?jī)纱?，這種做法要明顯好于前一種做法.當(dāng)然，這兩種方法都具有一般性，同樣適用于n枚銀元的情形.這是信息論中的一個(gè)模型，可以幫助我們找出某些特殊信息.

從以上兩個(gè)問題中可以看出，同一個(gè)問題可能存在著多種算法，其中一些可能要比另一些好.在實(shí)際問題和算法理論中，找出好的算法是一項(xiàng)重要的工作.1.算法案的基本思想方程近似解算法其算法步驟如下：1.確定有解區(qū)間[a,b]（f(a)×f(b)<0）.2.取[a,b]的中點(diǎn)x=（a+b）/2.3.計(jì)算函數(shù)f(x)在中點(diǎn)處的函數(shù)值f(（a+b）/2).4.判斷函數(shù)值f(（a+b）/2)是否為0；（1）如果為0，x=（a+b）/2就是方程的解，問題就得到可解決；（2）如果函數(shù)值f(（a+b）/2)不為0，則分析下列兩種情形：①若f(a)×f(（a+b）/2)<0,則確定新的有解區(qū)間為（a,（a+b）/2);xy0baxy=f（x）1.算法案的基本思想②若f(a)×f(（a+b）/2)>0,則確定新的有解區(qū)間為（（a+b）/2,b).5.判斷新的有解區(qū)間的長(zhǎng)度是否小于精確度：（1）如果新的有解區(qū)間長(zhǎng)度大于或等于精確度，則在新的有解區(qū)間的基礎(chǔ)上重復(fù)上述步驟；（2）如果新的有解區(qū)間長(zhǎng)度小于精確度，則取新的有解區(qū)間的中點(diǎn)為方程的近似解.1.算法案的基本思想例題解析例3

求方程f(x)=x3+x2-1=0在[0,1]上的近似解，精確度為0.01.解根據(jù)上述分析，可以通過下列步驟求得