《算法与程序实践习题解答2(数制转换)》由会员分享，可在线阅读，更多相关《算法与程序实践习题解答2(数制转换)（26页珍藏版）》请在金锄头文库上搜索。
1、目 录CS21：特殊的四位数1CS22：确定进制3CS23：skew数5CS24：十进制到八进制7CS25：八进制到十进制9CS26：二进制转化为十六进制10CS27：八进制小数（也属于高精度计算）13CS28：二进制数17CS29：回文数（Palindrom Numbers）19CS210：设计计算器（Basically Speaking）21CS211：24算法与程序实践习 题 解 答2数制转换解决数制转换问题时，如果所给的数值不是用十进制表示的，一般用一个字符型数组来存放。数组的每个元素分别存储它的一位数字。然后按位转换求和，得到十进制表示；再把十进制表示转换成所求的数制表示。转换的结果
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 的转换
3、需要分两种情况考虑：l数制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 止。l数制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、输出所有的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是第一个符合要求的数）输入：
5、本题没有输入。输出：你的程序要求输出2992及其他更大的、满足要求的四位数（要求严格按升序输出），每个数占一行（前后都没有空行），整个输出以换行符结尾。输出中没有空行。输出中的前几行如样例输出所示。样例输入：本题没有输入。样例输出：29922993299429952996299729982999.解题思路：该题在求解时要用到枚举的算法思想，即枚举所有的四位数（1000-9999），判断其是否满足十六进制、十二进制和十进制形式的各位数之和相等。这里要注意进制转换方法。将一个十进制数Num转换到M进制，其方法是：将Num除以M取余数，直到商为0为止，存储得到的余数，先得到的余数为低位，后得到的余数
6、为高位进行排序，余数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%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(s
7、16=s10) printf(%dn,Num);return 0;CS22：确定进制（来源： 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) = 1
8、21(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。样例输入：36
9、9 4211 11 1212 2 2样例输出：1330解题思路：此问题很简单。选择一个进制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;for(i=0;i=b) return -1;ret*=b;ret+=xi-0;return
10、(long)ret;int main()int n,b;char p8,q8,r8;long pb,qb,rb;/用来存储转换为十进制后的结果scanf(%d,&n);while(n-)scanf(%s%s%s,p,q,r);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(%dn,b);break;if(b=17) printf(0n);return 0;注意事项：1） 在数制b(2=b=16) 的表示中，每一位上的数字
11、一定都比b小。每读入一组数据后，需要根据其中的数字，判断b 的下限。在参考程序的b2ten 函数中，如果字符串x 中存储的数字比b 大、或者与b 相等，则返回-1，表明：按照数制b，x 中存储的表示形式是非法的，因此b 不可能是所求的值。2） 检查：在未找到合适的b 时，是否输出0。CS23：skew数（来源： 2973，程序设计导引及在线实践（李文新）例3.2 P101）问题描述：在skew binary表示中，第k位的值xk表示xk*(2k+1-1) 。每个位上的可能数字是0或1，最后面一个非零位可以是2，例如, 10120(skew) = 1*(25-1) + 0*(24-1) + 1*
12、(23-1) + 2*(22-1) +0*(21-1) = 31 + 0 + 7 + 6 + 0 = 44. 前十个skew 数是 0、1、2、10、11、12、20、100、101以及102。输入：输入包含一行或多行，每行包含一个整数n。如果n = 0 表示输入结束，否则n 是一个skew 数。输出：对于每一个输入，输出它的十进制表示。转换成十进制后， n 不超过 231-1 = 2 147 483 647。输入样例：1012020000000000000000000000000000010100000000000000000000000000000011100111110000011100
13、001011011020000输出样例：44214748364632147483647471041110737解题思路1：skew 数的相邻位上，基数之间没有等比关系。计算每一位的基数后，再把一个skew 数转换成十进制表示就很简单。对于长度为k 的skew 数，最后一位数字的基数为2k-1。由于转换成十进制后， n不超过 231-1，因此输入skew 数的最大长度不超过31。用一个整型数组base31，依次存储skew 数最末位、倒数第2 位、.、第31 位的基数值。使用这个数组，把每个skew 数转换成对应的十进制数。base0 = 1 basek = 2k+1 - 1 = 2 * (2k - 1) + 1 = 2 * basek -1 + 1参考程序1：#include #include int main()int i,k,base31,sum;char skew32;base0=1;for(i=1;i31;i+)basei=2*basei-1+1;while(1)scanf(%s,skew);if(strcmp(skew,0)=0)break;sum=0;k=strlen(skew);for(i=0;i strlen(skew);i+)k-;sum+=(skewi-0)*basek;printf(%dn,sum);return 0;
