1、1.3 算法案例算法案例 1.3.31.3.3进位制进位制 1、什么是进位制？2、最常见的进位制是什么？除此之外还有哪些常见的进位制？请举例说明问题一问题一 进位制是为了计数和运算方便而约进位制是为了计数和运算方便而约定的记数系统定的记数系统.如常见：逢十进一，就是十进制；如常见：逢十进一，就是十进制；每七天为一周，就是七进制；每十二个每七天为一周，就是七进制；每十二个月为一年，就是十二进制，每六十秒为月为一年，就是十二进制，每六十秒为一分钟，每六十分钟为一个小时，就是一分钟，每六十分钟为一个小时，就是六十进制；等等六十进制；等等.一般地，一般地，“满满k进一进一”就是就是k进制进制，其中，其
2、中k称为称为k进制的进制的基数基数.那那么么k是一个什么范围内的数？是一个什么范围内的数？我们了解十进制吗？所谓的十进制，我们了解十进制吗？所谓的十进制，它是如何构成的？它是如何构成的？十进制由两个部分构成十进制由两个部分构成例如：例如：372101231011021071037213其它进位制的数又是如何的呢？其它进位制的数又是如何的呢？第一、它有第一、它有0、1、2、3、4、5、6、7、8、9十个数字；十个数字；第二、它有第二、它有“权位权位”，即，即从右往左从右往左为个位、十位、为个位、十位、百位、千位等等。百位、千位等等。(用用10个数字来记数，称个数字来记数，称基数基数为为10)表示
3、有：表示有：1个个1，2个十，个十，7个百即个百即7个个10的平方，的平方，3个千即个千即3个个10的立方的立方问题二问题二二进制可使用的数字有二进制可使用的数字有0和和1,基数是基数是2;十六进制可使用的数字或符号有十六进制可使用的数字或符号有09等等10个数字个数字以及以及AF等等6个字母个字母(规定字母规定字母AF对应对应1015),十六进制的基数是十六进制的基数是16.注意注意:为了区分不同的进位制为了区分不同的进位制,常在数字常在数字的右下脚标明基数的右下脚标明基数,.,.如如111001111001(2)(2)表示二进制数表示二进制数,34,34(5)(5)表示表示5 5进制数进制
4、数.十进制数一般不标注基数十进制数一般不标注基数.十进制数十进制数3721中的中的3表示表示3个千个千,7表示表示7个个百百,2表示表示2个十个十,1表示表示1个一个一,从而它可以写成下从而它可以写成下面的形式面的形式:3721=3103+7102+2101+1100.想一想二进制数想一想二进制数1011(2)可以类似的写成什可以类似的写成什么形式么形式?1011(2)=123+022+121+120.同理同理:3421(5)=353+452+251+150.C7A16(16)=12164+7163+10162 +1161+6160.一般地一般地,若若k是一个大于是一个大于1的整数的整数,那么
5、以那么以k为为基数的基数的k进制数可以表示为一串数字连写在一进制数可以表示为一串数字连写在一起的形式起的形式anan-1a1a0(k)(0ank,0an-1,a1,a0n in 是否成立是否成立.若是，则输若是，则输 出出b b的值；否则，返回第三步的值；否则，返回第三步.第一步，输入第一步，输入a a和和n n的值的值.第三步，第三步，i=i+1.i=i+1.12iibba-=+?思考思考3:3:按照上述思路，把按照上述思路，把k k进制数进制数 化为十进制数化为十进制数b b的算法的算法步骤如何设计？步骤如何设计？12 1()nnkaa aa a-=L第四步，判断第四步，判断in in 是
6、否成立是否成立.若是，则若是，则输出输出b b的值；否则，返回第三步的值；否则，返回第三步.第一步，输入第一步，输入a a，k k和和n n的值的值.第二步，令第二步，令b=0b=0，i=1.i=1.第三步，第三步，i=i+1.i=i+1.1iibbak-=+?思考思考4:4:上述把上述把k k进制数进制数 化为十进制数化为十进制数b b的算法的程的算法的程序框图如何表序框图如何表示？示？12 1()nnkaa aa a-=L开始开始输入输入a，k，nb=0i=1把把a的右数第的右数第i位数字赋给位数字赋给tb=b+tki-1i=i+1in?结束结束是是输出输出b否否思考思考5:5:该程序框图
7、对应的程序如何表述？该程序框图对应的程序如何表述？开始开始输入输入a，k，nb=0i=1把把a的右数第的右数第i位数字赋给位数字赋给tb=b+tki-1i=i+1in?结束结束是是输出输出b否否INPUT aINPUT a，k k，n nb=0b=0i=1i=1t=a MOD10t=a MOD10DODOb=b+tb=b+t*k k（i-1i-1）a=a/10a=a/10t=a MOD10t=a MOD10i=i+1i=i+1LOOP UNTIL iLOOP UNTIL in nPRINT bPRINT bENDEND思考思考6:6:利用除利用除k k取余法，将十进制数取余法，将十进制数a a
8、化化为为k k进制数的算法步骤如何设计？进制数的算法步骤如何设计？第四步，若第四步，若q0q0，则，则a=qa=q，返回第二步；，返回第二步；否则，输出全部余数否则，输出全部余数r r排列得到排列得到 的的k k进制数进制数.第一步，输入十进制数第一步，输入十进制数a a和基数和基数k k的值的值.第二步，求出第二步，求出a a除以除以k k所得的商所得的商q q，余数，余数r.r.第三步，把所得的余数依次从右到左排第三步，把所得的余数依次从右到左排 列列.思考思考7:7:将除将除k k取余法的算法步骤用程序框取余法的算法步骤用程序框图如何表示？图如何表示？开始开始输入输入a，k求求a除以除以
9、k的商的商q求求a除以除以k的余数的余数r把所得的余数依次从右到左排列把所得的余数依次从右到左排列a=qq=0？结束结束输出全部余数输出全部余数r排排列得到的列得到的k k进制数进制数是是否否思考思考8:8:该程序框图对应的程序如何表述？该程序框图对应的程序如何表述？开始开始输入输入a，k求求a除以除以k的商的商q求求a除以除以k的余数的余数r把所得的余数依次从右到左排列把所得的余数依次从右到左排列a=qq=0？结束结束输出全部余数输出全部余数r排排列得到的列得到的k k进制数进制数是是否否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
