《1.3 算法案例》由會員分享，可在線閱讀，更多相關《1.3 算法案例（35頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、1.3 算 法 案 例 3 59 15問 題 1： 在 小 學 ， 我 們 已 經(jīng) 學 過 求 最 大 公 約 數(shù)的 知 識 ， 你 能 求 出 18與 30的 最 大 公 約 數(shù) 嗎 ？18 3023 18和 30的 最 大 公 約 數(shù) 是 2 3=6.先 用 兩 個 數(shù) 公 有 的 質 因 數(shù) 連 續(xù) 去 除 ,一 直 除 到所 得 的 商 是 互 質 數(shù) 為 止 ,然 后 把 所 有 的 除 數(shù) 連乘 起 來 .案 例 1 輾 轉 相 除 法 與 更 相 減 損 術 問 題 2:我 們 都 是 利 用 找 公 約 數(shù) 的 方 法 來 求最 大 公 約 數(shù) ， 如 果 兩 個 數(shù) 比 較

2、大 而 且 根 據(jù) 我們 的 觀 察 又 不 能 得 到 一 些 公 約 數(shù) ， 我 們 又 應該 怎 樣 求 它 們 的 最 大 公 約 數(shù) ？ 比 如 求 8251與6105的 最 大 公 約 數(shù) ? 研 探 新 知 1.輾 轉 相 除 法 :例 1 求 兩 個 正 數(shù) 8251和 6105的 最 大 公 約 數(shù) 。分 析 ： 8251與 6105兩 數(shù) 都 比 較 大 ， 而 且 沒有 明 顯 的 公 約 數(shù) ， 如 能 把 它 們 都 變 小 一 點 ， 根據(jù) 已 有 的 知 識 即 可 求 出 最 大 公 約 數(shù) .解 ： 8251 6105 1 2146顯 然 8251與 6105

3、的 最 大 公 約 數(shù) 也 必 是 2146的 約 數(shù) ， 同 樣 6105與 2146的 公 約 數(shù) 也 必 是 8251的 約 數(shù) ， 所 以 8251與 6105的 最 大 公 約 數(shù) 也 是6105與 2146的 最 大 公 約 數(shù) 。 1.輾 轉 相 除 法 :例 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ù) 。以 上 我

4、 們 求 最 大 公 約 數(shù) 的 方 法 就 是 輾 轉 相除 法 。 也 叫 歐 幾 里 德 算 法 ， 它 是 由 歐 幾 里 德 在公 元 前 300年 左 右 首 先 提 出 的 。 第 一 步 ,給 定 兩 個 正 數(shù) m,n 第 二 步 ,計 算 m除 以 n所 得 到 余 數(shù) r 第 三 步 ,m=n,n=r 第 四 步 ,若 r=0,則 m,n的 最 大 公 約 數(shù) 等 于 m;否 則 返 回 第 二 步輾 轉 相 除 法 求 最 大 公 約 數(shù) 算 法 ：思 考 ： 需 不 需 要 比 較 m， n的 大 小不 需 要 否開 始 輸 入 兩 個 正 數(shù) m,nr=m MOD

5、nr=0?輸 出 m結 束m=nn=r 是程 序 框 圖 練 習 1： 利 用 輾 轉 相 除 法 求 兩 數(shù) 4081與 20723的 最 大 公 約 數(shù) . (53)20723=4081 5+318;4081=318 12+265;318=265 1+53;265=53 5+0. 2.更 相 減 損 術 :我 國 早 期 也 有 解 決 求 最 大 公 約 數(shù) 問 題 的 算法 ， 就 是 更 相 減 損 術 .更 相 減 損 術 求 最 大 公 約 數(shù) 的 步 驟 如 下 ： 可半 者 半 之 ， 不 可 半 者 ， 副 置 分 母 、 子 之 數(shù) ， 以少 減 多 ， 更 相 減 損

6、， 求 其 等 也 ， 以 等 數(shù) 約 之 .翻 譯 出 來 為 ： 第 一 步 ： 任 意 給 出 兩 個 正 數(shù) ；判 斷 它 們 是 否 都 是 偶 數(shù) .若 是 ， 用 2約 簡 ； 若 不 是 ，執(zhí) 行 第 二 步 .第 二 步 ： 以 較 大 的 數(shù) 減 去 較 小 的 數(shù) ， 接 著 把較 小 的 數(shù) 與 所 得 的 差 比 較 ， 并 以 大 數(shù) 減 小 數(shù) 。 繼續(xù) 這 個 操 作 ， 直 到 所 得 的 數(shù) 相 等 為 止 ， 則 這 個 數(shù)（ 或 這 個 數(shù) 與 約 減 數(shù) 的 乘 積 ） 就 是 所 求 的 最 大 公約 數(shù) . 例 2 用 更 相 減 損 術 求 98

