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

2、我們還需要把任意一個(gè)十進(jìn)制數(shù)化為個(gè)十進(jìn)制數(shù)化為k k進(jìn)制數(shù)的算法，對(duì)此，進(jìn)制數(shù)的算法，對(duì)此，我們作些理論上的探討我們作些理論上的探討. .知識(shí)探究知識(shí)探究( (一一):):除除k k取余法取余法思考思考1:1:二進(jìn)制數(shù)二進(jìn)制數(shù)101101101101（2 2）化為十進(jìn)制化為十進(jìn)制數(shù)是什么數(shù)？十進(jìn)制數(shù)數(shù)是什么數(shù)？十進(jìn)制數(shù)8989化為二進(jìn)制數(shù)化為二進(jìn)制數(shù)是什么數(shù)？是什么數(shù)？101101101101（2 2）=2=25 5+2+23 3+2+22 2+1=45. +1=45. 89=289=2（2 2（2 2（2 2（2 22+12+1）+1+1）+0+0）+0+0）+1+1=1=12 26 6+

3、+0 02 25 5+ +1 12 24 4+ +1 12 23 3+ +0 02 22 2+ +0 02 21 1+ +1 12 20 0=1011001=1011001（2 2）. .思考思考2:2:上述化十進(jìn)制數(shù)為二進(jìn)制數(shù)的算上述化十進(jìn)制數(shù)為二進(jìn)制數(shù)的算法叫做法叫做除除2 2取余法取余法，轉(zhuǎn)化過程有些復(fù)雜，轉(zhuǎn)化過程有些復(fù)雜，觀察下面的算式你有什么發(fā)現(xiàn)嗎？觀察下面的算式你有什么發(fā)現(xiàn)嗎？ 21222502112222442891001101余數(shù)余數(shù)思考思考3:3:上述方法也可以推廣為把十進(jìn)制上述方法也可以推廣為把十進(jìn)制數(shù)化為數(shù)化為k k進(jìn)制數(shù)的算法，稱為進(jìn)制數(shù)的算法，稱為除除k k取余法取余

4、法，那么十進(jìn)制數(shù)那么十進(jìn)制數(shù)191191化為五進(jìn)制數(shù)是什么化為五進(jìn)制數(shù)是什么數(shù)？數(shù)？0515753851911321余數(shù)余數(shù)191=1231191=1231（5 5）思考思考4:4:若十進(jìn)制數(shù)若十進(jìn)制數(shù) a a除以除以2 2所得的商是所得的商是q q0 0，余數(shù)是，余數(shù)是r r0 0， 即即a=2qa=2q0 0+ r+ r0 0；q q0 0除以除以2 2所得的商是所得的商是q q1 1，余數(shù)是，余數(shù)是r r1 1， 即即q q0 0=2q=2q1 1+ r+ r1 1； q qn-1n-1除以除以2 2所得的商是所得的商是0 0，余數(shù)是，余數(shù)是r rn n， 即即q qn-1n-1= r=

5、 rn n，那么十進(jìn)制數(shù)那么十進(jìn)制數(shù)a a化為二進(jìn)制數(shù)是什么數(shù)？化為二進(jìn)制數(shù)是什么數(shù)？a=ra=rn nr rn-1n-1rr1 1r r0(2)0(2)知識(shí)探究知識(shí)探究( (二二):):十進(jìn)制化十進(jìn)制化k k進(jìn)制的算法進(jìn)制的算法 思考思考1:1:根據(jù)上面的分析，將十進(jìn)制數(shù)根據(jù)上面的分析，將十進(jìn)制數(shù)a a化化為二進(jìn)制數(shù)的算法步驟如何設(shè)計(jì)？為二進(jìn)制數(shù)的算法步驟如何設(shè)計(jì)？第四步，若第四步，若q0q0，則，則a=qa=q，返回第二步；，返回第二步； 否則，輸出全部余數(shù)否則，輸出全部余數(shù)r r排列得到排列得到 的二進(jìn)制數(shù)的二進(jìn)制數(shù). .第一步，輸入十進(jìn)制數(shù)第一步，輸入十進(jìn)制數(shù)a a的值的值. .第二步

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

7、的商q q，余數(shù)，余數(shù)r.r.第三步，把所得的余數(shù)依次從右到左排第三步，把所得的余數(shù)依次從右到左排 列列. .思考思考3:3:將除將除k k取余法的算法步驟用程序框取余法的算法步驟用程序框圖如何表示？圖如何表示？ 開始開始輸入輸入a，k求求a除以除以k的商的商q求求a除以除以k的余數(shù)的余數(shù)r把所得的余數(shù)依次從右到左排列把所得的余數(shù)依次從右到左排列a=qq=0？結(jié)束結(jié)束輸出全部余數(shù)輸出全部余數(shù)r排排列得到的列得到的k k進(jìn)制數(shù)進(jìn)制數(shù)是是否否思考思考4:4:該程序框圖對(duì)應(yīng)的程序如何表述？該程序框圖對(duì)應(yīng)的程序如何表述？開始開始輸入輸入a，k求求a除以除以k的商的商q求求a除以除以k的余數(shù)的余數(shù)r把所

8、得的余數(shù)依次從右到左排列把所得的余數(shù)依次從右到左排列a=qq=0？結(jié)束結(jié)束輸出全部余數(shù)輸出全部余數(shù)r排排列得到的列得到的k k進(jìn)制數(shù)進(jìn)制數(shù)是是否否input ainput a，k kb=0b=0i=0i=0dodoq=a/kq=a/kr=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 將十進(jìn)制數(shù)將十進(jìn)制數(shù)458458分別轉(zhuǎn)化為四進(jìn)分別轉(zhuǎn)化為四進(jìn)制數(shù)和六進(jìn)制數(shù)制數(shù)和六進(jìn)制數(shù). .0414742841144458220

9、31余數(shù)余數(shù)06261267664582402余數(shù)余數(shù)458=13022458=13022（4 4）=2042=2042（6 6） 例例2 2 將五進(jìn)制數(shù)將五進(jìn)制數(shù)32413241（5 5）轉(zhuǎn)化為七進(jìn)轉(zhuǎn)化為七進(jìn)制數(shù)制數(shù). . 3024130241（5 5）=3=35 54 4+2+25 52 2+4+45+1=1946. 5+1=1946. 0757397278719460545余數(shù)余數(shù)3024130241（5 5）=5450=5450（7 7） 小結(jié)作業(yè)小結(jié)作業(yè) 1. 1.利用除利用除k k取余法，可以把任何一個(gè)取余法，可以把任何一個(gè)十進(jìn)制數(shù)化為十進(jìn)制數(shù)化為k k進(jìn)制數(shù)，并且操作簡(jiǎn)單、進(jìn)制數(shù)，并且操作簡(jiǎn)單、實(shí)用實(shí)用. . 2. 2