算法与程序实践习题解答2（数制转换）

目 录

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)可以表示成C

i-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

1

2995 2996 2997 2998 2999 ...

解题思路： 该题在求解时要用到枚举的算法思想，即枚举所有的四位数（1000-9999），判断其是否满足十六进制、十二进制和十进制形式的各位数之和相等。 这里要注意进制转换方法。将一个十进制数Num转换到M进制，其方法是：将Num除以M取余数，直到商为0为止，存储得到的余数，先得到的余数为低位，后得到的余数为高位进行排序，余数0不能舍去。由于此题需要得到Num在16、12和10进制下各位的和，所以只要累加其余数即可。

参考程序：

#include

int main() { int Num,tmp; for(Num=1000;Num<=9999;Num++) { int s16=0,s12=0,s10=0; tmp=Num; while(tmp) //求其十六进制的和 { s16+=tmp; tmp/=16; } tmp=Num; while(tmp) //求十二进制的和 { s12+=tmp; tmp/=12; } if(s16!=s12) continue; tmp=Num; while(tmp) { s10+=tmp; tmp/=10; } if(s16==s10) printf(\ }

2

}

return 0;

CS22：确定进制

（来源：poj.grids.cn 2972，程序设计导引及在线实践（李文新）例3.1 P98） 问题描述：

6*9 = 42 对于十进制来说是错误的，但是对于13进制来说是正确的。即, 6(13) * 9(13) = 42(13)， 而 42(13) = 4 * 131 + 2 * 130 = 54(10)。 你的任务是写一段程序读入三个整数p、q和r，然后确定一个进制B(2<=B<=16) 使得 p * q = r。如果 B有很多选择，输出最小的一个。例如：p = 11，q = 11，r = 121。则有 11(3) * 11(3) = 121(3) 因为 11(3) = 1 * 31 + 1 * 30 = 4(10) 和 121(3) = 1 * 32 + 2 * 31 + 1 * 30 = 16(10)。 对于进制10。有 11(10) * 11(10) = 121(10)。这种情况下，应该输出3。如果没有合适的进制，则输出0。 输入：

输入有T组测试样例。 T在第一行给出。每一组测试样例占一行，包含三个整数p、q、r。p、q、r的所有位都是数字，并且1 <= p、q、r <= 1,000,000。 输出：

对于每个测试样例输出一行。该行包含一个整数：即使得p * q = r成立的最小的B。如果没有合适的B，则输出 0。 样例输入： 3 6 9 42 11 11 121 2 2 2 样例输出： 13 3 0

解题思路：

此问题很简单。选择一个进制B，按照该进制将被乘数、乘数、乘积分别转换成十进制。然后判断等式是否成立。使得等式成立的最小B就是所求的结果。 分别用一个字符型数组存储p、q、r 的各位数字符号。先以字符串的方式读入p、q、r， 然后按不同的进制将它们转换成成十进制数，判断是否相等。 参考程序：

#include #include

long b2ten(char * x,int b) { int ret=0; int len=strlen(x); int i;

3

for(i=0;i=b) return -1; ret*=b; ret+=x[i]-'0'; } return (long)ret; }

int main() { int n,b; char p[8],q[8],r[8]; long pb,qb,rb;//用来存储转换为十进制后的结果 scanf(\ while(n--) { scanf(\ for(b=2;b<=16;b++) { pb=b2ten(p,b); qb=b2ten(q,b); rb=b2ten(r,b); if(pb==-1 || qb==-1 || rb==-1) continue; if(pb*qb==rb) { printf(\ break; } } if(b==17) printf(\ } return 0; }

注意事项：

1） 在数制b(2<=b<=16) 的表示中，每一位上的数字一定都比b小。每读入一组数据后，需

要根据其中的数字，判断b 的下限。在参考程序的b2ten 函数中，如果字符串x 中存储的数字比b 大、或者与b 相等，则返回-1，表明：按照数制b，x 中存储的表示形式是非法的，因此b 不可能是所求的值。 2） 检查：在未找到合适的b 时，是否输出0。

4

本文来源：https://www.bwwdw.com/article/p8hh.html