《算法案例 課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《算法案例 課件.ppt（21頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、1.3 算 法 案 例 第 一 課 時(shí) 問 題 提 出 t57301p 2 1.研 究 一 個(gè) 實(shí) 際 問 題 的 算 法 ， 主 要 從算 法 步 驟 、 程 序 框 圖 和 編 寫 程 序 三 方 面展 開 .在 程 序 框 圖 中 算 法 的 基 本 邏 輯 結(jié) 構(gòu)有 哪 幾 種 ？ 在 程 序 設(shè) 計(jì) 中 基 本 的 算 法 語句 有 哪 幾 種 ？ 2.“ 求 兩 個(gè) 正 整 數(shù) 的 最 大 公 約 數(shù) ”是 數(shù) 學(xué) 中 的 一 個(gè) 基 礎(chǔ) 性 問 題 ， 它 有 各 種解 決 辦 法 ， 我 們 以 此 為 案 例 ， 對(duì) 該 問 題的 算 法 作 一 些 探 究 . 知 識(shí) 探

2、究 （ 一 ） :輾 轉(zhuǎn) 相 除 法思 考 1:18與 30的 最 大 公 約 數(shù) 是 多 少 ？ 你是 怎 樣 得 到 的 ？ 先 用 兩 個(gè) 數(shù) 公 有 的 質(zhì) 因 數(shù) 連 續(xù) 去 除 ，一 直 除 到 所 得 的 商 是 互 質(zhì) 數(shù) 為 止 ， 然后 把 所 有 的 除 數(shù) 連 乘 起 來 即 為 最 大 公約 數(shù) . 思 考 2:對(duì) 于 8251與 6105這 兩 個(gè) 數(shù) ， 由 于其 公 有 的 質(zhì) 因 數(shù) 較 大 ， 利 用 上 述 方 法 求最 大 公 約 數(shù) 就 比 較 困 難 .注 意 到8251=6105 1+2146， 那 么 8251與 6105這 兩 個(gè) 數(shù) 的 公

3、約 數(shù) 和 6105與 2146的 公 約數(shù) 有 什 么 關(guān) 系 ？ 思 考 3:又 6105=2146 2+1813， 同 理 ，6105與 2146的 公 約 數(shù) 和 2146與 1813的 公約 數(shù) 相 等 .重 復(fù) 上 述 操 作 ， 你 能 得 到 8251與 6105這 兩 個(gè) 數(shù) 的 最 大 公 約 數(shù) 嗎 ？2146=1813 1+333，148=37 4+0.333=148 2+37，1813=333 5+148，8251=6105 1+2146，6105=2146 2+1813， 思 考 4:上 述 求 兩 個(gè) 正 整 數(shù) 的 最 大 公 約 數(shù)的 方 法 稱 為 輾 轉(zhuǎn)

4、相 除 法 或 歐 幾 里 得 算 法 .一 般 地 ， 用 輾 轉(zhuǎn) 相 除 法 求 兩 個(gè) 正 整 數(shù) m，n的 最 大 公 約 數(shù) ， 可 以 用 什 么 邏 輯 結(jié) 構(gòu) 來構(gòu) 造 算 法 ？ 其 算 法 步 驟 如 何 設(shè) 計(jì) ？ 第 一 步 ， 給 定 兩 個(gè) 正 整 數(shù) m， n(mn).第 二 步 ， 計(jì) 算 m除 以 n所 得 的 余 數(shù) r. 第 三 步 ， m=n， n=r.第 四 步 ， 若 r=0， 則 m， n的 最 大 公 約 數(shù) 等 于 m； 否 則 ， 返 回 第 二 步 . 思 考 5:該 算 法 的 程 序 框 圖 如 何 表 示 ？開 始輸 入 m， n求

5、m除 以 n的 余 數(shù) rm=nn=rr=0？是輸 出 m 結(jié) 束 否 思 考 6:該 程 序 框 圖 對(duì) 應(yīng) 的 程 序 如 何 表 述 ？INPUT m， nDOr=m MODnm=nn=rLOOP UNTIL r=0PRINT mEND開 始輸 入 m， n求 m除 以 n的 余 數(shù) rm=nn=rr=0？是輸 出 m 結(jié) 束 否 思 考 7:如 果 用 當(dāng) 型 循 環(huán) 結(jié) 構(gòu) 構(gòu) 造 算 法 ，則 用 輾 轉(zhuǎn) 相 除 法 求 兩 個(gè) 正 整 數(shù) m， n的 最大 公 約 數(shù) 的 程 序 框 圖 和 程 序 分 別 如 何 表示 ？ 開 始輸 入 m， n 求 m除 以 n的 余 數(shù) r

