輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法

《輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法》由會員分享，可在線閱讀，更多相關(guān)《輾轉(zhuǎn)相除法與更相減損術(shù)、秦九韶算法（32頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、1.3 算 法 案 例第 1課 時 輾 轉(zhuǎn) 相 除 法 與 更 相 減 損術(shù) 、 秦 九 韶 算 法 1.通 過 輾 轉(zhuǎn) 相 除 法 與 更 相 減 損 術(shù) 、 秦 九 韶 算 法 的 學 習 ,進一 步 體 會 算 法 思 想 ;2.通 過 古 代 著 名 的 算 法 ,理 解 掌 握 輾 轉(zhuǎn) 相 除 法 與 更 相 減 損術(shù) 、 秦 九 韶 算 法 的 含 義 ;(重 點 )3.了 解 其 計 算 過 程 ;(重 點 )4.了 解 其 算 法 程 序 框 圖 和 程 序 (難 點 ) 1. 回 顧 算 法 的 三 種 表 述 ：自 然 語 言程 序 框 圖 （ 三 種 邏 輯 結(jié) 構(gòu) ）程

2、 序 語 言 （ 五 種 基 本 語 句 ） 2.小 學 學 過 的 求 兩 個 數(shù) 最 大 公 約 數(shù) 的 方 法 .先 用 兩 個 公 有 的 質(zhì) 因 數(shù) 連 續(xù) 去 除 ， 一 直 除 到 所 得 的 商 是互 質(zhì) 數(shù) 為 止 ， 然 后 把 所 有 的 除 數(shù) 連 乘 起 來 .例 如 ： 求 兩 個 正 整 數(shù) 的 最 大 公 約 數(shù)（ 1） 求 25和 35的 最 大 公 約 數(shù)（ 2） 求 49和 63的 最 大 公 約 數(shù)25（ 1） 5 5 357 49（ 2） 7 7 639所 以 ， 25和 35的 最 大 公約 數(shù) 為 5. 所 以 ， 49和 63的 最 大 公約 數(shù)

3、 為 7.除 了 用 這 種 方 法 外 還 有沒 有 其 他 方 法 嗎 ？ 輾 轉(zhuǎn) 相 除 法 （ 歐 幾 里 得 算 法 ）思 考 ： 算 出 8 251和 6 105的 最 大 公 約 數(shù) .第 一 步 ,用 兩 數(shù) 中 較 大 的 數(shù) 除 以 較 小 的 數(shù) ， 求 得 商 和 余數(shù) 8 251=6 105 1+2 146.結(jié) 論 ： 8 251和 6 105的 公 約 數(shù) 就 是 6 105和 2 146的 公約 數(shù) ， 求 8 251和 6 105的 最 大 公 約 數(shù) ， 只 要 求 出 6 105和 2 146的 最 大 公 約 數(shù) 就 可 以 了 . 為 什 么 ？ 第 二

4、 步 ,對 6 105和 2 146重 復 第 一 步 的 做 法 ，6 105=2 146 2+1 813，同 理 6 105和 2 146的 最 大 公 約 數(shù) 也 是 2 146和 1 813的最 大 公 約 數(shù) . 完 整 的 過 程 : 8 251=6 105 1+2 146 6 105=2 146 2+1 813 2 146=1 813 1+3331 813=333 5+148333=148 2+37148=37 4+0 顯 然 37是 148和 37的 最 大 公 約 數(shù) ， 也 就 是 8 251和 6 105的最 大 公 約 數(shù) . 所 謂 輾 轉(zhuǎn) 相 除 法 ， 就 是 對

5、 于 給 定 的 兩 個 數(shù) ， 用 較大 的 數(shù) 除 以 較 小 的 數(shù) .若 余 數(shù) 不 為 零 ， 則 將 余 數(shù) 和 較小 的 數(shù) 構(gòu) 成 新 的 一 對 數(shù) ， 繼 續(xù) 上 面 的 除 法 ， 直 到 大 數(shù)被 小 數(shù) 除 盡 ， 則 這 時 較 小 的 數(shù) 就 是 原 來 兩 個 數(shù) 的 最 大公 約 數(shù) .（ 1） 輾 轉(zhuǎn) 相 除 法 （ 2） 算 法 步 驟第 一 步 ,輸 入 兩 個 正 整 數(shù) m,n(mn).第 二 步 ,計 算 m除 以 n所 得 的 余 數(shù) r.第 三 步 ,m=n,n=r.第 四 步 ,若 r 0,則 m,n的 最 大 公 約 數(shù) 等 于 m； 否

