《高一數(shù)學(xué) 算法案例課件 新人教A版必修3》由會(huì)員分享，可在線閱讀，更多相關(guān)《高一數(shù)學(xué) 算法案例課件 新人教A版必修3（35頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、四四.算法案例算法案例多項(xiàng)式求值的秦九韶方法多項(xiàng)式求值的秦九韶方法 nnnxaxaxaaxP22101n xPnktkukkxt kk2210kxaxaxaau kk1kk1kktauuxttn, 2 , 1k (3.4.2)作為遞推公式(3.4.2)的初值為: 000au1t(3.4.3)(1)逐項(xiàng)法多項(xiàng)式求值。 輸入：存放 的系數(shù)數(shù)組A(0：n）； xPn自變量x值。其中1n 輸出： 值P xPn xt;x1A0Ap tiAPP;xtt 012n1nnnaxaxaxaxaxP k1kknnaxuuau0 , 1 , 1 nk 0nuxP xPn xPn1n nAP iAxPP 例. 中國(guó)剩

2、余定理（孫子定理）若k2，且m1，m2，mk是兩兩互素的k個(gè)正整數(shù)，令M= m1m2mk=m1M1=m2M2=mkMk。 則同余式組：x1=b1(modm1)，x2=b2(modm2)，xk=bk(modmk) 其正整數(shù)解是：Xb1M1M1+b2M2M2+bkMkMk(modM) 其中Mi是滿足同余式： MiMi1(mod mi) （i = 1，2k） 用孫子定理解同余式組： xi=bi(modmi) （ i = 1，2k ）的算法步驟如下：kiiiiiiiiiiikiiMbaxMM, ., k)(imMMMkimMMmM1i0)(mod a . 31 )(mod1 . 2)., , 1( .

3、 1數(shù)解是：，則同余方程組的正整令的同余方程：分別解關(guān)于分別計(jì)算設(shè)2.對(duì)半法查找對(duì)半法查找(二分法二分法)算法算法對(duì)這種算法的實(shí)質(zhì)是在一個(gè)有限且有序的對(duì)象中，通過(guò)每次縮減一半查找范圍而達(dá)到迅速確定目的一個(gè)有效算法。因此有著很廣泛的應(yīng)用。例如，在數(shù)學(xué)中有很多方程是寫(xiě)不出根的解析表達(dá)式的，但是根的存在范圍比較容易確定，那么如何才能找到它的根的一個(gè)足夠準(zhǔn)確的近似值呢？這時(shí)對(duì)半查找算法就可以大顯身手了。由初等函數(shù)f(x)=0構(gòu)成的方程，如果有f(a)f(b)0，則可以肯定方程f(x)=0在（a , b）至少有一個(gè)實(shí)數(shù)根。 選擇（a , b）的中點(diǎn)c，若f(c)=0，則根就是x=c。若f(c)0，則用c

4、值取代相應(yīng)的a或b（取代原則是：保證有f(a)f(b) a b c 10，abc=30723，且，且a b+c，試確定，試確定a、b、c的值。的值。分析問(wèn)題分析問(wèn)題解決這個(gè)問(wèn)題應(yīng)當(dāng)從解決這個(gè)問(wèn)題應(yīng)當(dāng)從abc=30723入手。把入手。把30723三個(gè)整三個(gè)整數(shù)相乘的積，只能有有限種情況，我們可以把這些情況一一數(shù)相乘的積，只能有有限種情況，我們可以把這些情況一一羅列出來(lái)，然后分析哪一種情況是符合條件的。從而找到答羅列出來(lái)，然后分析哪一種情況是符合條件的。從而找到答案。案。(在列舉所有情況時(shí)，注意三個(gè)因子都大于在列舉所有情況時(shí)，注意三個(gè)因子都大于10，這可以減，這可以減少列舉的工作量少列舉的工作量)

5、。把把30723分解為分解為3個(gè)大于個(gè)大于10的因子的乘積只有的因子的乘積只有5種情況種情況1119147(三個(gè)因子的和是三個(gè)因子的和是177)1121133(三個(gè)因子的和是三個(gè)因子的和是165)194957 (三個(gè)因子的和是三個(gè)因子的和是101)114957 (三個(gè)因子的和是三個(gè)因子的和是117)192177 (三個(gè)因子的和是三個(gè)因子的和是117)在這在這5種情況中考察，符合種情況中考察，符合ab+c而且最大的數(shù)小于而且最大的數(shù)小于100的，的，只有最后一種情況，即只有最后一種情況，即a=77，b=21，c=19。計(jì)算算法計(jì)算算法設(shè)計(jì)窮舉算法的關(guān)鍵是如何列舉所有可能的情況，絕對(duì)不能設(shè)計(jì)窮舉算

6、法的關(guān)鍵是如何列舉所有可能的情況，絕對(duì)不能遺漏，最好不要重復(fù)。在列舉時(shí)注意變量的范圍，可以減少遺漏，最好不要重復(fù)。在列舉時(shí)注意變量的范圍，可以減少工作量。工作量。我們可以從最小的變量我們可以從最小的變量c入手，讓它從入手，讓它從10開(kāi)始變化。但變化開(kāi)始變化。但變化的范圍到哪里為止呢？粗略估算一下，三個(gè)數(shù)相乘是的范圍到哪里為止呢？粗略估算一下，三個(gè)數(shù)相乘是30723，最小的最小的c不超過(guò)它的立方根。我們可以用平方根做近似替代，不超過(guò)它的立方根。我們可以用平方根做近似替代，不必作太多推算。不必作太多推算。當(dāng)當(dāng)c值產(chǎn)生之后，就可以處理變量值產(chǎn)生之后，就可以處理變量b。因?yàn)樗恍∮?。因?yàn)樗恍∮赾，讓