6、m=nn0？否輸 出 m 結(jié) 束 是 n=r INPUT m， nWHILE n0r=m MODnm=nn=rWENDPRINT mEND 知 識(shí) 探 究 （ 二 ） :更 相 減 損 術(shù) 思 考 1:設(shè) 兩 個(gè) 正 整 數(shù) mn， 若 m-n=k， 則m與 n的 最 大 公 約 數(shù) 和 n與 k的 最 大 公 約 數(shù)相 等 .反 復(fù) 利 用 這 個(gè) 原 理 ， 可 求 得 98與 63的 最 大 公 約 數(shù) 為 多 少 ？98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28， 思 考 2:上 述 求 兩 個(gè) 正 整 數(shù) 的 最 大 公 約 數(shù)的 方

7、 法 稱 為 更 相 減 損 術(shù) .一 般 地 ， 用 更 相減 損 術(shù) 求 兩 個(gè) 正 整 數(shù) m， n的 最 大 公 約 數(shù) ，可 以 用 什 么 邏 輯 結(jié) 構(gòu) 來 構(gòu) 造 算 法 ？ 其 算法 步 驟 如 何 設(shè) 計(jì) ？第 一 步 ， 給 定 兩 個(gè) 正 整 數(shù) m， n(mn). 第 二 步 ， 計(jì) 算 m-n所 得 的 差 k. 第 三 步 ， 比 較 n與 k的 大 小 ， 其 中 大 者 用 m表 示 ， 小 者 用 n表 示 . 第 四 步 ， 若 m=n， 則 m， n的 最 大 公 約 數(shù) 等 于 m； 否 則 ， 返 回 第 二 步 . 思 考 3:該 算 法 的 程

8、序 框 圖 如 何 表 示 ？開 始輸 入 m， nnk？m=n是 輸 出 m結(jié) 束mn？k=m-n是 否 n=km=k否 思 考 4:該 程 序 框 圖 對(duì) 應(yīng) 的 程 序 如 何 表 述 ？INPUT m， nWHILE mnk=m-nIF nk THENm=nn=kELSEm=kEND IFWENDPRINT mEND開 始輸 入 m， nnk？m=n是 輸 出 m結(jié) 束mn？k=m-n是 否 n=km=k否 “ 更 相 減 損 術(shù) ” 在 中 國 古 代 數(shù) 學(xué) 專 著 九 章 算 術(shù) 中 記 述 為 ： 可 半 者 半 之 ， 不 可 半 者 ， 副 置 分 母 、 子之 數(shù) ， 以

9、 少 減 多 ， 更 相 減 損 ， 求 其 等 也 ，以 等 數(shù) 約 之 . 理 論 遷 移 例 1 分 別 用 輾 轉(zhuǎn) 相 除 法 和 更 相 減 損術(shù) 求 168與 93的 最 大 公 約 數(shù) . 輾 轉(zhuǎn) 相 除 法 ： 168=93 1+75， 93=75 1+18， 75=18 4+3， 18=3 6. 更 相 減 損 術(shù) :168-93=75， 93-75=18， 75-18=57， 57-18=39， 39-18=21， 21-18=3， 18-3=15， 15-3=12， 12-3=9， 9-3=6， 6-3=3. 例 2 求 325， 130， 270三 個(gè) 數(shù) 的 最 大公

10、 約 數(shù) . 因 為 325=130 2+65， 130=65 2，所 以 325與 130的 最 大 公 約 數(shù) 是 65. 因 為 270=65 4+10， 65=10 6+5，10=5 2， 所 以 65與 270最 大 公 約 數(shù) 是 5. 故 325， 130， 270三 個(gè) 數(shù) 的 最 大 公 約數(shù) 是 5. 1.輾 轉(zhuǎn) 相 除 法 ， 就 是 對(duì) 于 給 定 的 兩 個(gè) 正 整數(shù) ， 用 較 大 的 數(shù) 除 以 較 小 的 數(shù) ， 若 余 數(shù) 不 為零 ， 則 將 余 數(shù) 和 較 小 的 數(shù) 構(gòu) 成 新 的 一 對(duì) 數(shù) ，繼 續(xù) 上 面 的 除 法 ， 直 到 大 數(shù) 被 小 數(shù) 除 盡 為 止 ，這 時(shí) 的 較 小 的 數(shù) 即 為 原 來 兩 個(gè) 數(shù) 的 最 大 公 約數(shù) . 小 結(jié) 作 業(yè) 2. 更 相 減 損 術(shù) ， 就 是 對(duì) 于 給 定 的 兩 個(gè) 正整 數(shù) ， 用 較 大 的 數(shù) 減 去 較 小 的 數(shù) ， 然 后 將 差和 較 小 的 數(shù) 構(gòu) 成 新 的 一 對(duì) 數(shù) ， 繼 續(xù) 上 面 的 減法 ， 直 到 差 和 較 小 的 數(shù) 相 等 ， 此 時(shí) 相 等 的 兩數(shù) 即 為 原 來 兩 個(gè) 數(shù) 的 最 大 公 約 數(shù) . 作 業(yè) ：P45練 習(xí) ： 1.P48習(xí) 題 1.3A組 ： 1.