蓝桥杯备赛——进制转化相关问题

一、基础概念

二、问题研究（1）

代码解读：

1. transfer 函数

代码功能概述

详细步骤

2. main 函数

代码功能概述

详细步骤

三、运用递归解决

（一）

代码如下：

代码解读：

（二）

代码如下：

代码2：（使用库函数）

（三）

示例

一、基础概念

常见的进制包括：

二进制（Base 2）：0b1010（C++14支持前缀）

八进制（Base 8）：以 0 开头的数字，如 012

十进制（Base 10）：默认表示方式，如 42

十六进制（Base 16）：以 0x 开头，如 0x2A

二、问题研究（1）

设计一个函数，将十进制数转换成二进制、八进制和十六进制。然后在主函数中读入一个整数，调用函数，输出转换结果。

思路：

• 假设将十进制数 57 转换为二进制
• 从右到左写出每列的位值，直到发现位值大于该十进制数的列。这样就先得到
位值：64 32 16 8 4 2 1

• 然后去掉位值为 64 的列，得到：
位值：32 16 8 4 2 1

• 然后，从左至右进行。 57 除以 32 得商为 1 ，余数为 25 ，所以在 32 这列写下 1 ，然后 25 除以 16 商为 1 ，余数为 9 ，所以在 16 这列写下 1 ， ……
位值： 32 16 8 4 2 1

符号值： 1 1 1 0 0 1 所以(57)10=(111001)2

• 假设将十进制数 57 转换为八进制
• 从右到左写出每列的位值，直到发现位值大于该十进制数的列。这样就先得到
位值：64 8 1

• 然后去掉位值为 64 的列，得到：
位值：8 1

• 然后，从左至右进行。 57 除以 8 得商为 7 ，余数为 1 ，所以在 8 这列写下 1 ，然后 1 除以 1 商为 1 ，余数为 0 ，所以在 1 这列写下 1.
位值： 8 1

符号值： 7 1 所以(57)10=(71)8

代码（1）（常规不使用递归）：

void transfer(int num, int base)
{
	int p, k;
	p = 1;
	while (p <= num) //求p：p是base的x次幂，且p大于num 
		p = p * base;
 
	p = p / base;
 
	/*循环求base进制数的各位*/
	while (p != 0) {
		k = num / p; /*计算当前要输出的那个base进制数*/
		if (k <= 9)
			printf("%d", k);
		else
			printf("%c", k-10+'A');
 
		num = num % p;
		p = p / base;
	}
}
int main()
{
	int num = 0;
	int base = 0;
	printf("先输入要转化的数：");
	scanf("%d", &num);
	printf("输入转化进制：");
	scanf("%d", &base);
	transfer(num, base);
	return 0;
}

代码解读：

1. `transfer` 函数

void transfer(int num, int base)
{
    int p, k;
    p = 1;
    while (p <= num) //求p：p是base的x次幂，且p大于num 
        p = p * base;
 
    p = p / base;
 
    /*循环求base进制数的各位*/
    while (p != 0) {
        k = num / p; /*计算当前要输出的那个base进制数*/
        if (k <= 9)
            printf("%d", k);
        else
            printf("%c", k-10+'A');
 
        num = num % p;
        p = p / base;
    }
}

代码功能概述

该函数接受两个参数：num 表示要转换的十进制数，base 表示目标进制。函数的主要作用是将十进制数 num 转换为 base 进制数并输出。

详细步骤

初始化变量：
- p 用于存储 base 的幂次，初始化为 1。
- k 用于存储当前位的数字。
计算 p 的值：
- 使用 while 循环不断将 p 乘以 base，直到 p 大于 num。此时 p 是 base 的某个幂次，且这个幂次是使得 p 大于 num 的最小幂次。
- 然后将 p 除以 base，得到最大的小于等于 num 的 base 的幂次。
循环求 base 进制数的各位：
- 进入 while 循环，只要 p 不为 0，就继续循环。
- 计算当前位的数字 k，通过 num / p 得到。
- 如果 k 小于等于 9，则直接输出该数字。
- 如果 k 大于 9，则输出对应的字母（A - Z），通过 k - 10 + 'A' 实现。
- 更新 num 为 num % p，去掉已经处理过的高位。
- 更新 p 为 p / base，处理下一位。

2. `main` 函数

