




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、算法案例 輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法 更相減損術(shù)更相減損術(shù) 秦九韶算法秦九韶算法 進(jìn)位制進(jìn)位制輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法1、求兩個正整數(shù)的最大公約數(shù)、求兩個正整數(shù)的最大公約數(shù)(1)求)求25和和35的最大公約數(shù)的最大公約數(shù)(2)求)求49和和63的最大公約數(shù)的最大公約數(shù)2、求、求8251和和6105的最大公約數(shù)的最大公約數(shù) 25(1)55357所以,所以,25和和35的最大公約數(shù)為的最大公約數(shù)為5輾轉(zhuǎn)相除法(歐幾里得算法)輾轉(zhuǎn)相除法(歐幾里得算法)觀察用輾轉(zhuǎn)相除法求觀察用輾轉(zhuǎn)相除法求8251和和6105的最大公約數(shù)的過程的最大公約數(shù)的過程 第一步第一步 用兩數(shù)中較大的數(shù)除以較小的數(shù),求得商和余數(shù)用兩數(shù)中較
2、大的數(shù)除以較小的數(shù),求得商和余數(shù)8251=61051+2146結(jié)論:結(jié)論: 8251和和6105的公約數(shù)就是的公約數(shù)就是6105和和2146的公約數(shù),求的公約數(shù),求8251和和6105的最大公約數(shù),只要求出的最大公約數(shù),只要求出6105和和2146的公約數(shù)就可以了。的公約數(shù)就可以了。第二步第二步 對對6105和和2146重復(fù)第一步的做法重復(fù)第一步的做法6105=21462+1813同理同理6105和和2146的最大公約數(shù)也是的最大公約數(shù)也是2146和和1813的最大公約數(shù)。的最大公約數(shù)。 完整的過程完整的過程8251=61051+2146 6105=21462+1813 2146=18131+
3、3331813=3335+148333=1482+37148=374+0顯然顯然37是是148和和37的最大公約的最大公約數(shù),也就是數(shù),也就是8251和和6105的最大的最大公約數(shù)公約數(shù) 思考思考1:從上面的兩個例子可以看出計(jì):從上面的兩個例子可以看出計(jì)算的規(guī)律是什么?算的規(guī)律是什么? S1:用大數(shù)除以小數(shù):用大數(shù)除以小數(shù)S2:除數(shù)變成被除數(shù),余數(shù)變成除數(shù):除數(shù)變成被除數(shù),余數(shù)變成除數(shù)S3:重復(fù):重復(fù)S1,直到余數(shù)為,直到余數(shù)為0 輾轉(zhuǎn)相除法是一個反復(fù)執(zhí)行直到余數(shù)等于輾轉(zhuǎn)相除法是一個反復(fù)執(zhí)行直到余數(shù)等于0停止停止的步驟,這實(shí)際上是一個循環(huán)結(jié)構(gòu)。的步驟,這實(shí)際上是一個循環(huán)結(jié)構(gòu)。8251=6105
4、1+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0m = n q r用程序框圖表示出右邊的過程用程序框圖表示出右邊的過程r=m MOD nm = nn = rr=0?是否九章算術(shù)九章算術(shù)更相減損術(shù)更相減損術(shù) 算理:算理:可半者半之,不可半者,副置分母、子之?dāng)?shù),可半者半之,不可半者,副置分母、子之?dāng)?shù),以少減多,更相減損,求其等也,以等數(shù)約之。以少減多,更相減損,求其等也,以等數(shù)約之。第一步:第一步:任意給頂兩個正整數(shù);判斷他們是否都是任意給頂兩個正整數(shù);判斷他們是否都是偶數(shù)。若是,則用偶數(shù)。若是,則用2約簡
5、;若不是則執(zhí)行第二步。約簡;若不是則執(zhí)行第二步。第二步:第二步:以較大的數(shù)減較小的數(shù),接著把所得的差以較大的數(shù)減較小的數(shù),接著把所得的差與較小的數(shù)比較,并以大數(shù)減小數(shù)。繼續(xù)這個操作,與較小的數(shù)比較,并以大數(shù)減小數(shù)。繼續(xù)這個操作,直到所得的減數(shù)和差相等為止,則這個等數(shù)就是所直到所得的減數(shù)和差相等為止,則這個等數(shù)就是所求的最大公約數(shù)。求的最大公約數(shù)。例例3 用更相減損術(shù)求用更相減損術(shù)求98與與63的最大公約數(shù)的最大公約數(shù)解:由于解:由于63不是偶數(shù),把不是偶數(shù),把98和和63以大數(shù)減小數(shù),并輾轉(zhuǎn)相減以大數(shù)減小數(shù),并輾轉(zhuǎn)相減 9863356335283528728721217141477所以,所以,
6、98和和63的最大公約數(shù)等于的最大公約數(shù)等于7 這種算法用了幾次乘法?幾次加法?這種算法用了幾次乘法?幾次加法?這種算法用了幾次乘法?幾次加法?這種算法用了幾次乘法?幾次加法?5次乘法,次乘法,5次加法次加法.進(jìn)位制是人們?yōu)榱擞?jì)數(shù)和運(yùn)算便而約定的進(jìn)位制是人們?yōu)榱擞?jì)數(shù)和運(yùn)算便而約定的記數(shù)系統(tǒng)記數(shù)系統(tǒng).“滿十進(jìn)一滿十進(jìn)一”就是十進(jìn)制,就是十進(jìn)制,“滿滿二進(jìn)一二進(jìn)一”就是二進(jìn)制,就是二進(jìn)制,“滿滿k進(jìn)一進(jìn)一”就是就是k進(jìn)制進(jìn)制,因此,因此k進(jìn)制需數(shù)進(jìn)制需數(shù)k個數(shù)字個數(shù)字.判斷下列數(shù)表達(dá)是否正確?判斷下列數(shù)表達(dá)是否正確?(1) 12(2)(2) 061(7)(3) 291(8)一般地,若一般地,若k是
7、一個大于是一個大于1的整數(shù),那么的整數(shù),那么以以k為基數(shù)的為基數(shù)的k進(jìn)制數(shù)進(jìn)制數(shù)可以表示為一串?dāng)?shù)字連可以表示為一串?dāng)?shù)字連寫在一起的形式:寫在一起的形式:),0 ,0( 011)(011kaaakaaaaannknn 3721=3103+7 102+2 101+1 100110011(2)=125+1 24+ 023+0 22 + 121+1 207342(8)=783+3 82+4 81+280將將k進(jìn)制數(shù)轉(zhuǎn)為十進(jìn)制數(shù):進(jìn)制數(shù)轉(zhuǎn)為十進(jìn)制數(shù):)(011 knnaaaa 001111kakakakannnn 例例 把二進(jìn)制數(shù)把二進(jìn)制數(shù)110011(2)化為十進(jìn)制數(shù)化為十進(jìn)制數(shù).解:解:110011
8、(2)=125+1 24+ 023+0 22 + 121+1 20 =51練習(xí):把下列數(shù)化為十進(jìn)制數(shù)練習(xí):把下列數(shù)化為十進(jìn)制數(shù)(1) 1011010(2)(2) 10212(3)(3) 2376(3)將十進(jìn)制數(shù)轉(zhuǎn)為將十進(jìn)制數(shù)轉(zhuǎn)為k進(jìn)制數(shù):進(jìn)制數(shù):除除k取余法取余法例例 把把89化為二進(jìn)制數(shù)化為二進(jìn)制數(shù).例例 把把89化為五進(jìn)制數(shù)化為五進(jìn)制數(shù).除除2取余法取余法除除5取余法取余法2、十進(jìn)制轉(zhuǎn)換為二進(jìn)制、十進(jìn)制轉(zhuǎn)換為二進(jìn)制例例2 把把89化為二進(jìn)制數(shù)化為二進(jìn)制數(shù)522212010余數(shù)余數(shù)11224889222201101注意:注意:1.最后一步商為最后一步商為0,2.將上式各步所得的余數(shù)將上式各步所得的余數(shù)從下到上排列從下到上排列,得到:,得到:89=1011001(2)練習(xí)練習(xí)將下面的十進(jìn)制數(shù)化為二進(jìn)制數(shù)?將下面的十進(jìn)制數(shù)化為二進(jìn)制數(shù)?(1)10(2)20(3)128(4)256例把例把89化為五進(jìn)制數(shù)化為五進(jìn)制數(shù)3、十進(jìn)制轉(zhuǎn)換為其它進(jìn)制、十進(jìn)制轉(zhuǎn)換為其它進(jìn)制解:解: 根據(jù)根據(jù)除除k取余法取余法以以5作為除數(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)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年邯鄲貨運(yùn)資格證題庫及答案大全
- 二零二五版房產(chǎn)中介獨(dú)家代理合同范文
- 包機(jī)運(yùn)輸協(xié)議書模板二零二五年
- 二零二五合法的合租房屋租賃合同
- 外教教師聘用合同
- 保險(xiǎn)契約居間合同二零二五年
- 存量房購買居間合同
- 物業(yè)管理公司財(cái)務(wù)管理制二零二五年
- 二零二五簡單土地買賣合同
- 鞋廠廠長車間管理制度
- 向最高檢察院提起申訴書范文
- 2023年江蘇鹽城音樂美術(shù)中考試卷及答案
- 菜鳥WMS(大寶)操作手冊 (修復(fù)的)
- 潔凈區(qū)微生物及衛(wèi)生知識培訓(xùn)根據(jù)GMP
- 臺灣問題專題解讀
- nc600產(chǎn)品說明書串口服務(wù)器使用
- (完整版)食品安全自查、從業(yè)人員健康管理、進(jìn)貨查驗(yàn)記錄、食品安全事故處置保證食品安全規(guī)章制度
- 特種設(shè)備安全管理人員(A)考試題庫
- GB/T 34936-2017光伏發(fā)電站匯流箱技術(shù)要求
- 摩擦學(xué)發(fā)展前沿課件
- 吊車牽引放線跨越公路和停電10千伏線路方案說明
評論
0/150
提交評論