各种进制的相互转换【进制转换器】【进制转换】【算法】

第一种进制转换：

写此篇题解之前，已经发布十进制转换M进制详解，R进制转换成十进制详解。

那第一种进制转换就是将十进制作为跳板，融合以上两种进制转换，到达由M进制转换成R进制的效果。

PS：此处不再讲解M进制转换十进制，以及十进制转换成R进制，需要的可根据上面的链接进行学习。

例：可进行数制转换的计算器

问题描述

某计算器能够在不同数制之间进行转换。该计算器显示屏有7位，除了数字0到9之外，它的按钮还包括大写字母A到F，因此它将支持基数2至16的不同进制。

请为该计算器编写不同进制的数的转换程序。

输入

输入包含多组测试用例。每个测试用例占1行，每行将有三个数字。第一个数字是要转换的数。第二个数字是要转换的数的基数。第三个数字是要转换后的数字的基数。

输出

输出将仅是计算器显示屏上显示的转换后的数字。数字应在7位显示屏中右对齐。如果数字太长而无法显示在显示屏上，则在显示屏上右对齐输出“ERROR”（不带引号）。

输入样例

1111000[bk][bk]2[bk]10

1111000[bk][bk]2[bk]16

2102101[bk][bk]3[bk]10

2102101[bk][bk]3[bk]15

[bk][bk]12312[bk][bk]4[bk][bk]2

[bk][bk][bk][bk][bk]1A[bk]15[bk][bk]2

1234567[bk]10[bk]16

[bk][bk][bk]ABCD[bk]16[bk]15

输出样例

[bk][bk][bk][bk]120

[bk][bk][bk][bk][bk]78

[bk][bk][bk]1765

[bk][bk][bk][bk]7CA

[bk][bk]ERROR

[bk][bk]11001

[bk]12D687

[bk][bk][bk]D071

说明：样例中的一个“[bk]”仅表示一个空格，实际的输入和输出时就是一个空格。

思路：

为完成基数为A的整数X转换为基数为B的整数Y。可以先采用X按权值展开的方式将X转换为十进制整数Z，再将十进制整数Z按“除B取余”的方法转换为B进制的整数Y

AC代码：

#include <iostream>
using namespace std;

//思路：以十进制做为跳板，采用X按权值展开的方式将X转换为十进制整数Z
//      再将十进制整数Z按“除B取余”的方法转换为B进制的整数Y。 
char table[20]="0123456789ABCDEF"; 
int main(int argc, char** argv) {
	char str[10]; //输入要转换的数，以str数组进行存储 
	while(scanf("%s",&str)!=EOF)  //持续输入
	{
		int a,b;//a为输入的进制数，b为要转换的进制数 
		cin>>a>>b;
		long long sum=0;
		int i;
		for(i=0;str[i]!='\0';i++)  //遍历数组str，按权加将其转换成十进制 
		{
			if(str[i]>='0'&&str[i]<='9') //将字符型的0-9转换成int型
			sum=sum*a+str[i]-'0';	
			else
			sum=sum*a+str[i]-'A'+10; //将A-F转换成10-15

		} 
		//将十进制转换成对应的b进制数 
		char num[30]; //存储转换成对应的b进制数 
		int len=0;  //记录num数组的长度 
		while(sum)    //除b取余，将十进制转换成对应的进制数
		{
			num[len++]=table[sum%b];
			sum/=b;
		}
         //输出
		if(len>7)  cout<<"  ERROR"<<endl;
		else
		{
			for (i=0;i<7-len;i++)
                printf(" ");
            for (i=len-1;i>=0;i--)
				cout<<num[i];
				cout<<endl;
		}
	} 
	return 0;
}

由上可知，如果超过7位以上，不进行输出。故，一般不同进制转换是以10进制为中介进行转换，但若转换的数较大的话，int类型只能存储32位（2*32-1），故在转换成十进制时，容易出现溢出。在进行简单的进制转换，此种方式容易书写且效率极高。

如果需要进行大数进制的相互转换，则需采取第二种进制转换方式。

第二种进制转换：

可以采用短除法直接将A进制数x直接转化为B进制数y，其基本原理是将x每次除以B，得到的余数的逆序列是就B进制表示的结果。每次除的时候，从最高位开始除，商作为x当前位的值保存，得到的余数乘以A加到下一位，一直到最低位。最后得到的余数作为B进制数y的某位保存。重复这一过程，直到A进制数x为0。

用一个例子简单说明：将十六进制数6E转换为八进制数。

为方便说明，设用数组x存储十六进制的各位数字，用数组y存储转换后得到的八进制各位数字。

首先将表示十六值数6E的字符串转换为x中存储的各位整数。转换后 x[0]=14，x[1]=6。

从高位开始除，x[1]=6， 6/8商为0，余数为6，将商保存到当前位x[1]中，x[1]=0，将余数 6*16加到下一位x[0]中，x[0]=14+6*16=110。

再接着进行下一位的除法。 X[0]=110，110/8商为13，余数为6，将商保存到当前位x[0]中，x[0]=13，因为这是最低位（个位），一次除法结束，余数6作为转换后八进制数的数字保存到y数组中，y[0]=6。

去掉x数组的高位前导0后，x数组中 x[0]=13，x[1]=0。