int main()
{
    int num = 0;
    int base = 0;
    printf("先输入要转化的数：");
    scanf("%d", &num);
    printf("输入转化进制：");
    scanf("%d", &base);
    transfer(num, base);
    return 0;
}

代码功能概述

main 函数是程序的入口，负责从用户那里获取要转换的十进制数和目标进制，然后调用 transfer 函数进行转换。

详细步骤

初始化变量：
- num 用于存储用户输入的要转换的十进制数，初始化为 0。
- base 用于存储用户输入的目标进制，初始化为 0。
获取用户输入：
- 使用 printf 函数提示用户输入要转换的数，然后使用 scanf 函数读取用户输入并存储到 num 中。
- 使用 printf 函数提示用户输入目标进制，然后使用 scanf 函数读取用户输入并存储到 base 中。
调用 transfer 函数：
- 调用 transfer 函数，将 num 和 base 作为参数传递给该函数进行转换。
返回值：
- 程序正常结束，返回 0。

三、运用递归解决

（一）

题目描述
给定一个十进制整数 𝑛和一个小整数 𝑥。将整数 𝑛 转为 𝑥进制。对于超过十进制的数码，用 A，B ...表示。

输入格式
第一行一个整数
𝑛

第二行一个整数
𝑥

输出格式
输出仅包含一个整数，表示答案。

输入输出样例
输入
1000
2
输出
1111101000

代码如下：

#include <iostream>
using namespace std;
string s = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
void print(int n, int x)
{
 if (n >= x)
 print(n / x, x);
 cout << s[n % x];
}
int main()
{
 int n = 0;
 int x = 0;
 cin >> n >> x;
 print(n, x);
 return 0;
}

代码解读：

全局变量部分

定义了一个全局字符串变量 s，它包含了从 0 到 9 以及从 A 到 Z 的字符。这个字符串用于在进制转换时表示不同进制下的每一位数字。在转换过程中，通过索引来从这个字符串中取出对应的字符进行输出，从而方便处理大于 9 的数字（如十六进制中的 A - F）。

print 函数部分、

void print(int n, int x)
{
    if (n >= x)
        print(n / x, x);
    cout << s[n % x];
}

函数功能概述

print 函数是一个递归函数，其作用是将十进制整数 n 转换为 x 进制数并输出。

详细步骤

递归条件判断：
- if (n >= x)：如果当前的十进制数 n 大于或等于目标进制 x，说明 n 还可以继续分解为更高位的 x 进制数。
- print(n / x, x)：递归调用 print 函数，将 n 除以 x 的商作为新的 n 继续进行转换。这样做的目的是先处理高位的 x 进制数，因为递归会不断深入，直到处理到最高位。
输出当前位数字：
- cout << s[n % x];：当 n 小于 x 时，递归调用结束，开始回溯输出。n % x 得到 n 除以 x 的余数，这个余数就是当前位的 x 进制数字。通过 s[n % x] 从字符串 s 中取出对应的字符并输出。

main 函数部分

int main()
{
    int n = 0;
    int x = 0;
    cin >> n >> x;
    print(n, x);
    return 0;
}

函数功能概述

main 函数是程序的入口，负责从用户那里获取要转换的十进制数和目标进制，然后调用 print 函数进行转换和输出。

详细步骤

变量初始化：
- int n = 0;：定义并初始化一个整型变量 n，用于存储用户输入的要转换的十进制数。
- int x = 0;：定义并初始化一个整型变量 x，用于存储用户输入的目标进制。
获取用户输入：
- cin >> n >> x;：使用标准输入流 cin 从用户那里读取两个整数，分别存储到 n 和 x 中。
调用 print 函数：
- print(n, x);：调用 print 函数，将 n 转换为 x 进制数并输出。
返回值：
- return 0;：程序正常结束，返回 0 表示程序成功执行。

（二）

题目描述
给一个小整数 x 和一个 x 进制的数 𝑆将 𝑆转为 10进制数。对于超过十进制的数码，用 A，B，
…表示。

输入格式
第一行一个整数
𝑥

第二行一个字符串
𝑆

输出格式
输出仅包含一个整数，表示答案。

代码如下：

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
 int x = 0;
 string s;
 cin >> x;
 cin >> s;
 int ret = 0;
 int n = s.size();
 int i = 0;
 while (--n >= 0)
 {
 if (s[n] <= '9')
 ret += (s[n] - '0') * pow(x, i);
 else
 ret += (s[n] + 10 - 'A') * pow(x, i);
 i++;
 }
 cout << ret << endl;
 return 0;
}

