高二数学下学期

1、1.3 1.3 算法案例算法案例1.3.4 1.3.4 十进制化十进制化K K进制进制1.3.1 1.3.1 辗转相除法和更相减损术辗转相除法和更相减损术1.3.2 1.3.2 秦九韶算法秦九韶算法1.3.3 K1.3.3 K进制化十进制进制化十进制1.3 1.3 算法案例算法案例1.3.1 1.3.1 辗转相除法辗转相除法和更相减损术和更相减损术复习复习1.1.研究一个实际问题的算法，主要从哪几方面展开？研究一个实际问题的算法，主要从哪几方面展开？2.2.在程序框图中算法的基本逻辑结构有哪几种？在程序框图中算法的基本逻辑结构有哪几种？3.3.在程序设计中基本的算法语句有哪几种？在程序设计中基

2、本的算法语句有哪几种？算法步骤、程序框图和编写程序算法步骤、程序框图和编写程序三方面展开三方面展开. .顺序结构、条件结构、循环结构顺序结构、条件结构、循环结构输入语句、输出语句、赋值语句、条件语句、循环语句输入语句、输出语句、赋值语句、条件语句、循环语句情境创设 韩信是秦末汉初的著名军事家.据说有一次汉高祖刘邦在卫士的簇拥下来到练兵场,刘邦问韩信有什么方法,不要逐个报数,就能知道场上的士兵的人数,韩信先令士兵排成3列纵队,结果有2人多余,接着下令排成5列纵队,结果又多出3人,随后他又下令改为7列纵队,这次又剩下2人无法成整行.在场的人都哈哈大笑,以为韩信不能清点出准确的人数,不料笑声刚落,韩

3、信高声报告共有士兵2333人.众人听了一楞,不知道韩信用什么方法这么快就能得到正确的结果的.今天,我们将以这些古典案例的思想,设计出适宜计算机的运行程序,提高我们对基本算法结构和算法语句在实际中的运用能力.探究一,辗转相除法思考思考1:在小学中我们是如何求出两个正整数在小学中我们是如何求出两个正整数的最大公约数的呢的最大公约数的呢?算法案例算法案例之求最大公约数之求最大公约数求以下几组正整数的最大公约数。(注：若整数m和n满足n整除m，则（m,n）=n。用（m,n）来表示m和n的最大公约数。)（1）（18，30） （2）（24，16）（3）（63，63） （4）（72，8） （5）（301，1

4、33 ）解：2 1 8 2 4 用公有质因数2除， 3 9 1 2 用公有质因数3除， 3 4 3和4互质不除了。 得：18和24最大公约数是：236 例、求18与24的最大公约数：6；8；63；8；7；短除法短除法想一想，如何求8251与6105的最大公约数？ 思考思考2:2:对于对于82518251与与61056105这两个数，它们这两个数，它们的最大的最大公约数是多少？你是怎样得到的？公约数是多少？你是怎样得到的？ 由于它们公有的质因数较大，利用上述方法求由于它们公有的质因数较大，利用上述方法求最大公约数就比较困难最大公约数就比较困难. .有没有其它的方法可以较简有没有其它的方法可以较简

5、单的找出它们的最大公约数呢？单的找出它们的最大公约数呢？ 思考思考3 3：注意到：注意到8251=61058251=61051+21461+2146，那么，那么82518251与与61056105这两个数的公约数和这两个数的公约数和61056105与与21462146的公约数有的公约数有什么关系？什么关系？ 我们发现我们发现6105=21466105=21462+18132+1813，同理，同理，61056105与与21462146的公约数和的公约数和21462146与与18131813的公约数相等的公约数相等. . 思考思考4 4：重复上述操作，你能得到：重复上述操作，你能得到8251825

6、1与与61056105这这两个数的最大公约数吗？两个数的最大公约数吗？2146=18132146=18131+3331+333，148=37148=374+0.4+0.333=148333=1482+372+37，1813=3331813=3335+1485+148，8251=61058251=61051+21461+2146，6105=21466105=21462+18132+1813，定义定义:所谓的辗转相除法,就是对于给定的两个数,用较大的数除以较小的数,若余数不为零,则将余数和较小的数构成新的数对,继续上面的除法, 直到大数被小数除尽,则这是较小的数就是原来两个数的最大公约数辗转相除法