7、它，讓它從從c開(kāi)始，也讓它變化到開(kāi)始，也讓它變化到30723的平方根。的平方根。有了有了c和和b的值之后，就要判斷他們是否都是的值之后，就要判斷他們是否都是30723的因子。的因子。如果是，計(jì)算出第三個(gè)因子如果是，計(jì)算出第三個(gè)因子a，然后進(jìn)行判斷：，然后進(jìn)行判斷：a是否大于是否大于b+c并且并且a100。滿足條件就是解答了。滿足條件就是解答了。例題例題 (錢(qián)幣問(wèn)題錢(qián)幣問(wèn)題)在日程生活中常常需要用一些較小面額的錢(qián)幣去組合出一定的幣值?，F(xiàn)有面值為1元、2元和5元的鈔票(假設(shè)每種鈔票的數(shù)量都足夠多)，從這些鈔票中取出30張使其總面值為100元，問(wèn)有多少種取法？每種取法的各種面值的鈔票各為多少?gòu)?？分?/p>

8、問(wèn)題分析問(wèn)題顯然列出一條算式來(lái)解決錢(qián)幣問(wèn)題是有困難的。既然解析法很難用上，我們嘗試通過(guò)列舉所有可能的情況(窮舉)，從中判斷出合符條件的解答。 當(dāng)鈔票數(shù)量比較多，總幣值比較大時(shí)，人工列舉所有鈔票組合(窮舉)就很麻煩，這時(shí)需要使用計(jì)算機(jī)來(lái)幫我們窮舉。但使用計(jì)算機(jī)來(lái)窮舉，必須清楚地說(shuō)出窮舉的每一個(gè)步驟，并通過(guò)程序設(shè)計(jì)語(yǔ)言轉(zhuǎn)化為計(jì)算機(jī)能后執(zhí)行的過(guò)程，才能解決問(wèn)題。 錢(qián)幣問(wèn)題有3種面額的鈔票，鈔票的總張數(shù)是30張，又應(yīng)當(dāng)如何窮舉呢？經(jīng)分析可以知道：當(dāng)有兩種面額的鈔票數(shù)目確定了之后，可以從總張數(shù)為30確定第三種鈔票的張數(shù)，然后由總面額是否100元而判斷這個(gè)組合是否合乎要求。此外，先確定面額大的鈔票可以使窮

9、舉的次數(shù)少些。設(shè)計(jì)算法設(shè)計(jì)算法 用ONE、TWO、FIVE分別記錄1元、2元、5元鈔票的張數(shù)。變量ANSWER記錄符合條件的解的數(shù)目。窮舉的過(guò)程如下：讓ANSWER=0，F(xiàn)IVE=0；TWO=0讓ONE=30 TWO FIVE；檢查5FIVE2TWOONE 是否等于100，若是， 則得到一組解，這時(shí)讓ANSWER增加1。并且輸出解答如果TWO30，那么讓TWO增加1，轉(zhuǎn)步驟；如果FIVE20，那么讓FIVE增加1，轉(zhuǎn)步驟結(jié)束可把這些步驟用框圖表示如圖4-7：Click to display漢諾漢諾(Hanoi)塔問(wèn)題是一個(gè)著名的應(yīng)用遞歸算法解決的問(wèn)題。塔問(wèn)題是一個(gè)著名的應(yīng)用遞歸算法解決的問(wèn)題。

