算法与程序实践习题解答数制转换.doc

目 录 CS21：特殊的四位数 1 CS22：确定进制 3 CS23：skew数 5 CS24：十进制到八进制 7 CS25：八进制到十进制 9 CS26：二进制转化为十六进制 10 CS27：八进制小数（也属于高精度计算） 13 CS28：二进制数 17 CS29：回文数（Palindrom Numbers） 19 CS210：设计计算器（Basically Speaking） 21 CS211： 24 《算法与程序实践》习 题 解 答2——数制转换 解决数制转换问题时，如果所给的数值不是用十进制表示的，一般用一个字符型数组来存放。数组的每个元素分别存储它的一位数字。然后按位转换求和，得到十进制表示；再把十进制表示转换成所求的数制表示。转换的结果也用一个字符型数组表示，每个元素表示转换结果的一位数字。 根据数制表示中相邻位的基数关系，可以把不同的数制分成两类。一类数制表示中，相邻位的基数是等比关系，例如我们熟悉的十进制表示。另一类数制表示中，相邻位的基数是不等比的。例如在时间表示中，从秒到分采用60进进制；从月到年采用12进制。把一个数值从数制B的表示bmbm-1b m-2 ... b1 转换成十进制表示dnd n-1d n-2 ... d1 比较简单。假设数制B中，第i位的基数为basei(1=i=m)，直接把basei与bi 相乘，然后对全部乘积求和。从十进制表示dnd n-1d n-2 ... d1 到bmbm-1b m-2 ... b1 的转换需要分两种情况考虑： ?数制B 中相邻数字的基数是等比关系，即：basei(1=i=m)可以表示成Ci-1 ，其中C是一个常量。将dnd n-1d n-2 ... d1 除以C，余数即为b1；将dnd n-1d n-2 ... d1 和C 相除的结果再除以C，余数即为b2；… ；直至计算出为bm 止。 ?数制B 中相邻数字的基数不等比。需要先判断dnd n-1d n-2 ... d1 在数制B 中需要的位数m，然后从高位到低位依次计算bm、bm-1 、b m-2 、...、b1。 CS21：特殊的四位数 （来源：POJ 2196 ZOJ 2405程序设计方法及在线实践指导（王衍等）例3.4，P140） 问题描述： 找出并输出所有的4位数（十进制数）中具有如下属性的数：四位数字之和等于其十六进制形式各位数字之和，也等于其十二进制形式各位数字之和。 例如：十进制数2991，其四位数字之和2+9+9+1 = 21。由于2991 = 1*1728 + 8*144 + 9*12 + 3, 其十二进制形式为1893(12), 其各位数字之和也为21.但是它的十六进制形式为BAF(16)，其各位数字之和等于11+10+15 = 36。因此你的程序要舍去2991这个数据。 下一个数2992，其十进制、十二进制、十六进制形式各位数字之和均为22，因此2992符合要求，应该输出来。（只考虑4位数，2992是第一个符合要求的数） 输入： 本题没有输入。 输出： 你的程序要求输出2992及其他更大的、满足要求的四位数（要求严格按升序输出），每个数占一行（前后都没有空行），整个输出以换行符结尾。输出中没有空行。输出中的前几行如样例输出所示。 样例输入： 本题没有输入。 样例输出： 2992 2993 2994 2995 2996 2997 2998 2999 ... 解题思路： 该题在求解时要用到枚举的算法思想，即枚举所有的四位数（1000-9999），判断其是否满足十六进制、十二进制和十进制形式的各位数之和相等。 这里要注意进制转换方法。将一个十进制数Num转换到M进制，其方法是：将Num除以M取余数，直到商为0为止，存储得到的余数，先得到的余数为低位，后得到的余数为高位进行排序，余数0不能舍去。由于此题需要得到Num在16、12和10进制下各位的和，所以只要累加其余数即可。 参考程序： #include stdio.h int main() { int Num,tmp; for(Num=1000;Num=9999;Num++) { int s16=0,s12=0,s10=0; tmp=Num; while(tmp) //求其十六进制的和 { s16+=tmp%16; tmp/=16; } tmp=Num; while(tmp) //求十二进制的和 { s12+=tmp%12; tmp/=12; } if(s16!=s12) continue; tmp=Num; while(tmp) { s10+=tmp%10; tmp/=10; } if(s16==s10) pri