7、求两个数的最大公约数，其算法可以描述如下：辗转相除法是一个反复执行直到余数等于0停止的步骤，这实际上是一个循环结构 思考思考4 4：辗转相除直到何时结束？：辗转相除直到何时结束？主要运用的是哪种算法结构？主要运用的是哪种算法结构？如此循环，直到得到结果。 输入两个正整数m和n； 求余数r：计算m除以n，将所得余数存放到变量r中；更新被除数和余数：m=n，n=r。判断余数r r是否为0：若余数为0则输出结果，否则转向第步继续循环执行。第一步，给定两个正整数第一步，给定两个正整数m m，n(mn).n(mn).第二步，计算第二步，计算m m除以除以n n所得的余数所得的余数r. r. 第三步，第三

8、步，m=nm=n，n=r.n=r. 第四步，若第四步，若r=0r=0，则，则m m，n n的最大公约数等于的最大公约数等于m m；否则，返回第二步否则，返回第二步. . 思考思考5:5:你能把辗转相除法编成一个计算机程序吗？你能把辗转相除法编成一个计算机程序吗？程序框图程序框图开始开始输入输入m m，n n求求m m除以除以n n的余数的余数r rm=nm=nn=rn=rr=0r=0？是是输出输出m m结束结束否否INPUT mINPUT m，n nDODOr=m MOD nr=m MOD nm=nm=nn=rn=rLOOP UNTIL r=0LOOP UNTIL r=0PRINT mPRIN

9、T mENDEND 思考思考6:6:如果用当型循环结构构造算法，则用辗如果用当型循环结构构造算法，则用辗转相除法求两个正整数转相除法求两个正整数m m、n n的最大公约数的程序框的最大公约数的程序框图和程序分别如何表示？图和程序分别如何表示？开始开始输入输入m m，n n求求m m除以除以n n的余数的余数r rm=nm=nr0r0？否否输出输出m m结束结束是是n=rn=rINPUT mINPUT m，n nWHILE r0WHILE r0r=m MOD nr=m MOD nm=nm=nn=rn=rWENDWENDPRINT mPRINT mENDEND练习：用辗转相除法求下列两数的最大公约

10、数：（1）（225，135） （2）（98，196）（3）（72，168） （4）（153，119）45982417二、更相减损术二、更相减损术 九章算术九章算术是中国古代的数学专著，其中的是中国古代的数学专著，其中的“更相减损术更相减损术”也可以用来求两个数的最大公约数，也可以用来求两个数的最大公约数，即即“可半者半之，不可半者，副置分母、子之数，可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也以少减多，更相减损，求其等也.以等数约之以等数约之.”意思是：意思是： 第一步：任意给定两个正整数，判断它们是否第一步：任意给定两个正整数，判断它们是否都是偶数都是偶数. 若是，用

11、若是，用2约简；若不是，执行第二步约简；若不是，执行第二步. 第二步：以较大的数减去较小的数，接着把差第二步：以较大的数减去较小的数，接着把差与较小的数比较，并以大数减小数与较小的数比较，并以大数减小数.继续这个操作，继续这个操作，直到所得的数相等为止，则这个等数或这个数与约直到所得的数相等为止，则这个等数或这个数与约简的数的乘积就是所求的最大公约数简的数的乘积就是所求的最大公约数.例例1 1：用更相减损术求：用更相减损术求9898与与6363的最大公约数的最大公约数. .98-63=3598-63=35，14-7=7.14-7=7.21-7=1421-7=14，28-7=2128-7=21，

