高中數(shù)學第一章算法初步1.3算法案例課件新人教A版.ppt

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

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