版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、1. 3算法案例第一課時問題提出1研究一個實際問題的算法,主要從算法步驟、程序框圖和編寫程序三方面展開.在程序框圖中算法的基本邏輯結(jié)構(gòu)有哪幾種?在程序設(shè)計中基本的算法語句有哪幾種?2“求兩個正整數(shù)的最大公約數(shù)” 是數(shù)學(xué)中的一個基礎(chǔ)性問題,它有各種 解決辦法,我們以此為案例,對該問題 的算法作一些探究.知識探究(一):輾轉(zhuǎn)相除法思考1:18與30的最大公約數(shù)是多少?你 是怎樣得到的?先用兩個數(shù)公有的質(zhì)因數(shù)連續(xù)去除, 一直除到所得的商是互質(zhì)數(shù)為止,然 后把所有的除數(shù)連乘起來即為最大公 約數(shù).思考2:對于8251與6105這兩個數(shù),由于 其公有的質(zhì)因數(shù)較大,利用上述方法求 最大公約數(shù)就比較困難注意到
2、8251=6105X1+2146,那么8251與6105這 兩個數(shù)的公約數(shù)和6105與2146的公約數(shù) 有什么關(guān)系?思考3:又6105=2146X2+1813,同理,6105與2146的公約數(shù)和2146與1813的公 約數(shù)相等重復(fù)上述操作,你能得到8251與6105這兩個數(shù)的最大公約數(shù)嗎?8251=6105X1+2146,6105=2146X2+1813, 2146=1813X1+333,1813=333X5+148, 333=148X2+ ,148=X4+0思考4:上述求兩個正整數(shù)的最大公約數(shù) 的方法稱為輾轉(zhuǎn)相除法或歐幾里得算法. 一般地,用輾轉(zhuǎn)相除法求兩個正整數(shù)m, n的最大公約數(shù),可以用
3、什么邏輯結(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:該算法的程序框圖如何表示?/ 11,求 m 除以 n 的余數(shù) r思考6:該程序框圖對應(yīng)的程序如何表述?INPUT m, nDOr=m MOD nm=nn=rLOOP UNTIL r=0PRINT mm=n否出 m/MSEND思考7:如果用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法, 則用輾轉(zhuǎn)相除法求兩個正整數(shù)m, n的最 大公約數(shù)的程序框圖和程序分別如何表 示?/侖出m /INPUTWHILEm=
4、m9nn0MODnrxi知識探究(二):更相減損術(shù)思考1:設(shè)兩個正整數(shù)mn,若m-n二k,貝Ijm與n的最大公約數(shù)和n與k的最大公約數(shù)相 等反復(fù)利用這個原理,可求得98與63的 最大公約數(shù)為多少?98-63=35,63-35=28,35-28=7,28-7=21,21-7=14,14-7=7.7-7=0.思考2:上述求兩個正整數(shù)的最大公約數(shù) 的方法稱為更相減損術(shù).一般地,用更相 減損術(shù)求兩個正整數(shù)m, n的最大公約數(shù), 可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法?其算 法步驟如何設(shè)計?第一步,給定兩個正整數(shù)叫n (mn).第二步,計算m-n所得的差k.第三步,比較11與k的大小,其中大者用示,小者用n表示.
5、第四步,若m=n,則m, n的最大公約數(shù)等于m;否則,返回第二步.思考4:該程序框圖對應(yīng)的程序如何表述?INPUT m, n WHILEmon k=m-nIF nk THEN m=nn=kELSE ,m=kEND IFWEND思考3:該算法的程序框圖如何表示?PRINT mEND“更相減損術(shù)”在中國古代數(shù)學(xué)專著九章算術(shù)中記述為:可半者半之,不可半者,副置分母、子 之?dāng)?shù),以少減多,更相減損,求其等也, 以等數(shù)約之.理論遷移例1分別用輾轉(zhuǎn)相除法和更相減損 術(shù)求168與93的最大公約數(shù).輾轉(zhuǎn)相除法:168=93X1+75,93=75X1+18,75=18X4+3,18=3X6+0.更相減損術(shù):168
6、-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ù)的最大 公約數(shù).因為325=130X2+65,130=65X2,所以325與130的最大公約數(shù)是65.10=5X2,所以65與270最大公約數(shù)是5.故325, 130, 270三個數(shù)的最大公約 數(shù)是5小結(jié)作業(yè)為27065=11輾轉(zhuǎn)相除法,就是對于給定的兩個正整數(shù), 用較大的數(shù)除以較小的數(shù), 若余數(shù)不為 零,則將余數(shù)和較小的數(shù)構(gòu)成新的一對數(shù), 繼續(xù)上面的除法,直到大數(shù)被小數(shù)除盡為止, 這時的較小的數(shù)即為原來兩個數(shù)的最大公約數(shù).2.更相減損術(shù),就是對于給定的兩個正 整數(shù),
溫馨提示
- 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)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 神秘動物:你知道什么是神秘動物嗎
- 小學(xué)領(lǐng)導(dǎo)能力模擬測試
- 化學(xué)物質(zhì)與人類健康的關(guān)系
- 游樂園的設(shè)計和安全措施
- 小學(xué)一年級英語閱讀理解測試
- 加強(qiáng)交通安全意識防患于未然
- 2024年水利工程行業(yè)技能考試-自來水廠運(yùn)行工考試近5年真題集錦(頻考類試題)帶答案
- 2024年機(jī)械制造行業(yè)技能考試-數(shù)控裝調(diào)維修工考試近5年真題集錦(頻考類試題)帶答案
- 2024年新疆住院醫(yī)師-新疆住院醫(yī)師放射腫瘤科考試近5年真題集錦(頻考類試題)帶答案
- 2024年教師招聘考試-教師招聘面試考試近5年真題集錦(頻考類試題)帶答案
- 《信息素養(yǎng)的提升》課件
- 國開電大操作系統(tǒng)-Linux系統(tǒng)使用-實驗報告
- 焊接夾具設(shè)計及制作標(biāo)準(zhǔn)
- ICU患者發(fā)生呼吸機(jī)相關(guān)肺炎(VAP)原因分析品管圈魚骨圖柏拉圖
- 共拾朝花歲有余香-初中語文七年級上冊《朝花夕拾》導(dǎo)讀課(公開課一等獎創(chuàng)新教學(xué)設(shè)計)
- 2023版公路水運(yùn)工程施工企業(yè)主要負(fù)責(zé)人和安全生產(chǎn)管理人員考核大綱及模擬題庫
- 【公文】正高級會計師答辯面試資料
- 建筑電氣與智能化專業(yè)大學(xué)生職業(yè)生涯規(guī)劃書
- 直線投影相關(guān)知識簡介
- 大同年產(chǎn)xxx臺氫燃料加氫站設(shè)備項目立項報告
- 有限空間作業(yè)的事故案例分析和經(jīng)驗教訓(xùn)總結(jié)
評論
0/150
提交評論