12、35-28=735-28=7，63-35=2863-35=28，因为因为63不是偶数，所以不是偶数，所以所以最大公约数是所以最大公约数是7. 例例2 2 分别用辗转相除法和更相减损术求分别用辗转相除法和更相减损术求168168与与9393的最大公约数的最大公约数. . 168=93168=931+751+75， 93=7593=751+181+18， 75=1875=184+34+3， 18=318=36.6.辗转相除法：辗转相除法：更相减损术更相减损术: : 168-93=75 168-93=75， 93-75=1893-75=18， 75-18=5775-18=57， 57-18=3957

13、-18=39， 39-18=2139-18=21， 21-18=321-18=3， 18-3=1518-3=15， 15-3=1215-3=12， 12-3=912-3=9， 9-3=69-3=6， 6-3=3.6-3=3.例例3 3 用更相减损术求用更相减损术求8080与与3636的最大公的最大公约数约数. . 例例4 4 求求325325，130130，270270三个数的最大公约数三个数的最大公约数. . 因为因为325=130325=1302+652+65，130=65130=652 2，所以，所以325325与与130130的最大公约数是的最大公约数是65.65. 因为因为270=6

14、5270=654+104+10，65=1065=106+56+5，10=510=52 2，所以所以6565与与270270最大公约数是最大公约数是5. 5. 故故325325，130130，270270三个数的最大公约数是三个数的最大公约数是5.5. 练习练习: :用更相减损术求两个正整数用更相减损术求两个正整数m m，n n的最大公的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？如何设计？ 第一步，给定两个正整数第一步，给定两个正整数m m，n(mn).n(mn). 第二步，计算第二步，计算m-nm-n所得的差所得的差k. k.

15、第三步，比较第三步，比较n n与与k k的大小，其中大者用的大小，其中大者用m m表示，表示，小者用小者用n n表示表示. . 第四步，若第四步，若m=nm=n，则，则m m，n n的最大公约数等于的最大公约数等于m m；否则，返回第二步否则，返回第二步. . 讨论讨论: :该算法的程序框图如何表示？该算法的程序框图如何表示？开始开始输入输入m m，n nnknk？m=nm=n是是输出输出m m结束结束mnmn？k=m-nk=m-n是是否否n=kn=km=km=k否否 讨论讨论: :该程该程序框图对应的程序框图对应的程序如何表述？序如何表述？INPUT mINPUT m，n nWHILE mW

16、HILE mn nk=m-nk=m-nIF nk THENIF nk THENm=nm=nn=kn=kELSEELSEm=km=kEND IFEND IFWENDWENDPRINT mPRINT mENDEND开始开始输入输入m m，n nnknk？m=nm=n是是输出输出m m结束结束mnmn？k=m-nk=m-n是是否否n=kn=km=km=k否否 1 1、辗转相除法、辗转相除法. . 小结小结 2 2、更相减损术、更相减损术. .布置作业：布置作业：P45P45练习：练习：1.1.P48P48习题习题1.3A1.3A组：组：1.1.1.3.2 1.3.2 秦九韶算法秦九韶算法 1 1、什

17、么是辗转相除法和更相减损术？、什么是辗转相除法和更相减损术？ 2 2、辗转相除法和更相减损术，是求两个正整、辗转相除法和更相减损术，是求两个正整数的最大公约数的优秀算法，我们将算法转化为数的最大公约数的优秀算法，我们将算法转化为程序后，就可以由计算机来执行运算，实现了古程序后，就可以由计算机来执行运算，实现了古代数学与现代信息技术的完美结合代数学与现代信息技术的完美结合. .复习复习探究三、秦九昭算法 思考思考1,在初中在初中,我们是如何求一个多项式的我们是如何求一个多项式的值的值的? 思考思考2,已知一个已知一个n 次多项式次多项式f(x)=anxn+an-1xn-1+a1x+a0当当x=x

18、0时，除时，除了用代入法求解外是否还有更好的方法呢？了用代入法求解外是否还有更好的方法呢？秦九韶算法秦九韶算法的基本思想的基本思想 思考思考1:1:对于多项式对于多项式f(x)=xf(x)=x5 5+x+x4 4+x+x3 3+x+x2 2+x+1+x+1，求，求f(5)f(5)的值的值. . 4+3+2+1=104+3+2+1=10次乘法运算，次乘法运算，5 5次加法运算次加法运算. . 分析：把分析：把5 5代入多项式，若先计算各项的值，代入多项式，若先计算各项的值，然后再相加，那么一共要做：然后再相加，那么一共要做： 思考思考2:2:另一种做法是先计算另一种做法是先计算x x2 2的值，

