2019_2020學(xué)年高中數(shù)學(xué)第1章算法初步1_3_1輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法學(xué)案新人教A版必修3.docx

第1課時(shí)輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法1理解輾轉(zhuǎn)相除法與更相減損術(shù)的含義，了解其執(zhí)行過(guò)程2理解秦九韶算法的計(jì)算過(guò)程，并了解它提高計(jì)算效率的實(shí)質(zhì)1輾轉(zhuǎn)相除法與更相減損術(shù)(1)輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法，又叫歐幾里得算法，是一種求兩個(gè)正整數(shù)的最大公約數(shù)的古老而有效的算法輾轉(zhuǎn)相除法的算法步驟第一步，給定兩個(gè)正整數(shù)m，n.第二步，計(jì)算m除以n所得的余數(shù)r.第三步，mn，nr.第四步，若r0，則m，n的最大公約數(shù)等于m；否則，返回第二步(2)更相減損術(shù)的算法步驟第一步，任意給定兩個(gè)正整數(shù)，判斷它們是否都是偶數(shù)若是，用2約簡(jiǎn)；若不是，執(zhí)行第二步第二步，以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)繼續(xù)這個(gè)操作，直到所得的數(shù)相等為止，則這個(gè)數(shù)(等數(shù))或這個(gè)數(shù)與約簡(jiǎn)的數(shù)的乘積就是所求的最大公約數(shù)(3)輾轉(zhuǎn)相除法和更相減損術(shù)的區(qū)別與聯(lián)系名稱輾轉(zhuǎn)相除法更相減損術(shù)區(qū)別(1)以除法為主；(2)兩個(gè)整數(shù)的差值較大時(shí)，運(yùn)算次數(shù)較少；(3)相除，余數(shù)為0時(shí)得結(jié)果(1)以減法為主；(2)兩個(gè)整數(shù)的差值較大時(shí)，運(yùn)算次數(shù)較多；(3)相減，減數(shù)與差相等時(shí)得結(jié)果；(4)相減前要進(jìn)行是否都是偶數(shù)的判斷聯(lián)系(1)都是求兩個(gè)正整數(shù)最大公約數(shù)的方法；(2)二者的實(shí)質(zhì)都是遞推的過(guò)程；(3)二者都要用循環(huán)結(jié)構(gòu)來(lái)實(shí)現(xiàn)2.秦九韶算法(1)秦九韶算法簡(jiǎn)介秦九韶算法要解決的問(wèn)題是求多項(xiàng)式的值秦九韶算法的特點(diǎn)通過(guò)一次式的反復(fù)計(jì)算，逐步得到高次多項(xiàng)式的值，即將一個(gè)n次多項(xiàng)式的求值問(wèn)題歸結(jié)為重復(fù)計(jì)算n個(gè)一次多項(xiàng)式的值的問(wèn)題秦九韶算法的原理將f(x)anxnan1xn1a1xa0改寫為：f(x)(anxn1an1xn2a1)xa0(anxn2an1xn3a2)xa1)xa0先計(jì)算最內(nèi)層括號(hào)內(nèi)一次多項(xiàng)式的值，即v1anxan1，再由內(nèi)向外逐層計(jì)算一次多項(xiàng)式vk的值(2)秦九韶算法的操作方法算法步驟如下第一步，輸入多項(xiàng)式次數(shù)n、最高次項(xiàng)的系數(shù)an和x的值第二步，將v的值初始化為an，將i的值初始化為n1.第三步，輸入i次項(xiàng)的系數(shù)ai.第四步，vvxai，ii1.第五步，判斷i是否大于或等于0.若是，則返回第三步；否則，輸出多項(xiàng)式的值v.程序框圖如圖所示程序如下1實(shí)際應(yīng)用更相減損術(shù)時(shí)要做的第一步工作是什么？提示先判斷a，b是否為偶數(shù)，若是，都除以2再進(jìn)行2判斷正誤(正確的打“”，錯(cuò)誤的打“”)(1)輾轉(zhuǎn)相除法的基本步驟是用較大的數(shù)除以較小的數(shù)()(2)求最大公約數(shù)的方法除輾轉(zhuǎn)相除法之外，沒(méi)有其他方法()(3)編寫輾轉(zhuǎn)相除法的程序時(shí)，要用到循環(huán)語(yǔ)句()提示(1)(2)(3)題型一輾轉(zhuǎn)相除法和更相減損術(shù)的應(yīng)用【典例1】用輾轉(zhuǎn)相除法求612與468的最大公約數(shù)，并用更相減損術(shù)檢驗(yàn)所得結(jié)果思路導(dǎo)引將612作為大數(shù)，468作為小數(shù)，執(zhí)行輾轉(zhuǎn)相除法和更相減損術(shù)的步驟即可. 解用輾轉(zhuǎn)相除法：6124681144,468144336,144364，即612和468的最大公約數(shù)是36.用更相減損術(shù)檢驗(yàn)：612和468為偶數(shù)，兩次用2約簡(jiǎn)得153和117,15311736,1173681,813645,45369,36927,27918,1899，所以612和468的最大公約數(shù)為92236.求最大公約數(shù)的兩種方法步驟(1)利用輾轉(zhuǎn)相除法求給定的兩個(gè)數(shù)的最大公約數(shù)，即利用帶余除法，用數(shù)對(duì)中較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的數(shù)對(duì)，再利用帶余除法，直到大數(shù)被小數(shù)除盡，則這時(shí)的較小數(shù)就是原來(lái)兩個(gè)數(shù)的最大公約數(shù)(2)利用更相減損術(shù)求兩個(gè)正整數(shù)的最大公約數(shù)的一般步驟是：首先判斷兩個(gè)正整數(shù)是否都是偶數(shù)若是，用2約簡(jiǎn)，也可以不除以2，直接求最大公約數(shù)，這樣不影響最后結(jié)果針對(duì)訓(xùn)練1用輾轉(zhuǎn)相除法求80與36的最大公約數(shù)，并用更相減損術(shù)檢驗(yàn)?zāi)愕慕Y(jié)果解803628，36844,8420，即80與36的最大公約數(shù)是4.驗(yàn)證：80240,36218；40220,1829；20911,1192；927,725；523,321；211,1224；所以80與36的最大公約數(shù)為4.題型二求三個(gè)正整數(shù)的最大公約數(shù)【典例2】求325,130,270三個(gè)數(shù)的最大公約數(shù)思路導(dǎo)引求三個(gè)數(shù)的最大公約數(shù)，可先求兩個(gè)數(shù)的最大公約數(shù)，再求這個(gè)最大公約數(shù)與第三個(gè)數(shù)的最大公約數(shù)解解法一(輾轉(zhuǎn)相除法)：因?yàn)?25130265,130652，所以325和130的最大公約數(shù)為65. 因?yàn)?7065410,651065,1052, 所以65和270的最大公約數(shù)為5, 故325,130,270三個(gè)數(shù)的最大公約數(shù)為5. 解法二(更相減損術(shù))：325130195,19513065,1306565. 所以325和130的最大公約數(shù)是65. 27065205,20565140,1406575,756510,651055,551045,451035,351025,251015,15105,1055. 所以65和270的最大公約數(shù)為5，故325,130,270三個(gè)數(shù)的最大公約數(shù)為5.理解輾轉(zhuǎn)相除法的實(shí)質(zhì)，從計(jì)算結(jié)果上看，輾轉(zhuǎn)相除法是以相除余數(shù)為零而得到結(jié)果的. 針對(duì)訓(xùn)練2求三個(gè)數(shù)175,100,75的最大公約數(shù). 解先求175與100的最大公約數(shù)：175100175,10075125,75253, 175與100的最大公約數(shù)是25. 再求25與75的最大公約數(shù)：752550,502525, 75和25的最大公約數(shù)是25. 175,100,75的最大公約數(shù)是25. 題型三秦九韶算法【典例3】已知一個(gè)5次多項(xiàng)式為f(x)4x52x43.5x32.6x21.7x0.8，用秦九韶算法求這個(gè)多項(xiàng)式當(dāng)x5時(shí)的值. 思路導(dǎo)引可根據(jù)秦九韶算法的原理，將所給的多項(xiàng)式改寫，然后由內(nèi)到外逐次計(jì)算解將f(x)改寫為f(x)(4x2)x3.5)x2.6)x1.7)x0.8，由內(nèi)向外依次計(jì)算一次多項(xiàng)式，當(dāng)x5時(shí)的值：v04；v145222；v22253.5113.5；v3113.552.6564.9；v4564.951.72826.2；v52826.250.814130.2.所以當(dāng)x5時(shí)，多項(xiàng)式的值等于14130.2.(1)用秦九韶算法求多項(xiàng)式f(x)當(dāng)xx0的值的思路為：改寫計(jì)算結(jié)論f(x0)vn.(2)應(yīng)用秦九韶算法計(jì)算多項(xiàng)式的值應(yīng)注意的3個(gè)問(wèn)題要正確將多項(xiàng)式的形式進(jìn)行改寫計(jì)算應(yīng)由內(nèi)向外依次計(jì)算當(dāng)多項(xiàng)式函數(shù)中間出現(xiàn)空項(xiàng)時(shí)，要以系數(shù)為零的齊次項(xiàng)補(bǔ)充針對(duì)訓(xùn)練3用秦九韶算法計(jì)算多項(xiàng)式f(x)1235x8x26x45x53x6在x4時(shí)的值時(shí)，v3的值為()A144 B136 C57 D34解析根據(jù)秦九韶算法多項(xiàng)式可化為f(x)(3x5)x6)x0)x8)x35)x12.由內(nèi)向外計(jì)算v03；v13(4)57；v27(4)634；v334(4)0136.答案B課堂歸納小結(jié)1.求兩個(gè)正整數(shù)的最大公約數(shù)的問(wèn)題，可以用輾轉(zhuǎn)相除法，也可以用更相減損術(shù)用輾轉(zhuǎn)相除法，即根據(jù)anbr這個(gè)式子，反復(fù)相除，直到r0為止；用更相減損術(shù)，即根據(jù)r|ab|這個(gè)式子，反復(fù)相減，直到r0為止2.秦九韶算法的關(guān)鍵在于把n次多項(xiàng)式轉(zhuǎn)化為一次多項(xiàng)式，注意體會(huì)遞推的實(shí)現(xiàn)過(guò)程，實(shí)施運(yùn)算時(shí)要由內(nèi)向外，一步一步執(zhí)行1輾轉(zhuǎn)相除法可解決的問(wèn)題是()A求兩個(gè)正整數(shù)的最大公約數(shù)B多項(xiàng)式求值C求兩個(gè)正整數(shù)的最小公倍數(shù)D排序問(wèn)題解析輾轉(zhuǎn)相除法可以求兩個(gè)正整數(shù)的最大公約數(shù). 答案A2用輾轉(zhuǎn)相除法求72與120的最大公約數(shù)時(shí)，需要做除法次數(shù)為()A4 B3C5 D6解析12072148,7248124,48242.答案B3用更相減損術(shù)求36與134的最大公約數(shù)，第一步應(yīng)為_解析36與134都是偶數(shù)，第一步應(yīng)先除以2，得到18與67.答案先分別除以2，得到18與674用秦九韶算法求f(x)2x3x3當(dāng)x3時(shí)的值v2_.解析f(x)(2x0)x1)x3，v02，v12306，v263119.答案195用秦九韶算法求多項(xiàng)式f(x)8x75x63x42x1，當(dāng)x2時(shí)的值解根據(jù)秦九韶算法，把多項(xiàng)式改寫成如下形式：f(x)8x75x60x53x40x30x22x1(8x5)x0)x3)x0)x0)x2)x1.而x2，所以有v08，v182521，v2212042，v3422387，v48720174，v517420348，v634822698，v7698211397.所以當(dāng)x2時(shí)，多項(xiàng)式的值為1397.算法案例在實(shí)際生活中的應(yīng)用通過(guò)算法案例的學(xué)習(xí)，知道算法的核心是一般意義上的解決問(wèn)題的策略的具體化對(duì)于一個(gè)實(shí)際問(wèn)題，我們?cè)诜治觥⑺伎己罂蓪⒅D(zhuǎn)化為數(shù)學(xué)問(wèn)題，從而獲得解決它的基本思路. 【典例】現(xiàn)有長(zhǎng)度為2.4 m和5.6 m兩種規(guī)格的鋼筋若干，要焊接一批棱上無(wú)接點(diǎn)的正方體模型，問(wèn)怎樣設(shè)計(jì)才能保證正方體的體積最大且不浪費(fèi)材料？思路導(dǎo)引要焊接正方體，就是將兩種規(guī)格的鋼筋截成長(zhǎng)度相等的鋼筋條為了保證不浪費(fèi)材料，應(yīng)使得每種規(guī)格的鋼筋截取后沒(méi)有剩余，因此截取的長(zhǎng)度應(yīng)為2.4與5.6的公約數(shù)；為使得正方體的體積最大，因此截取的長(zhǎng)度應(yīng)為2.4與5.6的最大公約數(shù). 解用更相減損術(shù)來(lái)求2.4與5.6的最大公約數(shù)：562.43.2, 322.40.8, 240.81.6, 160.80.8, 因此2.4與5.6的最大公約數(shù)為0.8. 所以使得正方體的棱長(zhǎng)為0.8 m時(shí)，正方體的體積最大且不浪費(fèi)材料. 針對(duì)訓(xùn)練甲，乙，丙三種溶液的質(zhì)量分別為147 g，343 g，133 g，現(xiàn)要將它們分別全部裝入小瓶中，每個(gè)小瓶中裝入溶液的質(zhì)量相同，問(wèn)每瓶最多裝多少？解由題意，每個(gè)小瓶中裝入的溶液的質(zhì)量應(yīng)是三種溶液質(zhì)量的最大公約數(shù)先求147與343的最大公約數(shù)：343147196,19614749,1474998,984949，所以147與343的最大公約數(shù)是49.再求49與133的最大公約數(shù)：1334984,844935,493514,351421,21147,1477，所以147,343,133的最大公約數(shù)為7，即每瓶最多裝7 g.課后作業(yè)(八) (時(shí)間45分鐘)學(xué)業(yè)水平合格練(時(shí)間25分鐘)1秦九韶算法與直接計(jì)算相比較，下列說(shuō)法錯(cuò)誤的是()A秦九韶算法與直接計(jì)算相比，大大節(jié)省了做乘法的次數(shù)，使計(jì)算量減少，并且邏輯結(jié)構(gòu)簡(jiǎn)單B秦九韶算法減少了做乘法的次數(shù)，在計(jì)算機(jī)上也就加快了計(jì)算的速度C秦九韶算法減少了做乘法的次數(shù)，在計(jì)算機(jī)上也就降低了計(jì)算的速度D秦九韶算法避免了對(duì)自變量x單獨(dú)做冪的計(jì)算，而且與系數(shù)一起逐次增長(zhǎng)冪次，從而提高計(jì)算的精度解析秦九韶算法減少了做乘法的次數(shù)，在計(jì)算機(jī)上也就加快了計(jì)算的速度，故選項(xiàng)C錯(cuò)誤答案C2下列說(shuō)法中正確的個(gè)數(shù)為()輾轉(zhuǎn)相除法也叫歐幾里得算法；輾轉(zhuǎn)相除法的基本步驟是用較大的數(shù)除以較小的數(shù)；求最大公約數(shù)的方法，除輾轉(zhuǎn)相除法之外，沒(méi)有其他方法；編寫輾轉(zhuǎn)相除法的程序時(shí)，要用到循環(huán)語(yǔ)句A1 B2 C3 D4解析、正確，錯(cuò)誤答案C3利用秦九韶算法求f(x)12x3x26x5當(dāng)x2時(shí)的值時(shí)，下列說(shuō)法正確的是()A先求122B先求625，第二步求2(625)4Cf(2)122322423524625直接運(yùn)算求解D以上都不對(duì)解析利用秦九韶算法應(yīng)先算anxan1，再算(anxan1)xan2，故選B.答案B4中國(guó)古代有計(jì)算多項(xiàng)式值的秦九韶算法，下圖是實(shí)現(xiàn)該算法的程序框圖執(zhí)行該程序框圖，若輸入的x2，n2，依次輸入的a為2,2,5，則輸出的s()A7 B12 C17 D34解析該題考查程序框圖的運(yùn)行及考生的識(shí)圖能力由程序框圖知，第一次循環(huán)：x2，n2，a2，s0222，k1；第二次循環(huán)：a2，s2226，k2；第三次循環(huán)：a5，s62517，k3.結(jié)束循環(huán)，輸出s的值為17，故選C.答案C5用更相減損術(shù)求117和182的最大公約數(shù)時(shí)，需做減法的次數(shù)是()A8 B7 C6 D5解析18211765,1176552,655213,521339,391326,261313，13是117和182的最大公約數(shù)，需做減法的次數(shù)是6.答案C6用秦九韶算法求n次多項(xiàng)式f(x)anxnan1xn1a1xa0當(dāng)xx0時(shí)的值，求f(x0)需要乘方、乘法、加法的次數(shù)分別為()A.，n，nBn,2n，nC0,2n，nD0，n，n解析因?yàn)閒(x)(anxan1)xan2)xa1)xa0，所以乘方、乘法、加法的次數(shù)分別為0，n，n.答案D7用秦九韶算法求多項(xiàng)式f(x)1235x8x279x36x45x53x6當(dāng)x4的值時(shí)，其中v1的值為_解析f(x)1235x8x279x36x45x53x6，v0a63，v1v0xa53(4)57.答案78378和90的最大公約數(shù)為_解析37890418,901850，378與90的最大公約數(shù)是18.答案189求1356和2400的最小公倍數(shù)解2400135611044，135610441312，10443123108，312108296，10896112，96128.所以1356與2400的最大公約數(shù)為12.則1356與2400的最小公倍數(shù)為(13562400)12271200.10用秦九韶算法求多項(xiàng)式f(x)7x76x65x54x43x32x2x當(dāng)x3時(shí)的值解f(x)(7x6)x5)x4)x3)x2)x1)x，所以v07，v173627，v2273586，v38634262，v426233789，v5789322369，v62369317108，v77108321324.故x3時(shí)，多項(xiàng)式f(x)7x76x65x54x43x32x2x的值為21324.應(yīng)試能力等級(jí)練(時(shí)間20分鐘)11下列哪組的最大公約數(shù)與1855,1120的最大公約數(shù)不同()A1120,735 B385,350C385,735 D1855,325解析(1855,1120)(735,1120)(735,385)(350,385)(350,35)，1855與1120的最大公約數(shù)是35，由以上計(jì)算過(guò)程可知選D.答案D12用秦九韶算法計(jì)算多項(xiàng)式f(x)3x64x55x46x37x28x1，當(dāng)x0.4時(shí)的值時(shí)，需要做乘法和加法的次數(shù)分別是()A6,6B5,6C5,5D6,5解析根據(jù)秦九韶算法，把多項(xiàng)式改寫為f(x)(