版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1.3算法案例
第一課時1.3算法案例第一課時1
我們是如何求兩個正數(shù)的最大公約數(shù)的?如:求下面兩個正整數(shù)的最大公約數(shù):(1)求25和35的最大公約數(shù)(2)求2520和1470的最大公約數(shù)25(1)55357(2)1470101472520252所以,25和35的最大公約數(shù)為5所以,2520和1470的最大公約數(shù)為210解:回顧736217123如何算出8251和6105的最大公約數(shù)?我們是如何求兩個正數(shù)的最大公約數(shù)的?如:求下面兩個正整數(shù)的2輾轉(zhuǎn)相除法(歐幾里德算法)輾轉(zhuǎn)相除法(歐幾里德算法)3思考1:對于8251與6105這兩個數(shù),由于8251=6105×1+2146
8251與6105的公約數(shù)就是6105與2146的公約數(shù)。?那么,8251與6105這兩個數(shù)的公約數(shù)和
6105與2146的公約數(shù)有什么關(guān)系?思考1:對于8251與6105這兩個數(shù),由于824思考2:重復(fù)上述操作,如何得到8251與6105這兩個數(shù)的最大公約數(shù)?思考2:重復(fù)上述操作,如何得到8251與5完整的過程8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0例:用輾轉(zhuǎn)相除法求225和135的最大公約數(shù)225=135×1+90135=90×1+4590=45×2+0顯然37是148和37的最大公約數(shù),也就是8251和6105的最大公約數(shù)顯然45是90和45的最大公約數(shù),也就是225和135的最大公約數(shù)S1:用大數(shù)除以小數(shù)S2:除數(shù)變成被除數(shù),余數(shù)變成除數(shù)S3:重復(fù)S1,直到余數(shù)為0從上面的兩個例子中可以看出計算的規(guī)律是什么?完整的過程8251=6105×1+21466105=2146
輾轉(zhuǎn)相除法是一個反復(fù)執(zhí)行直到余數(shù)等于0停止的步驟,這實際上是一個循環(huán)結(jié)構(gòu)。8251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0m=n×q+r思考3:輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)?其算法步驟如何設(shè)計?
第一步:給定兩個正整數(shù)m,n(m>n)。第二步:計算m除以n所得的余數(shù)r。
第三步:m=n,n=r。第四步:判斷“r=0”是否成立,若r=0,則m,n的最大公約數(shù)等于m;否則,返回第二步。
輾轉(zhuǎn)相除法是一個反復(fù)執(zhí)行直8251=6105×78251=6105×1+21466105=2146×2+18132146=1813×1+3331813=333×5+148333=148×2+37148=37×4+0m=n×q+r思考3:輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)?其算法步驟如何設(shè)計?
用程序框圖表示出右邊的過程r=mMODnm=nn=r是否r=0?8251=6105×1+21466105=2146×28思考5:
如果用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法,則用輾轉(zhuǎn)相除法求兩個正整數(shù)m、n的最大公約數(shù)的程序框圖和程序分別如何表示?思考5:9是開始求m除以n的余數(shù)rm=n否輸出m結(jié)束n=rr≠0?輸入m,nr=1開始求m除以n的余數(shù)rm=n否輸出m結(jié)束n=rr≠0?輸入m10練習(xí)1:利用輾轉(zhuǎn)相除法求兩數(shù)4081與20723的最大公約數(shù).(53)20723=4081×5+3184081=318×12+265318=265×1+53265=53×5+0練習(xí)1:利用輾轉(zhuǎn)相除法求兩數(shù)4081與(53)2011練習(xí)2:求325,130,270三個數(shù)的最大公約數(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ù)是5.練習(xí)2:求325,130,270三個數(shù)的最∵325=12
可半者半之,不可半者,副置分母、子之?dāng)?shù),以少減多,更相減損,求其等也,以等數(shù)約之?!毒耪滤阈g(shù)》中的更相減損術(shù):背景介紹:任意給定兩個正整數(shù);判斷他們是否都是偶數(shù)。若是,則用2約簡;若不是,則以較大的數(shù)減較小的數(shù),接著把所得的差與較小的數(shù)比較,并以大數(shù)減小數(shù)。繼續(xù)這個操作,直到所得的減數(shù)和差相等為止,則這個等數(shù)就是所求的最大公約數(shù)。
現(xiàn)代數(shù)學(xué)中的更相減損術(shù):可半者半之,不可半者,副置分母、子之?dāng)?shù),以少13例:用更相減損術(shù)求98與63的最大公約數(shù).解:由于63不是偶數(shù),把98和63以大數(shù)減小數(shù),并輾轉(zhuǎn)相減所以,98和63的最大公約數(shù)等于798-63=35,14-7=7.21-7=14,28-7=21,35-28=7,63-35=28,例:用更相減損術(shù)求98與63的最大公約數(shù).解:由于63不是1498-63=3514-7=721-7=1428-7=2135-28=763-35=28思考6:
用什么邏輯結(jié)構(gòu)來構(gòu)造算法?其算法步驟如何設(shè)計?程序框圖如何表示?m-n=k第一步,給定兩個正整數(shù)m,n(m>n).
第二步,計算m-n所得的差k.
第三步,比較n與k的大小,其中大者用m表示,小者用n表示.
第四步,若m=n,則m,n的最大公約數(shù)等于m;否則,返回第二步.98-63=3514-7=721-7=1428-7=213515理論遷移
例1.分別用輾轉(zhuǎn)相除法和更相減損術(shù)求168與93的最大公約數(shù).輾轉(zhuǎn)相除法:168=93×1+75 93=75×1+18 75=18×4+3 18=3×6+0理論遷移例1.分別用輾轉(zhuǎn)相除法和更相減損輾轉(zhuǎn)相16更相減損術(shù):168-93=75,18-3=15,93-75=18,15-3=12,75-18=57,12-3=9,57-18=39,9-3=6,39-18=21,6-3=3。21-18=3,
更相減損術(shù):17比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別(1)都是求最大公約數(shù)的方法,計算上輾轉(zhuǎn)相除法以除法為主,更相減損術(shù)以減法為主,計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少,特別當(dāng)兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯。(2)從結(jié)果體現(xiàn)形式來看,輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到,而更相減損術(shù)則以減數(shù)與差相等而得到小結(jié)比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別小結(jié)181.輾轉(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ù).1.輾轉(zhuǎn)相除法,就是對于給定的兩個正整數(shù),用較大的數(shù)除19比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別(1)都是求最大公約數(shù)的方法,計算上輾轉(zhuǎn)相除法以除法為主,更相減損術(shù)以減法為主,計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少,特別當(dāng)兩個數(shù)字大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯。(2)從結(jié)果體現(xiàn)形式來看,輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到,而更相減損術(shù)則以減數(shù)與差相等而得到小結(jié)比較輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別小結(jié)20任意給定兩個正整數(shù);判斷他們是否都是偶數(shù)。若是,則用2約簡;若不是,則以較大的數(shù)減較小的數(shù),接著把所得的差與較小的數(shù)比較,并以大數(shù)減小數(shù)。繼續(xù)這個操作,直到所得的減數(shù)和差相等為止,則這個等數(shù)就是所求的最大公約數(shù)。任意給定兩個正整數(shù);判斷他們是否都是偶數(shù)。若是21例2求325,130,270三個數(shù)的最大公約數(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.例2求325,130,270三個數(shù)的最大公約數(shù).22該算法的程序框圖:開始輸入m,n求m除以n的余數(shù)rm=nn=rr=0?是輸出m結(jié)束否該算法的程序框圖:開始輸入m,n求m除以n的余數(shù)rm=nn=23思考4:該程序框圖對應(yīng)的程序如何表述?INPUTm,nDOr=mMODnm=nn=rLOOPUNTIL
r=0PRINTmEND是開始輸入m,n求m除以n的余數(shù)rm=nn=rr=0?輸出m結(jié)束否思考4:該程序框圖對應(yīng)的程序如何表述?INPUTm,nD24開始輸入m,n求m除以n的余數(shù)rm=nr=0?否輸出m結(jié)束n=rINPUTm,nWHILEn>0r=mMODnm=nn=rWENDPRINTmEND是開始輸入m,n求m除以n的余數(shù)rm=nr=0?否輸出m結(jié)束n25知識探究(二):更相減損術(shù)
可半者半之,不可半者,副置分母、子之?dāng)?shù),以少減多,更相減損,求其等也,以等數(shù)約之。第一步:任意給定兩個正整數(shù);判斷他們是否都是偶數(shù)。若是,則用2約簡;若不是則執(zhí)行第二步。第二步:以較大的數(shù)減較小的數(shù),接著把所得的差與較小的數(shù)比較,并以大數(shù)減小數(shù)。繼續(xù)這個操作,直到所得的減數(shù)和差相等為止,則這個等數(shù)就是所求的最大公約數(shù)。(1)、《九章算術(shù)》中的更相減損術(shù):1、背景介紹:(2)、現(xiàn)代數(shù)學(xué)中的更相減損術(shù):知識探究(二):更相減損術(shù)可半者半之,不可半者26INPUT“m,n=“;m,nIFm<nTHENa=mm=nn=aENDIFK=0WHILEmMOD2=0ANDnMOD2=0m=m/2n=n/2k=k+1WENDd=m-nWhiled<>nIFd>nthenm=dELSEm=nn=dEndifd=m-nWendd=2^k*dPRINTdEnd
INPUT“m,n=“;m,nWhiled<>n27作業(yè):P45練習(xí):1.P48習(xí)題1.3A組:1.作業(yè):28
科學(xué)精神
——
歐幾里德留給現(xiàn)代文明的寶貴遺產(chǎn)
他的生平,后人所知甚少。大概早年在雅典就讀,深悉柏拉圖的學(xué)說。公元前300年左右,歐幾里德接受托勒密王(公元前364~前283)的邀請,來到亞歷山大城,長期在那里工作。他是一位溫良敦厚的教育家,對有志數(shù)學(xué)之士,總是循循善誘。但反對投機(jī)取巧、不肯刻苦鉆研的作風(fēng),也反對狹隘實用觀點。
218x32014kjpg
歐幾里德-陳具才,具才軟件...
科學(xué)精神
——
29學(xué)問追求真理而并非追求實利
知識淵博的歐幾里德在教授學(xué)生時,像一個真正的父親那樣引導(dǎo)學(xué)生,關(guān)心他們。然而有時,他也用辛辣的諷刺來鞭撻學(xué)生中的傲慢之徒。
斯托貝烏斯(約公元500年)轉(zhuǎn)述:有個學(xué)生在聽講“第一定理”之后,便問道:“學(xué)習(xí)幾何,究竟會有什么好處?”于是,歐幾里得轉(zhuǎn)身吩咐傭人說:“格魯米阿,拿三個錢幣給這位先生,因為他想在學(xué)習(xí)中獲得實利。”“幾何學(xué)里沒有王者大道”
及“科學(xué)無坦途”
據(jù)希臘學(xué)者普羅克洛斯(約410~485年)轉(zhuǎn)述歷史記載,亞歷山大國王多祿米曾師從歐幾里得學(xué)習(xí)幾何,有一次對于歐幾里得一遍又一遍地解釋他的原理表示不耐煩。國王問道:“有沒有比你的方法簡捷一些的學(xué)習(xí)幾何學(xué)的途徑?”
歐幾里德回答:“陛下!原野上有兩種道路,一種是供平民百姓走的崎嶇小路,一條種供王者走的坦途。但是在幾何學(xué)里,大家只能走同一條崎嶇小路!走向?qū)W問,是沒有什么王者大道的!請陛下明白?!?/p>
歐幾里德的這番話,后代廣為傳誦,簡略為“幾何無王者之大道”、“求知無坦途”,又成為馬克思引用并信奉的名言:“在科學(xué)上是沒有康莊大道可走的;只有在那崎嶇小路上不畏勞苦、勇敢攀登的人,有希望達(dá)到光輝的頂點!”
學(xué)問追求真理而并非追求實利
30
16世紀(jì)以前多少世代,中國在技術(shù)方面一直領(lǐng)先于歐洲。但從來沒有出現(xiàn)一個可以同歐幾里德相比的、具有真正邏輯思維的中國數(shù)學(xué)家。結(jié)果,中國從未擁有過歐洲人那樣的數(shù)學(xué)理論體系。華夏文明和印度文明等東方文明固然偉大,但是在思維方式方面,自古以來就是存在嚴(yán)重欠缺的!自古以來,中國思想界一向擅長綜合、聯(lián)想、類比,固然具有“中國特色”,但是容易墮入籠統(tǒng)、含混、武斷、臆測、想當(dāng)然、浮皮潦草、牽強(qiáng)附會、不符實際的聯(lián)想類比、望文生義、不求甚解、含糊朦朧的表述方式……。造成的危害是難以估量的。大量事實(甚至某些令人痛心而又可笑可嘆可悲的事實)表明,中國人普遍的思維方式亟需提高!這需要我們大家做許多扎實的認(rèn)真的工作!
16世紀(jì)以前多少世代,中國在技術(shù)方面一直領(lǐng)先于歐洲。但從來31復(fù)習(xí)引入1.回顧算法的三種表示方法:(1)、自然語言(2)、程序框圖(3)、程序語言(三種邏輯結(jié)構(gòu))(五種基本語句)復(fù)習(xí)引入1.回顧算法的三種表示方法:(1)、自然語言(2)32思考2:重復(fù)上述操作,如何得
溫馨提示
- 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)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 二零二五年度醫(yī)療健康PPP項目合同執(zhí)行與監(jiān)督辦法2篇
- 二零二五年度房地產(chǎn)項目全域整合推廣與社區(qū)服務(wù)合同3篇
- 2025產(chǎn)業(yè)園項目幕墻二次深化設(shè)計、施工監(jiān)理及后期運維合同3篇
- 2025場“好贊服務(wù)”市場拓展與代理合同3篇
- 二零二五年度版權(quán)質(zhì)押合同:涉及圖書出版權(quán)的金融抵押問題3篇
- 二零二五年度建筑工程勞務(wù)分包清包勞務(wù)合同范本全新出臺6篇
- 2025版農(nóng)業(yè)設(shè)施建設(shè)項目勞務(wù)分包合同安全協(xié)議2篇
- 二零二五年度安徽省綠色建筑推廣應(yīng)用合同2篇
- 2024版?zhèn)€體戶營業(yè)執(zhí)照租賃合同范本3篇
- 二零二五年度房屋出售廣告宣傳代理合同3篇
- 2024-2025學(xué)年山東省德州市高中五校高二上學(xué)期期中考試地理試題(解析版)
- 2025年國務(wù)院發(fā)展研究中心信息中心招聘應(yīng)屆畢業(yè)生1人高頻重點提升(共500題)附帶答案詳解
- 2024年公安機(jī)關(guān)理論考試題庫500道及參考答案
- 特殊情況施工的技術(shù)措施
- 《急診科建設(shè)與設(shè)備配置標(biāo)準(zhǔn)》
- 《中國糖尿病防治指南(2024版)》更新要點解讀
- 大學(xué)物理(二)知到智慧樹章節(jié)測試課后答案2024年秋湖南大學(xué)
- 銀行運營集中規(guī)劃
- 《數(shù)據(jù)分析你懂的》課件
- TSGD7002-2023-壓力管道元件型式試驗規(guī)則
- 《鐵路危險貨物運輸管理規(guī)則》
評論
0/150
提交評論