技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> m进制转换为n进制-任意进制转换算法

m进制转换为n进制-任意进制转换算法

浏览:2798次  出处信息

    这种题也是一道经典的面试题,主要考察进制转换细想,Coding质量等。

    当我们把十进制转成二进制的时候,我们通过辗转相除,取余,逆置余数序列的过程得到新的进制的数。因此我们可以借助这种思想把M进制转成N进制的数。

    如下是C的详细的实现方法

void m2n(int m, char* mNum, int n, char* nNum) 
{
	int i = 0;
	char c, *p = nNum;

	//这是一个考察地方,是否能用最少乘法次数。
	while (*mNum != \'\\0\')
		i = i*m + *mNum++ - \'0\';
	
	//辗转取余
	while (i) {
		*p++ = i % n + \'0\';
		i /= n;
	}
	*p-- = \'\\0\';

	//逆置余数序列
	while (p > nNum) {
		c = *p;
		*p-- = *nNum;
		*nNum++ = c;
	}
}

     

    观察上面的代码,存在着众多的不足。例如,要对输入参数做检查,数值的大小收到int值最大值的限制等。不过好在一点,该算法的时间复杂度是O(n)的。

    但是我们霹雳无敌的赵大叔又提供了一种用Java实现的通用的进制转换方法,即使Windows的计算器也转不了的大数,这个算法也可以转。算和上面的算法相比,他的基本思想不变,还是辗转除,但是用了字符串做大数相除,很不错的创新点,赞一个。代码如下:

package test;

/**
 * 功能:将一个数从M进制转换成N进制
 * MValue:M进制数的字符串表示方法
 * Shang:保存中间运算结果
 * M:M进制
 * N:N进制
 */
public class M2N {
	// 在这里对输入赋值
	public static String MValue = "1231412423534674574757";
	public static String Shang = null;
	public static int M = 10;
	public static int N = 8;

	public static void main(String[] args) {
		String nValue = "";
		Shang = MValue;
		while(Shang.length() > 0) {
			nValue = qiuyu(Shang) + nValue;
		}
		System.out.println(nValue);
	}

	/**
	 * 功能:对给定的M进制字符串对n求余。
	 * 
	 * @param MTempValue
	 * @param m
	 * @param n
	 * @return
	 */
	public static String qiuyu(String MTempValue) {
		Shang = "";
		int temp = 0;
		while (MTempValue.length() > 0) {
			int t = getIntFromStr(MTempValue.substring(0, 1));
			MTempValue = MTempValue.substring(1);
			temp = temp * M + t;
			Shang += getStrFromInt(temp / N);
			temp = temp % N;
		}
		while(Shang.length() > 0 && Shang.charAt(0) == \'0\'){
			Shang = Shang.substring(1);
		}
		return getStrFromInt(temp);
	}

	public static int getIntFromStr(String str){
		return str.charAt(0) <= \'9\' && str.charAt(0) >= \'0\'? 
			str.charAt(0) - \'0\' : str.charAt(0) - \'a\' + 10;
	}

	public static String getStrFromInt(int value){
		String result = null;
		if (value >= 0 && value <= 9)
			result = String.valueOf((char)(\'0\' + value));
		else if (value > 9 && value < 36)
		{
			result = String.valueOf((char)(\'a\' + value - 10));
 		}
		else
		{
			result = "-1";// 出错误了
		}
		return result;
	}
}

    赵大叔的算法好了不少,除了参数检查,大小写之外都很好。值得我们借鉴。

    下载源码:

    M2N.Java (2.90 kb)

QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1