算法案例 課件.ppt

上傳人:小** 文檔編號:22193404 上傳時間:2021-05-22 格式:PPT 頁數(shù):21 大?。?86.50KB
收藏 版權(quán)申訴 舉報 下載
算法案例 課件.ppt_第1頁
第1頁 / 共21頁
算法案例 課件.ppt_第2頁
第2頁 / 共21頁
算法案例 課件.ppt_第3頁
第3頁 / 共21頁

下載文檔到電腦,查找使用更方便

5 積分

下載資源

還剩頁未讀,繼續(xù)閱讀

資源描述:

《算法案例 課件.ppt》由會員分享,可在線閱讀,更多相關(guān)《算法案例 課件.ppt(21頁珍藏版)》請在裝配圖網(wǎng)上搜索。

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

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

3、約 數(shù) 和 6105與 2146的 公 約數(shù) 有 什 么 關(guān) 系 ? 思 考 3:又 6105=2146 2+1813, 同 理 ,6105與 2146的 公 約 數(shù) 和 2146與 1813的 公約 數(shù) 相 等 .重 復(fù) 上 述 操 作 , 你 能 得 到 8251與 6105這 兩 個 數(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:上 述 求 兩 個 正 整 數(shù) 的 最 大 公 約 數(shù)的 方 法 稱 為 輾 轉(zhuǎn)

4、相 除 法 或 歐 幾 里 得 算 法 .一 般 地 , 用 輾 轉(zhuǎn) 相 除 法 求 兩 個 正 整 數(shù) m,n的 最 大 公 約 數(shù) , 可 以 用 什 么 邏 輯 結(jié) 構(gòu) 來構(gòu) 造 算 法 ? 其 算 法 步 驟 如 何 設(shè) 計 ? 第 一 步 , 給 定 兩 個 正 整 數(shù) m, n(mn).第 二 步 , 計 算 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:該 程 序 框 圖 對 應(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:如 果 用 當 型 循 環(huán) 結(jié) 構(gòu) 構(gòu) 造 算 法 ,則 用 輾 轉(zhuǎn) 相 除 法 求 兩 個 正 整 數(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ù) 思 考 1:設(shè) 兩 個 正 整 數(shù) mn, 若 m-n=k, 則m與 n的 最 大 公 約 數(shù) 和 n與 k的 最 大 公 約 數(shù)相 等 .反 復(fù) 利 用 這 個 原 理 , 可 求 得 98與 63的 最 大 公 約 數(shù) 為 多 少 ?98-63=35,14-7=7.21-7=14,28-7=21,35-28=7,63-35=28, 思 考 2:上 述 求 兩 個 正 整 數(shù) 的 最 大 公 約 數(shù)的 方

7、 法 稱 為 更 相 減 損 術(shù) .一 般 地 , 用 更 相減 損 術(shù) 求 兩 個 正 整 數(shù) m, n的 最 大 公 約 數(shù) ,可 以 用 什 么 邏 輯 結(jié) 構(gòu) 來 構(gòu) 造 算 法 ? 其 算法 步 驟 如 何 設(shè) 計 ?第 一 步 , 給 定 兩 個 正 整 數(shù) m, n(mn). 第 二 步 , 計 算 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:該 程 序 框 圖 對 應(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三 個 數(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三 個 數(shù) 的 最 大 公 約數(shù) 是 5. 1.輾 轉(zhuǎn) 相 除 法 , 就 是 對 于 給 定 的 兩 個 正 整數(shù) , 用 較 大 的 數(shù) 除 以 較 小 的 數(shù) , 若 余 數(shù) 不 為零 , 則 將 余 數(shù) 和 較 小 的 數(shù) 構(gòu) 成 新 的 一 對 數(shù) ,繼 續(xù) 上 面 的 除 法 , 直 到 大 數(shù) 被 小 數(shù) 除 盡 為 止 ,這 時 的 較 小 的 數(shù) 即 為 原 來 兩 個 數(shù) 的 最 大 公 約數(shù) . 小 結(jié) 作 業(yè) 2. 更 相 減 損 術(shù) , 就 是 對 于 給 定 的 兩 個 正整 數(shù) , 用 較 大 的 數(shù) 減 去 較 小 的 數(shù) , 然 后 將 差和 較 小 的 數(shù) 構(gòu) 成 新 的 一 對 數(shù) , 繼 續(xù) 上 面 的 減法 , 直 到 差 和 較 小 的 數(shù) 相 等 , 此 時 相 等 的 兩數(shù) 即 為 原 來 兩 個 數(shù) 的 最 大 公 約 數(shù) . 作 業(yè) :P45練 習(xí) : 1.P48習(xí) 題 1.3A組 : 1.

展開閱讀全文
溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號:ICP2024067431-1 川公網(wǎng)安備51140202000466號


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請立即通知裝配圖網(wǎng),我們立即給予刪除!