【步步高 學(xué)案導(dǎo)學(xué)設(shè)計(jì)】高中數(shù)學(xué) 1.3算法案例課時(shí)作業(yè) 新人教A版必修3.doc

1.3算法案例課時(shí)目標(biāo)通過(guò)三種算法案例：輾轉(zhuǎn)相除法與更相減損術(shù)，秦九韶算法，進(jìn)位制，進(jìn)一步體會(huì)算法的思想，提高算法設(shè)計(jì)水平，體會(huì)中國(guó)古代數(shù)學(xué)對(duì)世界的貢獻(xiàn)1輾轉(zhuǎn)相除法(1)輾轉(zhuǎn)相除法，又叫歐幾里得算法，是一種求兩個(gè)正整數(shù)的最大公約數(shù)的古老而有效的算法(2)輾轉(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秦九韶算法把一個(gè)n次多項(xiàng)式f(x)anxnan1xn1a1xa0改寫(xiě)成如下形式：(anxan1)xan2)xa1)xa0，求多項(xiàng)式的值時(shí)，首先計(jì)算最內(nèi)層括號(hào)內(nèi)一次多項(xiàng)式的值，即v1anxan1，然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值，即v2v1xan2，v3v2xan3，vnvn1xa0這樣，求n次多項(xiàng)式f(x)的值就轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值4進(jìn)位制進(jìn)位制是人們?yōu)榱擞?jì)數(shù)和運(yùn)算方便而約定的記數(shù)系統(tǒng)，“滿k進(jìn)一”就是k進(jìn)制，k進(jìn)制的基數(shù)是k.把十進(jìn)制轉(zhuǎn)化為k進(jìn)制數(shù)時(shí)，通常用除k取余法一、選擇題1下列說(shuō)法中正確的個(gè)數(shù)為()(1)輾轉(zhuǎn)相除法也叫歐幾里得算法；(2)輾轉(zhuǎn)相除法的基本步驟是用較大的數(shù)除以較小的數(shù)；(3)求最大公約數(shù)的方法，除輾轉(zhuǎn)相除法之外，沒(méi)有其他方法；(4)編寫(xiě)輾轉(zhuǎn)相除法的程序時(shí)，要用到循環(huán)語(yǔ)句a1 b2 c3 d4答案c解析(1)、(2)、(4)正確，(3)錯(cuò)誤2用更相減損術(shù)求294和84的最大公約數(shù)時(shí)，需做減法的次數(shù)是()a2 b3 c4 d5答案c解析由于294和84都是偶數(shù)，所以用2約簡(jiǎn)：2942147，84242，又由于147不是偶數(shù)，所以14742105，1054263，634221，422121，故需做4次減法，故選c.31 037和425的最大公約數(shù)是()a51 b17 c9 d3答案b解析1 0374252187，425187251，18751334，5134117，34172，即1 037和425的最大公約數(shù)是17.4用秦九韶算法計(jì)算多項(xiàng)式f(x)6x65x54x43x32x2x7在x0.4時(shí)的值時(shí)，需做加法和乘法的次數(shù)的和為()a10 b9 c12 d8答案c解析f(x)(6x5)x4)x3)x2)x1)x7加法6次，乘法6次，6612(次)，故選c.5已知f(x)x52x33x2x1，應(yīng)用秦九韶算法計(jì)算x3時(shí)的值時(shí)，v3的值為()a27 b11 c109 d36答案d解析將函數(shù)式化成如下形式f(x)(x0)x2)x3)x1)x1由內(nèi)向外依次計(jì)算：v01，v11303，v233211，v3113336，v43631109，v510931328.6下列有可能是4進(jìn)制數(shù)的是()a5 123 b6 542 c3 103 d4 312答案c解析4進(jìn)制數(shù)每位上的數(shù)字一定小于4，故選c.二、填空題7輾轉(zhuǎn)相除法程序中有一空請(qǐng)?zhí)钌洗鸢竌 mod b解析mod用來(lái)表示a除以b的余數(shù)8更相減損術(shù)程序中有兩空請(qǐng)?zhí)钌洗鸢竌bbr9已知三個(gè)數(shù)12(16)，25(7)，33(4)，將它們按由小到大的順序排列為_(kāi)答案33(4)12(16)25(7)解析將三個(gè)數(shù)都化為十進(jìn)制數(shù)12(16)116218，25(7)27519，33(4)34315，33(4)12(16)25(7)三、解答題10用兩種方法求210與98的最大公約數(shù)解用輾轉(zhuǎn)相除法：21098214，98147.210與98的最大公約數(shù)為14.用更相減損術(shù)：210與98都是偶數(shù)，用2約簡(jiǎn)得105和49，1054956,56497，49742,42735，35728,28721，21714,1477.210與98的最大公約數(shù)為2714.11用秦九韶算法計(jì)算多項(xiàng)式f(x)x612x560x4160x3240x2192x64當(dāng)x2時(shí)的值解將f(x)改寫(xiě)為f(x)(x12)x60)x160)x240)x192)x64由內(nèi)向外依次計(jì)算一次多項(xiàng)式當(dāng)x2時(shí)的值v01，v1121210，v21026040，v340216080，v480224080，v580219232，v6322640.f(2)0，即x2時(shí)，原多項(xiàng)式的值為0.能力提升12把111化為五進(jìn)制數(shù)解111化為五進(jìn)制數(shù)為421(5)13把10 231(5)化為四進(jìn)制數(shù)解先化成十進(jìn)制數(shù)10 231(5)154053252351162550151691再化為四進(jìn)制數(shù)10 231(5)22 303(4).1輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別和聯(lián)系(1)都是求最大公約數(shù)的方法(2)二者的實(shí)質(zhì)都是遞歸的過(guò)程(3)二者都要用循環(huán)結(jié)構(gòu)來(lái)實(shí)現(xiàn)2秦九韶算法的特點(diǎn)秦九韶算法的特點(diǎn)在于把求一個(gè)n次多項(xiàng)式的值轉(zhuǎn)化為求n個(gè)一次多項(xiàng)式的值，即把求f(x)anxnan1xn1a1xa0的值轉(zhuǎn)化為求遞推公式：這樣可以最多計(jì)算n次乘法和n次加法即可得多項(xiàng)式的值，和直接代入多項(xiàng)式相比減少了乘法的運(yùn)算次數(shù)，提高了運(yùn)算效率3十進(jìn)制與其他進(jìn)制的轉(zhuǎn)化(1)將k進(jìn)制轉(zhuǎn)化為十