POJ1220-NUMBER BASE CONVERSION（任意进制转换）

2020年7月21日13:11:25数据结构和算法评论383字数 1859阅读6分11秒阅读模式

一、题目描述

Description

Write a program to convert numbers in one base to numbers in a second base. There are 62 different digits: { 0-9,A-Z,a-z }
HINT: If you make a sequence of base conversions using the output of one conversion as the input to the next, when you get back to the original base, you should get the original number.

Input

The first line of input contains a single positive integer. This is the number of lines that follow. Each of the following lines will have a (decimal) input base followed by a (decimal) output base followed by a number expressed in the input base. Both the input base and the output base will be in the range from 2 to 62. That is (in decimal) A = 10, B = 11, ..., Z = 35, a = 36, b = 37, ..., z = 61 (0-9 have their usual meanings).

Output

The output of the program should consist of three lines of output for each base conversion performed. The first line should be the input base in decimal followed by a space then the input number (as given expressed in the input base). The second output line should be the output base followed by a space then the input number (as expressed in the output base). The third output line is blank.

Sample Input

8
62 2 abcdefghiz
10 16 1234567890123456789012345678901234567890
16 35 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2
35 23 333YMHOUE8JPLT7OX6K9FYCQ8A
23 49 946B9AA02MI37E3D3MMJ4G7BL2F05
49 61 1VbDkSIMJL3JjRgAdlUfcaWj
61 5 dl9MDSWqwHjDnToKcsWE1S
5 10 42104444441001414401221302402201233340311104212022133030

62 2 abcdefghiz

10 16 1234567890123456789012345678901234567890

16 35 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2

35 23 333YMHOUE8JPLT7OX6K9FYCQ8A

23 49 946B9AA02MI37E3D3MMJ4G7BL2F05

49 61 1VbDkSIMJL3JjRgAdlUfcaWj

61 5 dl9MDSWqwHjDnToKcsWE1S

5 10 42104444441001414401221302402201233340311104212022133030

Sample Output

62 abcdefghiz
2 11011100000100010111110010010110011111001001100011010010001

10 1234567890123456789012345678901234567890
16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2

16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2
35 333YMHOUE8JPLT7OX6K9FYCQ8A

35 333YMHOUE8JPLT7OX6K9FYCQ8A
23 946B9AA02MI37E3D3MMJ4G7BL2F05

23 946B9AA02MI37E3D3MMJ4G7BL2F05
49 1VbDkSIMJL3JjRgAdlUfcaWj

49 1VbDkSIMJL3JjRgAdlUfcaWj
61 dl9MDSWqwHjDnToKcsWE1S

61 dl9MDSWqwHjDnToKcsWE1S
5 42104444441001414401221302402201233340311104212022133030

5 42104444441001414401221302402201233340311104212022133030
10 1234567890123456789012345678901234567890

62 abcdefghiz

2 11011100000100010111110010010110011111001001100011010010001

10 1234567890123456789012345678901234567890

16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2

35 333YMHOUE8JPLT7OX6K9FYCQ8A

23 946B9AA02MI37E3D3MMJ4G7BL2F05

49 1VbDkSIMJL3JjRgAdlUfcaWj

61 dl9MDSWqwHjDnToKcsWE1S

5 42104444441001414401221302402201233340311104212022133030

10 1234567890123456789012345678901234567890

Source

Greater New York 2002

二、题目解析

题目的意思是实现62进制内任意进制数据的转换，其中A-Z表示10-35，a-z表示36-62。

这道题目一共考察了两个问题点，第一个是进制转换，第二个是大数据处理。更倾向于考察第二个问题点。

看了很多题解，百度上的题解基本都是copy的，一模一样的代码套进去，都没有说明白为什么要这样，没有任何价值。最后是google到的一篇题解才真正明白，其实解题的思路很简单，就是实现进制转换的短除法，然后处理除法过程中的大数据运算。

2.1 进制转换

解题前首先要搞清楚进制之间的转换逻辑，A进制转B进制如何转？

一般的思路是先从当前进制转到10进制，再从10进制转成目标进制。

从其他进制转换成十进制的办法是按权相加：

POJ1220-NUMBER BASE CONVERSION（任意进制转换）-图片1

从十进制转成其他进制的办法是短除法：

POJ1220-NUMBER BASE CONVERSION（任意进制转换）-图片2

2.2 大数计算

除了进制转换以外，最重要的功能就是除法的实现了，如何通过除法来获取余和商。

因为题目给的数据范围过大，如果用整形来保存数据，肯定是不够的，即使是long long或者更大的类型，都不足以容纳下题目所要求的数据范围。因此，数据只能用字符数组来保存，每个数组元素表示1位数字。

那么这道题目就转变成了通过字符串数组来求商和余数的问题了，只要循环求出所有的商和余数，问题就解决了。

三、代码

代码一共分为几个步骤：

将字符数组中的每个元素都转成整形，方便运算。
对每个元素求商和余数，模拟短除法，记录余数。
反转所有的余数，转成字符形式，输出。

第一部分，62进制字符和数字之间的相互转换：

// char转整形
static int char2int(char ch) {
    if (ch >= '0' && ch <= '9')
        return ch - '0';
    else if (ch >= 'a' && ch <= 'z')
        return ch - 'a' + 36;
    else
        return ch - 'A' + 10;
}

// 整形转char
static char int2char(int n) {
    if (n >= 0 && n <= 9)
        return '0' + (char) n;
    else if (n >= 10 && n <= 35)
        return 'A' + n - 10;
    else
        return 'a' + n - 36;
}

// char转整形

