陜西省藍(lán)田縣焦岱中學(xué)高中數(shù)學(xué)必修三21算法的基本思想（1）課件

§1算法的基本思想（1）第二章§1算法的基本思想第二章算法初步引入作為家里的一員，在平時(shí)分擔(dān)一些力所能及的家務(wù)是我們應(yīng)盡的義務(wù)，你每天都幫家里做家務(wù)嗎？你會(huì)燒開(kāi)水嗎？請(qǐng)寫(xiě)出你在家中燒開(kāi)水的過(guò)程.1.往壺內(nèi)注水；2.點(diǎn)火加熱；3.觀察：如果水開(kāi)，則停止燒火，否則繼續(xù)燒火；4.如果水未開(kāi)，重復(fù)過(guò)程“3”，直至水開(kāi).§1算法的基本思想第二章算法初步引入狼羊菜過(guò)河一個(gè)獵人帶著一只羊，一只狼和一棵白菜回家，路上遇到一條河。河邊只有一條船，但船太小，一次最多只可載獵人和另一樣?xùn)|西過(guò)河。但獵人不在時(shí)，狼要吃羊，羊要吃白菜。請(qǐng)問(wèn)怎樣才能把狼，羊，白菜都安全運(yùn)過(guò)河？§1算法的基本思想第二章算法初步事實(shí)上，我們完成任何事，都要有步驟，合理安排步驟，這樣會(huì)達(dá)到事半功倍的效果.從我們數(shù)學(xué)的意義來(lái)講，在解決某些問(wèn)題時(shí)，需要設(shè)計(jì)出一系列可操作或可計(jì)算的步驟，通過(guò)實(shí)施這些步驟來(lái)解決問(wèn)題，我們通常把這些步驟稱(chēng)為解決問(wèn)題的一種算法.這種描述不是算法的定義，但反映了算法的基本思想.一、算法的思想§1算法的基本思想第二章算法初步隨著計(jì)算科學(xué)和信息技術(shù)的飛速發(fā)展，算法的思想已經(jīng)滲透到社會(huì)的方方面面.在以前的學(xué)習(xí)中，雖然沒(méi)有出現(xiàn)算法這個(gè)名詞，但實(shí)際上在數(shù)學(xué)教學(xué)中已經(jīng)滲透了大量的算法思想，如四則運(yùn)算的過(guò)程、求解方程的步驟等.完成這些工作都需要一系列程序化的步驟，這就是算法的思想.一、算法的思想§1算法的基本思想第二章算法初步一、算法的思想

算法可以理解為由基本運(yùn)算及規(guī)定的運(yùn)算順序構(gòu)成的完整的解題步驟，或看成按要求設(shè)計(jì)好的、有限的、確切的計(jì)算序列，并且這樣的步驟或序列能解決一類(lèi)問(wèn)題.現(xiàn)代意義上的“算法”通常是指可以用計(jì)算機(jī)來(lái)解決的某一類(lèi)問(wèn)題的程序或步驟.§1算法的基本思想第二章算法初步一、算法的思想說(shuō)明：1.算法實(shí)際上就是解決某一類(lèi)問(wèn)題的步驟和方法，在解決問(wèn)題時(shí)形成的規(guī)律性的東西，按照算法描述的規(guī)則與步驟，一步一步地去做，最終便能解決問(wèn)題.2.算法的基本思想就是我們分析問(wèn)題時(shí)的想法.由于想法不同、思考的角度不同，著手點(diǎn)不一樣，同一問(wèn)題存在不同的算法，算法有優(yōu)劣之分.3.從熟悉的問(wèn)題出發(fā)，體會(huì)算法的程序化思想，學(xué)會(huì)用自然語(yǔ)言來(lái)描述算法.§1算法的基本思想第二章算法初步二、算法的特征1、通用性2、程序性3、確定性4、有窮性5、精確性能解決一類(lèi)問(wèn)題，重復(fù)使用算法的過(guò)程要一步一步執(zhí)行算法的每一步執(zhí)行的操作必須確切，不能含混不清必須在有限步內(nèi)完成任務(wù)，不能無(wú)限制地執(zhí)行要注意細(xì)節(jié)和精細(xì)化§1算法的基本思想第二章算法初步三、算法案例案例1（看商品猜價(jià)格）在電視臺(tái)的某個(gè)娛樂(lè)節(jié)目中，要求參與者快速猜出物品價(jià)格.主持人出示某件物品，參與者每次估算出一個(gè)價(jià)格，主持人只能回答高了、低了或者正確.在某次節(jié)目中，主持人出示了一臺(tái)價(jià)值在1000元以?xún)?nèi)的隨身聽(tīng)，并開(kāi)始了競(jìng)猜.下面是主持人和參與者之間的一段對(duì)話：參與者：800元！主持人：高了！參與者：400元！主持人：低了！參與者：600元！主持人：低了!……如果你是參與者，你接下來(lái)會(huì)怎么猜？§1算法的基本思想第二章算法初步三、算法案例實(shí)際上，可以把過(guò)程概括如下：按照上述方法，繼續(xù)判斷，直到游戲結(jié)束.像這樣的一系列步驟通常稱(chēng)為解決這個(gè)問(wèn)題的一個(gè)算法.§1算法的基本思想第二章算法初步三、算法案例案例2（素因數(shù)分解）

