文章

【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

1
2
123
25

输出 #1

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


示例代码

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
32
33
#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;
}

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

GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页

luogu-”系列题目已加入洛谷Java、C++初学团队作业清单,可在线评测,团队名额有限,欢迎加入。

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

本文由作者按照 CC BY 4.0 进行授权