《133《算法案例——进位制》（新人教A版必修3）》由会员分享，可在线阅读，更多相关《133《算法案例——进位制》（新人教A版必修3）（33页珍藏版）》请在金锄头文库上搜索。
1、v主讲老师 潘学国 提出问题提出问题人们为了计数和运算方人们为了计数和运算方便，约定了各种进位制，便，约定了各种进位制，这些进位制是什么概念，这些进位制是什么概念，它们与十进制之间是怎它们与十进制之间是怎样转化的？对此，我们样转化的？对此，我们从理论上作些了解和研从理论上作些了解和研究究. . 进位制是人们为了计数和运算方便而约定的记数进位制是人们为了计数和运算方便而约定的记数系统，如满二进一，就是二进制；满十进一，就是十系统，如满二进一，就是二进制；满十进一，就是十进制；每七天为一周，就是七进制；每十二个月为一进制；每七天为一周，就是七进制；每十二个月为一年，就是十二进制，每六十秒为一分钟，
2、每六十分钟年，就是十二进制，每六十秒为一分钟，每六十分钟为一个小时，就是六十进制；等等。一般地，为一个小时，就是六十进制；等等。一般地，“满几满几进一进一”就是几进制，几进制的基数就是几。就是几进制，几进制的基数就是几。 进位制进位制基数都是大于基数都是大于1 1的整数的整数。思考：思考：基数的范围是什么？基数的范围是什么？ 二进制可使用的数字有二进制可使用的数字有0和和1，基数是，基数是2； 八进制可使用的数字有八进制可使用的数字有07，基数是，基数是8； 十六进制可使用的数字或符号有十六进制可使用的数字或符号有09等等10个数字个数字以及以及AF等等6个字母个字母(规定字母规定字母AF对应
3、对应1015)，十六进，十六进制的基数是制的基数是16. 等等。等等。思考：思考：十进制使用十进制使用09十个数字，那么其它进制分别十个数字，那么其它进制分别使用哪些数字？使用哪些数字？ 计数时，几个数字排成一行，从右起，位数依次计数时，几个数字排成一行，从右起，位数依次增大。增大。 注意：为了区分不同的进位制注意：为了区分不同的进位制, ,常在数字的右下常在数字的右下角标明基数角标明基数. . 如如111001111001(2)(2)表示二进制数表示二进制数,34,34(5)(5)表示表示5 5进制数进制数. .十进制数一般不标注基数十进制数一般不标注基数.思考：思考：k进制如何计数？进制如
4、何计数？ 思考：思考：一般地，若一般地，若k是一个大于是一个大于1的整数，则以的整数，则以k为基为基数的数的k进制数可以表示为一串数字连写在一起的形式：进制数可以表示为一串数字连写在一起的形式： anan-1a1a0(k). 其中各个数位上的数字其中各个数位上的数字an，an-1，a1，a0的的取值范围如何？取值范围如何？ an，an-1， a1，a0 N，0ank，0an-1， a1，a0 n in 是否成立是否成立. .若是，则输出若是，则输出b b的值；否的值；否则，返回第三步则，返回第三步. .第一步，输入第一步，输入a a，k k和和n n的值；的值；第二步，令第二步，令b=0b=0
5、，i=1i=1；思考：思考：如何改进上述算法，把如何改进上述算法，把k进制数进制数anan-1a1a0(k)化化为十进制数？为十进制数？第三步，第三步，b=b+ab=b+ai*ki-1 ，i=i+1；例例2：设计一个算法，把设计一个算法，把k进制数进制数a（共有（共有n位）化为十位）化为十进制数进制数b？开始开始输入输入a，k，nb=0i=1把把a a的右数第的右数第i i位数字赋给位数字赋给t tb=b+tki-1i=i+1in?结束结束是是输出输出b否否程序框图：程序框图：程序：程序：INPUT a，k，nb=0i=1t=a MOD10DOb=b+t*k （i-1）a=a10t=a MOD
6、10i=i+1LOOP UNTIL inPRINT bEND例例3：已知已知10b1（2）=a02（3），求数字，求数字a，b的值的值.所以所以2b+9=9a+22b+9=9a+2，即，即9a-2b=79a-2b=7. 10b1（2）=123+b2+1=2b+9.a02（3）=a32+2=9a+2.故故a=1，b=1. 利用利用k k进制数化十进制数的一般算式，可进制数化十进制数的一般算式，可以构造算法，设计程序，通过计算机就能把以构造算法，设计程序，通过计算机就能把任何一个任何一个k k进制数化为十进制数。在实际应用进制数化为十进制数。在实际应用中，我们还需要把任意一个十进制数化为中，我们还
7、需要把任意一个十进制数化为k k进进制数的算法，对此，我们作些理论上的探讨。制数的算法，对此，我们作些理论上的探讨。例例4：把把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=52+1,
8、5=22+1, 可以用可以用2连续去除连续去除89或所得商或所得商(一直到商为一直到商为0为止为止)，然后取余数，然后取余数 - 除除2取余法取余法.2=12+0, 1=02+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).44 1我们可以用下面的除法算式表示除我们可以用下面的除法算式表示除2取余法取余法：289 余数余数222 0211 0
9、25 122 121 020 1 把算式中各步所得的余数把算式中各步所得的余数从从下到上排列下到上排列，得到，得到89=1011001(2). 这种方法也可以推广为这种方法也可以推广为把十进制数化为把十进制数化为k进制数的算进制数的算法法,称为称为除除k取余法取余法.练习：练习：将十进制数将十进制数458458分别转化为四进制数和六进制数分别转化为四进制数和六进制数. .041474284114445822031余数余数06261267664582402余数余数458=13022（4）=2042（6）练习练习：十进制数十进制数8910化为化为十六十六进制数是什么数？进制数是什么数？016216
10、3416556168910141222余数余数8910=22CE（16）算法分析：算法分析：若十进制数若十进制数a除以除以k所得的商是所得的商是q0，余数，余数是是r0，即，即a=kq0+ r0，则，则r0是是a的的k进制数的右边数第进制数的右边数第1位数；若位数；若q0除以除以k所得的商是所得的商是q1，余数是，余数是r1，即，即q0=kq1+ r1，则则r1是是a的的k进制数的右边数进制数的右边数第第2位数位数； qn-1除以除以k所得的商是所得的商是0，余数是，余数是rn，即，即qn-1= rn，则则rn是是a的的k进制数进制数的的左左边边数数第第1位数位数. 即：即：a=rnrn-1r
11、1r0(k)例例5：设计一个程序，实现设计一个程序，实现“除除k取余法取余法”（k N，2k 9）. .算法步骤：算法步骤：第四步，若第四步，若q0q0，则，则a=qa=q，返回第二步；否则，输出全，返回第二步；否则，输出全部余数部余数r r排列得到的排列得到的k k进制数进制数. .第一步，输入十进制数第一步，输入十进制数a a和基数和基数k k的值的值.第二步，求出第二步，求出a a除以除以k k所得的商所得的商q q，余数，余数r r.第三步，把所得的余数依次从右到左排列第三步，把所得的余数依次从右到左排列.程序框图：程序框图： 开始开始输入输入a，k求求a a除以除以k k的商的商q
12、q求求a a除以除以k k的余数的余数r r把所得的余数依次从右到左排列把所得的余数依次从右到左排列a=qq=0？结束结束输出全部余数输出全部余数r r排排列得到的列得到的k k进制数进制数是是否否程序：程序：INPUT a，kb=0i=0DOq=akr=a MOD kb=b+r*10 ii=i+1a=qLOOP UNTIL q=0PRINT bEND例例6：将五进制数将五进制数30241（5）转化为七进制数转化为七进制数. 30241（5）=354+252+45+1=1946. 0757397278719460545余数余数30241（5）=5450（7） 课时小结课时小结: : 1. k进
13、制数使用进制数使用0（k-1）共）共k个数字，个数字，但左侧第一个数位上的数字（首位数字）不但左侧第一个数位上的数字（首位数字）不为为0. 2.用用 表示表示k进进制数，其中制数，其中k称为基数，十进制数一般不标称为基数，十进制数一般不标注基数注基数. 3. 把把k进制数化为十进制数的一般算式是：进制数化为十进制数的一般算式是：课时小结课时小结: : 1.利用除利用除k取余法，可以把任取余法，可以把任何一个十进制数化为何一个十进制数化为k进制数，并进制数，并且操作简单、实用且操作简单、实用. 2.通过通过k进制数与十进制数的进制数与十进制数的转化，我们也可以将一个转化，我们也可以将一个k进制数进制数转化为另一个不同基数的转化为另一个不同基数的k进制数进制数.1： P48 A组组 3（1）（）（3）2：资料：资料作业布置作业布置