代码解读：

int x = 0;：声明并初始化一个整型变量 x，用于存储输入的进制数，初始值为 0。
string s;：声明一个字符串变量 s，用于存储 x 进制的数字字符串。
cin >> x;：从标准输入读取一个整数，赋值给 x，表示要转换的数字的进制。
cin >> s;：从标准输入读取一个字符串，赋值给 s，表示 x 进制的数字。
int ret = 0;：声明并初始化一个整型变量 ret，用于存储最终转换后的十进制结果，初始值为 0。
int n = s.size();：获取字符串 s 的长度，存储在变量 n 中，后续用于遍历字符串。
int i = 0;：声明并初始化一个整型变量 i，用于记录当前处理的字符对应的幂次，初始值为 0。

while (--n >= 0)
{
    if (s[n] <= '9')
        ret += (s[n] - '0') * pow(x, i);
    else
        ret += (s[n] + 10 - 'A') * pow(x, i);
    i++;
}

while (--n >= 0)：这是一个 while 循环，--n 先将 n 的值减 1，然后判断是否大于等于 0。通过这种方式从字符串 s 的最后一个字符开始向前遍历。
if (s[n] <= '9')：判断当前字符是否为数字字符（即 0 - 9）。
- 如果是数字字符，s[n] - '0' 可以将字符转换为对应的整数值，例如字符 '5' 减去字符 '0' 得到整数 5。然后乘以 pow(x, i)，pow(x, i) 是 x 的 i 次幂，表示该位对应的权重，最后将结果累加到 ret 中。
else：如果当前字符不是数字字符，说明是字母字符（如 A - Z），代表大于 9 的数字。s[n] + 10 - 'A' 可以将字母字符转换为对应的整数值，例如字符 'A' 转换为 10，'B' 转换为 11 等。同样乘以 pow(x, i) 并累加到 ret 中。
i++;：每处理完一位，幂次 i 加 1，用于处理下一位的权重。

代码2：（使用库函数）

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
 int x = 0;
 string s;
 cin >> x;
 cin >> s;
 int ret = 0;
 ret = stoi(s, NULL, x);
 cout << ret << endl;
 return 0;
}

关于stoi的讲解，请看博客C++ string超详解！！（小白也能看懂）-CSDN博客

（三）

把数x转化成m进制。

思路：不难发现，其实就是上面两个题的结合体。

代码如下：

#include <iostream>
using namespace std;
string str = "0123456789ABCDEF";
void print(int num, int m)
{
 if (num >= m)
 print(num / m, m);
 cout << str[num % m];
}
int main()
{
 int n = 0;
 string s;
 int m = 0;
 cin >> n;
 cin >> s;
 cin >> m;
 int num = stoi(s, NULL, n);
 print(num, m);
 return 0;
}

变量声明与输入获取：
- int n = 0;：用于存储输入的源进制，初始化为 0。
- string s;：用于存储 n 进制的字符串。
- int m = 0;：用于存储目标进制，初始化为 0。
- cin >> n;、cin >> s;、cin >> m;：依次从标准输入读取源进制 n、n 进制的字符串 s 和目标进制 m。
进制转换：
- int num = stoi(s, NULL, n);：使用 stoi 函数将字符串 s 从 n 进制转换为十进制数，结果存储在 num 中。stoi 函数的第一个参数是要转换的字符串，第二个参数 NULL 表示不使用字符串结束位置的指针，第三个参数 n 表示源进制。
输出结果：
- print(num, m);：调用 print 函数，将十进制数 num 转换为 m 进制数并输出。
返回值：
- return 0;：程序正常结束，返回 0 表示程序执行成功。

示例

假设输入 n = 16，s = "FF"，m = 10。

stoi(s, NULL, n) 会将十六进制字符串 "FF" 转换为十进制数 255，存储在 num 中。
调用 print(num, m)，即 print(255, 10)。
- 递归调用 print(255 / 10, 10) 即 print(25, 10)，继续递归调用 print(25 / 10, 10) 即 print(2, 10)。
- 因为 2 < 10，输出 str[2 % 10] 即 2。
- 回溯到 print(25, 10)，输出 str[25 % 10] 即 5。
- 回溯到 print(255, 10)，输出 str[255 % 10] 即 5。
- 最终输出结果为 255