必修三算法案例

1、算法案例輾轉(zhuǎn)相除法更相減損術(shù)秦九韶算法進(jìn)位制輾轉(zhuǎn)相除法1、求兩個正整數(shù)的最大公約數(shù)（1）求25和35的最大公約數(shù)（2）求49和63的最大公約數(shù)2、求8251和6105的最大公約數(shù) 25（1）55357所以，25和35的最大公約數(shù)為5輾轉(zhuǎn)相除法（歐幾里得算法）觀察用輾轉(zhuǎn)相除法求8251和6105的最大公約數(shù)的過程 第一步 用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)8251=61051+2146結(jié)論： 8251和6105的公約數(shù)就是6105和2146的公約數(shù)，求8251和6105的最大公約數(shù)，只要求出6105和2146的公約數(shù)就可以了。第二步 對6105和2146重復(fù)第一步的做法6105=2146

2、2+1813同理6105和2146的最大公約數(shù)也是2146和1813的最大公約數(shù)。 為什么呢？完整的過程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0顯然37是148和37的最大公約數(shù)，也就是8251和6105的最大公約數(shù) 思考1：從上面的兩個例子可以看出計(jì)算的規(guī)律是什么？ S1：用大數(shù)除以小數(shù)S2：除數(shù)變成被除數(shù)，余數(shù)變成除數(shù)S3：重復(fù)S1，直到余數(shù)為0 輾轉(zhuǎn)相除法是一個反復(fù)執(zhí)行直到余數(shù)等于0停止的步驟，這實(shí)際上是一個循環(huán)結(jié)構(gòu)。8251=61051+2146 6105=21462+

3、1813 2146=18131+3331813=3335+148333=1482+37148=374+0m = n q r用程序框圖表示出右邊的過程r=m MOD nm = nn = rr=0?是否思考2：輾轉(zhuǎn)相除法中的關(guān)鍵步驟是哪種邏輯結(jié)構(gòu)？ 九章算術(shù)更相減損術(shù) 算理：可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。第一步：任意給頂兩個正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡；若不是則執(zhí)行第二步。第二步：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的減數(shù)和差相等為止，則這個等數(shù)就是所求的最大公約數(shù)。例3 用

4、更相減損術(shù)求98與63的最大公約數(shù)解：由于63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減 9863356335283528728721217141477所以，98和63的最大公約數(shù)等于7 秦九韶算法這種算法用了幾次乘法？幾次加法？這種算法用了幾次乘法？幾次加法？5次乘法，5次加法.進(jìn)位制是人們?yōu)榱擞?jì)數(shù)和運(yùn)算便而約定的記數(shù)系統(tǒng).“滿十進(jìn)一”就是十進(jìn)制，“滿二進(jìn)一”就是二進(jìn)制，“滿k進(jìn)一”就是k進(jìn)制，因此k進(jìn)制需數(shù)k個數(shù)字.進(jìn)位制判斷下列數(shù)表達(dá)是否正確？(1) 12(2)(2) 061(7)(3) 291(8)一般地，若k是一個大于1的整數(shù)，那么以k為基數(shù)的k進(jìn)制數(shù)可以表示為一串?dāng)?shù)字連寫在一起

5、的形式：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ù)110011(2)化為十進(jìn)制數(shù).解：110011(2)=125+1 24+ 023+0 22 + 121+1 20 =51練習(xí)：把下列數(shù)化為十進(jìn)制數(shù)(1) 1011010(2)(2) 10212(3)(3) 2376(3)將十進(jìn)制數(shù)轉(zhuǎn)為k進(jìn)制數(shù)：除k取余法例 把89化為二進(jìn)制數(shù).例 把89化為五進(jìn)制數(shù).除2取余法除5取余法2、十進(jìn)制轉(zhuǎn)換為二進(jìn)制例2 把89化為二進(jìn)制數(shù)522212010余數(shù)11224889222201101注意：1.最后一步商為0，2.將上式各步所得的余數(shù)從下到上排列，得到：89=1011001（2）練習(xí)將下面的十進(jìn)制數(shù)化為二進(jìn)制數(shù)？（1）10（2）20（3）128（4）256例把89化為五進(jìn)制數(shù)3、十進(jìn)制轉(zhuǎn)換為其它進(jìn)制解：根據(jù)除k取余法以5作為除數(shù)，相應(yīng)的除法算式為：所以，8