【题解】NOIP2000 进制转换

发表于 更新于 分类于 阅读次数： Disqus：

题目链接

P1017 进制转换

题目分析

这道题考察的是负进制转换。

我们都知道，十进制转化为二进制应该不断用原数除以2取余，得到的余数由高位到低位排列则能得到十进制数字在二进制下的数字。

十进制转二进制的代码如下：

1
2
3
4
5
int binary[255], cur = 0;
while (n > 0) {
    binary[++cur] = n % m;
    n /= m;
}

其中n为十进制下的数字，m为需要转换的进制。

那么当目标进制为负数的时候要注意什么呢？

余数不能为负数。

例如，(19)10(19)_{10}要转换成−9-9进制。

19/−9=−2...119/-9=-2...1

−2/−9=1...7-2/-9=1...7（注意这里不是**0...−20...-2**！因为负数不能做余数。）

1/−9=0...11/-9=0...1（当商为0时计算完成）

代码实现

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
/* P1017 进制转换
 * 来源: NOIP2000
 * 作者: RainbowBird
 * 日期: 2020-08-28
 * 算法: 负进制转换
 */

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

char nums[20] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'};

int main() {
    int n, r;
    scanf("%d %d", &n, &r);

    printf("%d=", n);

    char ans[10005], cur = 0;
    while (n != 0) { // 注意这里是不等于，因为商可能为负数
        int mod = n % r; // 获取余数
        n /= r;          // 获取商
        
        // 如果余数小于0，那么商进一位，余数则等于进制数的绝对值减去余数的绝对值
        if (mod < 0) n++, mod = abs(r) - abs(mod);
        ans[cur++] = nums[mod];
    }
    
    // 由高位到低位倒序输出
    for (int i = cur - 1; i >= 0; i--) printf("%c", ans[i]); 
    printf("(base%d)\n", r);
    return 0;
}