7、與 63的 最 大 公 約 數(shù) .解 ： 由 于 63不 是 偶 數(shù) ， 把 98和 63以 大 數(shù)減 小 數(shù) ， 并 輾 轉 相 減 ， 即 ： 98 63 35; 63 35 28; 35 28 7; 28 7 21; 21 7 14; 14 7 7.所 以 ， 98與 63的 最 大 公 約 數(shù) 是 7。練 習 2： 用 更 相 減 損 術 求 兩 個 正 數(shù) 84與 72的 最 大公 約 數(shù) 。 (12) 2021/6/16 11 INPUT m, nIF mn THEN a=m m=n n=aEND IFK=0WHILE m MOD 2=0 AND n MOD 2=0 m=m/2 n

8、=n/2 k=k+1WENDd=m-nWHILE dn IF dn THEN m=d ELSE m=n n=d END IF d=m-nWENDd=2 k*dPRINT dEND思 考 ： 你 能 根 據(jù) 更 相減 損 術 設 計 程 序 ， 求兩 個 正 整 數(shù) 的 最 大 公約 數(shù) 嗎 ？ 輾 轉 相 除 法 與 更 相 減 損 術 的 比 較 : （ 1） 都 是 求 最 大 公 約 數(shù) 的 方 法 ， 計 算 上輾 轉 相 除 法 以 除 法 為 主 ， 更 相 減 損 術 以 減 法 為主 ;計 算 次 數(shù) 上 輾 轉 相 除 法 計 算 次 數(shù) 相 對 較 少 ，特 別 當 兩 個

9、 數(shù) 字 大 小 區(qū) 別 較 大 時 計 算 次 數(shù) 的 區(qū)別 較 明 顯 。（ 2） 從 結 果 體 現(xiàn) 形 式 來 看 ， 輾 轉 相 除 法體 現(xiàn) 結 果 是 以 相 除 余 數(shù) 為 0則 得 到 ， 而 更 相 減 損術 則 以 減 數(shù) 與 差 相 等 而 得 到 . 問 題 1設 計 求 多 項 式 f(x)=2x5-5x4-4x3+3x2-6x+7當 x=5時 的 值 的 算 法 ,并 寫 出 程 序 .x=5f=2 x5-5 x4-4 x3+3 x2-6 x+7PRINT fEND程 序點 評 :上 述 算 法 一 共 做 了 15次 乘 法 運 算 ,5次 加 法運 算 .優(yōu)

10、點 是 簡 單 ,易 懂 ;缺 點 是 不 通 用 ,不 能 解決 任 意 多 項 式 求 值 問 題 ,而 且 計 算 效 率 不 高 .n次 多 項 式 至 多 n(n+1)/2次 乘 法 運 算 和 n次 加 法 運 算案 例 2 秦 九 韶 算 法 這 析 計 算 上 述 多 項 式 的 值 ,一 共 需 要 9次 乘法 運 算 ,5次 加 法 運 算 .問 題 2有 沒 有 更 高 效 的 算 法 ?分 析 :計 算 x的 冪 時 ,可 以 利 用 前 面 的 計 算 結果 ,以 減 少 計 算 量 ,即 先 計 算 x2,然 后 依 次 計 算2 2 2,( ) ,( ) )x x

