【NOIP】2000真题解析 luogu-P1017 进制转换

NOIP 2000真题，负进制转换原理与实现，重点理解C++中取模运算的特性。GESP 五、六级考生可以练习。题目难度⭐⭐⭐☆☆，洛谷难度等级普及/提高−。

luogu-P1017 [NOIP 2000 提高组] 进制转换

题目要求

题目描述

我们可以用这样的方式来表示一个十进制数：将每个阿拉伯数字乘以一个以该数字所处位置为指数，以  为底数的幂之和的形式。例如  可表示为  这样的形式。

与之相似的，对二进制数来说，也可表示成每个二进制数码乘以一个以该数字所处位置为指数，以  为底数的幂之和的形式。

一般说来，任何一个正整数  或一个负整数  都可以被选来作为一个数制系统的基数。如果是以  或  为基数，则需要用到的数码为 。

例如当  时,所需用到的数码是 ，这与其是  或  无关。如果作为基数的数绝对值超过 ，则为了表示这些数码，通常使用英文字母来表示那些大于  的数码。例如对  进制数来说,用  表示 ，用  表示 ，用  表示 ，以此类推。

在负进制数中是用  作为基数，例如 （十进制）相当于 （进制），并且它可以被表示为  的幂级数的和数：

设计一个程序，读入一个十进制数和一个负进制数的基数，并将此十进制数转换为此负进制下的数。

输入格式

输入的每行有两个输入数据。

第一个是十进制数 。第二个是负进制数的基数 。

输出格式

输出此负进制数及其基数，若此基数的绝对值超过 ，则参照  进制的方式处理。

输入输出样例 #1

输入 #1

30000 -2

输出 #1

30000=11011010101110000(base-2)

输入输出样例 #2

输入 #2

-20000 -2

输出 #2

-20000=1111011000100000(base-2)

输入输出样例 #3

输入 #3

28800 -16

输出 #3

28800=19180(base-16)

输入输出样例 #4

输入 #4

-25000 -16

输出 #4

-25000=7FB8(base-16)

说明/提示

【数据范围】

对于  的数据，，。

【题目来源】

NOIP 2000 提高组第一题

题目分析

1. 核心思路：短除法与负数取模

进制转换的通用解法是“短除法”：每次用被除数除以进制数（基数），把每一次得到的余数记录下来，作为新进制下的一位数字（从低位到高位），然后把商作为新的被除数，继续除以基数，直到商为 0。最后把取得的余数倒序排列即可。

负进制转换的核心思想仍然是“短除法”，但我们需要特别处理一个关键问题：C++ 中负数对负数取模，余数可能是一个负数。

例如，。 在常规的数学进制表示中，这一位对应的余数作为“数码”，不可能是负数，必须是  之间的正整数或零。而如果余数为负数，则不能直接作为计算结果的每一位输出。

解题策略：转化余数为正数

根据除法的定义：被除数 = 商  除数 + 余数

即： （其中  为余数， 为商）

当我们在 C++ 里计算 ，如果余数 ，我们要怎么把它变成正的呢？ 只要我们在算式中增加一个除数 ，再减去一个除数  即可：

我们知道  是负数（如 ），那么  实际就相当于加上了负进制数的绝对值，此时新的余数  就变成正数了。 为了保持等式成立，新的商变成了 。

通过这种“借位”的思想，若遇到负数的余数，我们可以：

1. 余数 减去基数 R（相当于加上 ），成为正数。
2. 商 加 1，继续下一步的短除。

2. 算法流程

1. 处理0的特判：如果输入的十进制数  一开始就是 0，直接输出其基数的 0 即可，但根据本题数据测试，我们可以将其整合到正常逻辑中，或者短除时循环至少执行一次。我们通常使用递归或栈来将得到的余数倒序输出。
2. 短除法运算（递归或迭代）：
• 当  时，计算商  和余数 。
• 如果余数 ，按照我们的调整策略，让 ，同时让 。
• 记录此余数对应在数码表中的字符。我们需要准备一个包含 0-9 和 A-J 的字符数组，以便可以查询任意正数在特定进制（最高到 20 进制）下的代表字母。本题绝对值最高到 20，因此准备充足的字符映射足以应对。
• 更新 ，继续循环或递归。
3. 输出格式：将得到的字符串倒序输出，格式要求严格：${原始n}=${结果}(base${R})。

3. 核心要点总结

• C++ 取模机制： C++ 中取模运算 -15 % -2 的结果是 -1。理解并处理这种语言特性的直接行为，是做这类问题的基础。
• 借位调整策略： 如果余数为负数，必须通过 余数 -= 进制， 商 += 1 的方式将其转正。
• 倒序转换特性： 短除法求出的第一个余数是数字的最低位代码，最后一次得到的余数是最高位。这里可以使用递归巧妙地倒置输出，或者将每次得到的字母存入字符串，最后进行reverse。
• 数字对应的字符： 当除数绝对值大于 10 时，余数可能是 10, 11... 我们需要建立字符映射表，根据下标快速获取正确的那个英文字母。

示例代码

方案一：使用递归实现，代码更简洁

#include<iostream>#include<string>// 数字到字符的映射表，最大处理至36进制 (问题中|R|<=20，这里给全足够)const std::string P = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";// 递归进行进制转换输出voidtransform(int n, int r){    if (n == 0) {        return; // 除到商为0，结束递归    }    int remain = n % r; // 计算余数    int quotient = n / r; // 计算商    // 如果余数小于0，修正为正整数范围 [0, |r|-1]    if (remain < 0) {        remain -= r;    // 相当于加上进制数r的绝对值        quotient++;     // 为了保持等式成立，商加1    }    // 递归处理之后的商 (不断往高位递归)    transform(quotient, r);    // 递归回溯阶段打出对应位上的字符，巧妙实现倒序输出    std::cout << P[remain];}intmain(){    // 优化输入输出流    std::ios_base::sync_with_stdio(false);    std::cin.tie(NULL);    int n, r;    // 读取十进制数 n 和负进制数的基数 r    std::cin >> n >> r;    std::cout << n << "="; // 输出原始值及等号    // 特判，如果数字一开始就是 0，结果为 0    if (n == 0) {        std::cout << 0;    } else {        // 调用递归函数输出进制转换结果        transform(n, r);    }    // 按题目要求的后缀格式输出基数    std::cout << "(base" << r << ")\n";    return 0;}

方案二：使用循环和字符串翻转实现

#include<iostream>#include<string>#include<algorithm>// 数字到字符的映射表const std::string P = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";intmain(){    // 优化输入输出流    std::ios_base::sync_with_stdio(false);    std::cin.tie(NULL);    int n, r;    std::cin >> n >> r;    std::cout << n << "=";    if (n == 0) {        std::cout << 0;    } else {        std::string ans = "";        int temp = n; // 保留原值，用临时变量递推        // 迭代进行短除法计算        while (temp != 0) {            int remain = temp % r;            int quotient = temp / r;            // 将负数余数转化为正数，同时商进位            if (remain < 0) {                remain -= r;                quotient++;            }            // 把每一位余数映射成对应字符并拼接到字符串中            ans += P[remain];            temp = quotient;  // 更新商        }        // 短除法得到的是反序的，这里将其翻转为正序（高位在前）        std::reverse(ans.begin(), ans.end());        // 输出得到的结果        std::cout << ans;    }    // 输出题目要求的基数格式    std::cout << "(base" << r << ")\n";    return 0;}

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。