高中數(shù)學 1.3.1 輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法課件1 新人教A版必修3.ppt

1 3算法案例第1課時輾轉(zhuǎn)相除法與更相減損術(shù) 秦九韶算法 1 通過輾轉(zhuǎn)相除法與更相減損術(shù) 秦九韶算法的學習 進一步體會算法思想 2 通過古代著名的算法 理解掌握輾轉(zhuǎn)相除法與更相減損術(shù) 秦九韶算法的含義 重點 3 了解其計算過程 重點 4 了解其算法程序框圖和程序 難點 1 回顧算法的三種表述 自然語言程序框圖 三種邏輯結(jié)構(gòu) 程序語言 五種基本語句 2 小學學過的求兩個數(shù)最大公約數(shù)的方法 先用兩個公有的質(zhì)因數(shù)連續(xù)去除 一直除到所得的商是互質(zhì)數(shù)為止 然后把所有的除數(shù)連乘起來 例如 求兩個正整數(shù)的最大公約數(shù) 1 求25和35的最大公約數(shù) 2 求49和63的最大公約數(shù) 所以 25和35的最大公約數(shù)為5 所以 49和63的最大公約數(shù)為7 除了用這種方法外還有沒有其他方法嗎 輾轉(zhuǎn)相除法 歐幾里得算法 思考 算出8251和6105的最大公約數(shù) 第一步 用兩數(shù)中較大的數(shù)除以較小的數(shù) 求得商和余數(shù)8251 6105 1 2146 結(jié)論 8251和6105的公約數(shù)就是6105和2146的公約數(shù) 求8251和6105的最大公約數(shù) 只要求出6105和2146的最大公約數(shù)就可以了 為什么 第二步 對6105和2146重復第一步的做法 6105 2146 2 1813 同理6105和2146的最大公約數(shù)也是2146和1813的最大公約數(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是148和37的最大公約數(shù) 也就是8251和6105的最大公約數(shù) 所謂輾轉(zhuǎn)相除法 就是對于給定的兩個數(shù) 用較大的數(shù)除以較小的數(shù) 若余數(shù)不為零 則將余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù) 繼續(xù)上面的除法 直到大數(shù)被小數(shù)除盡 則這時較小的數(shù)就是原來兩個數(shù)的最大公約數(shù) 1 輾轉(zhuǎn)相除法 2 算法步驟第一步 輸入兩個正整數(shù)m n m n 第二步 計算m除以n所得的余數(shù)r 第三步 m n n r 第四步 若r 0 則m n的最大公約數(shù)等于m 否則轉(zhuǎn)到第二步 第五步 輸出最大公約數(shù)m 3 程序框圖 4 程序 inputm ndor mmodnm nn rloopuntilr 0printmend 更相減損術(shù)算理 可半者半之 不可半者 副置分母 子之數(shù) 以少減多 更相減損 求其等也 以等數(shù)約之 第一步 任意給定兩個正整數(shù) 判斷它們是否都是偶數(shù) 若是 則用2約簡 若不是則執(zhí)行第二步 第二步 以較大的數(shù)減較小的數(shù) 接著把所得的差與較小的數(shù)比較 并以大數(shù)減小數(shù) 繼續(xù)這個操作 直到所得的數(shù)相等為止 則這個數(shù) 等數(shù) 或其與約簡的數(shù)的乘積就是所求的最大公約數(shù) 更相減損術(shù) 1 算理 所謂更相減損術(shù) 就是對于給定的兩個數(shù) 用較大的數(shù)減去較小的數(shù) 然后將差和較小的數(shù)構(gòu)成新的一對數(shù) 再用較大的數(shù)減去較小的數(shù) 反復執(zhí)行此步驟 直到差數(shù)和較小的數(shù)相等 此時相等的兩數(shù)便為原來兩個數(shù)的最大公約數(shù) 2 算法步驟第一步 輸入兩個正整數(shù)a b a b 第二步 若a不等于b 則執(zhí)行第三步 否則轉(zhuǎn)到第五步 第三步 把a b的差賦予r 第四步 如果b r 那么把b賦給a 把r賦給b 否則把r賦給a 執(zhí)行第二步 第五步 輸出最大公約數(shù)b 3 程序框圖 4 程序 input a b a bwhilea br a bifb rthena bb relsea rendifwendprintbend 例1用更相減損術(shù)求98與63的最大公約數(shù) 解 由于63不是偶數(shù) 把98和63以大數(shù)減小數(shù) 并輾轉(zhuǎn)相減 98 63 3563 35 2835 28 728 7 2121 7 1414 7 7所以 98和63的最大公約數(shù)等于7 秦九韶算法的基本思想對于求n次多項式的值 在我國古代數(shù)學中有一個優(yōu)秀算法 即秦九韶算法 我們將對這個算法作些了解和探究 思考1 對于多項式f x x5 x4 x3 x2 x 1 求f 5 的值 若先計算各項的值 然后再相加 那么一共要做多少次乘法運算和多少次加法運算 4 3 2 1 10次乘法運算 5次加法運算 思考2 在上述問題中 若先計算x2的值 然后依次計算x2 x x2 x x x2 x x x的值 這樣每次都可以利用上一次計算的結(jié)果 再將這些數(shù)與x和1相加 那么一共做了多少次乘法運算和多少次加法運算 4次乘法運算 5次加法運算 思考3 利用后一種算法求多項式f x anxn an 1xn 1 a1x a0的值 這個多項式應寫成哪種形式 f x anxn an 1xn 1 a1x a0 anxn 1 an 1xn 2 a2x a1 x a0 anxn 2 an 1xn 3 a2 x a1 x a0 anx an 1 x an 2 x a1 x a0 這是怎樣的一種改寫方式 最后的結(jié)果是什么 思考4 對于f x anx an 1 x an 2 x a1 x a0 由內(nèi)向外逐層計算一次多項式的值 其算法步驟如何 第一步 計算v1 anx an 1 第二步 計算v2 v1x an 2 第三步 計算v3 v2x an 3 第n步 計算vn vn 1x a0 最后的一項是什么 思考5 上述求多項式f x anxn an 1xn 1 a1x a0的值的方法稱為秦九韶算法 利用該算法求f x0 的值 一共需要多少次乘法運算 多少次加法運算 思考6 在秦九韶算法中 記v0 an 那么第k步的算式是什么 vk vk 1x an k k 1 2 n 秦九韶算法的程序設(shè)計思考1 用秦九韶算法求多項式的值 可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法 其算法步驟如何設(shè)計 第一步 輸入多項式的次數(shù)n 最高次項的系數(shù)an和x的值 第二步 令v an i n 1 第三步 輸入i次項的系數(shù)ai 第四步 v vx ai i i 1 第五步 判斷i 0是否成立 若是 則返回第三步 否則 輸出多項式的值v 思考2 該算法的程序框圖如何表示 開始 輸入n an x的值 v an v vx ai 輸入ai i 0 i n 1 i i 1 結(jié)束 是 輸出v 否 思考3 該程序框圖對應的程序如何表述 開始 輸入n an x的值 v an v vx ai 輸入ai i 0 i n 1 i i 1 結(jié)束 是 輸出v 否 input n ninput an ainput x xv ai n 1whilei 0print i iinput ai av v x ai i 1wendprintvend 例2已知一個5次多項式為f x 4x5 2x4 3 5x3 2 6x2 1 7x 0 8 用秦九韶算法求這個多項式當x 5時的值 解 根據(jù)秦九韶算法把多項式改寫成如下形式 f x 4x 2 x 3 5 x 2 6 x 1 7 x 0 8 按照從內(nèi)到外的順序 依次計算一次多項式當x 5時的值 v0 4 v1 4 5 2 22 v2 22 5 3 5 113 5 v3 113 5 5 2 6 564 9 v4 564 9 5 1 7 2826 2 v5 2826 2 5 0 8 14130 2 所以f 5 14130 2 閱讀下列程序 說明它解決的實際問題是什么 解 求多項式f x 1 2x 3x2 4x3 5x4在x a時的值 input x an 0y 0whilen 5y y n 1 a nn n 1wendprintyend 1 用輾轉(zhuǎn)相除法求225和135的最大公約數(shù) 顯然45是90和45的最大公約數(shù) 也就是225和135的最大公約數(shù) 225 135 1 90 135 90 1 45 90 45 2 2 利用輾轉(zhuǎn)相除法求兩數(shù)4081與20723的最大公約數(shù) 20723 4081 5 318 4081 318 12 265 318 265 1 53 265 53 5 0 所以4081與20723的最大公約數(shù)是53 3 用秦九韶算法求多項式f x 2x5 5x4 4x3 3x2 6x 7當x 5時的值 解 首先將原多項式改寫成如下形式 f x 2x 5 x 4 x 3 x 6 x 7然后由內(nèi)向外逐層計算一次多項式當x 5時的值 即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 比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別 1 都是求最大公約數(shù)的方法 計算上輾轉(zhuǎn)相除法以除法為主 更相減損術(shù)以減法為主 計算次數(shù)上