m进制转换为n进制

admin管理员组

文章数量:1794759

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.valueOf((char)(\\'0\\' + value)); else if (value > 9 && value < 36) { result = String.valueOf((char)(\\'a\\' + value - 10)); } else { result = "-1";// 出错误了 } return result; } }     赵大叔的算法好了不少，除了参数检查，大小写之外都很好。值得我们借鉴。

    以上转自blogread/it/article/3302?f=wb

    本人愚钝，研究了一段时间才完全弄明白里面的原理。第一个算法是转换成十进制，再辗转相除取余，最后逆置余数序列得到结果。第二个算法是直接对原数据，用目标进制n直接进行辗转相除，取商和取余。相对于第一个算法，去掉了前面整个数据转换成十进制的操作（当然计算机默认操作数是十进制，所以每取一位还是先要先转换为十进制）。

    下面是本人用C语言改写的：

#include <stdio.h> #include <stdlib.h> #include <ctype.h> #include <string.h> #define MAX_CONVERT_NUM_LEN 50 char m2n(char m, char n, char *mNum, char *nNum) { char *np=nNum; char JINZHI[37] ="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; unsigned int dec; char shang[MAX_CONVERT_NUM_LEN], tt[MAX_CONVERT_NUM_LEN]; char *sp, *tp; char getm, temp; if(m<2 || m>36 || n<2 || n>36) return -1; strcpy(shang, mNum); sp = shang; while(*sp != '\\0'){ dec = 0; *tt = '\\0'; tp = tt; while(*sp != '\\0'){ getm = *sp > '9' ? (toupper(*sp++)-'A'+10) : ((*sp++)-'0'); if(getm < 0 || getm >= m ) return -1; dec = dec * m + getm; if((temp=dec/n) != 0 || *tp != '\\0') *tp++ = JINZHI[temp]; dec %= n; } *np++ = JINZHI[dec]; *tp = '\\0'; strcpy(shang, tt); sp = shang; } *np-- = '\\0'; while(np>nNum){ temp =*np; *np-- =*nNum; *nNum++ = temp; } return 0; } int main(int argc, char **argv) { char *m="123004560007890000abcdEF"; char n[MAX_CONVERT_NUM_LEN]; if(strlen(m) > 0 && 0 == m2n(16, 10, m, n)) printf("%s \\n",n); else printf("error!!!\\n"); system("pause"); return 0; }

本文标签： 转换为进制