【GESP】C++三级模拟题 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

1123
225

输出 #1

14N

题目分析

解题思路

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

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)$，需要存储结果字符串

示例代码

1#include <iostream>
2#include <string>
3
4int main() {
5    // 声明变量存储十进制数N和目标进制R
6    int N, R;
7    std::cin >> N >> R;
8
9    // 用字符串存储结果
10    std::string result = "";
11
12    do {
13        // 获取当前位的值
14        int cur = N % R;
15        // 更新N为商
16        N /= R;
17
18        char c;
19        // 如果当前位大于9，需要用字母A-Z表示
20        if (cur > 9) {
21            c = char(cur - 10 + (int)'A');
22        } else {
23            // 否则用数字0-9表示
24            c = char(cur + '0');
25        }
26        // 将当前位添加到结果字符串的开头
27        result = c + result;
28    } while (N != 0);  // 当N不为0时继续循环
29
30    // 输出结果
31    std::cout << result;
32    return 0;
33}