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

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

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