19、然后依的值，然后依次计算次计算x x2 2x x，(x(x2 2x)x)x x，(x(x2 2x)x)x)x)x x的的值，这样每次都可以利用上一次计算的结果，这值，这样每次都可以利用上一次计算的结果，这时一共做了：时一共做了： 4 4次乘法运算，次乘法运算，5 5次加法运算次加法运算. . 思考思考3:3:有没有更有效的算法呢？利用后一种算有没有更有效的算法呢？利用后一种算法求多项式法求多项式f(x)=af(x)=an nx xn n+a+an-1n-1x xn-1n-1+ +a+a1 1x+ax+a0 0的值，这的值，这个多项式应写成哪种形式？个多项式应写成哪种形式？f(x)=af(x)=

20、an nx xn n+a+an-1n-1x xn-1n-1+ +a+a1 1x+ax+a0 0 =(a=(an nx xn-1n-1+a+an-1n-1x xn-2n-2+ +a+a2 2x+ax+a1 1)x+a)x+a0 0=(a=(an nx xn-2n-2+a+an-1n-1x xn-3n-3+ +a+a2 2)x+a)x+a1 1)x+a)x+a0 0 = = =(=(a(an nx+ax+an-1n-1)x+a)x+an-2n-2)x+)x+a+a1 1)x+a)x+a0 0. . 这就是我国南宋时期数学家秦九韶在他的著作这就是我国南宋时期数学家秦九韶在他的著作数书九章数书九章中提

21、出的算法中提出的算法. .思考思考4:4:对于对于f(x)=(f(x)=(a(an nx+ax+an-1n-1)x+ a)x+ an-2n-2)x+)x+a+a1 1)x+a)x+a0 0，由内向外逐层计算一次多项式的值，其算法步骤如何？由内向外逐层计算一次多项式的值，其算法步骤如何？ 第一步，计算第一步，计算v v1 1=a=an nx+ax+an-1n-1. . 第二步，计算第二步，计算v v2 2=v=v1 1x+ax+an-2n-2. .第三步，计算第三步，计算v v3 3=v=v2 2x+ax+an-3n-3. . 第第n n步，计算步，计算v vn n=v=vn-1n-1x+ax+

22、a0 0. .上述方法称为秦九韶算法上述方法称为秦九韶算法. . 思考思考5:5:在秦九韶算法中，记在秦九韶算法中，记v v0 0=a=an n，那么第，那么第k k步的步的算式是什么？算式是什么？ v vk k=v=vk-1k-1x+ax+an-kn-k (k=1 (k=1，2 2，n)n)解：解：f(x)=(4x+2)x+3.5)x-2.6)x+1.7)x-0.8.f(x)=(4x+2)x+3.5)x-2.6)x+1.7)x-0.8.v v1 1=4=45+2=225+2=22；v v2 2=22=225+3.5=113.55+3.5=113.5；v v3 3=113.5=113.55-2

23、.6=564.95-2.6=564.9；v v4 4=564.9=564.95+1.7=2826.25+1.7=2826.2；v v5 5=2826.2=2826.25-0.8=14130.2.5-0.8=14130.2.所以所以f(5)= =14130.2.f(5)= =14130.2. 例例1 1 已知一个已知一个5 5次多项式为次多项式为 用秦九韶算法求用秦九韶算法求f(5)f(5)的值的值. . 8 . 07 . 16 . 25 . 3242345xxxxxxf练习：阅读下列程序，说明它解决的实际问题是什么？练习：阅读下列程序，说明它解决的实际问题是什么？INPUT INPUT “x=

