UVA389 题解

0x00AC3375 · 2023-08-24 14:29:03 · 题解

大致题意

输入一个字符串 s，两个整数 b_1,b_2，将 b_1 进制下字符串 s 表示的数字转化为 b_2 进制。
所有的输出对齐到左起第七位输出。如果结果的位数大于 7，应当在相应的位置对齐输出 ERROR。

分析

作为典型的进制转化问题，非十进制转化为非十进制的常规方法是先把 b_1 进制转化为十进制，再转化为 b_2 进制。

1. b_1 进制转化为 10 进制

由于字符串 s 下标大的表示低位，下标小的表示高位，因此按照数字减去 48，字母减去 55 的办法将字符转化为数值后，依次乘以 b_1 的幂次即可。参考代码：

for (int i = 0; i <= len1 - 1; i += 1)
{
    if (str[i] >= '0' && str[i] <= '9') b10value += (str[i] - 48ll) * p(b1, len1 - 1 - i);
    else if (str[i] >= 'A' && str[i] <= 'Z') b10value += (str[i] - 55ll) * p(b1, len1 - 1 - i);
}

2. 10 进制转化为 b_2 进制

为便于输出，我们可以使用下面的字符串事先数字、字母和数值 0\sim 36 的对应。输出时，使用 putchar 或 printf("%c") 输出对应的字符即可。

//使用一个字符串存储字符集, AtoZ表示10-35 
const char charset[40] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

转化过程中，重复“模 b_2 然后整除 b_2”的流程，再参考上面的序列将十进制数转化为由一系列字符组成的序列，然后倒序输出即可（因为重复这个流程，这个序列是从低位到高位依次排列的）。参考代码：

for (int i = 0; i <= 7; i += 1)
{
    result[i] = charset[b10value % b2];
    b10value /= b2;
    if(b10value==0) break;
}
//空位补上空格
for (int i = 6; i >=0;i-=1) putchar(result[i]=='\0' ? ' ' : result[i]);

3. 注意事项

输出时前面是补空格，不是补上前导 0。
字符数组如果初始化为零，所有位置都是 '\0'。使用 putchar 如果输出了 '\0'，输出显示在控制台上可能和标准输出没有区别，但是 OJ 可能会将其视为 Wrong answer。如果使用字符数组需要注意。

代码

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
long long p(long long a, long long x)
{
    return x ? a * p(a, x - 1) : 1;
}
void kernel(void)
{
    char str[10], result[100] = { 0 };
    //使用一个字符串存储字符集, AtoZ表示10-35 
    const char charset[40] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; 
    long long b1, b2, b10value = 0, len1, len2;
    if (scanf("%s%lld%lld", str, &b1, &b2) == EOF) exit(0);
    len1 = strlen(str);
    //b1进制数转化为10进制数
    for (int i = 0; i <= len1 - 1; i += 1)
    {
        if (str[i] >= '0' && str[i] <= '9') b10value += (str[i] - 48ll) * p(b1, len1 - 1 - i);
        else if (str[i] >= 'A' && str[i] <= 'Z') b10value += (str[i] - 55ll) * p(b1, len1 - 1 - i);
    }
    len2 = (long long)(log10(1.0 * b10value) / log10(1.0 * b2)) + 1;//对数换底公式确定b2进制有多长
    if (len2 >= 8)//超过7位报错
    {
        printf("  ERROR\n");
        return;
    }
    for (int i = 0; i <= 7; i += 1)
    {
        result[i] = charset[b10value % b2];
        b10value /= b2;
        if(b10value==0) break;
    }
    if(result[7])
    {
        printf("  ERROR\n");
        return;
    }
        //字符数组初始化为0, 要避免输出\0字符，应将未使用的空位替换为空格输出
    for (int i = 6; i >=0;i-=1) putchar(result[i]=='\0' ? ' ' : result[i]);
    putchar(10);
}

int main()
{
    while (1) kernel();
}

Extra

在 36 进制下，任何一个英文单词都可以转化为相应的十进制数（并且很可能会突破 unsigned __int64 的上限）。36 进制下，英文单词 ERROR 转化为十进制等于 24810219。