11、 x x x x x x x 的 值 .第 二 種 做 法 與 第 一 種 做 法 相 比 ,乘 法 的 運算 次 數(shù) 減 少 了 ,因 而 能 提 高 運 算 效 率 .而 且 對 于計 算 機 來 說 ,做 一 次 乘 法 所 需 的 運 算 時 間 比 做 一次 加 法 要 長 得 多 ,因 此 第 二 種 做 法 能 更 快 地 得 到結 果 . 問 題 3能 否 探 索 更 好 的 算 法 ,來 解 決 任 意 多項 式 的 求 值 問 題 ?f(x)=2x5-5x4-4x3+3x2-6x+7=(2x4-5x3-4x2+3x-6)x+7=(2x3-5x2-4x+3)x-6)x+7=(

12、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=534v 5=v4x+7=534 5+7=2677所 以 ,當 x=5時 ,多 項 式 的 值 是 2677.這 種 求 多 項 式 值 的 方 法 就 叫 秦 九 韶 算 法 .變 為 求 幾 個 一 次 式 的 值 幾 個 乘 法幾 個 加 法 ？秦 九 韶 數(shù) 書 九 章 . 2 -5 0 -4 3 -6 0 x=5 105 2525 125121 6056

13、08 30403034所 以 ,當 x=5時 ,多 項 式 的 值 是 15170.練 習 :用 秦 九 韶 算 法 求 多 項 式 f(x)=2x6-5x5-4x3+3x2-6x當 x=5時 的 值 .解 :原 多 項 式 先 化 為 : f(x)=2x6-5x5 +0 x4-4x3+3x2-6x+0列 表 2 1517015170 注 意 :n次 多 項 式 有 n+1項 ,因 此 缺 少 哪 一 項應 將 其 系 數(shù) 補 0. f(x)=anxn+an-1xn-1+an-2xn-2+a1x+a0.我 們 可 以 改 寫 成 如 下 形 式 :f(x)=(anx+an-1)x+an-2)x

14、+a1)x+a0.求 多 項 式 的 值 時 ,首 先 計 算 最 內 層 括 號 內 一次 多 項 式 的 值 ,即 v1=anx+an-1,然 后 由 內 向 外 逐 層 計 算 一 次 多 項 式 的 值 ,即一 般 地 ,對 于 一 個 n次 多 項 式v2=v1x+an-2, v3=v2x+an-3, , vn=vn-1x+a0.這 樣 ,求 n次 多 項 式 f(x)的 值 就 轉 化 為 求 n個一 次 多 項 式 的 值 .這 種 算 法 稱 為 秦 九 韶 算 法 . 點 評 :秦 九 韶 算 法 是 求 一 元 多 項 式 的 值 的一 種 方 法 .它 的 特 點 是 :

