算法分享———进制转换通用算法

模板一：任意（K）进制转10进制

将k进制的x转化为10进制的x

ll x=0;
for(int i=1;i<=n;++i)
{
x=x*k+a[i];
}
cout<<x<<endl;

模板二：十进制转m进制

ll x;
cin>>x;
while(x)
{
a[++cnt]=x%k;
x/=k;
}
reverse(a+1,a+1+cnt);//翻转一下使得高位到1的位置

上面的模板不好理解，我们用一种更好理解的模板（利用字符串）：

char ch[] = { '0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F' };
string ans;
	while (x)//10进制再转m进制
	{
		ans += ch[x % m];
		x /= m;
	}
	reverse(ans.begin(), ans.end());//反向迭代器逆转输出
	cout << ans << endl;

模板三：任意进制下（base）数的数位求和

int sumposition(int n, int base)
{
	int sum = 0;
	while (n > 0)

	{
		sum += n % base;
		n /=base;
	}
	return sum;
}

题目一：十六进制转二进制

代码示例：

#include<iostream>
using namespace std;
using ll = long long;
const int N = 50;
int a[N];
int main()
{
	string s = "2021ABCD";
	for (int i = 0; i < s.length(); ++i)
	{
		if ('0' <= s[i] && s[i] <= '9')a[i + 1] = s[i] - '0';
		else a[i + 1] = s[i] - 'A' + 10;
	}
	ll x = 0;
	for (int i = 1; i <= s.length(); i++)
	{
		x = x * 16 + a[i];
	}
	cout << x << endl;
	return 0;
}

运行结果：

题目二：九进制转十进制

代码示例：

#include<iostream>
using namespace std;
using ll = long long;
const int N = 10;
int a[N];
int main()
{
	int n = 4;
	string s = "2022";
	for (int i = 1; i <= 4; i++)a[i] = s[i - 1] - '0';
	ll x = 0;
	for (int i = 1; i <= n; i++)x = x * 9 + a[i];
	cout <<x<< endl;
	return 0;
}

运行结果：

题目三：两次进制转换

思路：
先将N进制转10进制，再将10进制转m进制，套用模板1和模板2
代码示例：

#include<iostream>
using namespace std;
using ll = long long;
const int N = 1000;
int a[N];
char ch[] = { '0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F' };
void solve()
{
	int n, m; cin >> n >> m;
	string s; cin >> s;
	int len = s.length();
	s = "#" + s;//方便从第一个位置开始处理
	for (int i = 1; i <= len; ++i)
	{
		if ('0' <= s[i] && s[i] <= '9')a[i] = s[i] - '0';
		else a[i] = s[i] - 'A' + 10;
	}
	ll x = 0;
	for (int i = 1; i <= len; ++i)x = x * n + a[i];//N进制先转10进制
	string ans;
	while (x)//10进制再转m进制
	{
		ans += ch[x % m];
		x /= m;
	}
	reverse(ans.begin(), ans.end());//反向迭代器逆转输出
	cout << ans << endl;
}
int main()
{
	ios::sync_with_stdio, cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while (t--)solve();
	return 0;
}

运行结果：

题目四：时空传送门

思路：
我们采用一个求数位和函数来分别求二进制下和四进制下的数位和，再枚举1到2024中的所有数，如果在二进制和四进制下数位和相等，计数器加1
代码示例：

#include<iostream>
using namespace std;
//函数用于计算任意进制下数值的数位之和
int sumposition(int n, int base)
{
	int sum = 0;
	while (n > 0)

	{
		sum += n % base;
		n /=base;
	}
	return sum;
}
int main()
{
	int count = 0;
	for (int i = 1; i <= 2024; ++i)
	{
		int binarysum = sumposition(i, 2);
		int quatersum = sumposition(i, 4);
		if (binarysum == quatersum){
			++count;
			}
	}
	cout << count << endl;
	return 0;
}

运行结果：