static int char2int(char ch) {

if (ch >= '0' && ch <= '9')

return ch - '0';

else if (ch >= 'a' && ch <= 'z')

return ch - 'a' + 36;

else

return ch - 'A' + 10;

}

// 整形转char

static char int2char(int n) {

if (n >= 0 && n <= 9)

return '0' + (char) n;

else if (n >= 10 && n <= 35)

return 'A' + n - 10;

else

return 'a' + n - 36;

}

第二部分，任意进制转换函数：

char *base_conversion(int from, int to, const char *src, char *ans) {
    int len, i, j, idx;
    unsigned int tmp[MAX_SIZE], ans_rev[MAX_SIZE];
    len = strlen(src);

    // 将字符串转成整形
    for (i = 0; i < len; i++) {
        tmp[i] = (char)char2int(src[i]);
    }
    tmp[len] = '\0';

    idx = 0;
    for (i = 0; i < len;) {
        // 短除法，辗转相除，从高位往低位除
        // 假设当前字符串是123，下面就是让123除2得到商61和余1的过程
        // 下一次再走进这里就是通过63取得商31和余1的过程
        for (j = i; j < len - 1; j++) {
            tmp[j + 1] += tmp[j] % to * from;
            tmp[j] = tmp[j] / to;
        }
        
        // 最后一位取余数，ans_rev是逆序排放的余数
        ans_rev[idx++] = tmp[len - 1] % to;
        tmp[len - 1] /= to;
        
        // tmp[i]现在是商，忽略掉头部的0
        while (i < len && !tmp[i])
            i++;
    }

    // 反转所有的余并转成字符形式
    ans[idx] = '\0';
    for (j = 0; j < idx; j++) {
        ans[j] = int2char(ans_rev[idx - j - 1]);
    }
    return ans;
}

char *base_conversion(int from, int to, const char *src, char *ans) {

int len, i, j, idx;

unsigned int tmp[MAX_SIZE], ans_rev[MAX_SIZE];

len = strlen(src);

// 将字符串转成整形

for (i = 0; i < len; i++) {

tmp[i] = (char)char2int(src[i]);

}

tmp[len] = '\0';

idx = 0;

for (i = 0; i < len;) {

// 短除法，辗转相除，从高位往低位除

// 假设当前字符串是123，下面就是让123除2得到商61和余1的过程

// 下一次再走进这里就是通过63取得商31和余1的过程

for (j = i; j < len - 1; j++) {

tmp[j + 1] += tmp[j] % to * from;

tmp[j] = tmp[j] / to;

}

// 最后一位取余数，ans_rev是逆序排放的余数

ans_rev[idx++] = tmp[len - 1] % to;

tmp[len - 1] /= to;

// tmp[i]现在是商，忽略掉头部的0

while (i < len && !tmp[i])

i++;

}

// 反转所有的余并转成字符形式

ans[idx] = '\0';

for (j = 0; j < idx; j++) {

ans[j] = int2char(ans_rev[idx - j - 1]);

}

return ans;

}

第三部分，main函数：

int main() {
    char input[MAX_SIZE], output[MAX_SIZE];
    int n, i = 0, from, to;
    scanf("%d", &n);
    while (++i < n) {
        scanf("%d %d %s", &from, &to, input);
        base_conversion(from, to, input, output);
        printf("%d %s\n%d %s\n\n",from, input, to, output);
    }
    return 0;
}

int main() {

char input[MAX_SIZE], output[MAX_SIZE];

int n, i = 0, from, to;

scanf("%d", &n);

while (++i < n) {

scanf("%d %d %s", &from, &to, input);

base_conversion(from, to, input, output);

printf("%d %s\n%d %s\n\n",from, input, to, output);

}

return 0;

}

要注意的一个问题是输出格式是三行，每行输出后面都要有一个空行。

单元测试案例

// 测试char和int互转
TEST(base_conversion, int2char_and_char2int) {
    char map_arr[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    int i;
    for (i = 0; i < 62; i++) {
        EXPECT_EQ(i, char2int(map_arr[i]));
    }
    for (i = 0; i < 62; i++) {
        EXPECT_EQ(map_arr[i], int2char(i));
    }
}

// 测试进制转换，数据来源样例输入
TEST(base_conversion, conversion) {
    char input[MAX_SIZE] = { 0 }, output[MAX_SIZE] = { 0 };
    strcpy(input, "103");
    EXPECT_STREQ(base_conversion(10, 2, input, output), "1100111");
    EXPECT_STREQ(base_conversion(62, 2, "abcdefghiz", output), "11011100000100010111110010010110011111001001100011010010001");
    EXPECT_STREQ(base_conversion(10, 16, "1234567890123456789012345678901234567890", output), "3A0C92075C0DBF3B8ACBC5F96CE3F0AD2");
    EXPECT_STREQ(base_conversion(16, 35, "3A0C92075C0DBF3B8ACBC5F96CE3F0AD2", output), "333YMHOUE8JPLT7OX6K9FYCQ8A");
    EXPECT_STREQ(base_conversion(35, 23, "333YMHOUE8JPLT7OX6K9FYCQ8A", output), "946B9AA02MI37E3D3MMJ4G7BL2F05");
    EXPECT_STREQ(base_conversion(23, 49, "946B9AA02MI37E3D3MMJ4G7BL2F05", output), "1VbDkSIMJL3JjRgAdlUfcaWj");
    EXPECT_STREQ(base_conversion(49, 61, "1VbDkSIMJL3JjRgAdlUfcaWj", output), "dl9MDSWqwHjDnToKcsWE1S");
}