题目描述

我们都知道每一个整数都可以用十进制来表示，从右往左起，第k个数权重是\(10^k\)，比如：9527实际上表示的值是 \[9527=9*10^3+5*10^2+2*10^1+7*10^0\] 我们现在引入负数进制，比如-10进制，在该进制的表示下由于: \[9527=1*(-10)^4+1*(-10)^3+6*(-10)^2+8*(-10)^1+7*(-10)^0\] 十进制9527在负十进制下的表示就是11687。现在给定任意一个整数N，和进制数R，请计算N在R进制下的表示形式。其中\(−20<=R<=−2\) 或 \(2<=R<=20\) ，由于R的绝对值可能大于10，我们用类似十六进制表示法：A表示10，B表示11，C表示12，...

输入：

一行数据2个整数，N和R，用空格间隔，(\(−1000000<=N<=1000000\)，\(−20<=R<=−2\) 或 \(2<=R<=20\)）

输出：

N在R进制下的表示

样例输入：

10086 -16

样例输出：

1E8A6

解释：\(10086=1*(-16)^4+14*(-16)^3+8*(-16)^2+10*(-16)^1+6*(-16)^0\)

分析：

当我第一次看到这个题目时，心里就产生一个疑问，如果 \(R\) 小于零，这种表示一定存在吗，如果存在那么表示的形式是唯一的吗？存在性可以用数学归纳法证明，唯一性可以用经典的反证法证明。

解决问题：

既然表示形式唯一，如果我们可以找到一种方法计算最末尾的数字，那么如何计算高位上的数字就是递归子问题，当递归终止时，我们就计算出了所有位。 现在的问题就转换成了如何计算 \(N\) 在 \(R\) 进制表示下最末尾的数字。由于在 \(R\) 进制下，每一位上的数字 \(k\) 必须满足 \(0<=k<|R|\)，如果 \(R\) 大于零，\(N\) 用 \(R\) 进制表示时，最末尾的数字就是 \(N \% R\)。但是如果 \(R\) 是负数，计算机计算的 \(N \% R\) 也是负数，这不符合条件，需要一次转换，将其转换到 \(0\) 到 \(|R| − 1\) 之间才行。令 \(k = N \% R\) 分下列 2 种情况考虑：

  1. 当\(k\)满足条件\(0<=k<|R|\)时，则\(N=x∗R+k\)，所以\(k\)就是R进制最末尾的数字，而\(x\)在R进制下的表示是递归子问题。
  2. 当\(k\)满足条件\(−|R|<k<0\)时，说明\(R<0\)，则\(R<k<0\)，有如下等式： \[ \begin{align} N&=x∗R+k \\ N&=x∗R+R−R+k \\ N&=(x+1)*R+(k−R) \end{align} \] 其中\(0<k−R<|R|\)，\(k−R\)是R进制下的最末尾数字，而\(x+1\)在R进制下的表示是递归子问题。 由于\(|x+1| < |N|\)，所以经过每一次递归（或者迭代），\(N\) 的绝对值是下降的，所以算法一定会终止。

当我们计算从低位向高位计算出所有位之后，再将结果逆序输出就是最终的答案了。

代码如下： 

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
#include <stdio.h>
const char *arr = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int main() {
    int N = 0;
    int R = 0;
    int i = 0;
    char result[1000];
    scanf("%d%d", &N, &R);

    if (N == 0) {
        printf("0\n");
        return 0;
    }

    while (N != 0) {
        int y = N%R;
        if (y >= 0) {
            result[i++] = arr[y];
            N = N/R;
        } else {
            result[i++] = arr[y-R];
            N = N/R + 1;
        }
    }

    while (--i >= 0) {
        printf("%c", result[i]);
    }
    printf("\n");
    return 0;
}