114算法案例算法案例學(xué)習(xí)目標(biāo)學(xué)習(xí)目標(biāo)1通過案例，進(jìn)一步體會(huì)算法的思想；通過案例，進(jìn)一步體會(huì)算法的思想；2理解并能利用案例中的算法解決具體問題理解并能利用案例中的算法解決具體問題課堂互動(dòng)講練課堂互動(dòng)講練知能優(yōu)化訓(xùn)練知能優(yōu)化訓(xùn)練11.4算算法法案案例例課前自主學(xué)案課前自主學(xué)案課前自主學(xué)案課前自主學(xué)案溫故夯基溫故夯基1編寫算法常用的語(yǔ)句有輸入語(yǔ)句、編寫算法常用的語(yǔ)句有輸入語(yǔ)句、_、賦值語(yǔ)句、賦值語(yǔ)句、_、循環(huán)語(yǔ)句，對(duì)應(yīng)著、循環(huán)語(yǔ)句，對(duì)應(yīng)著_結(jié)結(jié)構(gòu)、條件結(jié)構(gòu)、構(gòu)、條件結(jié)構(gòu)、_結(jié)構(gòu)結(jié)構(gòu)2在兩個(gè)正數(shù)的所有公約數(shù)中最大的一個(gè)公約數(shù)在兩個(gè)正數(shù)的所有公約數(shù)中最大的一個(gè)公約數(shù)為它們的為它們的_輸出語(yǔ)句輸出語(yǔ)句條件語(yǔ)句條件語(yǔ)句順序順序循環(huán)循環(huán)最大公約數(shù)最大公約數(shù)知新益能知新益能1輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法偽代碼如下：偽代碼如下：a MOD b2秦九韶算法秦九韶算法偽代碼如下：偽代碼如下：?jiǎn)栴}探究問題探究1用秦九韶算法求用秦九韶算法求x2時(shí)，時(shí)，f(x)x33x2x1的的值第一個(gè)一次多項(xiàng)式的值為多少？值第一個(gè)一次多項(xiàng)式的值為多少？提示：提示：由秦九韶算法知由秦九韶算法知f(x)(x3)x1x1.由內(nèi)到外第一個(gè)一次多項(xiàng)式的值為由內(nèi)到外第一個(gè)一次多項(xiàng)式的值為235.2“秦九韶算法秦九韶算法”的實(shí)質(zhì)是什么？的實(shí)質(zhì)是什么？提示：提示：其實(shí)質(zhì)是通過一次式的反復(fù)計(jì)算，逐步得出其實(shí)質(zhì)是通過一次式的反復(fù)計(jì)算，逐步得出高次多項(xiàng)式的值，對(duì)于一個(gè)高次多項(xiàng)式的值，對(duì)于一個(gè)n次多項(xiàng)式，最多只需次多項(xiàng)式，最多只需做做n次乘法和次乘法和n次加法即可次加法即可課堂互動(dòng)講練課堂互動(dòng)講練輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法考點(diǎn)突破考點(diǎn)突破輾轉(zhuǎn)相除法的操作過程是先用兩個(gè)數(shù)中較大的數(shù)除輾轉(zhuǎn)相除法的操作過程是先用兩個(gè)數(shù)中較大的數(shù)除以較小的數(shù)，得商和余數(shù)；再用除數(shù)除以余數(shù)，重以較小的數(shù)，得商和余數(shù)；再用除數(shù)除以余數(shù)，重復(fù)操作，直到出現(xiàn)余數(shù)為零，易出錯(cuò)的地方是用商復(fù)操作，直到出現(xiàn)余數(shù)為零，易出錯(cuò)的地方是用商除以余數(shù)，要特別注意除以余數(shù)，要特別注意 利用輾轉(zhuǎn)相除法求利用輾轉(zhuǎn)相除法求294和和84的最大公約數(shù)的最大公約數(shù)【思路點(diǎn)撥思路點(diǎn)撥】利用輾轉(zhuǎn)相除法，依據(jù)利用輾轉(zhuǎn)相除法，依據(jù)mnqr，反復(fù)執(zhí)行，直到反復(fù)執(zhí)行，直到r0為止為止【解解】29484342,84422，即，即294與與84的最大公約數(shù)為的最大公約數(shù)為42.【名師點(diǎn)評(píng)】【名師點(diǎn)評(píng)】利用輾轉(zhuǎn)相除法求給定的兩個(gè)數(shù)的利用輾轉(zhuǎn)相除法求給定的兩個(gè)數(shù)的最大公約數(shù)，即利用帶余除法，用數(shù)對(duì)中較大的數(shù)最大公約數(shù)，即利用帶余除法，用數(shù)對(duì)中較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的數(shù)對(duì)，再利用帶余除法，直到大數(shù)被小數(shù)構(gòu)成新的數(shù)對(duì)，再利用帶余除法，直到大數(shù)被小數(shù)除盡，則這時(shí)的較小數(shù)就是原來兩個(gè)數(shù)的最大公數(shù)除盡，則這時(shí)的較小數(shù)就是原來兩個(gè)數(shù)的最大公約數(shù)約數(shù)變式訓(xùn)練變式訓(xùn)練1利用輾轉(zhuǎn)相除法求利用輾轉(zhuǎn)相除法求46,115和和276的最大的最大公約數(shù)的最大公約數(shù)公約數(shù)的最大公約數(shù)解：解：求三個(gè)數(shù)的最大公約數(shù)，可以先求兩個(gè)數(shù)的最求三個(gè)數(shù)的最大公約數(shù)，可以先求兩個(gè)數(shù)的最大公約數(shù)，然后求第三個(gè)數(shù)與前兩個(gè)數(shù)的最大公約大公約數(shù)，然后求第三個(gè)數(shù)與前兩個(gè)數(shù)的最大公約數(shù)數(shù)276211546,11524623,46232所以所以276與與115的最大公約數(shù)為的最大公約數(shù)為23.又又46與與23的最大公約數(shù)為的最大公約數(shù)為23，所以，所以46、115和和276的的最大公約數(shù)為最大公約數(shù)為23.用二分法求方程的近似解或函數(shù)的零點(diǎn)可以設(shè)計(jì)程用二分法求方程的近似解或函數(shù)的零點(diǎn)可以設(shè)計(jì)程序用計(jì)算機(jī)來完成序用計(jì)算機(jī)來完成二分法二分法 寫出用二分法求方程寫出用二分法求方程x220的一個(gè)正的近的一個(gè)正的近似解似解(誤差不超過誤差不超過0.005)的算法的算法【思路點(diǎn)撥思路點(diǎn)撥】令令f(x)x22，確定有解區(qū)間，確定有解區(qū)間1,2，用二分法確定符合限制條件的解即可，用二分法確定符合限制條件的解即可【名師點(diǎn)評(píng)】【名師點(diǎn)評(píng)】用二分法求方程的近似解的步驟用二分法求方程的近似解的步驟:(1)畫草圖探索解所在的區(qū)間；畫草圖探索解所在的區(qū)間；(2)用二分法求符合用二分法求符合限制條件的解；限制條件的解；(3)編制程序用計(jì)算機(jī)完成編制程序用計(jì)算機(jī)完成變式訓(xùn)練變式訓(xùn)練2寫出用二分法求方程寫出用二分法求方程x32x30在在區(qū)間區(qū)間1,2內(nèi)的一個(gè)近似解內(nèi)的一個(gè)近似解(誤差不超過誤差不超過0.001)的一個(gè)的一個(gè)算法算法秦九韶算法秦九韶算法利用秦九韶算法將利用秦九韶算法將f(x)改寫成如下形式改寫成如下形式f(x)(anxan1)xan2)xa1)xa0，其計(jì)算步，其計(jì)算步驟為：先計(jì)算驟為：先計(jì)算v1anxan1，再計(jì)算，再計(jì)算v2v1xan2，每次都是把上一次的結(jié)果乘以，每次都是把上一次的結(jié)果乘以x再與下一再與下一個(gè)系數(shù)相加，其計(jì)算量為乘法個(gè)系數(shù)相加，其計(jì)算量為乘法n次，加法次，加法n次次 用秦九韶算法計(jì)算多項(xiàng)式用秦九韶算法計(jì)算多項(xiàng)式f(x)x612x560 x4160 x3240 x2192x64當(dāng)當(dāng)x2時(shí)的值時(shí)的值【解】【解】將將f(x)改寫為改寫為f(x)(x12)x60)x160)x240)x192)x64.由內(nèi)向外依次計(jì)算一次多項(xiàng)式當(dāng)由內(nèi)向外依次計(jì)算一次多項(xiàng)式當(dāng)x2時(shí)的值時(shí)的值v01，v1121210，v21026040，v340216080，v480224080，v580219232，v6322640，f(2)0，即，即x2時(shí)，原多項(xiàng)式的值為時(shí)，原多項(xiàng)式的值為0.【名師點(diǎn)評(píng)名師點(diǎn)評(píng)】利用秦九韶算法計(jì)算多項(xiàng)式的值關(guān)利用秦九韶算法計(jì)算多項(xiàng)式的值關(guān)鍵是能正確地將所給多項(xiàng)式改寫，然后由內(nèi)向外逐鍵是能正確地將所給多項(xiàng)式改寫，然后由內(nèi)向外逐次計(jì)算，由于后項(xiàng)計(jì)算需用到前項(xiàng)的結(jié)果，故應(yīng)認(rèn)次計(jì)算，由于后項(xiàng)計(jì)算需用到前項(xiàng)的結(jié)果，故應(yīng)認(rèn)真、細(xì)心，確保中間結(jié)果的準(zhǔn)確性真、細(xì)心，確保中間結(jié)果的準(zhǔn)確性變式訓(xùn)練變式訓(xùn)練3用秦九韶算法求多項(xiàng)式用秦九韶算法求多項(xiàng)式f(x)5x54x43x28x6，當(dāng)，當(dāng)x3時(shí)的值時(shí)的值解：解：f(x)5x54x43x28x6(5x4)x0)x3)x8)x6，當(dāng)當(dāng)x3時(shí)，時(shí)，v05，v153411，v2113033，v33333102，v410238314，v531436936.f(3)936.方法感悟方法感悟1輾轉(zhuǎn)相除法是當(dāng)大數(shù)被小數(shù)除盡時(shí)，結(jié)束除法輾轉(zhuǎn)相除法是當(dāng)大數(shù)被小數(shù)除盡時(shí)，結(jié)束除法運(yùn)算，較小的數(shù)就是最大公約數(shù)運(yùn)算，較小的數(shù)就是最大公約數(shù)2用秦九韶算法可大大降低乘法的運(yùn)算次數(shù)，提用秦九韶算法可大大降低乘法的運(yùn)算次數(shù)，提高了運(yùn)算速度用此方法求值，關(guān)鍵是正確地將所高了運(yùn)算速度用此方法求值，關(guān)鍵是正確地將所給多項(xiàng)式改寫，然后由內(nèi)向外計(jì)算，由于后項(xiàng)計(jì)算給多項(xiàng)式改寫，然后由內(nèi)向外計(jì)算，由于后項(xiàng)計(jì)算需用到前項(xiàng)結(jié)果，故應(yīng)認(rèn)真、細(xì)心，確保結(jié)果的準(zhǔn)需用到前項(xiàng)結(jié)果，故應(yīng)認(rèn)真、細(xì)心，確保結(jié)果的準(zhǔn)確性確性知能優(yōu)化訓(xùn)練知能優(yōu)化訓(xùn)練本部分內(nèi)容講解結(jié)束本部分內(nèi)容講解結(jié)束點(diǎn)此進(jìn)入課件目錄點(diǎn)此進(jìn)入課件目錄按按ESC鍵退出全屏播放鍵退出全屏播放謝謝使用謝謝使用