算法笔记之旅 | 进制转换

正版图书 Head First 设计模式(中文版) headfirst设计模式深入浅出讲清 java设计模式计算机编程零基础入门教程 【在售价】41.90 元 ----------------- 【立即下单】复制$eaaXcbZbXdA$打开手机淘宝立即下单

进制转换

进制转换是一个很常用的技巧,平时在刷题中一般是一个小模块,在一个大题里面作为数据处理的步骤。

数据定义:待转换数Q为W进制,需要转换为P进制。

下面是进制转换的一般流程:
(1)将Q先转换为10进制数temp
(2)将temp再转换为P进制

以下为算法的详细步骤:

(1)

首先要先明确一个定义,即十进制的数y=d1d2d2d3...dny=d_{1}d_{2}d_{2}d_{3}...d_{n}y=d1​d2​d2​d3​...dn​,如53245,5万2千3百4十5。令其为yyy,那么其中d1=5d_{1}=5d1​=5,d2=3...d3=2d_{2}=3...d_{3}=2d2​=3...d3​=2等等,它可以写成以下形式:

y=d110n1+d210n2+d310n3...+dny=d_{1}*10^{n-1}+d_{2}*10^{n-2}+d_{3}*10^{n-3}...+d_{n}y=d1​∗10n−1+d2​∗10n−2+d3​∗10n−3...+dn​

由此,一个WWW进制数Q=a1a2a2a3...anQ=a_{1}a_{2}a_{2}a_{3}...a_{n}Q=a1​a2​a2​a3​...an​也可以写成:

Q=a1Wn1+a2Wn2+a3Wn3...+anQ=a_{1}*W^{n-1}+a_{2}*W^{n-2}+a_{3}*W^{n-3}...+a_{n}Q=a1​∗Wn−1+a2​∗Wn−2+a3​∗Wn−3...+an​

而这个公式实际上就直接计算出了其10进制的值,对公式从右往左累加其值即可。由以上,将QQQ转换为10进制可以由如下循环得到:

	int x=1101;             //设定上为2进制,值应该为13,将其转换为10进制的y 
	int y=0,pro=1;          //pro为辅助值,用来计算2的阶乘如2^0=1,2^1=2,2^2=4,其值将分别为1,2,4
	while(x!=0)
	{
		y=y+(x%10)*pro;     //只要不断累加y,就可以计算出x的10进制值,原理就是借助上面的公式 
		x=x/10;
		pro=pro*2; 
	} 

(2)

将10进制数temp转化为P进制,可以用除基取余法。比如将15转化为2进制:

15除2,等于7,余1;
7出2,等于3,余1;
3除2,等于1,余1;
1除2,等于0,余1;算法终止。
这样将位数从后往前拼凑,答案即为1111。

实现如下:

	int x=11,num=0;        //x为10进制数,将要转化的2进制数的每一位放在ans里,num记录2进制数的位数 
	int ans[1024]={0};
	do
	{
		ans[num++]=x%2;
		x/=2;		
	}while(x!=0)

总结:进制转换作为一个小技巧,经常出现在大题的数据处理部分,其算法简单有效。本文介绍的两步,都是O(n)O(n)O(n)级的算法。其中初学者对(1)部分的算法容易忘记,可以尝试多编写,记忆。

栏目
榴芒一刻榴莲泡泡网红大福零食雪媚娘日本糯米糍榴莲麻薯甜品糕点 【在售价】138.00 元 【券后价】88.00元 ----------------- 【立即领券】复制$MYw6cZGNPHS$打开手机淘宝领券并下单