高中數學 1.3算法案例課件 新人教A版必修3.ppt

《高中數學 1.3算法案例課件 新人教A版必修3.ppt》由會員分享，可在線閱讀，更多相關《高中數學 1.3算法案例課件 新人教A版必修3.ppt（44頁珍藏版）》請在裝配圖網上搜索。

1 3算法案例 案例1輾轉相除法與更相減損術 35 915 問題1 在小學 我們已經學過求最大公約數的知識 你能求出18與30的最大公約數嗎 創(chuàng)設情景 揭示課題 1830 2 3 18和30的最大公約數是2 3 6 先用兩個數公有的質因數連續(xù)去除 一直除到所得的商是互質數為止 然后把所有的除數連乘起來 問題2 我們都是利用找公約數的方法來求最大公約數 如果公約數比較大而且根據我們的觀察又不能得到一些公約數 我們又應該怎樣求它們的最大公約數 比如求8251與6105的最大公約數 研探新知 1 輾轉相除法 例1求兩個正數8251和6105的最大公約數 分析 8251與6105兩數都比較大 而且沒有明顯的公約數 如能把它們都變小一點 根據已有的知識即可求出最大公約數 解 8251 6105 1 2146 顯然8251與6105的最大公約數也必是2146的約數 同樣6105與2146的公約數也必是8251的約數 所以8251與6105的最大公約數也是6105與2146的最大公約數 研探新知 1 輾轉相除法 例1求兩個正數8251和6105的最大公約數 解 8251 6105 1 2146 6105 2146 2 1813 2146 1813 1 333 1813 333 5 148 333 148 2 37 148 37 4 0 則37為8251與6105的最大公約數 以上我們求最大公約數的方法就是輾轉相除法 也叫歐幾里德算法 它是由歐幾里德在公元前300年左右首先提出的 利用輾轉相除法求最大公約數的步驟如下 第一步 用較大的數m除以較小的數n得到一個商q0和一個余數r0 m n q0 r0 第二步 若r0 0 則n為m n的最大公約數 若r0 0 則用除數n除以余數r0得到一個商q1和一個余數r1 n r0 q1 r1 第三步 若r1 0 則r0為m n的最大公約數 若r1 0 則用除數r0除以余數r1得到一個商q2和一個余數r2 r0 r1 q2 r2 依次計算直至rn 0 此時所得到的rn 1即為所求的最大公約數 第一步 給定兩個正數m n第二步 計算m除以n所得到余數r第三步 m n n r第四步 若r 0 則m n的最大公約數等于m 否則返回第二步 輾轉相除法求最大公約數算法 否 4 輾轉相除法的程序框圖及程序 開始 輸入兩個正數m n m n r mMODn r 0 輸出n 結束 m x m n n r 否 是 是 x n n m 練習1 利用輾轉相除法求兩數4081與20723的最大公約數 20723 4081 5 318 4081 318 12 265 318 265 1 53 265 53 5 0 2 更相減損術 我國早期也有解決求最大公約數問題的算法 就是更相減損術 更相減損術求最大公約數的步驟如下 可半者半之 不可半者 副置分母 子之數 以少減多 更相減損 求其等也 以等數約之 翻譯出來為 第一步 任意給出兩個正數 判斷它們是否都是偶數 若是 用2約簡 若不是 執(zhí)行第二步 第二步 以較大的數減去較小的數 接著把較小的數與所得的差比較 并以大數減小數 繼續(xù)這個操作 直到所得的數相等為止 則這個數 等數 就是所求的最大公約數 例2用更相減損術求98與63的最大公約數 解 由于63不是偶數 把98和63以大數減小數 并輾轉相減 即 98 63 35 63 35 28 35 28 7 28 7 21 21 7 14 14 7 7 所以 98與63的最大公約數是7 練習2 用更相減損術求兩個正數84與72的最大公約數 第一步 給定兩個正整數 不妨設m n 第二步 若m n都是偶數 則不斷用2約簡 使他們不同時是偶數 約簡后的兩個數仍記為m n第三步 d m n第四步 判斷 d0 是否成立 若是 則將n d中較大者記為m 較小的記為n 返回第三步 否則 2 k d k是約簡整數的2的個數 為所求的最大公約數 更相減損術算法 是 否 N d 是 是 否 INPUT m n m nIFm nTHENa mm nn aENDIFK 0WHILEmMOD2 0ANDnMOD2 0m m 2n n 2k k 1WENDd m n WhilednIFd nthenm dELSEm nn dEndifd m nWendd 2 k dPRINTdEnd 3 輾轉相除法與更相減損術的比較 1 都是求最大公約數的方法 計算上輾轉相除法以除法為主 更相減損術以減法為主 計算次數上輾轉相除法計算次數相對較少 特別當兩個數字大小區(qū)別較大時計算次數的區(qū)別較明顯 2 從結果體現(xiàn)形式來看 輾轉相除法體現(xiàn)結果是以相除余數為0則得到 而更相減損術則以減數與差相等而得到 作業(yè) 課本P45頁練習T1 P48頁A組T1 案例2秦九韶算法 教學設計 問題1 設計求多項式f x 2x5 5x4 4x3 3x2 6x 7當x 5時的值的算法 并寫出程序 點評 上述算法一共做了15次乘法運算 5次加法運算 優(yōu)點是簡單 易懂 缺點是不通用 不能解決任意多項多求值問題 而且計算效率不高 這析計算上述多項式的值 一共需要9次乘法運算 5次加法運算 問題2 有沒有更高效的算法 分析 計算x的冪時 可以利用前面的計算結果 以減少計算量 即先計算x2 然后依次計算 的值 第二種做法與第一種做法相比 乘法的運算次數減少了 因而能提高運算效率 而且對于計算機來說 做一次乘法所需的運算時間比做一次加法要長得多 因此第二種做法能更快地得到結果 問題3 能否探索更好的算法 來解決任意多項式的求值問題 f x 2x5 5x4 4x3 3x2 6x 7 2x4 5x3 4x2 3x 6 x 7 2x3 5x2 4x 3 x 6 x 7 2x2 5x 4 x 3 x 6 x 7 2x 5 x 4 x 3 x 6 x 7 v0 2v1 v0 x 5 2 5 5 5v2 v1x 4 5 5 4 21v3 v2x 3 21 5 3 108v4 v3x 6 108 5 6 534v5 v4x 7 534 5 7 2677 所以 當x 5時 多項式的值是2677 這種求多項式值的方法就叫秦九韶算法 例1 用秦九韶算法求多項式f x 2x5 5x4 4x3 3x2 6x 7當x 5時的值 解法一 首先將原多項式改寫成如下形式 f x 2x 5 x 4 x 3 x 6 x 7 v0 2v1 v0 x 5 2 5 5 5v2 v1x 4 5 5 4 21v3 v2x 3 21 5 3 108v4 v3x 6 108 5 6 534v5 v4x 7 534 5 7 2677 所以 當x 5時 多項式的值是2677 然后由內向外逐層計算一次多項式的值 即 2 5 43 67 x 5 10 5 25 21 105 108 540 534 2670 2677 所以 當x 5時 多項式的值是2677 原多項式的系數 多項式的值 例1 用秦九韶算法求多項式f x 2x5 5x4 4x3 3x2 6x 7當x 5時的值 解法二 列表 2 2 50 43 60 x 5 10 5 25 25 125 121 605 608 3040 3034 所以 當x 5時 多項式的值是15170 練一練 用秦九韶算法求多項式f x 2x6 5x5 4x3 3x2 6x當x 5時的值 解 原多項式先化為 f x 2x6 5x5 0 x4 4x3 3x2 6x 0列表 2 15170 15170 注意 n次多項式有n 1項 因此缺少哪一項應將其系數補0 f x anxn an 1xn 1 an 2xn 2 a1x a0 我們可以改寫成如下形式 f x anx an 1 x an 2 x a1 x a0 求多項式的值時 首先計算最內層括號內一次多項式的值 即 v1 anx an 1 然后由內向外逐層計算一次多項式的值 即 一般地 對于一個n次多項式 v2 v1x an 2 v3 v2x an 3 vn vn 1x a0 這樣 求n次多項式f x 的值就轉化為求n個一次多項式的值 這種算法稱為秦九韶算法 點評 秦九韶算法是求一元多項式的值的一種方法 它的特點是 把求一個n次多項式的值轉化為求n個一次多項式的值 通過這種轉化 把運算的次數由至多n n 1 2次乘法運算和n次加法運算 減少為n次乘法運算和n次加法運算 大大提高了運算效率 v1 anx an 1 v2 v1x an 2 v3 v2x an 3 vn vn 1x a0 觀察上述秦九韶算法中的n個一次式 可見vk的計算要用到vk 1的值 若令v0 an 得 這是一個在秦九韶算法中反復執(zhí)行的步驟 因此可用循環(huán)結構來實現(xiàn) 問題 畫出程序框圖 表示用秦九韶算法求5次多項式f x a5x5 a4x4 a3x3 a2x2 a1x a0當x x0 x0是任意實數 時的值的過程 然后寫出程序 否 程序框圖 開始 輸入a0 a1 a2 a3 a4 a5 輸入x0 n 5 n 1 v a5 v vx0 a5 n n n 1 輸出v 結束 是 課本P45頁練習T2 P48頁A組T2 案例3進位制 一 三維目標 a 知識與技能了解各種進位制與十進制之間轉換的規(guī)律 會利用各種進位制與十進制之間的聯(lián)系進行各種進位制之間的轉換 b 過程與方法學習各種進位制轉換成十進制的計算方法 研究十進制轉換為各種進位制的除k去余法 并理解其中的數學規(guī)律 c 情感態(tài)度與價值觀領悟十進制 二進制的特點 了解計算機的電路與二進制的聯(lián)系 進一步認識到計算機與數學的聯(lián)系 二 教學重難點重點 各進位制表示數的方法及各進位制之間的轉換難點 除k去余法的理解以及各進位制之間轉換的程序框圖的設計三 學法在學習各種進位制特點的同時探討進位制表示數與十進制表示數的區(qū)別與聯(lián)系 熟悉各種進位制表示數的方法 從而理解十進制轉換為各種進位制的除k去余法 問題1 我們常見的數字都是十進制的 但是并不是生活中的每一種數字都是十進制的 比如時間和角度的單位用六十進位制 電子計算機用的是二進制 那么什么是進位制 不同的進位制之間又有什么聯(lián)系呢 進位制是人們?yōu)榱擞嫈岛瓦\算的方便而約定的一種記數系統(tǒng) 約定滿二進一 就是二進制 滿十進一 就是十進制 滿十六進一 就是十六進制 等等 滿幾進一 就是幾進制 幾進制的基數就是幾 可使用數字符號的個數稱為基數 基數都是大于1的整數 如二進制可使用的數字有0和1 基數是2 十進制可使用的數字有0 1 2 8 9等十個數字 基數是10 十六進制可使用的數字或符號有0 9等10個數字以及A F等6個字母 規(guī)定字母A F對應10 15 十六進制的基數是16 注意 為了區(qū)分不同的進位制 常在數字的右下腳標明基數 如111001 2 表示二進制數 34 5 表示5進制數 十進制數一般不標注基數 問題2 十進制數3721中的3表示3個千 7表示7個百 2表示2個十 1表示1個一 從而它可以寫成下面的形式 3721 3 103 7 102 2 101 1 100 想一想二進制數1011 2 可以類似的寫成什么形式 1011 2 1 23 0 22 1 21 1 20 同理 3421 5 3 53 4 52 2 51 1 50 C7A16 16 12 164 7 163 10 162 1 161 6 160 一般地 若k是一個大于1的整數 那么以k為基數的k進制數可以表示為一串數字連寫在一起的形式 anan 1 a1a0 k 0 an k 0 an 1 a1 a0 k 意思是 1 第一個數字an不能等于0 2 每一個數字an an 1 a1 a0都須小于k k進制的數也可以表示成不同位上數字與基數k的冪的乘積之和的形式 即 anan 1 a1a0 k an kn an 1 kn 1 a1 k1 a0 k0 注意這是一個n 1位數 問題3 二進制只用0和1兩個數字 這正好與電路的通和斷兩種狀態(tài)相對應 因此計算機內部都使用二進制 計算機在進行數的運算時 先把接受到的數轉化成二進制數進行運算 再把運算結果轉化為十進制數輸出 那么二進制數與十進制數之間是如何轉化的呢 例1 把二進制數110011 2 化為十進制數 分析 先把二進制數寫成不同位上數字與2的冪的乘積之和的形式 再按照十進制數的運算規(guī)則計算出結果 解 110011 2 1 25 1 24 0 23 0 22 1 21 1 20 1 32 1 16 1 2 1 51 問題4 你會把三進制數10221 3 化為十進制數嗎 解 10221 3 1 34 0 33 2 32 2 31 1 30 81 18 6 1 106 k進制數轉化為十進制數的方法 先把k進制的數表示成不同位上數字與基數k的冪的乘積之和的形式 即 anan 1 a1a0 k an kn an 1 kn 1 a1 k1 a0 k0 再按照十進制數的運算規(guī)則計算出結果 例2 把89化為二進制的數 分析 把89化為二進制的數 需想辦法將89先寫成如下形式 89 an 2n an 1 2n 1 a1 21 a0 20 89 64 16 8 1 1 26 0 25 1 24 1 23 0 22 0 21 1 20 1011001 2 但如果數太大 我們是無法這樣湊出來的 怎么辦 89 44 2 1 44 22 2 0 22 11 2 0 11 5 2 1 5 2 2 1 2 1 2 0 1 0 2 1 89 44 2 1 44 22 2 0 22 11 2 0 11 5 2 1 5 2 2 1 89 44 2 1 22 2 0 2 1 11 2 0 2 0 2 1 5 2 1 2 0 2 0 2 1 2 2 1 2 1 2 0 2 0 2 1 1 2 0 2 1 2 1 2 0 2 0 2 1 1 26 0 25 1 24 1 23 0 22 0 21 1 20 1011001 2 可以用2連續(xù)去除89或所得商 一直到商為0為止 然后取余數 除2取余法 2 1 2 0 1 0 2 1 441 例2 把89化為二進制的數 我們可以用下面的除法算式表示除2取余法 220 110 51 21 10 01 把算式中各步所得的余數從下到上排列 得到 89 1011001 2 這種方法也可以推廣為把十進制數化為k進制數的算法 稱為除k取余法 例3 把89化為五進制的數 解 以5作為除數 相應的除法算式為 174 32 03 89 324 5 問題5 你會把三進制數10221 3 化為二進制數嗎 解 第一步 先把三進制數化為十進制數 10221 3 1 34 0 33 2 32 2 31 1 30 81 18 6 1 106 第二步 再把十進制數化為二進制數 106 1101010 2 小結 進位制的概念及表示方法 各種進位制之間的相互轉化 anan 1 a1a0 k an kn an 1 kn 1 a1 k1 a0 k0 作業(yè) 1 課本P45頁A組T3