数制转换

题意

将 2 到 16 进制的非负整数转换到另一个进制，字母部分统一使用大写输出。

思路

Python 的 int(text, base) 可直接将原进制数字转为整数。再不断执行 divmod(value, target_base)，余数就是从低到高的目标进制位，最后反转即可。零要单独处理。

代码

Python代码

python

1
2
3
4
5
6
7
8
9
10
11
12source_base, source_number, target_base = input().split()
value = int(source_number, int(source_base))
digits = "0123456789ABCDEF"

if value == 0:
    print(0)
else:
    converted = []
    while value:
        value, remainder = divmod(value, int(target_base))
        converted.append(digits[remainder])
    print("".join(reversed(converted)))

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a,b;
char str[100];
LL len;
char z[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };

vector<char> v;
/* n 进制  -> 10 进制 */
LL toDec(){
    LL sum = 0;
    LL t = 1;
    int i;
    for(i=len;i>=1;i--){
        sum +=  (str[i]*t);
        t *= a;
    }
    //printf("%lld\n",sum);
    return sum;
}
/* 10 进制  -> n 进制 */
void toN(LL x){
    while( x ){
        int t = x % b;
        v.push_back(z[t]);
        x /=b;
    }
}
int main(){
    scanf("%lld",&a);
    scanf("%s",str+1);
    len = strlen(str+1);
    if( len == 1 && str[1] == '0'){
        printf("0");
        return 0;
    }
    scanf("%lld",&b);
    int i;
    for(i=1;i<=len;i++){
        char &c = str[i];
        if( c >='0' && c<='9')
            str[i] -='0';
        else if( c >='a' && c <='z')
            str[i] -=('a'-10);
        else if( c >='A' && c <='Z')
            str[i] -=('A'-10);
    }
    toN(toDec());
    reverse(v.begin(),v.end());
    for (const auto& e : v) {
        printf("%c",e);
    }

    return 0;
}

复杂度

设输出位数为 $k$ ，时间复杂度为 $O(k)$ ，空间复杂度为 $O(k)$ 。

总结

进制转换可拆成“解析为数值”和“数值重新编码”两个独立步骤。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结