注：下面的X！=0的意思是数组x不等于0。

X!=0，继续重复上面的过程。x[0]=13，13/8商为1，余数为5，将商保存到当前位x[0]中，x[0]=1，同样因为这是最低位（个位），一次除法结束，余数作为转换后八进制数的数字保存到y数组中，y[1]=5。

X!=0，继续重复上面的过程。x[0]=1， 1/8商为0，余数为1，将商保存到当前位x[0]中，x[0]=0，同样因为这是最低位（个位），一次除法结束，余数作为转换后八进制数的数字保存到y数组中，y[2]=1。

至此，X等于0(数组x的每一位都为0)，转换结束。再将数组y中保存的数字按逆序的方式转换为字符串 156。也就是说，十六进制数6E转换为八进制数为 156。

例：进制转换器

问题描述

编写一个程序，将一个基数的数字转换为另一个基数。有62个不同的数字：｛0-9，A-Z，a-z｝

输入

第一行输入包含一个正整数N，表示测试用例的组数。之后N行，每一行将有一个十进制整数表示的输入基数，后跟一个十进制整数表示的输出基数，再跟一个以输入基数表示的数字。输入基数和输出基数都将在2到62的范围内。A=10，B=11，…，Z=35，a=36，b=37，…，z=61（0-9有其通常的含义）。

输出

程序的输出应包括每执行一次基本转换的三行输出。第一行应该是十进制的输入基数，后跟空格，然后是输入数字（以输入基数表示）。第二行应该是输出基数，后跟一个空格，然后是输出数字（以输出基数表示）。第三输出行为空。

输入样例

62 2 abcdefghiz

10 16 1234567890123456789012345678901234567890

16 35 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2

35 23 333YMHOUE8JPLT7OX6K9FYCQ8A

23 49 946B9AA02MI37E3D3MMJ4G7BL2F05

49 61 1VbDkSIMJL3JjRgAdlUfcaWj

61 5 dl9MDSWqwHjDnToKcsWE1S

5 10 42104444441001414401221302402201233340311104212022133030

输出样例

62 abcdefghiz

2 11011100000100010111110010010110011111001001100011010010001

10 1234567890123456789012345678901234567890

16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2

35 333YMHOUE8JPLT7OX6K9FYCQ8A

23 946B9AA02MI37E3D3MMJ4G7BL2F05

49 1VbDkSIMJL3JjRgAdlUfcaWj

61 dl9MDSWqwHjDnToKcsWE1S

5 42104444441001414401221302402201233340311104212022133030

10 1234567890123456789012345678901234567890

#include <iostream>
#include <string.h>
using namespace std;
#define maxn 10000  //此处可根据需要进行修改
void Base1toBase2(char a[],char b[],int base1,int base2)
//a为输入的进制数,b为输出的进制数，base1是输入的进制，base2是输出的进制
{
	int  n1[maxn],n2[maxn]; //数组n1存储数组a的int类型 n2逆序存储转换后的数 
	int j=0;	    	//记录数组n1的长度 
	int len1=strlen(a); //记录数组a的长度 
	int i;
	for(i=len1-1;i>=0;i--)  //遍历数组,将字符型转换成数字型（此时数组n1[0]为最高位） 
	{
		if(a[i]>='A'&&a[i]<='Z')   //将字符型A~Z转换成数字10-35 
			n1[j++]=a[i]-'A'+10;
		else if(a[i]>='a'&&a[i]<='z')  //将字符型a~z转换成数字36-61
		 	n1[j++]=a[i]-'a'+36;
		else			//将字符型的0-9转换成数字的0-9 
		n1[j++]=a[i]-'0'; 
	}
	int k=0;  	 //记录数组n2的长度
	while(len1!=0)  //当数组a长度不为0时,进行上述短除法转换 
	{
		for(i=len1-1;i>0;i--)	//短除法(第二次逆序，将n1变成正序,此时的n1[0]为最低位) 
		{
			n1[i-1]+=n1[i]%base2*base1; //得到的余数通过按权加转换成对应进制数 
			n1[i]/=base2; //将商作为本位进行保存 
		}
		n2[k++]=n1[0]%base2; //将数组n1的最低位得到的余数保存到n2中 
		n1[0]/=base2;  //商作为本位进行保存 
		while(len1>0&&n1[len1-1]==0) len1--; 
//短除法后的n1数组的n1[len1-1]都会为0，len1需自减 
	} 
//将结果int型数组n2转换成字符型数组b
	for(j=0,i=k-1;i>=0;i--)  
	{
		if(n2[i]<10) 	
		b[j++]=n2[i]+'0';
		else if(n2[i]<36)
		b[j++]=n2[i]-10+'A';
		else
		b[j++]=n2[i]-36+'a';
 	} 
 	b[j]='\0';
}
int main(int argc, char** argv) {
	int t,base1,base2;     //t为输入的组数,base1为输入的进制，base2为需要输出的进制 
	char a[maxn],b[maxn];  //数组a为输入的进制数,b为输出的进制数 
	cin>>t;
	while(t--)
	{
		cin>>base1>>base2;
		cin>>a;
		Base1toBase2(a,b,base1,base2);
		cout<<base1<<" "<<a<<endl;
		cout<<base2<<" "<<b<<endl<<endl;
	}
	return 0;
}