24、x=”；a an=0n=0y=0y=0WHLE n5WHLE n=0WHILE i=0INPUT INPUT “ai=ai=”；a a v=v v=v* *x+ax+ai=i-1i=i-1 WEND WENDPRINT vPRINT vENDENDPRINT PRINT “i=i=”；i i小结小结 2. 2.计算机的一个很重要的特点就是运算速度快，计算机的一个很重要的特点就是运算速度快，但评价算法好坏的一个重要标志是运算的次数，如但评价算法好坏的一个重要标志是运算的次数，如果一个算法从理论上需要超出计算机允许范围内的果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这样的算法就只能是

25、一个理论算法运算次数，那么这样的算法就只能是一个理论算法. .在多项式求值的各种算法中，秦九韶算法是一个优在多项式求值的各种算法中，秦九韶算法是一个优秀算法秀算法. . 1.1.秦九韶算法计算多项式的值及程序设计秦九韶算法计算多项式的值及程序设计. . 布置作业：布置作业：P45P45练习：练习：2.2.P48P48习题习题1.3A1.3A组：组：2.2.1.3.3 K1.3.3 K进制化十进制进制化十进制 1. 1.简述辗转相除法和更相减损术的用途及内容简述辗转相除法和更相减损术的用途及内容. .2、秦九韶算法的用途及内容、秦九韶算法的用途及内容. 将这些算法转化为程序，就可以由计算机来完将

26、这些算法转化为程序，就可以由计算机来完成相关运算成相关运算. . 复习复习进位制的概念进位制的概念 进位制是为了计数和运算方便而约定的记数系进位制是为了计数和运算方便而约定的记数系统统. .约定满二进一，就是二进制；约定满二进一，就是二进制；满十进一，就是十进制；满十进一，就是十进制；七天为一周，就是七进制；七天为一周，就是七进制；十二个月为一年，就是十二进制；十二个月为一年，就是十二进制； 六十秒为一分钟，六十分钟为一个小时，就是六十秒为一分钟，六十分钟为一个小时，就是六十进制；等等六十进制；等等. . 一般地，一般地，“满几进一满几进一”就是就是几进制几进制. . 思考思考1:1:十进制使

27、用十进制使用0 09 9十个数字，那么二进制、十个数字，那么二进制、五进制、七进制分别使用哪些数字？五进制、七进制分别使用哪些数字？ 在十进制中在十进制中1010表示十，在二进制中表示十，在二进制中1010表示表示2.2.一一般地，若般地，若k k是一个大于是一个大于1 1的整数，则以的整数，则以k k为基数的为基数的k k进进制数可以表示为一串数字连写在一起的形式：制数可以表示为一串数字连写在一起的形式： a an na an-1n-1a a1 1a a0(k)0(k). . “满满K K进一进一”就是就是K K进制进制，其中，其中k k称为称为k k进制的进制的基数基数. .那么那么k k

28、是一个什么范围内的数？是一个什么范围内的数？ 与十进制类似，其它的进位制也可以按照位置原与十进制类似，其它的进位制也可以按照位置原则计数则计数. . 思考思考2 2：其中各个数位上的数字：其中各个数位上的数字a an n，a an-1n-1，a a1 1，a a0 0的取值范围如何？的取值范围如何？ 例如例如: :十进制数十进制数37213721表示的数可以写成：表示的数可以写成： 110011110011（2 2）=1=12 25 5+1+12 24 4+0+02 23 3+0+02 22 2+1+12 21 1+1+12 20 0 =51=51 56715671（8 8）=5=58 83

29、3+6+68 82 2+7+78 81 1+1+18 80 0=3001.=3001. 例例1 1：把二进制数：把二进制数110011110011（2 2）化为十进制数化为十进制数. . 练习：把八进制数练习：把八进制数 56715671（8 8）化为十进制数化为十进制数. .3 310103 3+7+710102 2+2+210101 1+1+110100 0. . 探究探究: :如何将如何将k k进制数进制数a an na an-1n-1a a1 1a a0(k)0(k)写成各数位写成各数位上的数字与基数上的数字与基数k k的幂的乘积之和的形式？的幂的乘积之和的形式？ 讨论讨论: :在二进

