《算法与程序实践》习 题 解 答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) printf("%d\n",Num);
    }
    return 0;
}
CS22：确定进制
（来源：ids 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， 然后按不同的进制将它们转换成成十进制数，判断是否相等。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。