5进制转换

目录第5章进制转换问题.....................................................................................................................25.1基础知识............................................................................................................................25.1.1相关概念.................................................................................................................25.1.2各种常见的进制.....................................................................................................25.1.3进制转换.................................................................................................................35.2例5001特殊的四位数.....................................................................................................55.3例5002进制转换.............................................................................................................75.4例5003skew数................................................................................................................85.5例5004周易...................................................................................................................105.6例5005奶牛计算器.......................................................................................................125.7例5006计算器设计.......................................................................................................145.8例5007回文数...............................................................................................................17第5章进制转换问题5.1基础知识5.1.1相关概念1．数制数制是人们利用符号进行计数的一种科学方法。数制也称为计数制，是用一组固定的符号和统一的规则来表示数值的方法。2．进制进制也就是进位制，是人们规定的一种进位方法。对于任何一种进制——X进制，就表示某一位置上的数运算时是逢X进一位。十进制是逢十进一，十六进制是逢十六进一，二进制就是逢二进一。3．数码数制中表示基本数值大小的不同数字符号。例如，十进制有10个数码：0、1、2、3、4、5、6、7、8、9。4．基数数制所使用数码的个数。例如，二进制的基数为2；十进制的基数为10。5．位权位权表示数的符号在不同的位置上时所代表的值是不同的。也就是数制中某一位上的1所表示数值的大小（所处位置的价值）。例如，十进制的123，1的位权是100，2的位权是10，3的位权是1。5.1.2各种常见的进制人们通常采用的进制有十进制、二进制、八进制和十六进制等。1．十进制（Decimal）十进制是人们日常生活中最熟悉的进位计数制。在十进制中，数码共有0，1，2，3，4，5，6，7，8，9这十个符号。计数规则是逢十进一。2．二进制（Binary）二进制是在计算机系统中采用的进位计数制。二进制数有两个特点：在二进制中，数码只有0和1两个符号。计数规则是逢二进一。为区别于其它进制数，二进制数的书写通常在数的右下方注上基数2，或在后面加上B表示。例如：二进制数10110011可以写成（10110011）2，或写成10110011B。3．八进制数（Octal）由于二进制数据的基数比较小，所以二进制数据的书写和阅读很不方便，为此，在小型机中引入了八进制。八进制的基数R=8=23，有数码0、1、2、3、4、5、6、7，并且每个数码正好对应三位二进制数，所以八进制能很好地反映二进制。八进制用下标8或数据后面加O表示例如：二进制数据（11101010.010110100）2，对应的八进制数据(352.264)8或352.264O。4．十二进制（Duodecimal）十二进制在生活中也是经常用到的，例如，长度单位一英尺等于12英寸，一先令等于12便士，就连足球比赛罚点球的英制长度也是12码。此外还有一打12个，钟表转一圈12小时等等。一般在十二进制中，10和11可用M和N表示，有时候也可用A和B表示。5．十六进制（Hexadecimal）十六进制是人们在计算机指令代码和数据的书写中经常使用的数制。在十六进制中，由十六个字符0～9以及A，B，C，D，E，F（或a，b，…，f）组成（它们分别表示十进制数10～15）来描述。计数规则是逢十六进一，即基数R=16=24，通常在表示时用尾部标志H或下标16以示区别。例如：十六进制数4AC8可写成（4AC8）16，或写成4AC8H。6．六十进位制数（Sexagesimal）古代人由于生产劳动的需要，要研究天文和历法，就牵涉到时间和角度了。因为历法需要的精确度较高，时间的单位小时，角度的单位度都嫌太大。必须进一步研究他们的小数。它们的小数都具有这样的性质：使1/2，1/3，1/4，1/5，1/6等都能成为他的整数倍。以1/60作为单位，就正好具有这个性质。譬如：1/2等于30个1/60，1/3等于20个1/60，1/4等于15个1/60……这种小数的进位制在表示有些数时很方便。例如常遇到的1/3，在十进位制中要变成无限小数，但在这种进位制中就是一个整数。因此就出现了六十进制。5.1.3进制转换在实际运算中，我们经常用到各种不同的进制，这就需要在各种数制之间进行转换。1．其他进制转换为十进制（按权求和）方法是：将其它进制按权位展开，然后各项相加，就得到相应的十进制数。例1：N=（10110.101）B=（？）D按权展开N=1*24+0*23+1*22+1*21+0*20+1*2-1+0*2-2+1*2-3=16+4+2+0.5+0.125=（22.625）D例2：(38A.11)16转换为十进制数(38A.11)16=3×162+8×161+10×160+1×16-1+1×16-2=768+128+10+0.0625+0.0039=906.06642．十进制转换成其它进制方法是：分两部分分别进行的，即整数部分和小数部分。（1）整数部分：（基数除法）把我们要转换的数除以新的进制的基数，把余数作为新进制的最低位；把上一次得到的商再除以新的进制基数，把余数作为新进制的次低位；继续上一步，直到最后的商为零，这时的余数就是新进制的最高位。（2）小数部分：（基数乘法）把要转换数的小数部分乘以新进制的基数，把得到的整数部分作为新进制小数部分的最高位。把上一步得的小数部分再乘以新进制的基数，把整数部分作为新进制小数部分的次高位；继续上一步，直到小数部分变成零为止。或者达到预定的精度要求或位数要求也可以。3．二进制与八进制、十六进制的相互转换二进制转换为八进制、十六进制：它们之间满足23和24的关系，因此把要转换的二进制从低位到高位每3位或4位一组，高位不足时在有效位前面添“0”，然后把每组二进制数转换成八进制或十六进制即可。八进制、十六进制转换为二进制时，把上面的过程逆过来即可。也就是把一个八或十六进制位转换为3或4个二进制位。例3：N=（C1B）H=（？）B（C1B）H=1100/0001/1011=（110000011011）B4．数制转换的一般化（1）R进制转换成十进制任意R进制数按权展开，相加即可得十进制数据。例如：N=1101.0101B=1*23+1*22+0*21+1*20+0*2-1+1*2-2+0*2-3+1*2-4=8+4+0+1+0+0.25+0+0.0625=13.3125N=5A.8H=5*161+A*160+8*16-1=80+10+0.5=90.5（2）十进制转换R进制十进制数转换成R进制数，须将整数部分和小数部分分别转换。整数转换——除R取余法，规则：①用R去除给定的十进制数的整数部分，取其余数作为转换后的R进制数据的整数部分最低位数字；②再用R去除所得的商，取其余数作为转换后的R进制数据的高一位数字；③重复执行②操作，直到商为0结束。小数转换——乘R取整法，规则：①用R去乘给定的十进制数的小数部分，取乘积的整数部分作为转换后R进制小数点后第一位数字；②再用R去乘上一步乘积的小数部分，然后取新乘积的整数部分作为转换后R进制小数的低一位数字；②重复②操作，一直到乘积为0，或已达到精度要求或位数要求为止。解决数制转换问题时，如果所给的数值不是用十进制表示的，一般用一个字符型数组来存放。数组的每个元素分别存储它的一位数字。然后按位转换求和，得到十进制表示；再把十进制表示转换成所求的数制表示。转换的结果也用一个字符型数组表示，每个元素表示转换结果的一位数字。根据数制表示中相邻位的基数关系，可以把不同的数制分成两类。一类数制表示中，相邻位的基数是等比关系，例如我们熟悉的十进制表示。另一类数制表示中，相邻位的基数是不等比的。例如在时间表示中，从秒到分采用60进进制；从月到年则采用12进制。把一个数值从数制B的表示bmbm-1bm-2...b1转换成十进制表示dndn-1dn-2...d1比较简单。假设数制B中，第i位的基数为basei(1=i=m)，直接把basei与bi相乘，然后对全部乘积求和。从十进制表示dndn-1dn-2...d1到bmbm-1bm-2...b1的转换需要分两种情况考虑：数制B中相邻数字的基数是等比关系，即：basei(1=i=m)可以表示成Ci-1，其中C是一个常量。将dndn-1dn-2...d1除以C，余数即为b1；将dndn-1dn-2...d1和C相除的结果再除以C，余数即为b2；…；直至计算出为bm止。数制B中相邻数字的基数不等比。需要先判断dndn-1dn-2...d1在数制B中需要的位数m，然后从高位到低位依次计算bm、bm-1、bm-2、...、b1。5.2例5001特殊的四位数（来源：acm.zju.edu.cn2405/poj.org2196）问题描述：找出并输出所有的4位数（十进制数）中具有如下属性的数：四位数字之和等于其十六进制形式各位数字之和，也等于其十二进制形式各位数字之和。例如：十进制数2991，其四位数字之和2+9+9+1=21。由于2991=1*1728+8*144+9*12+3，其十二进制形式为1893(12),其各位数字之和也为21。但是它的十六进制形式为BAF(16)，其各位数字之和等于11+10+