30、制中，在二进制中，0+00+0，0+10+1，1+01+0，1+11+1的值分的值分别是多少？别是多少？a an n a an-1n-1a a1 1a a0(k) 0(k) = a= an nk kn n+ a+ an-1n-1k kn-1n-1+ + + a+ a1 1k k1 1+ a+ a0 0k k0 0 例例2:2:二进制数二进制数110011110011（3 3）化为十进制数是什么数？化为十进制数是什么数？ 110011110011（3 3）讨论讨论: : an an-1a1a0(2) 中a ai i化为十进制数是什么数？化为十进制数是什么数？=1=13 35 5+1+13 34

31、4+0+03 33 3+0+03 32 2+1+13 31 1+1+13 30 0 =243+81+3+1=243+81+3+1=328. =328. a ai i2 2i-1i-1 练习：将下列各进制数化为十进制数练习：将下列各进制数化为十进制数. .（1 1）1030410304（4 4） ； （2 2）43214321（5 5）. .1030410304（4 4）=1=14 44 4+3+34 42 2+4+44 40 0=308.=308.43214321（5 5）=4=45 53 3+3+35 52 2+2+25 51 1+1+15 50 0=586. =586. 探究：如何改进上述

32、算法，把其他进位制化为十探究：如何改进上述算法，把其他进位制化为十进制数？请举例说明进制数？请举例说明. . 例例3:3:设计一个算法，把设计一个算法，把2 2进制数进制数a a（共有（共有n n位）化位）化为十进制数为十进制数b b，并转化成程序框图，写出程序，并转化成程序框图，写出程序. . 第二步，令第二步，令b=0b=0，i=1.i=1. 第四步，判断第四步，判断in in 是否成立是否成立. .若是，则执行第五若是，则执行第五步；否则，返回第三步步；否则，返回第三步. .第一步，输入第一步，输入a a，2 2和和n n的值的值. . 第三步，第三步，b=b+ab=b+ai i2 2i

33、-1i-1，i=i+1.i=i+1.第五步，输出第五步，输出b b的值的值. . 练习练习: :设计一个算法，把设计一个算法，把k k进制数进制数a a（共有（共有n n位）位）化为十进制数化为十进制数b.b.第二步，令第二步，令b=0b=0，i=1.i=1.第四步，判断第四步，判断in in 是否成立是否成立. .若是，则执行第五步；若是，则执行第五步；否则，返回第三步否则，返回第三步. .第一步，输入第一步，输入a a，k k和和n n的值的值. .第三步，第三步，b=b+ab=b+ai ik ki-1i-1，i=i+1.i=i+1.第五步，输出第五步，输出b b的值的值. .开始开始输入

34、输入a a，k k，n nb=0b=0i=1i=1把把a a的右数第的右数第i i位数字赋给位数字赋给t tb=b+tb=b+tk ki-1i-1i=i+1i=i+1in?in?结束结束是是输出输出b b否否程序框图程序框图INPUT INPUT “a a，k k，n=n=”;a,k,n;a,k,nb=0b=0i=1i=1t=a MOD 10t=a MOD 10DODOb=b+tb=b+t* *k k（i-1i-1）a=a10a=a10t=a MOD 10t=a MOD 10i=i+1i=i+1LOOP UNTIL inLOOP UNTIL inPRINT bPRINT bENDEND开始开始

35、输入输入a a，k k，n nb=0b=0i=1i=1把把a a的右数第的右数第i i位数字赋给位数字赋给t tb=b+tb=b+tk ki-1i-1i=i+1i=i+1in?in?结束结束是是输出输出b b否否 例例4 4：已知：已知20a120a1（2 2）=b10=b10（3 3）, ,求数字求数字a a，b b的值的值. .所以所以2a+17=9b+32a+17=9b+3，即，即9b-2a=14. 9b-2a=14. 20a120a1（2 2）=2=22 23 3+a+a2+1=2a+17.2+1=2a+17.b10b10（3 3）=b=b3 32 2+1+13=9b+3.3=9b+3