6、則 轉(zhuǎn)到 第 二 步 . 第 五 步 ,輸 出 最 大 公 約 數(shù) m. （ 3） 程 序 框 圖 （ 4） 程 序INPUT m,nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT mEND開 始輸 入 m， n求 m除 以 n的 余 數(shù) rm=nn=rr=0？是輸 出 m結(jié) 束 否 更 相 減 損 術(shù) 算 理 ： 可 半 者 半 之 ， 不 可 半 者 ， 副 置 分 母 、 子 之 數(shù) ， 以 少減 多 ， 更 相 減 損 ， 求 其 等 也 ， 以 等 數(shù) 約 之 .第 一 步 ： 任 意 給 定 兩 個 正 整 數(shù) ， 判 斷 它 們 是 否 都 是 偶

7、 數(shù) .若 是 ， 則 用 2約 簡 ； 若 不 是 則 執(zhí) 行 第 二 步 .第 二 步 ： 以 較 大 的 數(shù) 減 較 小 的 數(shù) ， 接 著 把 所 得 的 差 與 較 小的 數(shù) 比 較 ， 并 以 大 數(shù) 減 小 數(shù) .繼 續(xù) 這 個 操 作 ， 直 到 所 得 的數(shù) 相 等 為 止 ， 則 這 個 數(shù) （ 等 數(shù) ） 或 其 與 約 簡 的 數(shù) 的 乘 積 就是 所 求 的 最 大 公 約 數(shù) . 更 相 減 損 術(shù)（ 1） 算 理 ： 所 謂 更 相 減 損 術(shù) ， 就 是 對 于 給 定 的 兩 個 數(shù) ，用 較 大 的 數(shù) 減 去 較 小 的 數(shù) ， 然 后 將 差 和 較 小

8、 的 數(shù) 構(gòu) 成 新的 一 對 數(shù) ， 再 用 較 大 的 數(shù) 減 去 較 小 的 數(shù) ， 反 復 執(zhí) 行 此 步驟 ， 直 到 差 數(shù) 和 較 小 的 數(shù) 相 等 ， 此 時 相 等 的 兩 數(shù) 便 為 原來 兩 個 數(shù) 的 最 大 公 約 數(shù) . （ 2） 算 法 步 驟第 一 步 ,輸 入 兩 個 正 整 數(shù) a,b(ab);第 二 步 ,若 a不 等 于 b ,則 執(zhí) 行 第 三 步 ； 否 則 轉(zhuǎn) 到 第 五 步 ；第 三 步 ,把 a-b的 差 賦 予 r;第 四 步 ,如 果 br, 那 么 把 b賦 給 a,把 r賦 給 b;否 則 把 r賦 給 a，執(zhí) 行 第 二 步 ；第

9、五 步 ,輸 出 最 大 公 約 數(shù) b. （ 3） 程 序 框 圖 開 始輸 入 a， bbr？a=b是 輸 出 b結(jié) 束ab？r=a-b是 否b=ra=r否 （ 4） 程 序 INPUT “ a,b=“ ;a,bWHILE a b r=a-b IF br THEN a=b b=r ELSE a=r END IFWENDPRINT bEND 例 1 用 更 相 減 損 術(shù) 求 98與 63的 最 大 公 約 數(shù) .解 ： 由 于 63不 是 偶 數(shù) ， 把 98和 63以 大 數(shù) 減 小 數(shù) ， 并 輾 轉(zhuǎn) 相 減 , 98 63 3563 35 2835 28 728 7 2121 7 1

10、414 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次

11、 加 法 運 算 . 思 考 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的 值 ， 這 個 多 項 式 應(yīng) 寫 成 哪 種 形 式

12、 ？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

13、+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è) 計

14、 思 考 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:該 算 法 的 程 序框 圖 如 何 表 示 ？ 開

