洛谷 B2143 进制转换 /一本通 1161 转进制 题解

信息学奥赛一本通（C++版）在线评测系统T1161
B2143 进制转换 - 洛谷 | 计算机科学教育新生态

本题描述中要求使用递归算法。而事实上，递归算法也是较优解。

例如，当我们将十进制数 2021 2021 2021 转化为十六进制数时，我们首先将它除以底数 16 16 16 ，得到商并记录余数。再将商继续除以 16 16 16，重复刚才步骤直至商为 0 0 0 时，最后将记录到的余数倒序输出。

如果使用数组进行存储数据需要倒序输出余数，但递归使得我们避免了这一点——不断递归使得最后得到的余数最先输出，即既能顺序计算又能倒序输出，而不需要分两部分代码完成。

一个小常识是：在十一进制到十六进制中，对于超过 9 9 9 的数我们依次使用字母A~F代替。因此可以开一个数组，记录下各个数字便于使用。

对十进制正整数 N N N，转换到 M M M 进制时，进行以下步骤：

1. 令 N N N 除以 M M M，记商为 a 1 a1 a1，余数为 a 2 a2 a2；

2. 记录 a 2 a2 a2 ，继续令 a 1 a1 a1 除以 M M M，记商为 b 1 b1 b1，余数为 b 2 b2 b2；

3. 重复 步骤 2 直至商为 0 0 0 时，记录余数，依次倒序输出刚刚记下的余数。

unsigned long long n; int m;//N的范围不确定，开大一点总不会错
char s[17] = "0123456798ABCDEF";//记录数字
void zh(int a, int b)
{
	string s1 = "";//使用字符串进行记录
	s1 += s[a % b];//将本次除法所得余数添加在答案字符串最后处
	if (a/b)//若商不为0
	{
	zh(a / b, b);//让商继续递推
	}
	cout << s1;
}

事实上就是多了头文件和主函数

#include
#include
using namespace std;
unsigned long long n; int m;
char s[17] = "0123456798ABCDEF";
void zh(int a, int b)
{
	string s1 = "";
	s1 += s[a % b];
	if (a/b)
	{
	zh(a / b, b);
	}
	cout << s1;
}
int main()
{
	cin >> n >> m;
	zh(n, m);
	return 0;
}