《高中數(shù)學(xué)第一章算法初步1.3算法案例課件新人教A版.ppt》由會員分享，可在線閱讀，更多相關(guān)《高中數(shù)學(xué)第一章算法初步1.3算法案例課件新人教A版.ppt（73頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1 3算法案例 自主預(yù)習(xí) 主題1 輾轉(zhuǎn)相除法如何求4557和1953的最大公約數(shù) 1 注意到4557 1953 2 651 那么4557和1953的公約數(shù)和1953與651的公約數(shù)有什么關(guān)系 提示 顯然4557與1953的最大公約數(shù)也是651的約數(shù)同樣1953與651的公約數(shù)也是4557的約數(shù) 2 又1953 3 651 0 因此1953和651的最大公約數(shù)為651 由此可得出4557和1953的最大公約數(shù)是多少 提示 4557和1953的最大公約數(shù)為651 結(jié)合以上的探究總結(jié)對輾轉(zhuǎn)相除法的認(rèn)識輾轉(zhuǎn)相除法的算法步驟第一步 給定兩個 第二步 計算 第三步 第四步 則m n的最大公約數(shù)等于 否則 返回 正整數(shù)m n m除以n所得的余數(shù)r m n n r 若r 0 m 第二步 主題2 更相減損術(shù)1 設(shè)兩個正整數(shù)m n 若m n k 則m與n的最大公約數(shù)和n與k的最大公約數(shù)相等嗎 提示 相等 2 反復(fù)利用上述原理如何求396與216的最大公約數(shù) 提示 由396 216 180 216 180 36 180 36 144 144 36 108 108 36 72 72 36 36 故36是396與216的最大公約數(shù) 總結(jié)以上探究歸納對更相減損術(shù)的理解 更相減損術(shù)第一步 任意給定兩個 判斷它們是否都是 若是 若不是 執(zhí)行 正整數(shù) 偶數(shù) 用2約簡 第二步 第二步 以 減去 接著把所得的差與較小的數(shù)比較 并以 繼續(xù)這個操作 直到 為止 則這個數(shù) 等數(shù) 或這個數(shù)與約簡的數(shù)的 就是所求的最大公約數(shù) 較大的數(shù) 較小的數(shù) 大數(shù)減小數(shù) 所得的數(shù)相等 乘積 主題3 秦九韶算法1 如何計算多項式f x x5 x4 x3 x2 x 1當(dāng)x 5時的值呢 統(tǒng)計所做的計算的種類及計算次數(shù)分別是什么 提示 f 5 55 54 53 52 5 1 3906 由計算統(tǒng)計可得出共需做10次乘法運(yùn)算 5次加法運(yùn)算 2 若將多項式變形為f x x 1 x 1 x 1 x 1 x 1統(tǒng)計計算x 5時的計算的種類及計算次數(shù)分別是什么 提示 從里往外計算僅需4次乘法和5次加法運(yùn)算即可得出結(jié)果 總結(jié)以上探究歸納秦九韶算法 秦九韶算法的步驟把一個n次多項式f x anxn an 1xn 1 a1x a0改寫成如下形式 f x anx an 1 x an 2 x a1 x a0 求多項式的值時 首先計算 即v1 然后 逐層計算一次多項式的值 即v2 v3 vn 這樣 求n次多項式f x 的值就轉(zhuǎn)化為求n個一次多項式的值 最內(nèi)層括號內(nèi)一次多項式 的值 anx an 1 由內(nèi)向外 v1x an 2 v2x an 3 vn 1x a0 主題4 進(jìn)位制1 常見的進(jìn)位制有 二進(jìn)制 七進(jìn)制 十進(jìn)制 十二進(jìn)制 六十進(jìn)制 它們的基數(shù)分別是什么 提示 它們的基數(shù)分別是 2 7 10 12 60 2 k進(jìn)制數(shù)的組成數(shù)字有哪些 如果k 8 那么在八進(jìn)制中 組成的數(shù)字有哪些 組成規(guī)律是什么 提示 k進(jìn)制數(shù)組成的數(shù)字有0 1 2 k 1共k個數(shù) 在八進(jìn)制中 基數(shù)是8 一共有0 1 2 3 4 5 6 7這八個不同的數(shù)字 組成規(guī)律是 滿八進(jìn)一 如 7 1 10 8 通過以上探究概括你對進(jìn)位制的理解 1 進(jìn)位制的概念及其表示 概念 人們?yōu)榱擞嫈?shù)和運(yùn)算方便而約定的記數(shù)系統(tǒng) 滿二進(jìn)一 就是二進(jìn)制 滿十進(jìn)一 就是十進(jìn)制 滿k進(jìn)一 就是 k進(jìn)制的基數(shù)是k 因此k進(jìn)制需要使用 數(shù)字 k進(jìn)制 k個 表示 一般地 若k是一個大于1的整數(shù) 那么以k為基數(shù)的k進(jìn)制數(shù)可以表示為一串?dāng)?shù)字連寫在一起的形式 an an 1 a1 a0 N 0 an k 0 an 1 a1 a0 k anan 1 a1a0 k 2 進(jìn)位制之間的轉(zhuǎn)化 k進(jìn)制的數(shù)轉(zhuǎn)化為十進(jìn)制 若anan 1 a1a0 k 表示一個k進(jìn)制的數(shù) 則轉(zhuǎn)化為十進(jìn)制數(shù)為 anan 1 a1a0 k an kn an 1 kn 1 a1 k a0 非十進(jìn)制的k進(jìn)制數(shù)a 共有n位 化為十進(jìn)制數(shù)b的算法步驟 第一步 輸入a k n的值 第二步 將b的值初始化為0 i的值初始化為1 第三步 b b aiki 1 i i 1 第四步 判斷 是否成立 若是 則執(zhí)行第五步 否則 返回第三步 i n 第五步 輸出b的值 將十進(jìn)制化為k進(jìn)制 用 用k連續(xù)去除十進(jìn)制數(shù)所得的商 直到商為零為止 然后將所得的余數(shù) 即為相應(yīng)的k進(jìn)制數(shù) 除k取余法 倒序?qū)懗?深度思考 1 結(jié)合教材P36例1 你認(rèn)為更相減損術(shù)的一般步驟是什么 第一步 第二步 給定兩個正整數(shù)m n 不妨設(shè)m n 若m n都是偶數(shù) 則不斷用2約簡 使它們不 同時是偶數(shù) 約簡后的兩個數(shù)仍記為m n 第三步 第四步 d m n 判斷 d n 是否成立 若是 則將n d中的 較大者記為m 較小者記為n 返回第三步 否則 2kd k是約簡整數(shù)2的個數(shù) 為所求的最大公約數(shù) 2 結(jié)合教材P38例2 你認(rèn)為利用秦九韶算法求值的一般步驟是什么 設(shè)Pn x anxn an 1xn 1 a1x a0 將其改寫為Pn x anxn 1 an 1xn 2 a1 x a0 anxn 2 an 1xn 3 a2 x a1 x a0 anx an 1 x an 2 x a1 x a0 第一步 第二步 第三步 第四步 第五步 輸入多項式次數(shù)n 最高次項的系數(shù)an和x的值 將v的值初始化為an 將i的值初始化為n 1 輸入i次項的系數(shù)ai v vx ai i i 1 判斷i是否大于或等于0 若是 則返回第三步 否則 輸出多項式的值v 預(yù)習(xí)小測 1 用更相減損術(shù)可求得78與36的最大公約數(shù)是 A 24B 18C 12D 6 解析 選D 先用2約簡得39 18 然后輾轉(zhuǎn)相減得39 18 21 21 18 3 18 3 15 15 3 12 12 3 9 9 3 6 6 3 3 所以所求的最大公約數(shù)為3 2 6 2 用輾轉(zhuǎn)相除法求294和84的最大公約數(shù)時 需要做除法的次數(shù)是 A 1B 2C 3D 4 解析 選B 因為294 84 3 42 84 42 2 所以選B 3 以下各數(shù)中有可能是五進(jìn)制數(shù)的是 A 55B 106C 732D 2134 解析 選D 在5進(jìn)制數(shù)中 所組成的數(shù)字為0 1 2 3 4 因此A B C不可能是5進(jìn)制數(shù) 4 用秦九韶算法求多項式f x x5 5x4 10 x3 10 x2 5x 1 當(dāng)x 2時的值為 解析 f x x5 5x4 10 x3 10 x2 5x 1 x 5 x 10 x 10 x 5 x 1 而x 2 所以有v0 1 v1 v0 x a4 1 2 5 3 v2 v1x a3 3 2 10 4 v3 v2x a2 4 2 10 2 v4 v3x a1 2 2 5 1 v5 v4x a0 1 2 1 1 故f 2 1 答案 1 5 將十進(jìn)制數(shù)30化為二進(jìn)制數(shù)為 解析 故30 10 11110 2 答案 11110 2 6 用秦九韶算法計算多項式f x x6 12x5 60 x4 160 x3 240 x2 192x 64在x 2時的值 仿照教材P38例2解析過程 解析 先將多項式f x 進(jìn)行改寫 f x x6 12x5 60 x4 160 x3 240 x2 192x 64 x 12 x 60 x 160 x 240 x 192 x 64 然后由內(nèi)向外計算得 v0 1 v1 v0 x a5 1 2 12 10 v2 v1x a4 10 2 60 40 v3 v2x a3 40 2 160 80 v4 v3x a2 80 2 240 80 v5 v4x a1 80 2 192 32 v6 v5x a0 32 2 64 0 所以當(dāng)x 2時 多項式的值為0 互動探究 1 在用秦九韶算法計算n次項式在x x0時的值 至多需要進(jìn)行幾次乘法和加法運(yùn)算 提示 n次乘法運(yùn)算和n次加法運(yùn)算 2 7進(jìn)制中 數(shù)3521中的3 5 2 1各表示什么意思 提示 3表示3個73 5表示5個72 2表示2個7 1表示1個1 3 如何進(jìn)行兩個非十進(jìn)制數(shù)之間的轉(zhuǎn)換 提示 以十進(jìn)制數(shù)作為橋梁 先將一個進(jìn)制的數(shù)轉(zhuǎn)化為十進(jìn)制數(shù) 再將十進(jìn)制數(shù)用除k取余法轉(zhuǎn)化為另一進(jìn)制的數(shù) 探究總結(jié) 知識歸納 注意事項 1 用更相減損術(shù)求兩正整數(shù)的最大公約數(shù)時 若兩數(shù)為偶數(shù) 可先約去2 這時莫忘記求得的相等兩數(shù)乘以約簡的數(shù)才是所求最大公約數(shù) 2 除k取余法的注意點 要連續(xù)除 用k連續(xù)去除十進(jìn)制數(shù)及所得的商 直到商為零為止 倒著寫 把各步得到的余數(shù)倒寫 即從下到上排列 就是相應(yīng)的k進(jìn)制數(shù) 題型探究 類型一 輾轉(zhuǎn)相除法與更相減損術(shù) 典例1 1 98 28這兩個數(shù)的最大公約數(shù)為 A 17B 16C 14D 8 2 1037和425的最大公約數(shù)是 A 51B 17C 9D 3 解題指南 1 因兩數(shù)較小 可采用輾轉(zhuǎn)相除法 也可用更相減損術(shù)求解 2 兩數(shù)相差較大 用輾轉(zhuǎn)相除法求最大公約數(shù) 解析 1 選C 方法一 98 28 3 14 28 14 2 所以98與28的最大公約數(shù)為14 方法二 因為98 28 70 70 28 42 42 28 14 28 14 14 所以98與28的最大公約數(shù)是14 2 選B 因為1037 425 2 187 425 187 2 51 187 51 3 34 51 34 1 17 34 17 2 即1037和425的最大公約數(shù)是17 規(guī)律總結(jié) 輾轉(zhuǎn)相除法和更相減損術(shù)求最大公約數(shù)的注意點 1 輾轉(zhuǎn)相除法是當(dāng)大數(shù)被小數(shù)除盡時 結(jié)束除法運(yùn)算 較小的數(shù)就是最大公約數(shù) 2 更相減損術(shù)是當(dāng)大數(shù)減去小數(shù)的差等于小數(shù)時停止減法 較小的數(shù)就是最大公約數(shù) 鞏固訓(xùn)練 1 兩個整數(shù)490和910的最大公約數(shù)是 A 2B 10C 30D 70 解析 選D 910 91 10 490 49 10 因為91 49 1 42 49 42 1 7 42 7 6 所以91與49的最大公約數(shù)為7 故910與490的最大公約數(shù)為70 2 求5280與12155的最大公約數(shù) 解析 12155 5280 2 1595 5280 1595 3 495 1595 495 3 110 495 110 4 55 110 55 2 故12155與5280的最大公約數(shù)為55 類型二 秦九韶算法 典例2 1 用秦九韶算法計算f x 6x5 4x4 x3 2x2 9x 需要加法與乘法的運(yùn)算次數(shù)分別為 A 5 4B 5 5C 4 4D 4 5 2 用秦九韶算法計算當(dāng)x 5時 多項式f x 2x4 6x3 5x2 4x 6的值時 v3的值等于 解題指南 1 利用秦九韶算法寫出多項式f x 可知加法 乘法的次數(shù) 2 利用秦九韶算法由內(nèi)到外依次計算即可得答案 解析 1 選D f x 6x 4 x 1 x 2 x 9 x 所以加法4次 乘法5次 2 將多項式化成如下形式f x 2x 6 x 5 x 4 x 6 由內(nèi)向外計算 v0 2 v1 2 5 6 4 v2 4 5 5 15 v3 15 5 4 79 答案 79 延伸探究 1 改變問法 典例2 2 中條件不變 求f 5 解析 v0 2 v1 2 5 6 4 v2 5 4 5 15 v3 15 5 4 79 v4 79 5 6 389 即f 5 389 2 改變問法 典例2 2 中 求f 5 的過程中有多少次加法 乘法運(yùn)算 解析 由f x 2x 6 x 5 x 4 x 6 所以有4次乘法運(yùn)算 4次加法運(yùn)算 規(guī)律總結(jié) 利用秦九韶算法計算多項式的值的策略 1 正確地將多項式改寫 若在多項式中有幾項不存在 可將這些項的系數(shù)看成0 即把這些項看成0 xn 2 由內(nèi)向外逐次計算 3 每一步計算結(jié)果準(zhǔn)確 由于下一次計算用到上一次計算的結(jié)果 應(yīng)認(rèn)真 細(xì)致地計算每一步 鞏固訓(xùn)練 用秦九韶算法計算多項式f x 12 35x 8x2 11x3 6x4 5x5 3x6當(dāng)x 4時的值時 v2的值為 解析 將f x 變形為f x 3x 5 x 6 x 11 x 8 x 35 x 12 所以v0 3 v1 3 4 5 7 v2 7 4 6 34 答案 34 類型三 進(jìn)位制 典例3 1 2016 鄭州高二檢測 將五進(jìn)制數(shù)444 5 化為四進(jìn)制數(shù)應(yīng)表示為 2 把87化為二進(jìn)制數(shù) 應(yīng)表示為 解題指南 1 先將五進(jìn)制數(shù)444 5 轉(zhuǎn)化為十進(jìn)制 再化為四進(jìn)制 2 利用除2取余法求解 解析 1 444 5 4 52 4 51 4 50 124 再將十進(jìn)制數(shù)124化為四進(jìn)制數(shù) 所以124 1330 4 所以444 5 1330 4 答案 1330 4 2 所以87 1010111 2 答案 1010111 2 規(guī)律總結(jié) 1 將k進(jìn)制轉(zhuǎn)化為十進(jìn)制的方法技巧 1 先將這個k進(jìn)制數(shù)寫成各位上的數(shù)字與k的冪的乘積之和的形式 再按照十進(jìn)制數(shù)的運(yùn)算規(guī)則計算出結(jié)果 如 anan 1 a1a0 k an kn an 1 kn 1 a1 k1 a0 k0 2 k的冪的最高次數(shù)是該k進(jìn)制數(shù)的位數(shù)減去1 然后逐個減少1 最后是零次冪 我們稱這種方法為方冪法 2 將十進(jìn)制化為k進(jìn)制的步驟 1 用k連續(xù)去除十進(jìn)制數(shù)及所得的商 直到商為零為止 2 把各步得到的余數(shù)倒寫就是相應(yīng)的k進(jìn)制數(shù) 鞏固訓(xùn)練 1 1 把67化為二進(jìn)制數(shù)為 A 1100001 2 B 1000011 2 C 110000 2 D 1000111 2 2 將八進(jìn)制數(shù)3726 8 化成十進(jìn)制數(shù)為 解題指南 1 利用除2取余法求解 2 利用八進(jìn)制數(shù)中各個數(shù)字的含義求解 解析 1 選B 所以67 1000011 2 2 因為3726 8 3 83 7 82 2 8 6 2006 所以3726 8 2006 答案 2006 2 把五進(jìn)制數(shù)1234 5 轉(zhuǎn)化為十進(jìn)制數(shù) 再把它轉(zhuǎn)化為八進(jìn)制數(shù) 解析 1234 5 1 53 2 52 3 51 4 50 194 10 因為所以1234 5 194 10 302 8