36、.故故a=2a=2，b=2. b=2. 1 1、k k进制数使用进制数使用0 0（k-1k-1）共）共k k个数字，但左个数字，但左侧第一个数位上的数字（首位数字）不为侧第一个数位上的数字（首位数字）不为0.0.小结小结 2 2、用、用 表示表示k k进制数，其中进制数，其中k k称为基数，十进制数一般不标注基数称为基数，十进制数一般不标注基数. .a an n a an-1n-1a a1 1a a0(k) 0(k) 3 3、把、把k k进制数化为十进制数的一般算式是：进制数化为十进制数的一般算式是：a an n a an-1n-1a a1 1a a0(k) 0(k) = a= an nk k

37、n n+ a+ an-1n-1k kn-1n-1+ + + a+ a1 1k k1 1+ a+ a0 0k k0 0布置作业：布置作业：P48P48习题习题1.3B1.3B组：组：1.1.1.3.4 1.3.4 十进制化十进制化K K进制进制1 1、“满几进一满几进一”就是几进制就是几进制. .2 2、k k进制使用进制使用0 0，1 1，k-1k-1这这k k个数字个数字. .3 3、k k进制数化为十进制数的一般算式进制数化为十进制数的一般算式: :a an n a an-1n-1a a1 1a a0(k) 0(k) = a= an nk kn n+ a+ an-1n-1k kn-1n-1

38、+ + + a+ a1 1k k1 1+ a+ a0 0k k0 0 复习复习4 4、利用、利用k k进制数化十进制数的一般算式，可以进制数化十进制数的一般算式，可以构造算法，设计程序，通过计算机就能把任何构造算法，设计程序，通过计算机就能把任何一个一个k k进制数化为十进制数进制数化为十进制数. .练习练习: :把二进制数把二进制数100101100101（2 2）化为十进制数化为十进制数. .100101100101（2 2）=2=25 5+2+22 2+1=37. +1=37. 讨论讨论: :怎样把十进制数怎样把十进制数8989化为二进制数？化为二进制数？例例1:1:把十进制数把十进制数

39、8989化为二进制数化为二进制数. .观察下面的算式你有什么发现吗？观察下面的算式你有什么发现吗？ 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+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连续去连续去除除8989或所得商，然后取余数或所得商，然后取余数. . 2 21 12 22 22 25 50 02 211112 222

40、222 244442 289891 10 00 01 11 10 01 1余数余数例例1:1:把十进制数把十进制数8989化为二进制数化为二进制数. . 上述化十进上述化十进制数为二进制数制数为二进制数的算法叫做的算法叫做除除2 2取余法取余法. . 练习练习: :把十进制数把十进制数196196化为五进制数化为五进制数. . 除二取余法也可以推广为把十进制数化为除二取余法也可以推广为把十进制数化为k k进进制数的算法，称为制数的算法，称为除除k k取余法取余法. .0 05 51 15 57 75 539395 51961961 14 42 21 1余数余数196=1241196=1241（

41、5 5）若十进制数若十进制数a a除以除以k k所得的商是所得的商是q q0 0，余数是，余数是r r0 0， 即即a=ka=kq q0 0+ r+ r0 0； q q0 0除以除以k k所得的商是所得的商是q q1 1，余数是，余数是r r1 1， 即即q q0 0=k=kq q1 1+ r+ r1 1； q qn-1n-1除以除以k k所得的商是所得的商是0 0，余数是，余数是r rn n， 即即q qn-1n-1= r= rn n，那么十进制数那么十进制数a a化为化为k k进制数是：进制数是：a=ra=rn nr rn-1n-1r r1 1r r0(2)0(2)推广：怎样把十进制数转化为推广：怎样把十进制数转化为k k进制数？进制数？ 例例2:2:根据上面的分析，将十进制数根据上面的分析，将十进制数a a化为二进化为二进制数的算法步骤如何设计？制数的算法步骤如何设计？ 第四步，若第四步，若q0q0，则，