1、算法案例輾轉(zhuǎn)相除法更相減損術(shù)秦九韶算法進位制第1頁輾轉(zhuǎn)相除法第2頁1、求兩個正整數(shù)最大條約數(shù)（1）求25和35最大條約數(shù)（2）求49和63最大條約數(shù)2、求8251和6105最大條約數(shù) 25（1）55357所以，25和35最大條約數(shù)為5第3頁輾轉(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重復第一步做法6105=21462+181

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

3、6=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)？ 第6頁九章算術(shù)更相減損術(shù) 算理：可半者半之，不可半者，副置分母、子之數(shù)，以少減多，更相減損，求其等也，以等數(shù)約之。第一步：任意給頂兩個正整數(shù)；判斷他們是否都是偶數(shù)。若是，則用2約簡；若不是則執(zhí)行第二步。第二步：以較大數(shù)減較小數(shù)，接著把所得差與較小數(shù)比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得減數(shù)和差相等為止，則這個等數(shù)就是所求最大條約數(shù)。第7頁例3 用更相減損術(shù)求98與6

4、3最大條約數(shù)解：因為63不是偶數(shù)，把98和63以大數(shù)減小數(shù)，并輾轉(zhuǎn)相減 9863356335283528728721217141477所以，98和63最大條約數(shù)等于7 第8頁秦九韶算法這種算法用了幾次乘法？幾次加法？第9頁這種算法用了幾次乘法？幾次加法？5次乘法，5次加法.第10頁第11頁第12頁第13頁進位制是人們?yōu)榱擞嫈?shù)和運算便而約定記數(shù)系統(tǒng).“滿十進一”就是十進制，“滿二進一”就是二進制，“滿k進一”就是k進制，所以k進制需數(shù)k個數(shù)字.進位制判斷以下數(shù)表示是否正確？(1) 12(2)(2) 061(7)(3) 291(8)第14頁普通地，若k是一個大于1整數(shù)，那么以k為基數(shù)k進制數(shù)能夠表

5、示為一串數(shù)字連寫在一起形式：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第15頁將k進制數(shù)轉(zhuǎn)為十進制數(shù)：例 把二進制數(shù)110011(2)化為十進制數(shù).解：110011(2)=125+1 24+ 023+0 22 + 121+1 20 =51第16頁練習：把以下數(shù)化為十進制數(shù)(1) 1011010(2)(2) 10212(3)(3) 2376(3)第17頁將十進制數(shù)轉(zhuǎn)為k進制數(shù)：除k取余法例 把89化為二進制數(shù).例 把89化為五進制數(shù).除2取余法除5取余法第18頁2、十進制轉(zhuǎn)換為二進制例2 把89化為二進制數(shù)522212010余數(shù)11224889222201101注意：1.最終一步商為0，2.將上式各步所得余數(shù)從下到上排列，得到：89=1011001（2）第19頁練習將下面十進制數(shù)化為二進制數(shù)？（1）10（2）20（3）128（4）256第20頁例把89化為五進制數(shù)3、十進制轉(zhuǎn)換為其它進制解：依據(jù)除k取余法以5作為除數(shù)，對應除法算式為：所以，89=324