在給定素?cái)?shù)表的條件下，設(shè)計(jì)算法，將936分解成素因數(shù)的乘積.(4000以?xún)?nèi)的素?cái)?shù)表見(jiàn)課本附錄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×117.§1算法的基本思想第二章算法初步三、算法案例案例2（素因數(shù)分解）

在給定素?cái)?shù)表的條件下，設(shè)計(jì)算法，將936分解成素因數(shù)的乘積.(4000以?xún)?nèi)的素?cái)?shù)表見(jiàn)課本附錄1)7.判斷117是否為素?cái)?shù)：否.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×13.11.判斷13是否為素?cái)?shù)：13是素?cái)?shù)，所以分解結(jié)束.分解結(jié)果是：936=2×2×2×3×3×13.§1算法的基本思想第二章算法初步三、算法案例案例2（素因數(shù)分解）

在給定素?cái)?shù)表的條件下，設(shè)計(jì)算法，將936分解成素因數(shù)的乘積.(4000以?xún)?nèi)的素?cái)?shù)表見(jiàn)課本附錄1)分析理解:1.查表判斷936是否是素?cái)?shù):（1）如果963是素?cái)?shù),則分解結(jié)束;（2）如果963不是素?cái)?shù),則進(jìn)行第2步.2.確定936的最小素因素:2.3.查表判斷468是否是素?cái)?shù):（1）如果468是素?cái)?shù),則分解結(jié)束;（2）如果468不是素?cái)?shù),則重復(fù)上述步驟,確定468的最小素因素.重復(fù)進(jìn)行上述步驟,直到找出936的所有素因素.§1算法的基本思想第二章算法初步三、算法案例案例2（素因數(shù)分解）

在給定素?cái)?shù)表的條件下，設(shè)計(jì)算法，將936分解成素因數(shù)的乘積.(4000以?xún)?nèi)的素?cái)?shù)表見(jiàn)課本附錄1)解算法步驟如下:1.判斷936是否是素?cái)?shù):否.2.確定936最小素因素:2.3.判斷468是否是素?cái)?shù):否.4.確定468最小素因素:2.5.判斷234是否是素?cái)?shù):否.6.確定234最小素因素:2.7.判斷117是否是素?cái)?shù):否.8.確定117最小素因素:3.9.判斷39是否是素?cái)?shù):否.10.確定39最小素因素:3.11.判斷13是否是素?cái)?shù):是,分解結(jié)束.分解結(jié)果是:短除法９３６２４６８２２３４２１１７３９３１３３§1算法的基本思想第二章算法初步三、算法案例案例3（最大公因數(shù)）

設(shè)計(jì)一個(gè)算法，求840與1764的最大公因數(shù).1.先將840進(jìn)行素因數(shù)分解：；2.然后將1764進(jìn)行素因數(shù)分解：

；3.確定它們的公共素因數(shù):2,3,7；4.確定公共素因數(shù)的指數(shù)：公共素因數(shù)2,3,7的指數(shù)分別為2,1,1;5.最大公因數(shù)為:.解：算法步驟如下：練習(xí)1.設(shè)計(jì)一個(gè)算法,求324,440,556的最大公因數(shù).練習(xí)2.設(shè)計(jì)一個(gè)算法,