10、 問(wèn)題問(wèn)題4-17： 傳說(shuō)在古代印度的貝拿勒斯神廟里安放了一塊黃銅板，傳說(shuō)在古代印度的貝拿勒斯神廟里安放了一塊黃銅板，板上插了三根寶石柱，在其中一根寶石柱自上而下由小到大板上插了三根寶石柱，在其中一根寶石柱自上而下由小到大地疊放著地疊放著64個(gè)大小不等的金盤(pán)。一名僧人把這些金盤(pán)從一根個(gè)大小不等的金盤(pán)。一名僧人把這些金盤(pán)從一根寶石柱移到另外一根上。僧人在移動(dòng)金盤(pán)時(shí)遵守下面寶石柱移到另外一根上。僧人在移動(dòng)金盤(pán)時(shí)遵守下面3條規(guī)條規(guī)則：則：一次只能移動(dòng)一個(gè)金盤(pán)。一次只能移動(dòng)一個(gè)金盤(pán)。每個(gè)金盤(pán)只能由一根寶石柱移到另外一根寶石柱。每個(gè)金盤(pán)只能由一根寶石柱移到另外一根寶石柱。任何時(shí)候都不能把大的金盤(pán)放在小的

11、金盤(pán)上。任何時(shí)候都不能把大的金盤(pán)放在小的金盤(pán)上。神化說(shuō)，如果僧人把64個(gè)金盤(pán)完全地從一根寶石柱移到了另外一根上，世界的末日就要到了。當(dāng)然，神化只能當(dāng)故事聽(tīng)，世界不可以因?yàn)閭€(gè)別人的活動(dòng)而導(dǎo)致末日。不過(guò)，如果能夠計(jì)算出僧人按規(guī)則搬完64個(gè)金盤(pán)，地球能否繼續(xù)存在也的確是個(gè)問(wèn)題！因?yàn)榧词股说膭?dòng)作十分敏捷，每秒都能移動(dòng)一個(gè)金盤(pán)，那也得要幾億年！分析問(wèn)題分析問(wèn)題 要模擬金盤(pán)的移動(dòng)過(guò)程是比較困難的，但如果用遞歸的思想來(lái)進(jìn)行(壓縮規(guī)模，把問(wèn)題解決在最簡(jiǎn)單的情況)，則問(wèn)題可以解決。 我們把3根寶石柱分別命名為A、B、C。最初有N個(gè)金盤(pán)放在A，需要把它們?nèi)堪匆?guī)則移動(dòng)到B。 當(dāng)N=1時(shí)，直接把金盤(pán)從A搬到B就可

12、以了，1次成功。 當(dāng)N2，那么需要利用C柱來(lái)過(guò)渡。按照遞歸的思想，我們假設(shè)已經(jīng)找到一種把N1個(gè)金盤(pán)從一根柱搬到另外一根柱的方法，然后看看如何通過(guò)它來(lái)實(shí)現(xiàn)搬動(dòng)N個(gè)金盤(pán)。我們只要把N1個(gè)金盤(pán)從A搬到C，然后把最大的金盤(pán)從A搬到B，最后把C上的N1個(gè)金盤(pán)搬到B就可以了。靠遞歸的思想，我們輕而易舉地完成了整個(gè)搬動(dòng)。設(shè)計(jì)算法設(shè)計(jì)算法我們定義一個(gè)過(guò)程Hanoi(N，A，B，C)，表示有N個(gè)金盤(pán)需要從A柱搬到B柱(以C柱為過(guò)渡)。那么完成它只需3步：Hanoi(N1，A，C，B)它的意思是把A柱上的N1個(gè)金盤(pán)搬到C柱，AB它的意思是把一個(gè)(最大的)金盤(pán)從A柱搬到B柱，Hanoi(N，C，B，A)它的意思是把C柱上的N1個(gè)金盤(pán)搬到B柱。