m进制转换为n进制-任意进制转换算法（百度面试题）

代码下载：进制转换代码

这里有很多深藏不漏的高手，在这里聊这种基本问题是有点小儿科。不过本人只是想分享下自己的新的，代码，算法有不足之处，还请大家指正，共同进步。

 

这种题也是一道经典的面试题，主要考察进制转换细想，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)('0'+ value);
		else if(vlaue > 9 && value <36)
		{
			result = (String)('0'+ value - 10);
		}
		else
		{
			result = “-1”;//出错误了
		}
		return result;
	}
}

 

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

讨论更好的方法。

评论

1 楼 xudanhui 2010-10-27  

M<N的时候，不能算的啊。。
字符串拼接的操作，我对效率很怀疑。