luogu-B3849 [GESP样题 三级] 进制转换

GESP三级模拟样题，字符串和进制转换相关，难度★★✮☆☆。

luogu-B3849 [GESP样题 三级] 进制转换

题目要求

题目描述

小美刚刚学习了十六进制，她觉得很有趣，想到是不是还有更大的进制呢？在十六进制中，用 A 表示 $10$、F 表示 $15$。如果扩展到用 Z 表示 $35$，岂不是可以表示 $36$ 进制数了嘛！

所以，你需要帮助她写一个程序，完成十进制转 $R$ 进制（$2\le R\le 36$）的工作。

输入格式

输入两行，第一行包含一个正整数 $N$，第二行包含一个正整数 $R$，保证 $1\le N\le 10^6$。

输出格式

输出一行，为 $N$ 的 $R$ 进制表示。

输入输出样例 #1

输入 #1

123
25

输出 #1

4N

题目分析

解题思路

十进制转换为其他进制的基本思路是:

1. 不断用目标进制R除十进制数N，得到余数
2. 余数即为当前位的值，商作为新的N继续除以R
3. 所有余数从后往前拼接即为结果
4. 如果余数大于9，则用A-Z表示（A表示10，B表示11，以此类推）

例如，将123转换为25进制:

1. 123 ÷ 25 = 4 余 23（用N表示）
2. 4 ÷ 25 = 0 余 4
3. 从后往前拼接：4N

因此，本题的解题思路可以分为以下几个步骤：

1. 读取输入数据：

   • 读取十进制数N
   • 读取目标进制R（2≤R≤36）

2. 进制转换处理：

   • 循环处理N，直到N为0：
     • 计算当前位的值：N对R取余
     • 更新N：N除以R取整
     • 根据余数确定当前位的表示：
       • 余数小于等于9时，用数字表示
       • 余数大于9时，用字母A-Z表示（10用A，35用Z）
     • 将当前位添加到结果字符串的开头

复杂度分析：

• 时间复杂度：$O(\log_R N)$，需要进行N除以R的次数
• 空间复杂度：$O(\log_R N)$，需要存储结果字符串

{% include custom/custom-post-content-inner.html %}

示例代码

#include <iostream>
#include <string>

int main() {
    // 声明变量存储十进制数N和目标进制R
    int N, R;
    std::cin >> N >> R;
    
    // 用字符串存储结果
    std::string result = "";
    
    do {
        // 获取当前位的值
        int cur = N % R;
        // 更新N为商
        N /= R;
        
        char c;
        // 如果当前位大于9，需要用字母A-Z表示
        if (cur > 9) {
            c = char(cur - 10 + (int)'A');
        } else {
            // 否则用数字0-9表示
            c = char(cur + '0');
        }
        // 将当前位添加到结果字符串的开头
        result = c + result;
    } while (N != 0);  // 当N不为0时继续循环
    
    // 输出结果
    std::cout << result;
    return 0;
}

{% include custom/custom-post-content-footer.md %}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

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

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

GESP/CSP 认证学习微信公众号