CCF NOI1076 进制转换

问题链接：CCF NOI1076 进制转换。

时间限制: 1000 ms 空间限制: 262144 KB

题目描述

用递归算法将一个十进制数X(1<=X<=10^9)转换成任意进制数M（2<=M<=16）。

输入

一行两个正整数X和M。

输出

输出X的M进制的表示。

样例输入

21 16
样例输出

数据范围限制

提示

问题分析

这是一个进制问题。

题目要求用递归实现。递归实现比起递推实现速度上慢，而且耗费程序的堆栈空间。

用进制的基数（例如：10进制的基数为10）取余数计算可以获得数的最低位，除以进制的基数则相当于右移1位（扔掉最低位）。重复取余数和做除法，可以顺序得到一个数的从低位到高位。

需要注意的是，输出一个数要先输出高位，再输出低位。

程序说明

函数convert()用于将数转换为给定的进制。

这里给出递归和非递归两种程序。

要点详解

C语言程序中，从重用性考虑，尽量将功能封装到函数中。

参考链接：（略）。

100分通过的C语言程序（非递归）：

#include <stdio.h>

#define N 100000000
char a[N];

void convert(int n, int base)
{
    int i;

    i = 0;
    while(n) {
        a[i] = n % base;
        if(a[i] >= 10)
            a[i] = 'A' + a[i] - 10;
        else
            a[i] += '0';
        i++;

        n /= base;
    }

    i--;
    while(i>=0) {
        printf("%c", a[i]);
        i--;
    }
    printf("
");
}

int main(void)
{
    int x, m;

    scanf("%d%d", &x, &m);

    convert(x, m);

    return 0;
}

100分通过的C语言程序（递归）：

#include <stdio.h>

void convert(int n, int base)
{
    char digit;

    if(n) {
        convert(n / base, base);

        digit = n % base;
        if(digit >= 10)
            digit = 'A' + digit - 10;
        else
            digit += '0';
        printf("%c", digit);
    }
}

int main(void)
{
    int x, m;

    scanf("%d%d", &x, &m);

    convert(x, m);
    printf("
");

    return 0;
}