m进制转换为n进制-任意进制转换算法
浏览:2806次 出处信息
这种题也是一道经典的面试题,主要考察进制转换细想,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; } }
赵大叔的算法好了不少,除了参数检查,大小写之外都很好。值得我们借鉴。
下载源码:
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
扫一扫订阅我的微信号:IT技术博客大学习
<< 前一篇:一个Sqrt函数引发的血案
后一篇:人脸识别算法综述-(LPP,PCA,K-L,SVM) >>
文章信息
- 作者:pkuoliver 来源: 码农
- 标签: 进制
- 发布时间:2011-02-20 23:36:24
近3天十大热文
- [55] IOS安全–浅谈关于IOS加固的几种方法
- [54] 图书馆的世界纪录
- [54] 如何拿下简短的域名
- [54] android 开发入门
- [52] Go Reflect 性能
- [52] Oracle MTS模式下 进程地址与会话信
- [49] 【社会化设计】自我(self)部分――欢迎区
- [48] 读书笔记-壹百度:百度十年千倍的29条法则
- [41] 程序员技术练级攻略
- [35] 视觉调整-设计师 vs. 逻辑