题目描述:
将M进制的数X转换为N进制的数输出。
输入:
输入的第一行包括两个整数:M和N(2<=M,N<=36)。
下面的一行输入一个数X,X是M进制的数,现在要求你将M进制的数X转换成N进制的数输出。
输出:
输出X的N进制表示的数。
样例输入:
16 10
F
样例输出:
15
提示:
输入时字母部分为大写,输出时为小写,并且有大数据。
代码:
#include <iostream>
#include <cstring>
#include <ctype.h>
using namespace std;
int main(){
int M,N;
string X;
while(cin>>M>>N){
cin>>X;
int data[1010]; //保存M进制下的各个位数
int output[1010]; //保存N进制下的各个位数
memset(output,0,sizeof(output));
for(int i=0;i<X.length();i++){
if(isalpha(X[i]))
data[i] = X[i] - 'A' + 10;
else
data[i] = X[i] - '0';
}
int sum = 1;
int d = 0;
int len = X.length();
int k = 0;
while(sum){
sum = 0;
for(int i=0;i<len;i++){
d = data[i] / N;
sum += d;
if(i == len-1){
output[k++] = data[i] % N;
}
else{
data[i+1] += (data[i] % N) * M;
}
data[i] = d;
}
}
if(k == 0){
output[k] = 0;
k--;
}
if(k == -1){
cout<<0<<endl;
}
else{
for(int i=0;i<k;i++){
if(output[k-i-1] > 9)
cout<<(char)(output[k-i-1]+ 'a' - 10);
else
cout<<output[k-i-1];
}
}
cout<<endl;
}
return 0;
}
作者提醒
输入时字母部分为大写,输出时为小写,并且有大数据。
做完这道题,我已是疲惫不堪。。
首先,这道题属于进制转换题,因为涉及到大整数,所以处理起来和以往有些不同。不同之处在于,
不能将M进制的数转化为十进制,因为long long型无论如何也是存不了的。
至于输入有大写字母,输出有小写字母,倒是很容易处理。只要稍微与'a','A'进行运算即可。
下面主要讲解大整数的运算。
首先来看一个例子。
十进制的123456789 转为 二进制,注意这里要手工算。
让我来解释一下这张图,很重要。data[]数组里面保存的是 待转化的数,因为这里数比较大,
不能直接除以2,求模。要一步一步算。首先是第一位1除以2,余数是0,模是1,
然后考虑第二个数,注意第二个数的值应该是前一个数与2取模之后得到的1再乘以10,再加上2,即12
然后循环下去,当到了最后一个数的时候,将余数1保存到output数组里面去。
这只是第一次相除,因为余数061728394不等于0,所以还要继续循环,模拟除以2的过程,
直到各个位都为0,即sum(保存各个位的和)= 0,最终的结果就是output数组的倒序输出。
这里要注意的是,这个过程不光可以模拟十进制转二进制,而且可以实现任意进制的转换,
(不需要先转化成十进制这个过度)。只要把10改成M,把2改成N即可。
还要注意,当output数组为空时,即数字为0,直接输出即可。