论坛首页 招聘求职论坛

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

浏览 4139 次
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
作者 正文
   发表时间:2010-10-27  

代码下载:进制转换代码

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

 

这种题也是一道经典的面试题,主要考察进制转换细想,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;
	}
}
 

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

讨论更好的方法

   发表时间:2010-10-27  
M<N的时候,不能算的啊。。
字符串拼接的操作,我对效率很怀疑。
0 请登录后投票
论坛首页 招聘求职版

跳转论坛:
Global site tag (gtag.js) - Google Analytics