高中數(shù)學(xué) 1.3算法案例課件 新人教A版必修3.ppt

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

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