15、始輸 入 n， an， x的 值v=an v=vx+ai輸 入 a ii0？i=n-1 i=i-1結(jié) 束 是 輸 出 v 否 思 考 3:該 程 序 框 圖 對 應(yīng) 的 程 序 如 何 表 述 ？開 始輸 入 n， an， x的 值v=an v=vx+a i輸 入 aii0？i=n-1 i=i-1結(jié) 束 是輸 出 v 否 INPUT “ n=” ； nINPUT “ an =” ； aINPUT “ x=” ； x v=a i=n-1WHILE i=0 PRINT “ i=” ;i INPUT “ ai=” ； a v=v*x+a i=i-1WENDPRINT vEND 例 2 已 知 一 個

16、 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；v 3=113.5 5-2.6=564.9；v4=564.9 5+1.7=2 826.2；v5=2 826.2

17、5-0.8=14 130.2.所 以 f(5)=14 130.2. 閱 讀 下 列 程 序 ， 說 明 它 解 決 的 實 際 問 題 是 什 么 ？解 ： 求 多 項 式 f(x)=1+2x+3x 2+4x3+5x4在 x=a時 的 值 . INPUT “ x=” ； an=0y=0WHILE n5 y=y+(n+1)*a n n=n+1WENDPRINT yEND 1. 用 輾 轉(zhuǎn) 相 除 法 求 225和 135的 最 大 公 約 數(shù) .顯 然 45是 90和 45的 最 大 公 約 數(shù) ， 也 就 是 225和 135的 最 大公 約 數(shù) . 225=135 1+90135=90 1+

18、4590=45 2 2.利 用 輾 轉(zhuǎn) 相 除 法 求 兩 數(shù) 4 081與 20 723的 最 大 公 約 數(shù) .20 723 =4 081 5+318;4 081 =318 12+265;318=265 1+53;265=53 5+0. 所 以 4 081與 20 723的 最 大 公 約 數(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) 向 外 逐 層 計 算 一 次 多 項

19、 式 當 x=5時 的 值 ,即v0=2 v1=v0 x-5=2 5-5=5v2=v1x-4=5 5-4=21v 3=v2x+3=21 5+3=108v4=v3x-6=108 5-6=534v5=v4x+7=534 5+7=2 677所 以 ,當 x=5時 ,多 項 式 的 值 是 2 677. 1.比 較 輾 轉(zhuǎn) 相 除 法 與 更 相 減 損 術(shù) 的 區(qū) 別（ 1） 都 是 求 最 大 公 約 數(shù) 的 方 法 ， 計 算 上 輾 轉(zhuǎn) 相 除 法 以 除法 為 主 ， 更 相 減 損 術(shù) 以 減 法 為 主 ， 計 算 次 數(shù) 上 輾 轉(zhuǎn) 相 除法 計 算 次 數(shù) 相 對 較 少 ， 特 別

20、 當 兩 個 數(shù) 字 大 小 區(qū) 別 較 大 時 ，計 算 次 數(shù) 的 區(qū) 別 較 明 顯 .（ 2） 從 結(jié) 果 體 現(xiàn) 形 式 來 看 ， 輾 轉(zhuǎn) 相 除 法 體 現(xiàn) 結(jié) 果 是 以 相除 余 數(shù) 為 0而 得 到 ， 而 更 相 減 損 術(shù) 則 以 減 數(shù) 與 差 相 等 而 得到 . 2.評 價 一 個 算 法 好 壞 的 一 個 重 要 標 志 是 運 算 的 次 數(shù) ， 如果 一 個 算 法 從 理 論 上 需 要 超 出 計 算 機 允 許 范 圍 內(nèi) 的 運 算次 數(shù) ， 那 么 這 樣 的 算 法 就 只 能 是 一 個 理 論 算 法 .在 多 項 式求 值 的 各 種 算 法 中 ， 秦 九 韶 算 法 是 一 個 優(yōu) 秀 算 法 . 昨 天 的 努 力 就 是 今 天 的 收 獲 ， 今 天 的 努 力就 是 未 來 的 希 望 .歲 月 不 饒 人 ， 不 妨 現(xiàn) 在就 行 動 ！