必修三(算法案例)

1、算法案例 輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法 更相減損術(shù)更相減損術(shù) 秦九韶算法秦九韶算法 進(jìn)位制進(jìn)位制輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法1、求兩個(gè)正整數(shù)的最大公約數(shù)、求兩個(gè)正整數(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ù)的過(guò)程的最大公約數(shù)的過(guò)程 第一步第一步 用兩數(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ù)就可以了。第二步第二步 對(duì)對(duì)6105和和2146重復(fù)第一步的做法重復(fù)第一步的做法6105=21462+1813同理同理6105和和2146的最大公約數(shù)也是的最大公約數(shù)也是2146和和1813的最大公約數(shù)。的最大公約數(shù)。 完整的過(guò)程完整的過(guò)程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：從上面的兩個(gè)例子可以看出計(jì)：從上面的兩個(gè)例子可以看出計(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)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于0停止停止的步驟，這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu)。的步驟，這實(shí)際上是一個(gè)循環(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用程序框圖表示出右邊的過(guò)程用程序框圖表示出右邊的過(guò)程r=m MOD nm = nn = rr=0?是否九章算術(shù)九章算術(shù)更相減損術(shù)更相減損術(shù) 算理：算理：可半者半之，不可半者，副置分母、子之?dāng)?shù)，可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。以少減多，更相減損，求其等也，以等數(shù)約之。第一步：第一步：任意給頂兩個(gè)正整數(shù)；判斷他們是否都是任意給頂兩個(gè)正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用偶數(shù)。若是，則用2約簡(jiǎn)

5、；若不是則執(zhí)行第二步。約簡(jiǎn)；若不是則執(zhí)行第二步。第二步：第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的減數(shù)和差相等為止，則這個(gè)等數(shù)就是所直到所得的減數(shù)和差相等為止，則這個(gè)等數(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個(gè)數(shù)字個(gè)數(shù)字.判斷下列數(shù)表達(dá)是否正確？判斷下列數(shù)表達(dá)是否正確？(1) 12(2)(2) 061(7)(3) 291(8)一般地，若一般地，若k是

7、一個(gè)大于是一個(gè)大于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ù)