1、1.3 1.3 算法案例算法案例 第四課時第四課時 問題提出問題提出 1.“ 1.“滿幾進一滿幾進一”就是幾進制，就是幾進制，k k進制進制使用哪幾個數字，使用哪幾個數字，k k進制數化為十進制數進制數化為十進制數的一般算式是什么？的一般算式是什么？121( )1210121nnknnnna aa aakakakak-=+LL 2. 2.利用利用k k進制數化十進制數的一般算進制數化十進制數的一般算式，可以構造算法，設計程序，通過計式，可以構造算法，設計程序，通過計算機就能把任何一個算機就能把任何一個k k進制數化為十進制進制數化為十進制數數. .在實際應用中，我們還需要把任意一在實際應用中，

2、我們還需要把任意一個十進制數化為個十進制數化為k k進制數的算法，對此，進制數的算法，對此，我們作些理論上的探討我們作些理論上的探討. .例例1:把把89化為二進制的數化為二進制的數.分析分析:把把89化為二進制的數化為二進制的數,需想辦法將需想辦法將89先寫成如下形式先寫成如下形式89=an2n+an-12n-1+a121+a020 .89=64+16+8+1=126+025+124 +123+022+021+120 =1011001(2).但如果數太大但如果數太大,我們是無法這樣湊出來的我們是無法這樣湊出來的,怎么辦怎么辦?89=442+1, 44=222+0, 22=112+0, 11=

3、52+1, 5=22+1, 2=12+0, 1=02+1, 89=442+1, 44=222+0, 22=112+0, 11=52+1, 5=22+1, 89=442+1, =(222+0)2+1 =(112+0)2+0)2+1 =(52+1)2+0)2+0)2+1 =(22+1)2+1)2+0) 2+0)2+1 =(12)+0)2+1)2+1)2+0) 2+0)2+1=126+025+124 +123+022+021+120=1011001(2).可以用可以用2連續去除連續去除89或所得商或所得商(一直到商為一直到商為0為止為止),然后取余數然后取余數-除除2取余法取余法.2=12+0, 1

4、=02+1, 44 1我們可以用下面的除法算式表示除我們可以用下面的除法算式表示除2取余法取余法:289 余數余數222 0211 025 122 121 020 1把算式中各步所得的余數把算式中各步所得的余數從下到上排列從下到上排列,得到得到89=1011001(2).這種方法也可以推廣為把這種方法也可以推廣為把十進制數化為十進制數化為k進制數的進制數的算法算法,稱為稱為除除k取余法取余法.知識探究知識探究( (一一):):除除k k取余法取余法練習練習: :十進制數十進制數191191化為五進制數是什么化為五進制數是什么數？數？0515753851911321余數余數191=1231191

5、=1231（5 5）思考思考: :若十進制數若十進制數 a a除以除以2 2所得的商是所得的商是q q0 0，余數是，余數是r r0 0， 即即a=2qa=2q0 0+ r+ r0 0；q q0 0除以除以2 2所得的商是所得的商是q q1 1，余數是，余數是r r1 1， 即即q q0 0=2q=2q1 1+ r+ r1 1； q qn-1n-1除以除以2 2所得的商是所得的商是0 0，余數是，余數是r rn n， 即即q qn-1n-1= r= rn n，那么十進制數那么十進制數a a化為二進制數是什么數？化為二進制數是什么數？a=ra=rn nr rn-1n-1rr1 1r r0(2)0

6、(2)知識探究知識探究( (二二):):十進制化十進制化k k進制的算法進制的算法 思考思考1:1:根據上面的分析，將十進制數根據上面的分析，將十進制數a a化化為二進制數的算法步驟如何設計？為二進制數的算法步驟如何設計？第四步，若第四步，若q0q0，則，則a=qa=q，返回第二步；，返回第二步； 否則，輸出全部余數否則，輸出全部余數r r排列得到排列得到 的二進制數的二進制數. .第一步，輸入十進制數第一步，輸入十進制數a a的值的值. .第二步，求出第二步，求出a a除以除以2 2所得的商所得的商q q，余數，余數r.r.第三步，把所得的余數依次從右到左排列第三步，把所得的余數依次從右到左

7、排列. .思考思考2:2:利用除利用除k k取余法，將十進制數取余法，將十進制數a a化化為為k k進制數的算法步驟如何設計？進制數的算法步驟如何設計？第四步，若第四步，若q0q0，則，則a=qa=q，返回第二步；，返回第二步； 否則，輸出全部余數否則，輸出全部余數r r排列得到排列得到 的的k k進制數進制數. .第一步，輸入十進制數第一步，輸入十進制數a a和基數和基數k k的值的值. .第二步，求出第二步，求出a a除以除以k k所得的商所得的商q q，余數，余數r.r.第三步，把所得的余數依次從右到左排第三步，把所得的余數依次從右到左排 列列. .思考思考3:3:將除將除k k取余法的

8、算法步驟用程序框取余法的算法步驟用程序框圖如何表示？圖如何表示？ 開始開始輸入輸入a，k求求a除以除以k的商的商q求求a除以除以k的余數的余數r把所得的余數依次從右到左排列把所得的余數依次從右到左排列a=qq=0？結束結束輸出全部余數輸出全部余數r排排列得到的列得到的k k進制數進制數是是否否思考思考4:4:該程序框圖對應的程序如何表述？該程序框圖對應的程序如何表述？開始開始輸入輸入a，k求求a除以除以k的商的商q求求a除以除以k的余數的余數r把所得的余數依次從右到左排列把所得的余數依次從右到左排列a=qq=0？結束結束輸出全部余數輸出全部余數r排排列得到的列得到的k k進制數進制數是是否否I

9、NPUT aINPUT a，k kb=0b=0i=0i=0DODOq=akq=akr=a MOD kr=a MOD kb=b+rb=b+r* *1010i ii=i+1i=i+1a=qa=qLOOP UNTIL q=0LOOP UNTIL q=0PRINT bPRINT bENDEND理論遷移理論遷移 例例1 1 將十進制數將十進制數458458分別轉化為四進分別轉化為四進制數和六進制數制數和六進制數. .041474284114445822031余數余數06261267664582402余數余數458=13022458=13022（4 4）=2042=2042（6 6） 例例2 2 將五進制數將五進制數3024130241（5 5）轉化為七轉化為七進制數進制數. . 3024130241（5 5）=3=35 54 4+2+25 52 2+4+45+1=1946. 5+1=1946. 0757397278719460545余數余數3024130241（5 5）=5450=5450（7 7） 小結作業小結作業 1. 1.利用除利用除k k取余法，可以把任何一個取余法，可以把任何一個十進制數化為十進制數化為k k進制數，并且操作簡單、進制數，并且操作簡單、實用實用. . 2.