15、把 求 一 個 n次 多 項 式 的 值 轉 化為 求 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,得v0=an,vK=vK-1x+an-k(k

16、=1,2,n）這 是 一 個 在 秦 九 韶 算 法 中 反 復 執(zhí) 行 的 步驟 ,因 此 可 用 循 環(huán) 結 構 來 實 現(xiàn) . 第 一 步 ,輸 入 多 項 式 次 數(shù) n、 最 高 次 項 的 系 數(shù) an和x的 值 第 二 步 ,將 v的 值 初 始 化 為 an， 將 i的 值 初 始 化 為n-1 第 三 步 ,輸 入 i次 項 的 系 數(shù) ai 第 四 步 ,v=vx+ai,i=i-1 第 五 步 ,若 i=0,則 返 回 第 三 步 ， 否 則 輸 出 v算 法 分 析 ： 否程 序 框 圖 開 始輸 入 n,an,x的 值 輸 入 aii=0?i=n-1v=an v=vx+

17、aii=i-1輸 出 v結 束 是 問 題 1我 們 常 見 的 數(shù) 字 都 是 十 進 制 的 ,但 是 并 不 是 生 活 中 的 每 一 種 數(shù) 字 都 是 十 進 制 的 .比 如 時 間 和 角 度 的 單 位 用 六 十 進 位 制 ,電 子 計算 機 用 的 是 二 進 制 .那 么 什 么 是 進 位 制 ?不 同 的進 位 制 之 間 又 有 什 么 聯(lián) 系 呢 ?進 位 制 是 人 們 為 了 計 數(shù) 和 運 算 的 方 便 而約 定 的 一 種 記 數(shù) 系 統(tǒng) ， 約 定 滿 二 進 一 ,就 是 二進 制 ;滿 十 進 一 ,就 是 十 進 制 ;滿 十 六 進 一 ,

18、就是 十 六 進 制 ;等 等 . “ 滿 幾 進 一 ” ,就 是 幾 進 制 ,幾 進 制 的 基 數(shù) 就 是幾 .可 使 用 數(shù) 字 符 號 的 個 數(shù) 稱 為 基 數(shù) .基 數(shù) 都 是大 于 1的 整 數(shù) . 案 例 3 進 位 制 如 二 進 制 可 使 用 的 數(shù) 字 有 0和 1,基 數(shù) 是 2; 十 進 制 可 使 用 的 數(shù) 字 有 0,1,2,8,9等 十 個數(shù) 字 ,基 數(shù) 是 10; 十 六 進 制 可 使 用 的 數(shù) 字 或 符 號 有 09等 10個 數(shù) 字 以 及 AF等 6個 字 母 (規(guī) 定 字 母 AF對 應1015),十 六 進 制 的 基 數(shù) 是 16.

19、注 意 :為 了 區(qū) 分 不 同 的 進 位 制 ,常 在 數(shù) 字的 右 下 腳 標 明 基 數(shù) ,. 如 111001(2)表 示 二 進 制 數(shù) ,34(5)表 示 5進 制 數(shù) .十 進 制 數(shù) 一 般 不 標 注 基 數(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

20、+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ù) 可 以 表 示 為 一 串 數(shù) 字 連 寫 在 一起 的 形 式anan-1a1a0(k) (0ank,0an-1,a1,a0k)意 思 是 :(1)第 一 個 數(shù) 字 an不 能 等 于 0;(2)每 一 個 數(shù) 字 an,an-1,a1,a0都 須 小 于 k.k進 制 的 數(shù) 也 可 以 表 示 成 不 同 位 上 數(shù) 字

21、與基 數(shù) k的 冪 的 乘 積 之 和 的 形 式 ,即a nan-1a1a0(k)=an kn+an-1 kn-1 +a1 k1+a0 k0 . 注 意 這 是 一個 n+1位 數(shù) . 問 題 3二 進 制 只 用 0和 1兩 個 數(shù) 字 ,這 正好 與 電 路 的 通 和 斷 兩 種 狀 態(tài) 相 對 應 ,因 此 計 算機 內 部 都 使 用 二 進 制 .計 算 機 在 進 行 數(shù) 的 運 算時 ,先 把 接 受 到 的 數(shù) 轉 化 成 二 進 制 數(shù) 進 行 運 算 ,再 把 運 算 結 果 轉 化 為 十 進 制 數(shù) 輸 出 .那 么 二 進 制 數(shù) 與 十 進 制 數(shù) 之 間 是

22、如 何 轉化 的 呢 ? 例 3:把 二 進 制 數(shù) 110011(2)化 為 十 進 制 數(shù) .分 析 :先 把 二 進 制 數(shù) 寫 成 不 同 位 上 數(shù) 字 與 2的 冪 的 乘 積 之 和 的 形 式 ,再 按 照 十 進 制 數(shù) 的 運 算規(guī) 則 計 算 出 結 果 .解 :110011(2) =1 25+1 24+0 23+0 22+1 21+1 20 =1 32+1 16+1 2+1=51. k進 制 數(shù) 轉 化 為 十 進 制 數(shù) 的 方 法先 把 k進 制 的 數(shù) 表 示 成 不 同 位 上 數(shù) 字 與 基數(shù) k的 冪 的 乘 積 之 和 的 形 式 ,即anan-1a1a0

23、(k)=an kn+an-1 kn-1+a1 k1+a0 k0 .再 按 照 十 進 制 數(shù) 的 運 算 規(guī) 則 計 算 出 結 果 . 例 4:把 89化 為 二 進 制 的 數(shù) .分 析 :把 89化 為 二 進 制 的 數(shù) ,需 想 辦 法 將 89先 寫 成 如 下 形 式89=an 2n+an-1 2n-1+a1 21+a0 20 . 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

24、) 2+1) 2+0) 2+0) 2+1 =(1 2)+0) 2+1) 2+1) 2+0) 2+0) 2+1=1 2 6+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, 44 1例 4:把 89化 為 二 進 制 的 數(shù) .我 們 可 以 用 下 面 的 除 法 算 式 表 示 除 2取 余 法 :2 89 余 數(shù)2 22 02 11 02 5 12 2 12 1 02 0 1 把 算 式 中 各 步

25、 所 得 的 余 數(shù)從 下 到 上 排 列 ,得 到89=1011001(2).這 種 方 法 也 可 以 推 廣 為 把十 進 制 數(shù) 化 為 k進 制 數(shù) 的算 法 ,稱 為 除 k取 余 法 . 例 5:把 89化 為 五 進 制 的 數(shù) .解 :以 5作 為 除 數(shù) ,相 應 的 除 法 算 式 為 :17 45 89 余 數(shù)5 3 25 0 3 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). 10221(3)=106= 1101010(2). 小 結 進 位 制 的 概 念 及 表 示 方 法 ; 各 種 進 位 制 之 間 的 相 互 轉 化 .anan-1a1a0(k)=an kn+an-1 kn-1+a1 k1+a0 k0 . 若 有 不 當 之 處 ， 請 指 正 ， 謝 謝 ！